Méthode du carré médian
En mathématiques et en informatique, la méthode du carré médian est une méthode de génération de nombres pseudo-aléatoires. Cette méthode est très imparfaite dans la pratique, pour des objectifs réels, car sa période est généralement très courte : autrement dit, répétée suffisamment de fois, la méthode du carré du milieu commencera à générer toujours le même nombre ou redonnera un nombre déjà obtenu dans la séquence, qui tournera alors en boucle indéfiniment.
Histoire
modifierLa méthode a été décrite par John von Neumann lors d'un colloque, en 1949[1].
Dans sa conférence de 1949, Von Neumann a plaisanté en disant que « Quiconque considère les méthodes arithmétiques pour produire des chiffres aléatoires est, bien sûr, dans un état de péché ». Ce qu'il voulait dire, a-t-il expliqué, est qu'il n'existe pas de véritables « nombres aléatoires », mais simplement des moyens de les produire, et qu'« une procédure arithmétique stricte », comme la méthode du carré médian, « n'est pas une telle méthode ». Néanmoins, il a trouvé ce genre de méthode des centaines de fois plus rapides que la lecture de nombres « véritablement » aléatoires sur des cartes perforées, ce qui avait une importance pratique pour son travail sur l'ENIAC. Il trouvait aussi que la « destruction » des séquences de carrés médians (c'est-à-dire la situation fréquente où la méthode produit rapidement une suite de zéros et donc s'arrête) était un facteur en leur faveur, car elle est facilement détectable : « on craint toujours l'apparition de cycles courts non détectés »[1]. Nicholas Metropolis a signalé des séquences de 750 000 chiffres avant cette « destruction » en utilisant des nombres de 38 bits avec la méthode du « carré médian »[2].
Dans son livre Au hasard, Ivar Ekeland raconte en détail comment la méthode aurait été inventée par un frère franciscain connu uniquement sous le nom de Frère Edvin, entre 1240 et 1250[3]. Le manuscrit serait aujourd'hui perdu, mais Jorge Luis Borges aurait envoyé à Ekeland une copie qu'il avait réalisée à la Bibliothèque du Vatican.
La méthode
modifierPour générer une séquence de nombres pseudo-aléatoires à n chiffres, on choisit d'abord une valeur de départ à n chiffres (la « graine ») et on l'élève au carré, ce qui génère en général un nombre à 2n chiffres. Si le résultat comporte moins de 2n chiffres (par exemple pour n=2, la valeur 11 élevée au carré donnerait 121, à trois chiffres seulement), des zéros non significatifs sont ajoutés pour compenser. Les n chiffres du milieu du résultat sont alors sélectionnés comme valeur suivante dans la séquence. Ce processus est ensuite répété, à partir du résultat obtenu (la nouvelle « graine »), pour générer plus de nombres.
La valeur de n doit être paire pour que la méthode fonctionne. Si la valeur de n est impaire, sélectionner les « n chiffres du milieu » ne pourra pas se faire de manière unique et bien définie. Ainsi, si un nombre à 3 chiffres est élevé au carré, il peut donner un nombre à 6 chiffres (un exemple est 5402 = 291600). Sélectionner les 3 chiffres du milieu laisserait 6 − 3 = 3 chiffres, soit à gauche, soit à droite de ceux sélectionnés et il n'est pas possible de répartir ces chiffres de manière égale des deux côtés ; il n'y a pas de « chiffres du milieu » dans ce cas. On peut par exemple compléter les graines avec des zéros à gauche afin de créer un nombre pair à n chiffres (ainsi remplacer 540 par 0540).
Pour un générateur de nombres à n chiffres, la période, c'est-à-dire le nombre d'étapes avant de retrouver un nombre déjà obtenu, ne peut pas dépasser 8n. Si les n chiffres du milieu sont tous des zéros, le générateur génère des zéros indéfiniment. Si la première moitié d’un nombre dans la séquence est constituée de zéros, les nombres suivants diminueront jusqu’à zéro. Même si, comme le soulignait von Neumann, le fait d'aboutir à des zéros est faciles à détecter, il se produit trop fréquemment pour que la méthode soit utile en pratique. La méthode du carré du milieu peut également rester bloquée sur un nombre autre que zéro. Pour n = 4, cela se produit ainsi avec les valeurs de départ 0100, 2500, 3792 et 7600. D'autres valeurs de départ forment des cycles répétitifs très courts, par exemple 0540 → 2916 → 5030 → 3009. Ces phénomènes sont encore plus évidents lorsque n = 2, car aucune des 100 graines possibles ne génère plus de 14 itérations sans revenir à 0, 10, 50, 60 ou à une boucle 24 ↔ 57.
En combinant l'algorithme du carré du milieu avec une suite de Weyl arithmétique, c'est-à-dire les restes des multiples successifs d'un entier impair divisés par une puissance de 2 (ce qui forme une suite équidistribuée discrète), il est possible d'améliorer la période et le caractère aléatoire[4],[5].
Exemple de mise en œuvre
modifierIci, l'algorithme est rendu en Python 3.11
seed_number = int(input("Veuillez entrer un nombre à 4 chiffres:\n[####] "))
number = seed_number
already_seen = set()
counter = 0
while number not in already_seen:
counter += 1
already_seen.add(number)
number = int(str(number * number).zfill(8)[2:6]) # zfill ajoute un remplissage de zéros
print(f"#{counter}: {number}")
print(f"Nous avons commencé avec {seed_number} et"
f" nous nous sommes répétés après {counter} étapes"
f" avec {number}.")
Références
modifier- Les articles de ce colloque ont été publiés seulement en 1951 : (en) John von Neumann, « Various techniques used in connection with random digits », dans A. S. Householder, G. E. Forsythe, and H. H. Germond, eds., Monte Carlo Method, Washington, D.C., U.S. Government Printing Office, coll. « National Bureau of Standards Applied Mathematics Series » (no 12), , p. 36–38.
- (en) Donald E. Knuth, The art of computer programming, vol. 2: Seminumerical algorithms, Reading, Mass., Addison-Wesley, , ch. 3, section 3.1.
- Ivar Ekeland, Au hasard : la chance, la science et le monde, Paris, Seuil, (ISBN 978-2020128773).
- (en) Ron Kneusel, Random Numbers and Computers, Cham, Springer, , p. 13–14.
- (en) Bernard Widynski, « Middle-Square Weyl Sequence RNG », sur Arxiv, .
