Generazione personale di numeri pseudo casuali

Generazione personale di numeri pseudo casuali

Nell’ultimo mio intervento nella sezione Articoli, ovvero:

http://blog.shareoffice.it/giannigiaccaglini/articles/11052.aspx

Ho esposto un procedimento che ritengo originale (e comunque ingegnoso, se permettete) in grado di “Scombussolare un documento Word” disponendo in modo random delle sue parti tri-letterali.

Il modo migliore per ovviare all’inconveniente, è dato da una sequenza molto ampia di numeri casuali ma che resta identica se se ne fissa il primo valore (il “seme”, in gergo).

Mi dicono che la cosa è possibile in Visual Studio con un complesso generatore Random, ma non nel convento VB6 su cui si fiondano le macro di MS Office. Per fortuna ci si può arrangiare con un algoritmo del cosiddetto metodo della congruenza lineare. Con un po’ di pazienza si può trovare descritto sul Web.

Illustrazione pratica del metodo con Excel

La formula che fornisce il successore di un siffatto casuale è abbastanza semplice:

x_i+1= (a* x_i + c) Mod m

ove Mod in VBA è proprio l’operatore che, per fare un esempio banale, con l’istruzione Resto = 12 Mod 5 ci dà il resto della divisione intera fra i due numeri interi, ossia 2 nella fattispecie.

Per comprendere più da presso la faccenda propongo di ricorrere a Excel. La figura seguente illustra un caso particolare dovuto alla scelta x₀ = 1, a = 12, c=5, m=11. Le intestazioni di riga e colonna sono omesse ma l’intervallo è “appeso” in A1.

Le formule nelle celle di colonna C sono subito viste:

C1=B1

C2:C15=RESTO($B$2*C1+$B$3;$B$4)

Ove la seconda formula si ottiene al volo in tre mosse: 1. Selezione di C1:C15; 2. Digitazione della formula in C2; 3. Consolidamento della stessa con Ctrl+Invio.

Si constaterà una sequenza di numeri ciclica di lunghezza 11:  1, 6, 0, 5, 10, 4, 9, 3, 8, 2, 7... Chiaramente troppo breve. Addirittura con certi valori la lunghezza è 1, ossia del tipo 3, 3, 3, 3,...

L’algoritmo proposto

La teoria chiarisce i criteri da adottare per ottenere sequenze di massima lunghezza. In base ad essi diversi studiosi, tra cui il famoso Knuth, hanno escogitato opportuni valori dei parametri suddetti. Suggerisco quelli dovuti a Goodman e Miller: m=2³¹ -1;  a = 7⁵; c=0

Il risultato è del tipo seguente:

Stavolta, per maggior generalità ho assegnato all’intervallino dei parametri i nomi X0, a ed m, tralasciando  c, che essendo nullo si può omettere nella formula base. Ed ecco infine le formule del caso:

B1=INT(CASUALE()*10000000000)

B2=7^5

B4=2^31-1

C1=X0

C2=RESTO(a*C1;m)

C3=RESTO(a*C2;m)

E via di seguito nelle celle sottostanti, a piacere. Premendo il tasto RICALCOLA, alias F9 si assisterà alla riproduzione di serie caratterizzate da un seme X0 variabile da zero a 10 alla decima.

Soluzione del nostro problema? problematica

Per lo scopo di cui all’inizio, sconvolgere un documento, salvarlo e recuperarne l’originale la soluzione è presto detta: usare un generatore come quello appena illustrato adottando come chiave un seme di massimo 10 cifre.

Chi legge attentamente anche l’articolo citato in apertura, se interessato e buon intenditore, può cavarsela anche da solo. Prima di chiudere tuttavia è doveroso precisare che nel frattempo ho scoperto un altro inghippo:

Il metodo sopra illustrato, tradotto in VBA purtroppo dà luogo a blocchi per “overflow”, a causa del limitato range del tipo Long.

Il guaio si può constatare, con raccapriccio, lanciando questo macrocodice:

Function NextRand(PrecRand) '

  Dim a, m

  a = CDec(7 ^ 5): m = CDec(2 ^ 31 - 1)

  Dim NextRnd As Double

  NextRnd = a * PrecRand Mod m

  NextRand = NextRnd

End Function

Sub Prova()

  x = 12345

  For i = 1 To 1000

  MsgBox x

  x = NextRand(x)

  Next

End Sub

Altrettanto male vanno le cose se ci si illude di sfruttare NextRand come funzione personale sul foglio di lavoro...

Ma ci si può accontentare

Provando e riprovando un po’ a casaccio ho trovato questi parametri:  a = 16807, c = 78125, m = 2047, che danno una sequenza di casuali di lunghezza 93. Questa sarebbe troppo breve se si adottasse il metodo per una crittografia, “classica”, ovvero di cifratura. Ma Nel nostro sistema scombussolante le cose vanno decisamente meglio.

Si lanci il seguente macrocodice:

Sub Scombussola()

  strOrig = "abcdefghijklmnopqrstuvwxyz"

  strRand = "793152468"

  NOrig = Len(strOrig): NRand = Len(strRand)

  ReDim VettRand(NOrig)

  j = 1

  For i = 1 To NOrig

     VettRand(i) = Mid(strRand, j, 1)

     j = IIf(j = NRand, 1, j + 1)

  Next

  ' Bubble sort

  For i = 1 To NOrig - 1

    For j = i To NOrig

      If VettRand(j) < VettRand(i) Then

        dep = VettRand(i)

        VettRand(i) = VettRand(j)

        VettRand(j) = dep

        dep = Mid(strOrig, i, 1)

        Mid(strOrig, i, 1) = Mid(strOrig, j, 1)

        Mid(strOrig, j, 1) = dep

      End If

    Next j

  Next

  For i = 1 To NOrig

    Debug.Print VettRand(i), Mid(strOrig, i, 1)

  Next

End Sub

La routine crea un banale VettRand di interi casuali di lunghezza 9, che si succedono come nella strRand, quindi si procede al bubble sort sia di VettRand  che della stringa originaria qui rappresentata dai  caratteri dell’alfabeto. Ed ecco il risultato nella finestra di Debug:

1              d

 1            m

 1            v

 2            o

 2            f

 2            x

 3            u

 3            c

 3            l

 4            p

 4            g

 4            y

 5            w

 5            e

 5            n

Eccetera...

In prima battuta si evince che l’ordinamento di VettRand ha creato ripetizioni, la qual cosa potrebbe far sorgere qualche timore, che però viene (ragionevolmente) fugato dalla constatazione che ciò nonostante un buon grado di disordine nella stringa, stravolta come “dmvofxuclpgywen....”.

Mi fermo qui, confidando in commenti e suggerimenti da parte dei più esperti.

posted on giovedì 1 dicembre 2011 17.23