Comment obtenir des entiers pseudo-aléatoires uniformément répartis en C assez bons pour la simulation statistique?

J’écris une simulation de Monte Carlo et je vais avoir besoin de beaucoup de bits aléatoires pour générer des entiers uniformément répartis sur {1,2, …, N} où N <40. Le problème avec l’utilisation de la fonction C rand est que j’aurais gaspillé beaucoup de bits parfaitement bons en utilisant la technique rand % N standard rand % N Quel est le meilleur moyen de générer les nombres entiers?

Je n’ai pas besoin de nombres aléatoires sécurisés par cryptographie, mais je ne veux pas qu’ils faussent mes résultats. En outre, je ne considère pas que télécharger un lot de bits de random.org soit une solution.

rand % N ne fonctionne pas; les résultats sont RAND_MAX + 1 sauf si RAND_MAX + 1 est un multiple de N

Une approche correcte consiste à déterminer le plus grand multiple de N inférieur à RAND_MAX , puis à générer des nombres aléatoires jusqu’à ce qu’il soit inférieur à cette valeur. Alors seulement devriez-vous faire l’opération modulo. Cela vous donne un taux de rejet de 50% dans le pire des cas.

en plus de la réponse d’oli:

si vous êtes désespérément préoccupé par les bits, vous pouvez gérer une file de bits à la main, en ne récupérant que le nombre nécessaire pour le nombre suivant (c’est-à-dire upper (log2 (n))).

mais vous devez vous assurer que votre générateur est assez bon. les générateurs congruentiels linéaires simples (sp?) sont meilleurs dans les bits les plus hauts que les plus bas (voir commentaires), votre approche actuelle de division modulaire a donc plus de sens.

Les recettes numériques ont une très bonne section sur tout cela et sont très faciles à lire (pas sûr que cela mentionne la sauvegarde des bits, mais comme une référence générale).

mettre à jour si vous ne savez pas si cela est nécessaire ou non, je ne m’inquiéterais pas de cela pour le moment (à moins que vous ne receviez de meilleurs conseils de la part de quelqu’un qui comprend votre contexte particulier).

Représentez rand en base40 et prenez les chiffres sous forme de nombres. Supprimez tous les chiffres incomplets, c’est-à-dire supprimez le premier chiffre s’il ne contient pas toute la plage [0..39] et supprimez le nombre entier aléatoire si le premier chiffre prend sa valeur la plus élevée possible (par exemple, si RAND_MAX est à base40, 21 23 05 06, supprimez tous les nombres ayant le chiffre le plus élevé en base 40) 21).