Problème du biais de modulo

Le code suivant illustre la pratique répandue :

u64 r = random_u64(); // uniform over [0..UINT64_MAX]
T chosen = choices[r % 10];

La fonction random_u64() génère un entier 64 bits uniformément distribué. Appliquer l’opérateur % 10 ne conserve pas cette uniformité lorsque le module n’est pas une puissance de deux. Sur un intervalle de 10 valeurs, les résidus 0,3,6,9 produisent le premier choix, soit 4 sur 10 = 40 % de probabilité, tandis que les deux autres reçoivent 30 % chacun. Le biais apparaît dès que le nombre d’issues n’est pas un diviseur exact de la taille de l’espace source.

Solutions via fonctions spécialisées

Une fonction random_between(l, h) qui renvoie chaque entier de l à h avec une probabilité 1/((h‑l)+1) élimine le biais. Elle nécessite toutefois de connaître les bornes exactes du sous‑intervalle souhaité. Une alternative plus expressive est random_choice(), qui accepte une collection d’options accompagnées de leurs probabilités. Ainsi, le même scénario s’écrit :

T chosen = random_choice([ (First, 0.4), (Second, 0.3), (Third, 0.3) ]);

Cette API oblige le développeur à déclarer explicitement la distribution, rendant les écarts immédiatement visibles.

Poids entiers relatifs et implémentation

Les poids en virgule flottante imposent que la somme soit exactement 1.0, ce qui peut introduire des imprécisions. La plupart des bibliothèques standard, comme Python, préfèrent des poids entiers relatifs. On représente les probabilités par des entiers dont le rapport au total définit la fréquence. L’exemple précédent devient (4, 3, 3) ; la somme vaut 10, donc chaque poids correspond à 4/10, 3/10, 3/10. L’algorithme consiste à choisir un entier k uniformément dans [0, total‑1] puis à sélectionner la première tranche cumulée qui dépasse k. Avec des poids (15, 12, 3) la somme est 30 ; un k compris entre 0‑14 donne le premier choix, 15‑26 le deuxième, 27‑29 le troisième. Cette méthode repose uniquement sur random_between(0, total‑1), ce qui montre que random_u64() est trop bas‑niveau pour la plupart des besoins de sélection.

Conséquences et bonnes pratiques

Le biais de modulo peut fausser des simulations, des algorithmes de répartition de charge ou des systèmes de jeu où l’équité est attendue. Utiliser random_between ou random_choice garantit une distribution conforme à la spécification. Lorsque les poids sont entiers, l’implémentation reste triviale et évite les erreurs d’arrondi. En pratique, les bibliothèques modernes exposent déjà ces fonctions ; les intégrer dans les API internes réduit le risque de réintroduire le biais. Enfin, documenter explicitement la distribution attendue aide les revues de code à détecter les déviations avant le déploiement.