Générateur de séquences pseudo-aléatoire non seulement un générateur de nombres

J'ai besoin d'un algorithme qui transforme à peu près un horodatage unix en un nombre aléatoire approprié, de sorte que si je "lis" les horodatages, je reçois les mêmes nombres aléatoires.Générateur de séquences pseudo-aléatoire non seulement un générateur de nombres

Et voici ce que je veux dire par convenablement:

La plupart des humains ne détectent pas une boucle ou un motif dans les nombres aléatoires.
Il n'est pas nécessaire de sécuriser cryptographiquement.
Tous les nombres doivent pouvoir être générés. (Je l'ai trouvé que LFSR ne fais pas ça)
Les chiffres sont des entiers 32 bits

et je voudrais que ce soit assez rapide. Jusqu'ici mon idée est de semer un PRNG encore et encore, mais je ne suis pas sûr que ce soit la meilleure façon de gérer cela.

Toutes pensées et idées seront très appréciées.

Merci.

Source

2009-11-07 Sam Washburn

Si vous changez la séquence de horodatages, faire vous voulez obtenir les mêmes nombres aléatoires dans un ordre différent? Par exemple. commençant w/[(1, 5), (2, 3), (3,9)], où le premier nombre d'une paire est l'horodatage, voudriez-vous [(2,3), (3,9), (1,5)] ou [(2,7), (3,4), (1,6)]? – outis

XKCD à la rescousse! - http://xkcd.com/221/ – JasCav

Bon point dehors, cela distinguerait un hachage d'un prng. –

S'il n'est pas nécessaire d'être statistiquement aléatoire, vous pouvez peut-être envoyer les horodatages à MD5 et tronquer le hachage. Le problème principal est que je ne sais pas si cela serait surjectif. D'autres algorithmes de hachage pourraient fonctionner mieux.

Source

2009-11-07 04:58:03 outis

Si les nombres aléatoires sont destinés à la consommation humaine, il est peu probable qu'une collision de hachage soit rapidement distinguée. MD4, MD5 serait assez rapide. –

Je vais tester le hachage et voir à quoi ressemble la distribution. Je veux quelque chose qui a une distribution qui soit proche de l'aléatoire, mais ça n'a pas besoin d'être si proche, si vous attrapez ma dérive. –

Je suis allé de l'avant et j'ai marqué cela comme la réponse acceptée parce que c'était ce que j'ai utilisé, bien que les autres solutions ici puissent s'avérer tout aussi utiles. –

Je suggère d'examiner la famille de fonctions drand48() conforme POSIX. Ils donnent des nombres aléatoires décents (mais certainement pas cryptographiques), et srand48() prend une valeur de départ de 32 bits. Ils sont déterministes, ainsi la réutilisation d'une graine donnée régénérera à nouveau la même séquence de nombres.

Source

2009-11-07 05:29:01

Je n'ai pas vu votre réponse plus tôt; le mien est à peu près le même, mais utiliser '(erand48/nrand48/jrand48)' est plus direct que 'srand48 + (drand48/lrand48/mrand48)'. – ephemient

@ ephemient: Tout est dans la famille :-) –

(timestamp^0x12345678) + 12345678 Est-ce assez subtile?

Si vous ne vous souciez pas de la réversibilité, vous pouvez crc32 chaque horodatage.

Source

2009-11-07 06:09:02

Je suggère que la chose la plus facile à faire est de donner votre temps à jrand48. Quelque chose comme

#include <stdlib.h> 
int mix(int t) { 
    unsigned short x[3] = {t, t<<16, t}; 
    return jrand48(x); 
}

Il est réversible (2 · x + · n≡0x5deece66d (2 1) · t + 0xb mod 2 ⇒ t≡0xdfe05bcb1365 · (2 · X + n-0xb) mod 2 où n∈ [0,2)) mais comme ce sont les 32 bits élevés de 48 bits, ce n'est pas trop facile. (Vous pouvez appliquer jrand48-x plus d'une fois aussi, tant que vous ne l'appliquez pas 2 -1 fois, les mêmes sortes de propriétés détiendront.)

Source

2009-11-07 06:45:57 ephemient

Je ne comprends pas la réversibilité pour savoir si j'en ai besoin ou non. Est-ce essentiellement en prenant le nombre généré et en récupérant la graine (timestamp)? –

Oui. En traitant 'x' comme un nombre de 48 bits, on met' x = (2^32 + 1) * t', alors 'jrand48' le change en' 0x5deece66d * x + 0xb' et renvoie les 32 bits hauts. Il suffit d'un peu d'arithmétique modulaire pour calculer l'inverse, c'est-à-dire passer de la sortie de 'jrand48' à l'originale' t'. Ce n'est généralement pas le cas en général (la sortie 32 bits ne suffit pas pour définir l'état de 48 bits) mais puisque nous n'avons qu'une entrée de 32 bits, c'est ici. – ephemient

Voulez-vous dire 't >> 16' plutôt que 't << 16'? Ce que vous avez fait passer les 16 bits de poids faible aux 16 bits d'ordre élevé, et la conversion en court-circuit supprime alors les 16 bits d'ordre supérieur, de sorte que vous avez écrit '{t, 0, t}' de façon amusante. –

Générateur de séquences pseudo-aléatoire non seulement un générateur de nombres

Répondre

Questions connexes