Arkistojen kätköstä löytyi random-funktio, joka yllättäen läpäisee minun random-testin – ja vielä huomattavasti paremmin, kuin mitä uudemmat rando-funktiot. Tein tämän random_pläjäyksen joskus vuonna 2008. Sen jälkeen ei olisi enää tarvinnut muita rnd-funktioita, vaan lopettaa kehittäminen ajoissa kun ratkaisu on konkreettisena koodina. Voisi kommentoida tuota koodia paljonkin, mutta en viitsi kommentoida muuta kuin…
#pragma hdrstop
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <conio.h>
#include <string.h>
unsigned avain[256]=
{
0x1935f4dfL, 0xcf745790L, 0xc4d3f7bbL, 0x1161a60dL,
0x3a0b8bc8L, 0x883cc23fL, 0x3676535eL, 0x72989197L,
0x80eb8a3aL, 0xd5fd72a7L, 0x74ba2922L, 0x49f377a3L,
0xb592209dL, 0xda157096L, 0xfaa6d72cL, 0xb778f819L,
0x136d885cL, 0x8bcc80aeL, 0x417fe363L, 0x4f80b6eaL,
0x431fb8b4L, 0xfdac2702L, 0xda4ebb69L, 0x3c002a4fL,
0xc3465e5aL, 0xe1aa284bL, 0x5363a7a8L, 0x6bdb68c1L,
0x48fa8cf8L, 0x59818937L, 0x1a71a354L, 0xc7e7df19L,
0x41b41329L, 0x554f5382L, 0x21b65363L, 0xbdd12730L,
0xa0832abfL, 0xd7834127L, 0x4738fb70L, 0x66a35d21L,
0x322c08d2L, 0xdd43f192L, 0xf3f122deL, 0x26922f58L,
0xd725f737L, 0xe5051232L, 0x585fbc77L, 0x06b4c0baL,
0x820b2664L, 0x3ffe79efL, 0xac9d32bfL, 0x52aa79efL,
0x2bc26b95L, 0x24473e3aL, 0xa141804cL, 0xa938a51cL,
0x8adf6074L, 0x4581ea07L, 0xdd948b12L, 0xfa2a52bbL,
0x303d76afL, 0x0cd40812L, 0x7c4a52b7L, 0xdc5b31c2L,
0x50701827L, 0x004f76beL, 0x003025b5L, 0x6f299d1eL,
0x0ce5824aL, 0x8ee3237eL, 0x02aec994L, 0xab100f73L,
0xb2dce46fL, 0x3abb44eaL, 0xefdb4f1dL, 0x7283a859L,
0xe173c7d3L, 0x55452103L, 0x0c40e18eL, 0x1e9d7d29L,
0x43e5b091L, 0xa64d6eabL, 0xca842fecL, 0x0ae63d3bL,
0x9a0d415dL, 0x15f38535L, 0x2c2a1248L, 0xef84fa58L,
0xd6c0750aL, 0x1a4428c6L, 0x2c8f83d1L, 0x849094e3L,
0x6334fb0aL, 0xa2be9201L, 0xfd1d64acL, 0x6b03da05L,
0xdc481a78L, 0x522a62caL, 0x456e5946L, 0x4ba4f949L,
0x72b697c0L, 0xb7b27b6eL, 0x58f7ac60L, 0x79e84c3bL,
0x6ed214dcL, 0xe82b7ce5L, 0x611e5f08L, 0xfdc3d2f7L,
0xe21ed654L, 0x5ce7ce25L, 0x24b31c57L, 0xb13dad7aL,
0xc8dd0927L, 0xbd402010L, 0x398f268eL, 0x398fed7fL,
0x4b375398L, 0xf12078d4L, 0x6a70f5d2L, 0x3f122e47L,
0x6f0957edL, 0xf64ead0dL, 0x5b10b4baL, 0x87ef4f90L,
0x5de4f9d6L, 0x82a7895cL, 0x3339f4c0L, 0x986819e8L,
0x80073544L, 0x21e12fc0L, 0xfaeb0ba6L, 0x7c7eab98L,
0xf272837eL, 0xb9f48b3eL, 0xf707f16dL, 0x1fc64046L,
0x4f1267a9L, 0x9818b69bL, 0x7634a635L, 0x081e6356L,
0xc5bbe582L, 0xa0fd437dL, 0x574fa287L, 0x08156141L,
0x0ec4bd22L, 0x851b0048L, 0x6678d01dL, 0xb5dd6eecL,
0x0b5f0e78L, 0x8080c224L, 0x55477c88L, 0xb5cfc2d9L,
0x32d98e63L, 0x992407cfL, 0xe40c61fbL, 0x382e7ff2L,
0xe186392dL, 0x0b7db079L, 0x5d5a81dbL, 0xa62c171fL,
0x576e8615L, 0x09dfdd06L, 0x8e8bc416L, 0x5dca9fd9L,
0x9e120ec2L, 0x2eaebb32L, 0x6f86b35aL, 0x7b74ecc8L,
0xd2a060b6L, 0x0581b253L, 0xc942bb83L, 0x89bf4aadL,
0x1f6032f7L, 0x44579f5fL, 0x76fe70d2L, 0xc898106fL,
0xd4c67731L, 0x72eda4e1L, 0x725b0b00L, 0x21c338bcL,
0x549f0ce3L, 0x19a1c364L, 0x26ad6920L, 0x47b8d3eeL,
0xcf35607bL, 0xf14d8147L, 0x5c11ed77L, 0xc3178933L,
0x9ca7a659L, 0xc68aa9ccL, 0xd4af92b7L, 0x6c5a1383L,
0x1db9c268L, 0xe24b1ec8L, 0x4e324d06L, 0x8a61debbL,
0x84ac3f42L, 0xc8549801L, 0x84297683L, 0x835df3f7L,
0x5cbf3b64L, 0xc4aae49dL, 0xfed5a37cL, 0xb0a60c6cL,
0x3bc33d32L, 0xb671c94cL, 0x917eee23L, 0xc9b598eaL,
0xc3e6ae7aL, 0xf7492308L, 0xcef97c63L, 0x636f206bL,
0x73b7c5f8L, 0x13687bffL, 0x298f08f8L, 0x65dfe5beL,
0x1f732af2L, 0x243813e7L, 0x2a549259L, 0xb9e3b912L,
0xb5ccad60L, 0x440c89fbL, 0xc5a640a5L, 0x1a241bc4L,
0xfa11743aL, 0x8b769f79L, 0xc6d05338L, 0xe5f9f615L,
0x71c9270eL, 0xafcc9603L, 0xb6c543cdL, 0xd81ff736L,
0xffaf566dL, 0x1707ab2dL, 0x9e43ade5L, 0x2b98a54fL,
0x453cb460L, 0x4d375d6aL, 0xf73afbfcL, 0xb66ffe39L,
0xbfa3940fL, 0x020577fbL, 0xd6d28bfbL, 0x7de8b197L,
0xa1eef1e6L, 0x450d00beL, 0xe306f6c5L, 0x0be4da69L,
0x7618708bL, 0xad3d5ffdL, 0xe510f167L, 0x8a557142L,
0x67139054L, 0x4980fe83L, 0x90bbda1fL, 0x99d088c5L,
};
typedef signed char int8;
typedef unsigned char uint8;
class LifeRnd256
{
public:
~LifeRnd256(void);
LifeRnd256(unsigned*);
unsigned rnd(unsigned max);
private:
uint8 *a, *b, *c, *d;
unsigned life[256];
uint8 abcd[0x04];
void inc4(void);
};
LifeRnd256::~LifeRnd256(void)
{
}
LifeRnd256::LifeRnd256(unsigned *avain)
{
int n=sizeof(unsigned)*256;
memcpy(life, avain, n);
a=abcd+0; *a=(uint8)0;
b=abcd+1; *b=(uint8)1;
c=abcd+2; *c=(uint8)2;
d=abcd+3; *d=(uint8)3;
}
void LifeRnd256::inc4(void)
{
int i=3;
uint8 t=1;
while (i >= 0)
{
if (!(abcd[i]+=t)) --i;
else if ((++i)==4) return;
else abcd[i]=abcd[i-1];
}
for (i=0; i<4; i++)
abcd[i] = (uint8)i;
}
inline unsigned LifeRnd256::rnd(unsigned max)
{
life[*a]+=(life[*a]>>16)^(life[*b]<<16);
life[*b]+=(life[*a]<<16)^(life[*b]>>16);
life[*a]+=life[*c];
life[*b]-=life[*d];
inc4(); /* 174 792 640 */
return (life[*a]^life[*b])%max;
}
/////////////////////////////////////
#define KPL 2 // Tällä parametril- //
// la voi säätää tutkittavan //
// numerosarjan pituutta. main- //
// funktio ottaa sitten selvää //
// sekvenssin jakaumasta. //
/////////////////////////////////////
int main(void)
{
unsigned maxKpl[KPL];
unsigned ketjut[KPL];
LifeRnd256 F(avain);
memset(maxKpl, 0, sizeof(unsigned)*KPL);
memset(ketjut, 0, sizeof(unsigned)*KPL);
for (int n, ede=0, print=0;;)
{
n=F.rnd(KPL);
ketjut[n]+=1;
for (int i=0; i<KPL; i++)
{
if (ketjut[i]!=maxKpl[i])
{
if (ketjut[i]>maxKpl[i])
{
maxKpl[i]=ketjut[i];
print=1;
}
}
}
if (n!=ede && print==0)
{
ede=n;
memset(ketjut, 0, sizeof(unsigned)*KPL);
}
if (print)
{
print=0;
memset(ketjut, 0, sizeof(unsigned)*KPL);
printf("| ");
for (int i=0; i<KPL; i++)
printf("%u | ", maxKpl[i]);
printf("\n");
}
}
}Muutama tekninen asia:
– Voisit poistaa epästandardit ja tarpeettomat rivit:
#pragma hdrstop #include <conio.h>
– Voisit käyttää standardikirjastossa tarjottuja valmiita muuttujatyyppejä, kuten jo edellisessä keskustelussa joku suositteli. Näin koodi toimisi varmemmin eri ympäristöissä.
#include <stdint.h>
uint32_t avain[256] = {0, 1, 2};
uint8_t abcd[4];– Voisit poistaa tarpeettomat muuttujat (oikeasti vakiot) a, b, c, d ja korvata nämä suoraan vastaavilla abcd-taulukon kohdilla.
– Voisit käyttää vakiomittaisten taulukoiden ja osoitinten tilalla luokkaa std::array, jotta ei tarvitsisi sohlata memset- ja memcpy-funktioilla ja osoittimilla (vieläpä ilman ilmoitettua kokoa!).
Muille lukijoille vinkiksi: Koodin mysteerifunktio inc4 tuottaa siis abcd-taulukkoon järjestyksessä kaikki neljän tavun jonot, joissa a<b<c<d. Eli (0,1,2,3), (0,1,2,4), ..., (0,1,2,255), (0,1,3,4), ... (252,253,254,255).
Aiemman rnd32-funktion (sama kuin vuoden 2005 koodivinkissä) tuottama sykli on tässä eliminoitu lisäämällä muistinkäyttöä niin, että kahden luvun sijasta käytetään 256 eri lukua vuorotellen 174792640 eri yhdistelmänä. Mutta onko lopputulos hintansa arvoinen, kun koodi vaatii yli kilotavun muistia ja on selvästi hitaampaa kuin ennen? Algoritmin muita ominaisuuksia voi edelleen lähinnä arvailla, kun algoritmi on taas esitetty vain koodina ilman analyysia tai minkään vertailukelpoisen testipatterin tuloksia (jotka epäilemättä olisivat kuitenkin hyvät, kun algoritmilla on noin iso tila eikä mikään sykli tai muu systemaattinen vika varmaankaan tule helposti esiin mielekkäässä testausajassa).
Metabolix kirjoitti:
Muille lukijoille vinkiksi: Koodin mysteerifunktio inc4 tuottaa siis abcd-taulukkoon järjestyksessä kaikki neljän tavun jonot, joissa a<b<c<d. Eli (0,1,2,3), (0,1,2,4), ..., (0,1,2,255), (0,1,3,4), ... (252,253,254,255).
Tarkoititko {0, 1, 2, 3}, {0, 1, 2, 4},... {0, 1, 2, 255}, {0, 1, 3, 0}, ... ~ 256^4 ~ noin 4294967296 kombinaatiota. Eli sekvenssin pituus on 256^4. Tein tällä randomilla esimerkiksi minimiharavan 4-oikein tulokselle. Jos käyttää Borlandin random(n) tai stdlibin rand()%n funktiota, haravasta tulee huomattavasti huonompi. hmm... tai jotenkin sinne päin.
jone2712 kirjoitti:
Tarkoititko {0, 1, 2, 3}, {0, 1, 2, 4},... {0, 1, 2, 255}, {0, 1, 3, 0}, ...
Tässähän (lainauksen viimeinen joukko) ei toteudu a < b < c < d, eli mikä tässä on pointtina?
jone2712 kirjoitti:
Tarkoititko ~ 256^4 ~ noin 4294967296 kombinaatiota.
En tarkoittanut. Olethan itsekin kirjoittanut koodin kommentiksi 174 792 640, joka on kuvaamallani tavalla muodostuvien jonojen määrä. Tämä on itse asiassa kombinaatioiden määrä eli 256!/252!/4!, koska jokainen kombinaatio esiintyy vain kerran ja järjestettynä ja kombinaatio voi sisältää saman luvun vain kerran.
Jos haluaisi aloittaa uudestaan nollasta, funktion voisi tehdä paljon selkeämmin. Toisaalta tästä voi tulla aika pahoja ongelmia algoritmiin, kun sitten kaavoissa käytetäänkin samaa lukua useaan asiaan samalla kierroksella, pahimmillaan esimerkiksi vähennyslaskun molemmilla puolilla.
Aihe on jo aika vanha, joten et voi enää vastata siihen.