9,9,9,9,9...

Lottos lille problem med tilfældige tal mindede mig om en af de mest deprimerende episoder som professionel programmør.

Jeg var ansat i et selskab der havde med kreditkort at gøre, både egne kort og nogle af de store kort.

Det kort som blev anset for europas svar på American Express regnede pinkoden ud ved at køre magnetstripens indhold igennem en DES algoritme med en top-hemmelig nøgle.

Men output fra DES er jo binært og de skulle bruge ciffre, så vejledningen beskrev hvordan man tog 16 nærmere angivne bits, og konverterede dem til hexadecimalt.

Og så var det at filmen knækkede: de 6 ikke decimale værdier skulle trunkeres decimalt, dvs A -> 0, B->1 ... F->5.

Resultatet var, at sandsynligheden for at der optrådte ciffre 0-5 i pinkoden var dobbelt så stor som for 6-9.

En telefonisk henvendelse bragte mig, efter en del postyr, i kontakt med en medarbejder der faktisk havde forstand på de dele hos kortudstederen.

Han indrømmede, i bestyrelsesformandens påhør, for den slags tophemmelige detailler kunne man ikke tale om uden overvågning, at den algoritme var de ikke så stolte af, som de havde været.

Men hvad kunne de gøre ? Der var millioner af kort udstedt allerede og tusinder af systemer der kendte algoritmen.

Fejlen lotto begik er ikke den klassiske:


/* we need a random number [0...99] */
r = random() % 100;

... og det bekymrer mig, for det lugter langt væk af klytprogrammering hvis de behandler ciffrene individuelt.

De burde vide bedre.

Vidste i forresten at DASK var den første computer med en hardware generator for tilfældige tal ?

phk

PS: Lad være med at afsløre hvad problemet er med kodestumpen ovenfor, de andre læsere skal også have lov til at tænke sig grundigt om.

PPS: Men fortæl mig gerne om det er noget i har lært noget om under jeres uddannelse

Kommentarer (32)
sortSortér kommentarer
  • Ældste først
  • Nyeste først
  • Bedste først
#3 Deleted User

Der bliver kun rundet til 0 mellem 0 og .5 og 99 mellem 98.5-99, det vil sige at chancen er halvt saa stor for 0 eller 99 i forhold til de andre tal. Kan ikke huske hvor jeg har hoert det kunne godt vaere paa skolen, men umiddelbart virker det ret indlysende.

  • 0
  • 0
#9 Mikkel Meyer Andersen

Lige præcis ved 100, er den vel ikke så gal, da 100 ikke kan skrives på formen 2^k? Så hvis man generelt har en random-funktion givet ved h(x) = x mod m så skal man vel sørge for at m != 2^k? Hvis m er det, så vil h(x) bare give de k lower-order bits.

Fra mit algoritmekursus husker jeg noget a la man kan lave den uniformt således: h(x) = ((a*k + b) mod p) mod m for gcd(a, p) = 1 og b < p.

(Alle tal er naturlige.)

  • 0
  • 0
#18 Dennis Krøger

Torben, din implementering smider vist en del tal væk...

Med 2000000000 iterationer er PHK's en smule langsommere end din, til gengæld er den ene procent hvert tal burde få maksimalt 1.000763%.

Med din implementering er den op til 1.002597%, næsten 3 gange så stor afvigelse (Har du forøvrigt ikke en fejl i din implementering? Jeg skulle gange med 200 for ikke at få 0-49).

Jeg har smækket min lynsammensmækkede, smånaive og sikkert fejlfyldte udgave på hp23c.dk/~d/pseudotest.c

Læg mærke til at jeg tester den useedede udgave (sammme som seeded med 1, vistnok), men der skulle ikke være den store forskel med andre seeds.

Hvis jeg har dummet mig, er en sviner selvfølgelig velkommen.

  • 0
  • 0
#19 Poul-Henning Kamp Blogger

For det første giver din formel kun tal [0..49] retur.

Men for det andet laver du (stadig) præcist den fejl jeg anførte.

Hvis du tester for alle r1 værdier og laver et histogram over de r-værdier der kommer ud, vil du se at ca. hver 3 værdi har 1/328 lavere sandsynlighed end de andre:

328 0 328 1 328 2 327 3 328 4 328 5 327 6 328 7 328 8 327 9 [...]

Hvis du skal gøre det rigtigt, er du nødt til at smide den del af dit indgangsinterval der ikke matcher udgangsintervallet bort.

Du lærte i virkeligheden det her i 1 klasse:

Der er ingen måde at dele 2147483648 æbler imellem 10 børn så de alle får lige mange. Der bliver 8 tilbage uanset hvad du gør.

Poul-Henning

  • 0
  • 0
#20 Deleted User

Hej Dennis og PHK,

ja jeg var lidt for hurtigt med de 0x10000, det skulle kun være halvdelen, derfor fås tallen 0..49 og ikke 0..99 (jeg brugte jo kun 0x7fff og ikke 0xffff i bitmasken).

