Satunnaislukugeneraattorin uusi käsittely (jatkuu)

Olen jonkin aikaa tutkinut tätä satunnaislukugeneraattoria: ja olen laatinut pari uutta ohjelmaa lähinnä kellosarjan jaksojen tutkimiseksi ja tuon b:n arvon määrittämiseksi. Tertun tekemisessä on ollut pieni luova tauko, mutta palaan siihen kyllä.. Kannattaa ehkä lukaista edellinen posti: http://moijari.com/?p=327

/*
 * (c)2013-2016 Jari Kuivaniemi, All rights reserved!
 */
unsigned char clockbyte()
{
 unsigned char byte;
 unsigned long usec,sec;

 struct timeval tv;

 gettimeofday(&tv,NULL);

 usec=tv.tv_usec;
 sec=tv.tv_sec;

 byte=(usec&0xff);

 return(byte);
}

genbytes(int size, unsigned char *buffer, int b) /* JariK ~2013*/
{
  int c,d,e,f;
  char byte;

  f=0;
  for(c=0;c<8*b;c++) {
    for(d=0;d<size;d++) {
      byte=clockbyte();
      e=buffer[d];
      e=((e&0x80)>>7) | ((e&0x7f)<<1);
      e=e^byte;
      buffer[d]=e;
    }
    for(d=0;d<size;d++) {
      f=(f+buffer[d])%size;
      e=buffer[d];
      buffer[d]=buffer[f];
      buffer[f]=e;
    }
  }
}

Tällä ensimmäisellä ohjelmalla voidaan katsella kello sarjan jonojen pituuksia: (Kellon sarjathan tai variaatiot niissä antavat edelliselle generaattorille satunnaisuutta)

main()
{
  int c,d,oldc,nextc,count,counts[1024];
  unsigned char buffer[BUFSIZE];

  for(c=0;c<1024;c++)
    counts[c]=0;

  for(d=0;d<BUFSIZE;d++)
    buffer[d]=clockbyte();

  oldc=-1;

  for(d=0;d<BUFSIZE;d++) {
    if(oldc==-1) {
      oldc=buffer[d];
      count=1;
    } else if(buffer[d]!=oldc) {
      counts[count]++;
      oldc=buffer[d];
      count=1;
    } else if(buffer[d]==oldc) {
      count++;
    }
  }

  for(c=0;c<1024;c++) {
    if(counts[c]!=0)
      fprintf(stdout," %d(%d)",counts[c],c);
  }
  fprintf(stdout,"\n");
  fflush(stdout);
}

Se tulostaa hitaalla koneella(raspberrypi) tälläisen rivin:

 431521(1) 308527(2)

Hiukan nopeammalla probookilla tälläisen:

 107(1) 101(2) 262(3) 2185(4) 9148(5) 23006(6) 122137(7)

Vielä hiukan nopeammalla inuc:lla tälläisen:

 12(1) 24(2) 22(3) 24(4) 23(5) 27(6) 13(7) 31(8) 22(9) 12(10) 21(11)
 25(12) 23(13) 27(14) 28(15) 26(16) 21(17) 26(18) 24(19) 29(20)
 26(21) 24(22) 22(23) 22(24) 22(25) 24(26) 25(27) 24(28) 12(29)
 21(30) 18(31) 28(32) 29(33) 21(34) 33(35) 38(36) 38(37) 72(38)
 118(39) 184(40) 495(41) 519(42) 1840(43) 736(44) 6856(45) 649(46)
 29676(47) 3708(48)

Ensimmäinen luku on jonojen lukumäärä ja sulkeissa on jonon pituus, Eli Raspberry pi:ssä jonot ovat 1 ja 2 pituisia, ja että reilusti enemmän jonoissa on kahden pituisia. Yleisin jono on siis 2 merkkiä pitkä.

Probookin jonojen pituudet taas vaihtelevat yhden ja seitsemän välillä, ja tässäkin pisintä jonoa on eniten.

Intel Nuc(3.10Ghz):ssa edelleen jonojen pituudet vaihtelevat 1 ja 48 välillä.

Edelliset rivit olivat lähinnä yhteenvetoja kellon sarjoista, seuraavalla ohjelmalla on yritetty päätellä pisimpien sarjojen pituuksia. (jos kello antaa pitkiä samoja merkkejä sisälltäviä sarjoja, se helpottaa huomattavasti kellon arvaamista)

