<foo> simply produces <foo>in the text).
<URL: http://somewhere.tld/ >,
and it will be automatically made into a link.
(Do not try any other way or it might count as an attempt to spam.)mailto: URI,
e.g. mailto:my.email@somewhere.tld,
if you do not have a genuine Web site).
Ruxor (2014-07-10T19:54:51Z)
@Nicolas T: Oui mais ça ça n'a aucun rapport avec les 2-adiques.
Nicolas T (2014-07-10T18:57:27Z)
L'exemple le plus frappant est plutôt le calcul magique de 1/sqrt(x), tellement célèbre maintenant que "Fast inverse square root" a même sa page wikipédia à lui tout seul.
http://en.wikipedia.org/wiki/Fast_inverse_square_root
http://www.lomont.org/Math/Papers/2003/InvSqrt.pdf
DM (2014-07-08T08:49:59Z)
Lorsque l'on veut résoudre *exactement* des systèmes d'égalités linéaires à coefficients entiers, le premier réflexe est de faire du pivot de Gauss avec des coefficients GMP. Le problème est que même si la matrice de départ et la forme échelonnée sont creuses à petits coefficients, les formes intermédiaires peuvent être denses avec d'assez grands coefficients, de sorte que même si l'algorithme est polynomial le calcul peut devenir prohibitivement coûteux.
Une façon de contourner cette difficulté est d'échelonner modulo différents p et de reconstituer le résultat par lemme chinois + récupération de rationnel (ça marche sauf si on tombe sur un p qui divise tous les pivots possibles d'une colonne, et alors on détecte le problème).
Une autre approche est de passer par les p-adiques, cf http://sagemath.org/doc/reference/matrices/sage/matrix/matrix_rational_dense.html (mais je ne sais pas comment ils font exactement).
Ruxor (2014-06-24T17:48:43Z)
@DH: Le carré d'un entier impair est toujours congru à 1 modulo 8, et inversement, dans les entiers 2-adiques, les nombres congrus à 1 modulo 8 sont exactement les carrés des entiers 2-adiques impairs. Ma fonction va renvoyer la racine carrée 2-adique approximée à 2^63 près pour ces nombres-là. Donc elle termine pour les nombres congrus à 1 modulo 8. Inversement, si a est impair, la première boucle termine toujours en calculant son inverse 2-adique à 2^64 près, et la seconde ne peut terminer que si x est (2-adiquement très proche d')une racine carrée de a. Donc la fonction termine sur un entier impair ssi il est congru à 1 modulo 8. (J'avoue, en revanche, ne pas avoir une idée très clair de la dynamique lorsque ce n'est pas le cas.)
DH (2014-06-24T08:48:07Z)
Tiens, j'ai recopié ton code en C99 pour voir ce que ça donne.
1. sur un entier pair : la fonction renvoie 1 (normal, elle n'est pas faite pour)
2. sur un entier impair qui est un carré parfait : la fonction renvoie bien la racine carrée "naturelle"
3. sur un entier impair non premier :
3.a. soit la fonction renvoie un nombre très grand (je suppose que ça a du sens dans les 2-adiques)
3.b. soit ça freeze
sans que je n'aie pu deviner pour quels nombres impairs non carrés on a 3a ou 3b.
C'est le comportement attendu ?
Arnaud Spiwack (2014-06-24T05:05:08Z)
Pour le truc de Vuillemin. Ça utilise l'addition (et la soustraction) plus ou moins tout le temps et la multiplication par 2 tout autant (toutes les deux rendent compte d'un bit d'état d'ailleurs). La multiplication par autre chose qu'une puissance de deux semble beaucoup plus rare.
Il semblerait que ça ait servi en pratique pour de vrai et tout. Ce qui est tout de même un bon début.
Ruxor (2014-06-23T12:27:15Z)
@Arnaud Spiwack: Ah oui, c'est un truc de Vuillemin. Mais ça ne m'a pas l'air super convaincant : si j'ai bien compris, en gros, il utilise les 2-adiques comme des suites binaires infinies et utilise à peine l'addition, et quasiment pas la multiplication, naturelle aux 2-adiques. Sinon, j'ai trouvé <URL: http://perso.ens-lyon.fr/damien.stehle/downloads/recbinary.pdf > (qui est expliqué de façon plus concise et peut-être plus claire par DJB dans <URL: http://permalink.gmane.org/gmane.comp.djb.bignum.devel/13 >) où Stehlé et Zimmermann montrent comment calculer le PGCD de deux entiers de façon efficace (aussi efficace que l'algorithme de Knuth-Schönhage mais beaucoup plus simple et compréhensible) par une technique de division 2-adique.
@Nick: Il doit être un microchouïa plus efficace sur 64-bits (en tout cas, il l'est asymptotiquement : le nombre de chiffres exacts dans une méthode de Newton double — en gros — à chaque itération, alors qu'avec une recherche par dichotomie il croît de 1 à chaque itération). Mais il faudrait benchmarker pour savoir vraiment. Après, il faut voir que le choix « dichotomie ou Newton » est orthogonal au choix « méthode réelle (i.e., par poids fort) ou 2-adique (i.e., par poids faible) » : je propose une méthode de Newton 2-adique, tu demandes à comparer à une dichotomie réelle, mais on peut aussi faire une dichotomie 2-adique ou une méthode de Newton réelle.
Nick (2014-06-23T07:48:37Z)
Sachant que pour 64 bits, il faut au plus 32 élévations au carré pour trouver une racine carrée, comment ton algorithme se compare-t-il à cette borne?
--
Nick pour la question bateau.
Arnaud Spiwack (2014-06-23T05:40:52Z)
La principale (l'unique?) utilisation sérieuse des entiers diadiques que je connaisse, en informatique, c'est la sémantique des circuits : le n-ième chiffre d'un diadique représente la valeur du fil au temps n. L'avantage de ce point de vu c'est que l'opération de décalage (l'intrusion du temps dans les circuits) est juste une multiplication par deux. Alors on peut décrire le comportement d'un circuit comme des expressions de l'arithmétique.
Ça sert vraiment, mais ce n'est pas parfait. D'abord la multiplication de deux diadiques est un circuit infini (il semblerait que ce circuit est utile quand-même parce qu'on peut le tronquer à une précision choisie et obtenir un circuit fini). Ensuite, on est forcé de mélanger l'arithmétique avec des opérations « bit à bit » dont les relations algébriques avec le reste des opérations ne sont pas aussi plaisantes qu'on rêverait.