Algoritmo pseudo-casuale semplice

Question

Mi serve un generatore pseudo-casuale che prende un numero come input e restituisce un altro numero che è riproducibile e sembra casuale.

• Ogni numero di ingresso deve corrispondere esattamente a un numero di uscita e viceversa
• stessi numeri di ingresso risultare sempre in numero di uscita stesse
• numeri di ingresso sequenziali che sono vicine tra loro (es. 1 e 2) dovrebbe produrre numeri di uscita completamente diversi (ad esempio 1 => 9783526, 2 => 283)

Non deve essere perfetto, è solo per creare dati di test casuali ma riproducibili.

Io uso C#.

---

Ho scritto questo divertente pezzo di codice qualche tempo fa che ha prodotto qualcosa di casuale.

public static long Scramble(long number, long max) 
    { 
    // some random values 
    long[] scramblers = { 3, 5, 7, 31, 343, 2348, 89897 }; 
    number += (max/7) + 6; 
    number %= max; 
    // shuffle according to divisibility 
    foreach (long scrambler in scramblers) 
    { 
     if (scrambler >= max/3) break; 
     number = ((number * scrambler) % max) 
     + ((number * scrambler)/max); 
    } 

    return number % max; 
    } 

Mi piacerebbe avere qualcosa di meglio, più affidabile, lavorando con tutto il formato del numero (nessun argomento max).

Questo potrebbe essere risolto utilizzando un algoritmo CRC? O roba un po 'trascinante.

Answer 1

È (forse) può farlo facilmente in C# utilizzando la classe Random:

public int GetPseudoRandomNumber(int input) 
{ 
    Random random = new Random(input); 
    return random.Next(); 
} 

Dal momento che si sta seminando in modo esplicito a caso con l'ingresso, si otterrà lo stesso risultato ogni volta dato lo stesso valore d'ingresso .

Answer 2

tolgo il codice Microsoft da questa risposta, il file di codice GNU è molto più a lungo ma in fondo contiene questo da http://cs.uccs.edu/~cs591/bufferOverflow/glibc-2.2.4/stdlib/random_r.c:

int32_t val = state[0]; 
val = ((state[0] * 1103515245) + 12345) & 0x7fffffff; 
state[0] = val; 
*result = val; 

per il vostro scopo, il seme è stato di [0] in modo che sarebbe più simile

int getRand(int val) 
{ 
    return ((val * 1103515245) + 12345) & 0x7fffffff; 
} 

Answer 3

le prime due regole suggeriscono una permutazione fisso o ingresso testa di serie dell'ingresso, ma la terza regola richiede una ulteriore trasformazione.

C'è qualche ulteriore restrizione su quali dovrebbero essere le uscite, per guidare quella trasformazione? - per esempio. esiste un set di input di valori di output tra cui scegliere?

Se l'unica guida è "no max", userei il seguente ...

1. Applicare un algoritmo di hash per l'intero input per ottenere il primo elemento di output. Un CRC potrebbe funzionare, ma per risultati più "casuali", utilizzare un algoritmo di crittografia hash come MD5.

2. Utilizzare un algoritmo di permutazione successivo (molti collegamenti su Google) sull'input.

3. Ripetere la permutazione hash-then-next fino a quando non vengono trovati tutti gli output richiesti.

La prossima permutazione può essere eccessivo, però, si potrebbe probabilmente solo incrementare il primo ingresso (e forse, in caso di overflow, incrementare il secondo e così via) prima di rifare l'hash.

Per l'hashing in stile crittografico, avrete bisogno di una chiave - derivate qualcosa dall'input prima di iniziare.

Answer 4

Un generatore di tausworthe è semplice da implementare e piuttosto veloce. La seguente implementazione pseudocodice ha ciclo completo (2 ** 31-1, perché zero è un punto fisso):

def tausworthe(seed) 
    seed ^= seed >> 13 
    seed ^= seed << 18 
    return seed & 0x7fffffff 

Non so C#, ma sto supponendo che ha XOR (^) e il bit shift (<<, >>) operatori come in C.

Impostare un valore iniziale di inizializzazione e richiamare con seed = tausworthe(seed).