Home

 Logithèque

TI95

Calcul de la racine carrée de 5 en multiprécision


Code

10000 STO A 11 STO B STO D 60 STO F 2 PAU STO IND D

INC D 23606 PAU STO IND D INC D 79774 PAU STO IND D

3 STO C

LBL PP RCL B STO D RCL F STO G RCL C STO J

LBL CA RCL IND D x^2 STO IND G INC G 0 STO IND G

INC G INC D DSZ J GTL CA CLR RCL B STO D RCL C - 1 = STO J RCL F STO G

LBL C1 RCL D + 1 = STO E RCL J STO K INC G RCL G STO H INC G

LBL C2 2 * RCL IND D * RCL IND E = ST+ IND H INC E

INC H DSZ K GTL C2 INC D DSZ J GTL C1

RCL C * 2 - 1 = STO J + RCL F = STO G 0 STO I

LBL NO RCL I + RCL IND G = / RCL A = - INT STO I

= * RCL A = STO IND G INV INC G DSZ J GTL NO

RCL F + RCL C - 1 = STO G 3 STO J CLR STO I

LBL SO RCL A ST* I - RCL IND G - 1 = ST+ I INC G

DSZ J GTL SO RCL B + RCL C = STO D RCL I /

44721359549 * RCL A = INT PAU STO IND D INC C GTL PP

(288 octets)

Le listing est présenté tel que lisible sur la TI95, sauf les labels qui sont soulignés.

Ce programme fonctionne au mieux avec une partition d'au moins 157 mémoires.


Mode d'emploi

Lancer le programme.

Les décimales de la racine carrée de 5 s'affichent, 5 par 5.

Arrêter le programme par [BRK]. Cette version ne permet pas plus de 49 tranches (voir plus loin).


Mathématiques à l'oeuvre

Bon booooonnn essayons de faire simple.

On veut trouver une suite d'entiers pn tels que pn/Z^n soit la meilleure approximation possible de racine de 5 par défaut. Ceci revient à dire que pn est le plus grand entier tel que : pn < Z^n * rac(5)

(l'égalité est impossible bien sûr si Z est entier).

Si on prend pour Z une puissance de 10, par exemple 10^u, alors pn est un nombre de n*u+1 chiffres. En gros, on obtient des tranches successives de racine de 5, de largeur u.

Posons la suite des tranches an, qui vérifie : pn+1 = Z.pn + an+1

Alors on obtient que : (Z.pn + an+1)^2 < 5.Z^(2.n+2)

Finalement après quelques manipulations on conclut que an est le plus grand entier vérifiant :

Or si on est à une étape où pn est grand devant Z, alors le terme entre parenthèses peut être remplacé par 1 sans problèmes (l'envie de vous le montrer me manque). Le numérateur du terme de droite, lui, ne peut certainement pas être simplifié.

Une astuce supplémentaire est que, puisque an est de l'ordre de Z tandis que pn est bien plus grand, on peut dans la division présente dans l'expression de droite se contenter des premiers chiffres de pn. On n'a donc pas besoin de diviser en multiprécision.


Fonctionnement du programme

Voici l'utilisation des mémoires :

A  Z  0
B reg base P   1
C  nb reg P  2
D  ptr P N°1  3
E   ptr P N°2  4
F  reg base buffer  5
G ptr buffer n°1   6
H ptr buffer n°2   7
I q, retenue, a   8
J  compteur n°1  9
K compteur n°2   10
   (libre)  11

On utilise deux variables en multiprécision : P (qui contient pn), et un "buffer" (qui contient le numérateur du terme de droite, voir ci-dessus). Pour adresser P on conserve son adresse de base, sa longueur, et on utilise deux pointeurs pour le parcourir : B, C, D et E respectivement. Pour le "buffer" le principe est le même mais la longueur est implicitement le double de celle de P, on utilise les variables F, G et H.

Les nombres en multiprécision sont stockées par tranches de 5 chiffres seulement car on a besoin parfois de faire des produits entre ces valeurs sans pouvoir accepter une perte de précision. Toutes les troncatures des tranches sont effectuées avec une constante valant 10^5 stockée dans A (c'est Z en fait).

On a besoin parfois de boucles doublement imbriquées, d'où l'utilisation de deux compteurs, I et J.

Enfin, l'espace à partir de la mémoire 011 est disponible. Dans le listing ci-dessus, on alloue P à partir du registre 011, et le buffer à partir de la mémoire 060 (voir première ligne du listing). En conséquence, on ne peut calculer plus de 49 tranches sans collision, ce qui limite le nombre de décimales calculables à 240 (la première tranche est utilisée par la partie entière, qui vaut 2). On comprend d'ailleurs maintenant pourquoi il faut une partition permettant au moins 157 mémoires. Pour en obtenir plus, il suffit de modifier la seconde constante citées ci-dessus selon la partition disponible. La TI95 de base disposant de 7200 octets, et le programme en occupant 288, on peut imaginer disposer de 863 mémoires, donc de placer "P" au registre 011 et le "buffer" au registre 298, permettant de calculer 1430 décimales. Le temps de calcul étant polynomial mais pas linéaire, risquerait d'être prohibitif.

Cette limite à 1430 décimales, pas fameuse, démontre à elle seule que ce programme n'est pas terrible...

Pour que l'algorithme fonctionne bien, on remarque que l'on stocke directement les deux premières tranches et qu'à la dernière ligne du listing on divise par 44721359549 qui est int(2*Z^2*rac(5)) (voir partie mathématique).