Je me demande régulièrement s'il serait possible de trouver une application des nombres p-adiques ailleurs qu'en mathématiques ; par exemple, une application des 2-adiques en informatique (ce qui semble le plus plausible, parce que les ordinateurs, manipulant des nombres binaires, manipulent en fait des entiers 2-adiques approchés). Je n'ai pour l'instant rien trouvé de bien convaincant. Voici cependant un exemple qui pourrait servir avec un peu d'imagination, et qui en tout cas fait un « tour de magie » rigolo :
Soit a un entier impair écrit en binaire, disons, sur 64 bits, dont on suppose qu'il est le carré d'un entier : on cherche à retrouver cette racine carrée (exacte). Voici une façon de s'y prendre : (1) itérer, en partant de y=1, la fonction y ↦ 2y − a·y², jusqu'à tomber sur un point fixe qu'on notera b (note : tous les calculs sont faits en binaire sur la même largeur, disons 64 bits ; comme il est habituel en informatique, on jette les bits supérieurs) ; (2) itérer, en partant de x=1, la fonction x ↦ x·(3−b·x²)/2. Autrement dit, en C :
unsigned long
exact_odd_square_root (unsigned long a) {
unsigned long y = 1;
for ( unsigned long yn = 0 ; y != (yn = 2*y - a*y*y) ; y = yn );
unsigned long x = 1;
for ( unsigned long xn = 0 ; x != (xn = x*((3-y*x*x)>>1)) ; x = xn );
if ( x & ((((unsigned long)(-1))>>2)+1) )
x = -x;
return x & ((unsigned long)(-1))>>1;
}
(Les dernières lignes servent à corriger le nombre : il y a quatre
valeurs de x sur vérifiant x²=a,
différant par le bit de poids fort et/ou par un changement de signe
global — la fonction renvoie donc celui dont les deux bits de poids
fort valent 0. L'écriture ((((unsigned
long)(-1))>>2)+1) sert à représenter le nombre ayant 1
juste au-dessous du poids fort sans avoir à faire d'hypothèse sur la
taille des unsigned long.)
La fonction est évidemment limitée (on pourrait calculer une
fonction exact_square_root() en décalant le nombre du
nombre de bits adéquat — forcément pair — jusqu'à trouver un nombre
impair, en appliquant la fonction exact_odd_square_root()
ci-dessus, puis en refaisant le décalage vers la gauche de la moitié
du nombre de bits, mais la gestion des bits de poids fort serait
encore un peu plus pénible). Il y a cependant un truc rigolo, c'est
qu'elle retrouve la racine carrée même si le calcul du carré a débordé
(par exemple, sur 64 bits, si on
fait 1000000000001*1000000000001, on
trouve 2003766205206896641 et
pas 1000000000002000000000001, mais la fonction ci-dessus
retrouve bien 1000000000001 comme racine carrée pour
cette valeur), du moins si les deux bits de poids fort valent 1 (on ne
peut pas faire mieux). Par ailleurs, le nombre d'itérations est très
petit (quelque chose comme 6 au pire dans chaque boucle pour un nombre
de 64 bits), donc on pourrait dérouler les boucles.
L'explication 2-adique est vraiment facile : la première itération calcule l'inverse 2-adique b de a par une méthode de Newton, la seconde calcule la racine carrée par une méthode du même genre (on peut peut-être la présenter comme une méthode de Newton, en tout cas j'ai cherché un polynôme ayant un point fixe superattractif où on veut). J'imagine que je ne suis pas le premier à écrire un truc de ce genre, je n'ai pas cherché. Par contre, ce que j'aimerais bien, c'est trouver des exemples plus frappants ou plus utiles.