Casuale come un numero

Questo articolo, pubblicato su Personal computer Club dell’ottobre 1991, descrive l’algoritmo della congruenza lineare per la generazione di numeri pseudocasuali e ne propone una implementazione in linguaggio Basic.

Spesso, nella realizzazione di videogame o di programmi di simulazione, vi è la necessità di generare valori casuali, per simulare, appunto, situazioni imprevedibili. I linguaggi di programmazione implementano una funzione utile allo scopo, ma non tutti sanno come vengono determinati i valori random. Scopo di questo articolo è di spiegare come sia possibile generare sequenze di valori distribuiti casualmente in un certo intervallo (tipicamente tra 0 e 1).

Si noti che il problema è formalmente irresolubile perché un calcolatore è un sistema deterministico; è cioé sempre possibile stabilire a priori i risultati delle sue operazioni (per nostra fortuna…). È per questo che, in realtà, non viene generata una sequenza casuale di valori ma, tramite particolari algoritmi, una sequenza le cui caratteristiche siano il più possibile vicine a quelle di una sequenza casuale.

Sono stati studiati molti algoritmi per risolvere il problema, alcuni validi ed altri un po’ meno. Il metodo più usato è quello della Congruenza Lineare che, a partire da un valore iniziale detto Seme, genera una sequenza pseudocasuale di numeri, definita dalla formula n(i+1) = (a * n(i) + c) mod m dove n(i) è il generico valore; n (i +1) è il valore successivo; a è detto moltiplicatore; c è detto incremento; m è detto modulo; mod rappresenta l’operatore Modulo (cioè il resto della divisione). I coefficienti a, m, c devono essere maggiori o uguali a zero.

Il listato pubblicato, sviluppato con sintassi Basic universale, genera sequenze pseudocasuali usando tre terne di valori (a, m, c) predefinite con la possibilità, da parte dell’utente, di inserirne una a scelta per eseguire esperimenti.

Vediamo ora qualche esempio per chiarire le idee e per scoprire le caratteristiche delle sequenze generate. Innanzitutto scopriamo che, per la
presenza dell’operatore mod, i numeri generati saranno sempre compresi tra 0 ed m-1. Per seguire gli esempi proposti, digitate il programma, lanciatelo e scegliete l’opzione 4 dal menu principale. Verranno chiesti i valori dei coefficienti, del seme iniziale, se volete valori compresi tra 0 e 1 (per ora rispondete N), ed il numero di valori random da generare (inserite qualunque valore maggiore di m, vedremo in seguito perché).
Inserendo, per prova, i seguenti valori:

m = 7, a = 3, c = 5, seme = 2 otterrete la sequenza: 2 – 4 – 3 – 0 – 5 – 6 – 2 – 4 – 3 (eccetera) Si nota subito che la sequenza è periodica, cioé i valori si ripetono. Questo è un
fenomeno che ci riscontra con qualunque scelta di parametri. Scegliendo, invece,
come seme iniziale 5, la sequenza sarà 5 – 6 – 2 – 4 – 3 – 0 – 5 – 6 … ossia
la stessa sequenza di prima, ma con inizio da 5 anziché da 2 (cioè con i valori
traslati di una certa quantità). Nella sequenza vista, m vale 7, quindi i numeri generati andranno da 0 al 6, tra questi ne manca solo
uno: l’1. Scegliendo questo valore, come seme, otteniamo la sequenza:
1 – 1 – 1 – 1…

Modifichiamo ora il parametro a, ponendolo uguale ad 1. Con un seme uguale, ad
esempio, a 3, otterremo la sequenza:
3 – 1 – 6 – 4 – 2 – 0 – 5 – 3 – 1 nella quale appaiono tutti i numeri compresi tra 0 ed m-1 , una volta ciascuno, senza ripetizioni ed è molto difficile,
senza conoscerlo, trovare un legame tra un valore ed il successivo. La sequenza trovata può essere quindi considerata sufficientemente casuale. Qualunque
valore sia assegnato al seme iniziale, la sequenza sarà la stessa, pur se traslata di qualche posizione. In questo caso ci raggiunge la massima lunghezza possibile della sequenza, ovviamente uguale ad m. Questo perché se, dopo m passaggi, si sono trovati tutti i numeri compresi tra 0 ed m-l, grazie alle caratteristiche della formula al passaggio (m+l)-esimo si dovrà ripetere un numero già trovato.

Riassumendo

Studiando il metodo della congruenza lineare abbiamo dunque individuato le seguenti proprietà:

  • Le sequenze sono periodiche.
  • La lunghezza massima della sequenza è pari al parametro m.
  • Particolari valori di altri parametri possono accorciare la sequenza.
  • I valori generati sono compresi tra 0 ed m-1.

