Simple pseudo-aléatoire algorithme

Question

Je suis besoin d'un générateur pseudo-aléatoire qui prend un certain nombre en entrée et retourne une autre sorcière numérique est reproductible et semble être aléatoire.

• Chaque numéro d'entrée doit correspondre exactement à un numéro de sortie et vice versa
• mêmes numéros d'entrée sont toujours le résultat en même nombre de sortie
• nombres d'entrée séquentiels qui sont proches les unes (p. 1 et 2) doivent produire des nombres de sortie complètement différentes (par ex. 1 => 9.783.526, 2 => 283)

Il ne doit pas être parfait, il est juste de créer des données de test aléatoires mais reproductibles.

J'utilise C #.

---

J'ai écrit cette pièce drôle code il y a quelque temps qui a produit quelque chose au hasard.

  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;
  }

Je voudrais avoir quelque chose de mieux, plus fiable, travaillant avec une taille de nombre (pas d'argument max).

Cela pourrait-il être probablement résolu en utilisant un algorithme CRC? Ou des choses peu traînant.

Answer 1

(peut-être) peut le faire facilement en C # en utilisant la classe aléatoire:

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

Puisque vous ensemençant explicitement au hasard avec l'entrée, vous obtiendrez le même résultat à chaque fois étant donné la même valeur d'entrée.

Answer 2

Je supprimer le code Microsoft de cette réponse, le fichier de code GNU est beaucoup plus longue, mais, fondamentalement, il contient cette 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;

pour votre but, la semence est l'état [0] il ressemblerait plus à

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

Answer 3

Les deux premières règles suggèrent une permutation fixe ou tête de série d'entrée de l'entrée, mais la troisième règle exige une transformation plus loin.

Y at-il d'autres restrictions sur ce que les résultats devraient être, pour guider cette transformation? - par exemple. est-il une entrée ensemble de valeurs de sortie à choisir?

Si le guide est seulement "pas max", j'utiliser ce qui suit ...

1. Appliquer un algorithme de hachage à l'ensemble d'entrée pour obtenir le premier élément de sortie. Un CRC pourrait fonctionner, mais pour plus de résultats « au hasard », utiliser un algorithme de hachage Crypto tels que MD5.

2. Utilisez un algorithme suivant de permutation (de nombreux liens sur Google) sur l'entrée.

3. Répéter le hachage puis-next-permutation jusqu'à ce que toutes les sorties nécessaires se trouvent.

La permutation suivante peut être surpuissant cependant, vous pourriez probablement augmenter la première entrée (et peut-être, en cas de débordement, incrémenter la deuxième et ainsi de suite) avant de refaire le hachage.

Pour le hachage de style Crypto, vous aurez besoin d'une clé -. Simplement tirer quelque chose de l'entrée avant de commencer

Answer 4

Un générateur de tausworthe est simple à mettre en œuvre et assez rapide. La mise en œuvre pseudocode suivant a cycle complet (2 ** 31-1, parce que le zéro est un point fixe):

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

Je ne sais pas C #, mais je suppose qu'il a des opérateurs XOR (de ^) et le décalage de bits (<<, >>) comme en C.

Définir une valeur de départ initiale, et invoquer avec seed = tausworthe(seed).