main()
{
  int c,first,lastbits,lastcount,countbits;

  for(c=0;c<SIZE;c++) {
    buffer[c]=clockbyte();
  }

  lastbits=-1;
  lastcount=0;
  first=1;

  for(c=0;c<SIZE;c++) {
    if(lastbits==-1) {
      lastbits=buffer[c];
      countbits=1;
    } else if(lastbits!=buffer[c]) {
      if(!first) {
        fprintf(stdout," ");
      }
      if(countbits<lastcount) {
        fprintf(stdout,"\n");
        first=1;
      }
      fprintf(stdout,"%d",countbits);
      first=0;
      lastbits=buffer[c];
      lastcount=countbits;
      countbits=1;
    } else if(lastbits==buffer[c]) {
      countbits++;
    }
  }
  fprintf(stdout,"\n");
  fflush(stdout);
}

Molemmissa testiin päässeissä laitteissa on yleisin sarja melko pitkä. Tässä listassa tosin ainoastaan jonojen pituudet vaikuttavat mihin summaan jono tulee, eli noissa yleisimmissä sarjoissa merkkien arvot voivat olla erilaisia. Ohjelmaa on ajettu komennolla:

$ ./rn9 | sort | uniq -cd | sort -gr | more
Intel Nuc:

1868891 47 47 47 47 47 47 47 47 48 
 375860 47 47 47 47 47 47 47 48 
 27043 39 
 26097 38 
 20677 47 47 47 47 47 47 47 47 47 48 
 17652 40 
 17511 37 
 15733 47 
 14121 41 42 42 
 13790 47 47 
 12311 41 42 
 12194 47 47 47 
 11962 41 
 11570 47 47 47 47 
 11155 47 47 47 47 47 
 11071 38 40 
 10748 47 47 47 47 47 47 
 10465 38 39 
 10386 39 40 
 10350 42 
 10301 36 
 10081 47 47 47 47 47 47 47 
 9613 45 
 9462 37 39 
 9148 43 
 8713 45 46 46 46 46 46 
 8583 45 47 
 8056 47 47 47 47 47 47 47 47 
 7304 37 40 
 7147 37 38 
 6830 45 46 46 46 46 46 46 
 6437 39 39 
 6229 45 48 
 6002 38 41 

HP Probook:

16694408 7 7 7 7 7 7 8 
4681171 7 7 7 7 7 8 
 356835 5 6 
 200135 7 7 7 7 7 7 7 7 7 8 
 144738 7 7 7 7 7 7 7 8 
  83786 5 5 6 
  25575 7 7 7 7 7 7 7 7 7 7 8 
  20908 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 8 
  16492 7 
  16318 6 7 8 
  14668 6 8 
  13082 3 
   9285 6 7 7 8 
   7329 7 7 
   7052 7 7 7 
   6833 7 7 7 7 
   6666 7 7 7 7 7 
   6336 4 
   5163 7 7 7 7 7 7 