Per ottenere numeri tra 0 ed 1, come nelle funzioni implementate nei linguaggi più noti, basterà dividere per m-l. Provate ancora con le terne inserite nello stesso programma pubblicato (ovviamente non chiedete di generare più di m valori) oppure con terne scelte da voi. Esistono criteri particolari per una scelta corretta dei tre parametri:

  • c ed m devono essere primi tra loro, cioé non devono avere divisori comuni;
  • i divisori primi di m devono essere divisori di a-l (il 4 deve essere considerato numero primo).

Le terne più usate, incluse nel listato pubblicato, sono:

  • Terna di Leormonth – Lewis
    • m = 2^31
    • a = 2^16
    • c = 0
  • Terna di Knuth
    • m = 2^31
    • a = int (pigreco * 10^8)
    • c = 45380624
  • Terna di Goodman – Miller
    • m = 2^31-1
    • a = 7^5
    • c = 0

Nelle funzioni di libreria il seme iniziale viene generalmente fissato in modo hardware, prelevandolo da locazioni di memoria usate per altri scopi, tra cui il clock di sistema.

Per concludere, un indovinello per i lettori, anche non espertissimi. L’operazione di modulo, che richiede una divisione, viene spesso realizzata anche con un’operazione logica, molto più veloce nell’esecuzione. Questo trucco ci può usare solo con le terne di Knuth e di Leormonth-Lewis, o con altre che abbiano “qualcosa” in comune con queste (che cosa? chissà!).Provate a definire l’operazione e a dimostrare la soluzione ottenuta. Per aiutarvi vi suggeriamo di riferirvi ai numeri binari.

Anche su disco

Come intuitivo, anche questi semplici programmi cono inseriti su Computer Club Disco di questo mese, nella sezione dedicata al software “intercambiabile” tra Amiga ed Ms-dos. Per esercizio, provate ad implementare le routine proposte in altri linguaggi, nonostante, come già precisato nell’articolo, siano disponibili specifiche funzioni per determinare numeri random.

Listato

N.B.: il programma è stato scritto nel 1991, in un linguaggio all’epoca già obsoleto. Þ fornito al solo scopo di mostrare una possibile implementazione dell’algoritmo.

30 REM Generatore random
50 REM (metodo di Congruanza lineare)
55 REM n (i+l) = (a* n(i) + c)mod m
60 REM Versione universale
91 REM
92 PRINT " Scegliere terne voluta"
93 PRINT " 1) Leormonth-Lewis"
94 PRINT " 2) Knuth": PRINT " 3) Goodman-Miller"
95 PRINT " 4) Altra terna"
96 INPUT "Scelta ": r
97 IP r < 1 OR r > 4 THEN 96
99 ON t GOSUB 120, 220, 320, 410
100 GOTO 500
110 REM Leormonth-Lewis
126 PRINT "Terna di Leormonth-Lewis"
130 PRINT " m=2^31 = 2147483648"
140 PRINT " a=2^16+3 = 65539"
150 PRINT " c=0"
160 a = 65539: c = 0: m = 2 ^ 31
170 RETURN
200 REM Knuth
220 PRINT "Terna di Knuth"
230 PRINT " m = 2^ 31 = 2147483648": m = 2 ^ 31
240 PRINT " a = int (pi * 10^8) = 314159265": a = 314159265
250 PRINT " c = 453806245": c = 453806245
270 RETURN
306 REM Goodman-Miller
320 PRINT "Terna di Goodman-Millar"
330 PRINT " m = 2^31 - 1 = 2147483647"
340 PRINT " a = 7^5 = 16807"
350 PRINT " c = 0"
360 m = 2^31 - 1: a = 7^5: c = 0
370 RETURN
410 PRINT "Inserire terna di valori"
420 INPUT "Inserire valore di m"; m
430 INPUT "Inserira valore di a"; a
440 INPUT "Inserire valore di c"; c
450 RETURN
500 INPUT "Seme iniz. sequenza"; n
501 INPUT "Valori tra 0 e l(s/n)": a$
502 IF a$ = "s" THEN m1 = m-l: GOTO 510
503 IF aS = "n" THEN m1 = 1: GOTO 510
504 GOTO 501
510 INPUT "Numero di valori": i
520 PRINT n / m1
530 FOR q = 1 TO i - 1
540 P = a * n + c
550 o = p - INT(p / m) * m
560 n = o: PRINT n/m1
570 NEXT
575 a$ = ""
580 INPUT "Ancora (s/n)": a$
590 IF a$ = "s" THEN RUN
600 IF a$ <> "n" THEN 580
610 END

Copyright © Fabrizio Tarizzo

Quest'opera è stata rilasciata sotto la licenza Creative Commons Attribuzione-Condividi allo stesso modo 3.0 Italia. Per leggere una copia della licenza visita il sito web http://creativecommons.org/licenses/by-sa/3.0/it/ o spedisci una lettera a Creative Commons, 171 Second Street, Suite 300, San Francisco, California, 94105, USA.