Les mathématiciens sont confrontés au problème de la découverte de carrés parfaits et de leurs racines depuis l’Antiquité. Des découvertes récentes en théorie computationnelle des nombres ont permis de développer des algorithmes efficaces pour découvrir les nombres carrés. Le professeur Philip Brown, du département des sciences fondamentales (mathématiques) du campus Galveston de l’université Texas A&M, a mis au point un nouvel algorithme capable de détecter un carré parfait et de construire sa racine en utilisant l’arithmétique binaire. Le professeur Brown démontre comment son algorithme est facilement mis en œuvre et peut tester des nombres avec des millions de chiffres.

Révélation des propriétés des carrés parfaits
 

Le professeur Brown a observé que certaines propriétés des carrés parfaits sont révélées si les nombres sont exprimés dans une base qui est une puissance de 2, comme dans les systèmes numériques binaire, octal et hexadécimal. Cela sous-tend la façon dont son algorithme peut identifier un carré parfait et construire sa racine carrée, en commençant par les chiffres d’ordre inférieur et en passant par les chiffres d’ordre supérieur.

Parce que l’algorithme construit les racines carrées en commençant par les chiffres d’ordre inférieur, il est plus facile à comprendre si nous lisons ou étiquetons les chiffres de droite à gauche.

Regiomontanus est considéré comme l’inventeur du symbole de la racine carrée. N’hésitez pas à Découvrir la page du Cnam Haute-Normandie pour en savoir plus sur la racine carrée.

Le professeur Brown démontre comment l’algorithme commence par convertir le nombre d’entrée N de la base 10 à la base 2. Si N est un nombre pair, alors son expression en base 2 commence (à droite) par une chaîne de chiffres binaires qui sont tous égaux à 0. Par exemple, les nombres décimaux 4 et 20 sont exprimés respectivement par 100 et 10100 en base 2. Lorsque le nombre d’entrée, N, est un nombre pair, la chaîne initiale de zéros de la représentation binaire du nombre est tronquée, laissant le nombre impair résultant à tester. Si ce nombre impair est un carré, alors N est soit un carré, soit deux fois un carré. Cela signifie que l’algorithme ne doit continuer que lorsque N est impair. Ainsi, étant donné un nombre entier impair N au format octal, l’algorithme déterminera si N est un carré parfait et calculera la racine carrée si nécessaire.

Observations avec la base 8
 

La base 8 est un système de nombres pratique pour démontrer l’algorithme du Prof Brown, car elle est la plus proche de la base 10. La multiplication par 4 en base 8, par exemple 1 x 4 = 4, 2 x 4 = 10, donne toujours un nombre avec un 0 ou un 4 du côté droit. Par conséquent, tous les carrés parfaits pairs exprimés en base 8 commencent (en lisant de droite à gauche) par un 0 ou un 4. Le professeur Brown montre également que tous les carrés parfaits impairs exprimés en base 8 commencent par un 1.

Le professeur Brown a développé une base théorique pour cet algorithme qui apporte un nouvel éclairage sur les propriétés des nombres carrés.

Base 2s
En outre, le professeur Brown démontre que pour les bases qui sont des puissances supérieures de 2, notées 2s, si le premier chiffre en base 2s d’un certain nombre N n’est pas congruent (modulo 2s) au carré d’un nombre impair. Alors le nombre N n’est pas un nombre carré.

Développements
 

Le professeur Brown a développé une base théorique pour cet algorithme qui apporte un nouvel éclairage sur les propriétés des nombres carrés en utilisant l’arithmétique binaire, octale et hexadécimale. Ce travail peut par ailleurs être étendu à d’autres systèmes de nombres avec des bases qui sont des puissances de 2 encore plus grandes.

Le nouvel algorithme peut détecter un carré parfait et construire sa racine en utilisant l’arithmétique binaire.

Le nouvel algorithme peut détecter un carré parfait et construire sa racine en utilisant l’arithmétique binaire. Il est relativement simple à utiliser et comparable à d’autres algorithmes en termes de complexité de calcul et d’espace de stockage, avec l’avantage que les résultats sont présentés avec certitude et ne nécessitent aucune interprétation des probabilités.

Dans l’algorithme, le professeur Brown offre à l’utilisateur un certain nombre d’options pour adapter l’algorithme à ses besoins individuels. Par exemple, le programmeur peut choisir de résoudre les inverses multiplicatifs en utilisant des matrices de sélection précalculées ou en déployant l’algorithme euclidien étendu. Ils ont également le choix de mettre en œuvre l’algorithme en base 8 ou toute autre base qui est une puissance supérieure à 2, ce qui peut dépendre de la taille du nombre à tester.