>>>>>

Scheda 8 - Caso, informazione e algoritmi

6. Come e` realizzato un GENERATORE di NUMERI pseudoCASUALI.

    Pur essendo giunti alla conclusione che non è possibile dimostrare la casualità di una successione, nella realtà interessa costruire degli algoritmi per generare delle successioni che, ai fini pratici, si comportino come se fossero "massimamente" casuali, cioè casuali nel senso di Chaitin.

    Dopo vari insuccessi, sono stati messi a punto vari generatori di successioni (pseudo)casuali di numeri. Attualmente i più usati sono basati sullo schema noto come metodo congruenziale lineare:

X_n+1 = (a·X_n + c) mod M   (a, X₀, c, M numeri naturali; a, X₀, c < M)

o su schemi simili, del tipo X_n = (a·X_n-h − b·X_n-k) mod M (dove tutte le costanti sono numeri naturali fissati).

    Si genera in tal modo una sequenza di numeri interi compresi tra 0 e M, da cui si può ottenere una sequenza di numeri in [0,1) dividendo ciascuno di essi per M.

    Scegliendo opportunamente a, X₀, c, M in IN si può verificare, attraverso test statistici, che tale successione si comporta, apparentemente (non realmente: è generata con un algoritmo!), in modo "massimamente" casuale. I test riguardano l'uniformità della distribuzione, l'indipendenza delle uscite (vedi inizio scheda 3) e più in generale il fatto che i numeri siano generati con un flusso stazionario, senza memoria, ordinario (vedi §5 della scheda 6), ma anche altri aspetti che non abbiamo considerato nel corso.

6

  I seguenti programmi simulano alcuni prototipi di generatore di numeri casuali (sono programmi in QBasic; usa essi o costruisci ed usa degli analoghi script [per es. ecco quello che corrisponde al primo dei seguenti programmi: lungrnd0.htm] o limitati ad osservare ed interpretare le uscite riportate sotto). Utilizzando le uscite numeriche o grafiche (riportate più avanti) cerca di individuarne i limiti (alcuni di questi prototipi sono stati effettivamente utilizzati o proposti, come è osservato nei commenti)

LUNGRND0.BAS:

DEFLNG a,c,m,x,n 'o: DEFDBL a,c,M,x,n a=7 : M=100 : c=70 : x0=60 n=0 : x=x0 10 n=n+1 GOSUB Rand PRINT x IF x<>x0 THEN GOTO 10 PRINT "N ="; n END RAND: x = (a*x+c) MOD M RETURN

uscite: 90 0 70 60 N = 4

LUNGRND1.BAS:

DEFLNG a,m,x,n 'o: DEFDBL a,M,x,n a=259 : M=65536 : x0=725 n=0 : x=x0 10 n=n+1 GOSUB Rand IF x<>x0 THEN GOTO 10 PRINT "N ="; n END RAND: x = a*x MOD M RETURN

uscita: 16384 Proposto in: "Le scienze con il calcolatore tascabile" (R.Green, J.Lewis - Muzzio Editore)

LUNGRND2.BAS:

p=ATN(1)*4 : R0=1/2 n=0 : R=R0 10 n=n+1 GOSUB Rand IF n\1000=n/1000 THEN PRINT n;: INPUT "premi ACapo", xx  IF R <> R0 THEN GOTO 10 PRINT "N ="; n END RAND: R=(R+p)^5 : R=R-INT(R) RETURN

Uscite: 10000 20000 ... Sembra che non termini; premi Ctrl+C per arrestarlo. Proposto nel manuale del pocket computer HP-25

    Esaminiamo i comportamenti del secondo e del terzo anche mediante uscite grafiche. Vediamo prima il comportamento del generatore di un attuale linguaggio di programmazione. Per esaminare quello del QBasic o del JavaScript incorporato nel navigatore potremmo generare un file di punti aventi coordinate casuali e visualizzarlo con Poligon. Esaminiamo direttamente quello di Poligon, con:
FOR #i=1 to 500: SHOW(rnd,rnd)

eseguendo due volte il comando (ossia generando 1000 punti) otteniamo:

Per il generatore descritto in LungRnd1.bas azioniamo in Poligon:
#a=259; #m=65536; #x=725
e poi:
for #i=1 to 500: #x=val((#a*#x)MOD#m);#u=val(#x);#x=val((#a*#x)MOD#m); show(#u/#m,#x/#m)
Se riazioniamo l'ultimo comando otteniamo i 1000 punti sotto a sinistra e poi, con altri due azionamenti, i 2000 punti raffigurati dopo:

Ha un comportamento simile l'RND dei PC Ibm prima metà anni 80

Per il generatore descritto in LungRnd2.bas azioniamo in Poligon:
#r=1/2
e poi:
for #i=1 to 500: #r=val((#r+pi)^5);#r=val(#r-int(#r));#u=val(#r);#r=val((#r+pi)^5);#r=val(#r-int(#r));show(#u,#r)
Se riazioniamo l'ultimo comando otteniamo i 1000 punti raffigurati sotto:

Sembrerebbe, da come si distribuiscono i punti, che l'ultimo sia un buon generatore. proviamo a verificare l'indipendenza delle uscite, come abbiamo fatto in scheda 3,§1 per il genratore del QBasic:

p = ATN(1) * 4: R = 1 / 2
VIA:
PRINT
INPUT "a, b (compresi tra 0 e 1) "; a, b
NX = 0: NY = 0: NXY = 0
FOR i = 1 TO 1000
GOSUB Rand: x = R: GOSUB rand: y = R
IF x < a THEN NX = NX + 1
IF y < b THEN NY = NY + 1
IF x < a AND Y < b THEN NXY = NXY + 1
NEXT
PRINT "FrRel(X<a)*FrRel(Y<b)="; TAB(30); NX / 1000 * NY / 10; "%"
PRINT "FrRel(X<a and Y<b)="; TAB(30); NXY / 10; "%"
GOTO VIA 
RAND: 
R = (R + p) ^ 5: R = R - INT(R)
RETURN

Si ottiene:

a, b (compresi tra 0 e 1) ? 0.5,0.5
FrRel(X<a)*FrRel(Y<b)=        24.3536 %
FrRel(X<a and Y<b)=           28.7 %

a, b (compresi tra 0 e 1) ? 0.2,0.6
FrRel(X<a)*FrRel(Y<b)=        13.3536 %
FrRel(X<a and Y<b)=           9.5 %

Non abbiamo lo stesso livello di indipendenza del generatore del QBasic.