Tämänhetkinen päätelmäni on että jos b:n arvo on niin korkea, että genbytes() palauttaa aina uniikkeja arvoja(parhaimmillaan 2^(bits-1) uniikkia arvoa, kellosta saadaan riittävän paljon satunnaisuutta. Tässä ohjelma, joka palauttaa listan ensimmäisistä b:n arvoista jotka palauttavat uniikkeja arvoja. Niille voidaan tehdä sitten pidempi jatkotarkastelu edellisen postin viimeisellä ohjelmalla. (tarkoituksena olisi tietysti löytää kaava tälle riittävän suurelle b:n arvolle, nimä ohjelmat ovat suhteellisen hitaita (kaavassa esimerkiksi b=?puskurin pituus, kellon jonojen pituus?).

struct list {
  struct list *next;
  char *string;
};

struct list *first;

char *filename="test23.txt";
char *procname=NULL;
FILE *fpd;

clearlist(struct list **l)
{
  struct list *l1,*l2;

  l1=*l;

  while(l1!=NULL) {
    free(l1->string);
    l2=l1->next;
    free(l1);
    l1=l2;
  }
  *l=NULL;
}

int addstring(struct list **l, char *string)
{
  struct list *l1,*ln,*llast;

  ln=malloc(sizeof(struct list));
  ln->next=NULL;
  ln->string=malloc(strlen(string)+1);
  strcpy(ln->string,string);

  l1=*l;
  if(l1==NULL) {
    *l=ln;
  } else {
    llast=NULL;
    while(l1!=NULL) {
      llast=l1;
      l1=l1->next;
    }
    if(llast!=NULL)
      llast->next=ln;
    else
      (*l)->next=ln;
  }
}

int findstring(struct list *l,char *string)
{
  int ok;

  ok=1;
  while(l!=NULL) {
    if(!strcmp(l->string,string)) {
      ok=0;
      break;
    }
    l=l->next;
  }
  return(ok);
}

dumpstrings(struct list *l)
{
  while(l!=NULL) {
    fprintf(stdout,"\ndump: %s",l->string);
    l=l->next;
  }
}

int dotest(int testsize, int b,int dumpsize,int testcount)
{
  int c,e,alku,loppu,dup;
  char filename[128];
  unsigned char buffer[32768];
  unsigned char string[32768],cdigit[3];
  FILE *fp1;
  struct list *l;

  l=NULL;

  dup=0;

  alku=(int)time(NULL);
  for(c=0;c<testcountmax*2;c++) { /* tuo kakkonen kaipaa säätämistä.. */
    memset(buffer,0,testsize);
    genbytes(testsize,buffer,b);
    string[0]='\0';
    if(dumpsize>testsize) {
      for(e=0;e<testsize;e++) {
        sprintf(cdigit,"%02x",buffer[e]);
        strcat(string,cdigit);
      }
    } else {
      for(e=0;e<dumpsize;e++) {
        sprintf(cdigit,"%02x",buffer[e]);
        strcat(string,cdigit);
      }
    }
    if(!findstring(l,string)) {
      dup=1;
      fprintf(stdout,", Duplicate");
      fflush(stdout);
      break;
    } else {
      addstring(&l,string);
    }
  }
  }
  loppu=(int)time(NULL);
  fprintf(fpd,"%d testsize, %d bytes per bit, %d total tries, %d testcountmax, %d total seconds, %f seconds per crypt, %d duplicate",
          testsize,b,c,testcountmax,loppu-alku,((double)((double)loppu-alku)/testcount),dup);
  if(dup==0) {
  } else {
    if(testcountmax<c)
      testcountmax=c;
  }
  fprintf(fpd,"\n");
  fflush(fpd);

  clearlist(&l);
  return(dup);
}

#define USE100 2
#define USE50 2
#define USE10 2
main(int argc,char *argv[])
{
  int c,b,last;

  procname=argv[0];

  testcountmax=1024*64;

  if((fpd=fopen(filename,"a"))==NULL) {
    fprintf(stdout,"%s: cannot open file %s\n",procname,filename);
  }

  for(c=16;c<=4096;c+=c) {
    testcountmax=1024*32;
    last=0;
#ifdef USE100
    for(b=last+1;b<1024;b+=100) {
      if(dotest(c,b,23,1048576*8)==0)
        break;
      last=b;
    }
#endif
#ifdef USE50
    for(b=last+1;b<1024;b+=50) {
      if(dotest(c,b,23,1048576*8)==0)
        break;
      last=b;
    }
#endif
#ifdef USE10
    for(b=last+1;b<1024;b+=10) {
      if(dotest(c,b,23,1048576*8)==0)
        break;
      last=b;
    }
#endif
    for(b=last+1;b<1024;b++) {
      if(dotest(c,b,23,1048576*8)==0)
        break;
      last=b;
    }
    fprintf(stdout,"%d testsize, %d bytes per bit\n",c,last);
  }
}

Tässä tuloste Probook laitteella:

16 testsize, 1 bytes per bit, 389 total tries, 32768 testcountmax, 0 total seconds, 0.000000 seconds per crypt, 1 duplicate
16 testsize, 101 bytes per bit, 36442 total tries, 32768 testcountmax, 91 total seconds, 0.000011 seconds per crypt, 1 duplicate
16 testsize, 201 bytes per bit, 72884 total tries, 36442 testcountmax, 370 total seconds, 0.000044 seconds per crypt, 0 duplicate
16 testsize, 102 bytes per bit, 19587 total tries, 36442 testcountmax, 46 total seconds, 0.000005 seconds per crypt, 1 duplicate
16 testsize, 152 bytes per bit, 72884 total tries, 36442 testcountmax, 295 total seconds, 0.000035 seconds per crypt, 0 duplicate
16 testsize, 103 bytes per bit, 72811 total tries, 36442 testcountmax, 219 total seconds, 0.000026 seconds per crypt, 1 duplicate
16 testsize, 113 bytes per bit, 28246 total tries, 72811 testcountmax, 75 total seconds, 0.000009 seconds per crypt, 1 duplicate
16 testsize, 123 bytes per bit, 145622 total tries, 72811 testcountmax, 649 total seconds, 0.000077 seconds per crypt, 0 duplicate
16 testsize, 114 bytes per bit, 145622 total tries, 72811 testcountmax, 630 total seconds, 0.000075 seconds per crypt, 0 duplicate

Ensimmäiset kierrokset kasvatetaan b:tä sadalla. Kun ensimmäinen vain uniikkipuskureita sisältävä rivi tulee vastaan (b=201), peruutetaan viimeiseen duplikaatteja palauttaneeseen riviin(b=101), ja jatketaan 50 välein seuraavasta b:n arvosta. Samoin käydään lääpi sekä kkymmenet ja ykköset. Tässä ensimmäinen potentiaalinen uniikkeja puskureita palauttava rivi on b:n arvolla 114.