Fibonacci ritardato

[orion1983]

Ciao a tutti....dovrei implementare una classe che generi numeri pseudocasuali attraverso Fibonacci Ritardato ma non so come fare in quanto se li implemento come dice sul sito di wikipedia o i numeri non sono casuali ma esce sempre lo stesso o devo comunque usare la Math.random....Qualcuno sa come devo fare????


grazie e ciao

[Dreamer89]

Per generare numeri casuali devi usare la classe Random.
es.

Random generator = new Random();
int numeroCasuale = generator.nextInt (10) //numeri casuali da 0 a 9

EDIT: java.util.Random :P

[orion1983]

Sì ok....ma siccome è un progettino per un esame volevo provare ad implementare io una classe per generare numeri casuali usando l'algoritmo di fibonacci ritardato appunto.....

[andbin]

Originariamente inviato da orion1983
volevo provare ad implementare io una classe per generare numeri casuali usando l'algoritmo di fibonacci ritardato appunto.....

Bene, allora inizia a definire una tua classe es. RandomFibonacci e come variabili di istanza avrai sicuramente i 2 precedenti termini della successione (come spiegato nella pagina linkata). Questo ovviamente perché servono per calcolare il prossimo valore nella successione e quindi li devi "tenere".

Poi definisci un tuo metodo es. estrai() a cui passi un valore 'm'. Quindi fai il calcolo e il modulo (sempre come spiegato nella pagina), aggiorni lo "stato" del tuo oggetto e restituisci il valore.

L'unica cosa che non saprei ora è a cosa inizializzare i due termini quando si istanzia l'oggetto. Cioè come valori iniziali. La pagina di wikipedia inglese spiega decisamente di più ma dovrei leggerla attentamente.

[orion1983]

Anch'io è quello che non ho capito infatti per generare j e k uso la classe Random di java così:

 public int getRandom(){
        long[] fibo = new long[90];
        
        fibo[0] = 0;
        fibo[1] = 1;
        
        for(int count = 2;count < 90; count++){
            fibo[count] = fibo[count-1] + fibo[count-2];
        }
      
        Random generator = new Random();
        
        int j = generator.nextInt(90);
        int k = generator.nextInt(90);
        int max = Math.max(j, k); 
        int min = Math.min(j, k); 
        //Prendo il resto della divisione per 6 e aggiungo 1 per farlo "diventare" un dado

        long rnd = (fibo[min] + fibo[max])%6 + 1;
        
        return (int)rnd;
    }

e funziona.....e anche abbastanza bene devo dire.....I dati reali si discostano di poco da quelli teorici...però la casualità non è data dalla classe che ho scritto io...però non vedo altre soluzioni


Ciao e Grazie

[andbin]

Originariamente inviato da orion1983
Anch'io è quello che non ho capito infatti per generare j e k uso la classe Random

Ho letto un pochino la pagina inglese di wikipedia che ho linkato. Ho capito a grandi linee come funziona (non sono un matematico ... e si vede ).

Stando alla documentazione, i valori di j e k devono essere scelti molto accuratamente per rispettare certi criteri e devono restare fissi. Quindi non devono essere scelti casualmente!!

Questi due valori indicano quali sono i due termini precedenti da usare. Visto che i valori possono essere alti (es. j=24 e k=55) allora vuol dire che, in generale, devi tenere una lista (una "coda" per essere precisi) degli ultimi k valori.

Il valore di 'm' dice che in genere è una potenza di 2 (es. 2^32 o 2^64).

Inoltre dice che l'output è molto "sensibile" alle condizioni iniziali, quindi la fase di inizializzazione deve essere fatta in modo accurato. E per questo punto, la inizializzazione, non ho le idee ben chiare ....

Prima di partire in quarta ... cerca di comprendere meglio la questione.

[orion1983]

Sì....Quelle coppie di valori sono generate da serie numeriche molto semplici....come dici te devono essere molto accurate in quanto servono a far in modo che la probabilità di uscita di ogni valore sia la stessa(altrimenti "l'estrazione" sarebbe truccata).... VVoVe:

La classe Random di Java già di per se rispetta questo vincolo infatti la distribuzione di probabilità che risulta dal mio programma dopo 1000 prove è praticamente identica a quella che ho calcolato in teoria con uno scarto che è sempre sotto 1%....Che è un ottimo risultato visto che le prove sono relativamente poche...

Inoltre aumentado le prove si avvicina sempre di più al risultato calcolato....


Ora sto guardando come è implementata la classe Random per vedere un po di capire come genera il numero casuale.....ma da quel che ho capito fin qui usa System.nanoTime()

[andbin]

Originariamente inviato da orion1983
Sì....Quelle coppie di valori sono generate da serie numeriche molto semplici....come dici te devono essere molto accurate in quanto servono a far in modo che la probabilità di uscita di ogni valore sia la stessa(altrimenti "l'estrazione" sarebbe truccata).... VVoVe:

Ad un certo punto parla del "periodo" del generatore. Dice:

[...] For the generator to achieve this maximum period, the polynomial:

y = x^k + x^j + 1

must be primitive over the integers mod 2. Values of j and k satisfying this constraint have been published in the literature. Popular pairs are:

{j = 7, k = 10}, {j = 5, k = 17}, {j = 24, k = 55}, { .........

Quindi dovresti scegliere una di queste coppie "note", non calcolarli tu!! Al fondo dice che ad esempio il gioco Freeciv utilizza questo algoritmo con {j = 24, k = 55}.

[orion1983]

Ciao....ho risolto...ieri mattina prima dell'esame ho avuto l'illuminazione e.....28!!!!


Grazie 10000 CIAO!!!