Og ja, den lineære skalering som jeg derefter laver giver tal i det rigtige interval (næsten :- hvis det ikke lige var for min sjuske-fejl), men den ændrer fordelingen en lille smule (det er jo heltals beregninger vi laver, ikke reele tal). Så problemet er som i den oprindelige modulus metode, nu er det bare nogle andre tal som bliver under-repræsenteret).

For at kunne optræde lige hyppigt skal de "100" stadig gå op i her 2^15.

Grunden til at den beskrevne metode er dårligere end den af PHK oprindeligt nævnte er pga. jeg faktisk nedskalerer til kun 15/16 bit opløsning, hvor PHK's modulus metode bevarer de 31/32-bits opløsning. Men det var jo for at kunne gange med 100 uden at få overflow :-).

/Torben.

  • 0
  • 0
#24 Deleted User

Det er essentielt, både i sikkerhed og lotteri, at sikre sig at udfaldsrummet af pseudotilfældige tal er homogent inden for det øskede interval. Men målet er jo i den sidste ende at angribere ikke skal kunne gætte tallene. I denne henseende er homogenitet utilstrækkeligt og snarere et middel end et mål.

Generatorer of pseudo-tilfældige som C's rand() er - ihvertfald så vidt jeg ved - strengt deterministiske, iterative beregnere af en intern tilstandsvariabel som skal være hemmelig hvis ikke output-sekvensen skal kunne forudsiges udefra.

Og hvis ikke tilstandsvariablen fra start omhyggeligt er sat til noget u-gætteligt vil hele den genererede sekvens kunne genskabes udefra - herunder også de tal som ikke er genereret endnu.

Interesserede kan læse http://www.cs.berkeley.edu/~daw/papers/ddj-netscape.html om hvordan Netscape's første version/implementation af SSL led af denne skavank og blev cracket på grund af den. Og http://www.ietf.org/rfc/rfc1750.txt er en gennemgang af hvordan "ugættelighed" kan tilvejebringes.

Mikael Sylvest.

  • 0
  • 0
#25 Dennis Krøger

Selvfølgelig, men når man tester, er det generelt en god idé at kunne genskabe den samme sekvens, enten ved ikke at seede, eller ved at seede med det samme sæt tal. (Alt efter hvilken test man vil udføre, selvfølgelig)

Et andet element er at blot fordi man har seeded værdien, kan man ikke være sikker på at sekvensen ikke kan gættes. Jeg læste om et tilfælde med en pokersite, der brugte generatoren således at det kunne gættes hvorhenne man var i sekvensen, ved at regne ud fra sine egne kort i et antal hænder i træk. Derefter kunne alles hænder gættes fremover.

  • 0
  • 0
#27 Erik Witthøfft Rasmussen

For det første: PHK's kode korrigerer for en defekt, der udgør en unøjagtighed på 0.0005 % (0.5 ppm). Men leverer random() virkelig en fordeling, der er 100.000000000 % jævn?

For det andet findes der deterministiske løsninger, der udfører den samme kompensation. Følgende vil virke på de fleste pc'ere med mere:

r = floor(100.0 * (double)random() / 2147483648.0);

Kræver at random() leverer en 32 bit int samt at double er mindst 64 bit.

  • 0
  • 0
#28 Henrik Christian Grove

@Peter: Ja, men sådan er verden.

@Erik: Det er korrekt at unøjagtigheden er ganske lille, og i nogle situationer kan det også være ganske rimeligt at se bort fra den (i så fald er gange/dividere-løsning ofte bedre end modulus-løsningen fordi de overrepræsenterede værdier er spredt ud over intervallet, med en bedre approksimation af bl.a. gennemsnittet til følge), men i andre situationer er det uacceptabelt, det handler om at være opmærksom på problemet.

Det er (forhåbenlig) et designkrav til alle pseudo-tilfældigheds-generatorer at deres uddata er ligefordelt. Det har også været let at verificere for alle dem jeg har set.

På systemer hvor random virker ved at systemet opsamler tilfældige bits fra eksterne enheder, er vi bare nødt til at håbe på at de opsamlede bits virkelig er tilfældige, men det tror jeg personligt også på, fordi jeg har set diskussioner mellem folk der så ud til at gå ret meget op i det.

Kort sagt kan du godt antage at random() leverer en fordeling der er 100% jævn.

Og nej, lige meget hvor mange gange du og andre gentager andet, så findes der ikke en løsning der kan løse problemet i garanteret endelig tid.

Din løsning er essentielt den samme som Torbens, du konverterer bare til en større datatype for at undgå overflow når du ganger med 100, hvor han fjernede nogle bits. Og det kan være at det betyder at det er nogle andre værdier der bliver overrepræsenteret med din løsning, men der vil være overrepræsenterede værdier.

Hvis vi nu forsimpler opgaven lidt, kan det være det bliver klart:

Hvis du kun har én mønt du kan slå plat og krone med (det genererer én tilfældig bit), hvordan vil du så afgøre om du skal købe en rød, grøn eller blå bil (hvis sandsynligheden for de tre skal være den samme?)

  • 0
  • 0
