Automi cellulari per generare numeri casuali
Come avviene la generazione di numeri casuali? Con algoritmi pseudo-casuali, dove le sequenze sono molto lunghe ma finite. A volte si usano metodi legati al tempo corrente in millisecondi, ma anche tali sistemi possono produrre risultati ben poco casuali. Esistono automi cellulari in grado di generare sequenze realmente “rumorose”. In accordo con la teoria degli automi cellulari di Wolfram, ho scritto una classe Java in grado di generare sequenze di numeri indipendenti tra di loro. La regola utilizzata è la #30.
Regola 30
La classe si inizializza con un vettore di 50 posizioni in cui tutti i valori sono a 0 tranne in una cella in cui metto 1. L’automa procede per 7 passi ed inizia a fornire numeri casuali. Ha dimostrato di essere molto efficiente rispetto al suo corrispettivo java.lang.Random.
L’idea non è mia, ma deriva dalla lettura del libro di S.Wolfram – “A new kind of science”.
Ecco il codice sorgente in java:
/**
* Automa alla Wolfram x generare rumore
*/
public class Random {
private final int SEED_RULE = 22; //30
int seed;
byte[] rule;
byte[] data;
protected static Random instance;
public static void main(String[] args) {
Random r = new Random();
for (int i = 0; i < 1000; i++) {
r.nextFloat();
System.out.println(r.nextFloat());
}
}
private Random() {
super();
seed = SEED_RULE;
init();
}
static public Random getInstance() {
if (instance == null) {
instance = new Random();
}
return instance;
}
private void init() {
//un buffer per i dati
data = new byte[50];
//init delle rules
rule = new byte[8];
int pad = 128;
for (int i = 7; i >= 0; i--) {
if ((seed & pad) == pad) {
rule[i] = 1;
}
pad = pad >> 1;
}
//init del livello
java.util.Random r = new java.util.Random();
int numSingolarita = r.nextInt(data.length-1);
numSingolarita++; //almeno 1 singolarita
for (int i = 0; i < numSingolarita; i++) {
//posizione singolarita' nella schiera dati
int pos = r.nextInt(data.length);
data[pos] = 1;
}
nextInt();
}
private int nextInt() {
//ritorna un'intero casuale
byte[] newdata = new byte[data.length];
for (int i = 0; i < (data.length - 1); i++) {
int a = (i == 0 ? data[(data.length - 1)] : data[i-1]);
int b = data[i];
int c = (i == (data.length - 1) ? data[0] : data[i+1]);
int n = c+2*b+4*a;
newdata[i+1] = automa(n);
}
System.arraycopy(newdata, 0, data, 0, data.length);
byte[] ret = new byte[32];
System.arraycopy(data, 10, ret, 0, 32);
long R = 0;
for (int i = 0; i < ret.length; i++) {
R += ret[i]*Math.pow(2, i);
}
/* per visualizzare i passaggi a console
for (int i = 0; i < data.length; i++) {
System.out.print((data[i] == 0 ? ' ' : 'x'));
}
System.out.print(" " + R + "\n");
*/
return (int)R;
}
public float nextFloat() {
//torna un float casuale
float ret = 0f;
int n = nextInt();
if ( n != 0 ) {
ret = (float) ((float)n / (float)(Integer.MAX_VALUE));
}
ret = Math.abs(ret);
return ret;
}
private byte automa(int n) {
return rule[n];
}
}