#29 Erik Witthøfft Rasmussen

Hernrik, du har selvfølgelig ret i at min kode er ligeså unøjagtig som statpunktet (random()%100). Det er bare nogle andre bins, der har større/mindre sandsynlighed.

Det er derimod ikke rigtigt, at der ikke findes deterministiske løsninger. De er måske alle mindre elegante end PHK's sløjfe, de findes dog.

Den, der ligger lige til højrebenet er denne:

long s = 0; for (i=0; i<N; ++1) s += random();

r = s mod % 100L;

Denne løsning har en nøjagtighed, der kvadratroden af N bedre end den "rå" nøjagtighed.

  • 0
  • 0
#30 Henrik Christian Grove

Er vist nogenlunde den eneste passende reaktion.

Jeg gentager: "lige meget hvor mange gange du og andre gentager andet, så findes der ikke en løsning der kan løse problemet i garanteret endelig tid."

Egentlig indrømmer du selv at din nye "løsning" ikke løser problemet ved at komme med et udsagn om dens nøjagtighed. Egentlig er den vel ikke længere.

Jeg har dog alligevel lyst til pointe at jeg ikke ville turde bruge din nye "løsning" til noget som helst, uden en grundig matematisk redegørelse for at modulus-operation udjævner den ujævne fordeling du får ud at af lægge N ligefordelte tal sammen (summen af to ligefordelte variable er ikke ligefordelt - det simpleste eksempel er at summen af to terninger oftere er 7 end 12).

Hvis vi skal prøve at udpensle hvorfor det ikke kan lade sig gøre: Det eneste computeren kan give dig er tilfældige bits (ét kald til random() giver dig 31, men det er let at smide nogle af dem væk), derfor kan du tal der er ligefordelt blandt 2^M muligheder. Det der er brug for er en afbildning fra en af disse mængder til mængden 0..99 der rammer hvert element lige mange gange. Men eftersom 2^M aldrig er deleligt med 100 findes sådan en ikke! Det bedste vi kan gøre er at vælge enten:

M=2 (mod 20) for så er 2^M=4 (mod 100), eller

M=12 (mod 20) for så er 2^M=96 (mod 100)

Resulterende i at vi kan komme ned på at have 4 tal der er enten over- eller under-repræsenteret, og jo større vi vælger M jo mindre bliver den procentvise fejl, men den er der, og det er et ufravigeligt faktum!

(Omvendt er M=1 (mod 20) (M=1 undtaget) eller M=11 (mod 20) de værst tænkelige valg idet de giver 48 over-/under-repræsenterede værdier.)

Jeg gentager endnu en gang: "lige meget hvor mange gange du og andre gentager andet, så findes der ikke en løsning der kan løse problemet i garanteret endelig tid."

.Henrik

  • 0
  • 0
#31 Erik Witthøfft Rasmussen

Jeg må med skam indrømme at min sum fra d. 12/10 ikke er korrekt. Når man adderer to ligeligt fordelte stokastiske variable bliver summen selvfølgelig ikke ligeligt fordelt. Herved er jeg endnu en gang blevet mindet om at tænke før jeg taler.

Men selvfølgelig kan man gøre det i endelig tid.

r = floor(100.0 * ((double)random() + (double) random()/2147483648.0) / 2147483648.0));

Denne variation kalder random() 2 gange og danner derved et tal med 62 tilfældige bit. Og ja, r vil stadig have en fejl. Men fejlen vil være mindre end 100 * 2^-62 større end den fejl random() selv laver.

  • 0
  • 0
#32 Henrik Christian Grove

for det du skal gøre er at løse det uden fejl!

Hvis der er nogen der ikke har fattet det endnu: Man kan ikke generere simulere en ligefordeling over 0..99 (eller generelt et hvert interval der ikke indeholder 2^N elementer) på andre måder end den Poul-Henning viste for 11 dage siden, som har det kedelige, men dog yderst teoretiske, problem at vi ikke kan garantere at den terminerer.

Med algoritmer vi kan garantere terminerer kan man selvfølgelig gøre fejlen lige så lille det skal være, men i nogen sammenhænge skal man generere så mange tilfældige tal at det bare bliver for dyrt at gøre det godt nok, i forhold til risikoen for at PHK's algoritme ikke virker.

Jeg har for resten også et svar på PHK's PPS (som må jeg bare håbe han ikke har droppet denne debat for længst): Jeg har ikke (direkte) hørt om dette problem som en del af min uddannelse (jeg har læst matematik og datalogi på KU), men som instruktur på KU (i et datalogikursus for matematikere, hvor de skulle lave noget statistisk simulering) talte jeg med de andre instruktorer om det, om vi blev enige om at præsentere problemet for de studerende, men ikke lægge vægt på det i bedømmelsen (det var trods alt ikke et statistik-kursus). Der blev det selvfølgelig også forværret af at den random()-funktion de havde adgang til genererede 16 bit tal (dvs. max 65535) og de skulle bruge ca. 100000 tilfældige tal.

  • 0
  • 0
Log ind eller Opret konto for at kommentere