Forum de mathématiques - Bibm@th.net

renéb

Membre

Inscription : 15-01-2023

Messages : 61

Racine carrée, extraction à la main. inédite?

Bonjour,

Voici la mise en code de l'algorithme utile à extraire une racine, chiffre par chiffre soumise à votre sagacité.
L’exemple choisi portera sur phi le nombre d’or.        $\frac{1+\sqrt5}{2}$
Extraire la racine de 5 et simultanément, de suite (sur le même chiffre) opérer sa division par 2 non sans avoir omis au préalable d’incrémenter d’une unité la valeur entière de la racine.

A bientôt

RB

#!/usr/bin/env python3
from math import *
from time import *

t2=time()
nb1=5             # nb    nombre dont on extrait la racine.
div=2             #diviseur du nombre en construction
h=14              #nbre de décimales demandées
solution,o=0,0
r=(nb1)**0.5
nb,nb2=nb1,str(nb1)
sol,phi=[],[]
print("nombre dont on extrait la racine:",nb)
print("résultat calculatrice racine de 5 =",r)
print("nbre de décimales:",h)
s=len(nb2)
##x=int(input("dernier carré entier < les 2 1er chiffres de nb * 10*le nombre de chifrre de nb -2/2   "))
##x=int(x*10**((s-2)/2))
##print(x)

#appel à calculer le "racine" pour poursuivre l'algorythme?

if s>1:
    x=int(int(nb1/(10**(s-2)))**0.5)*(10**(int((s-2)/2)))
else:
    x=int(nb1**0.5) 
print("x=",x)
sol.append(x)
sol[0]+=1            #ajout de 1 au résultat. nombre d'or= (1+racine 5)/2
u=sol[0]
u=int(u/div)
phi.append(u)
rdiv=(u%div)
solution=solution*10**o+x
for t in range(h):
    o,nb=len(sol),nb1
    solution= solution*10
    x=int(((nb*10**(2*o))-(solution**2))/(2*solution+1))
    sol.append(x)
    solution=solution+x
    phir=int((rdiv*10+x)/div)
    rdiv=(rdiv*10+x)%div
    phi.append(phir)
print("phi=",phi)
sol.insert(1,',')
t1=time()-t2
print()
print(solution,"(manque la virgule)")
print("durée:",t1,"secondes")

#50000 décimales en  360.816890001297 secondes.  1876 lignes de chiffres

## phi =1,618 033 988 749 894 848 204 586 834 365 638 117 720 309
## 179 805 762 862 135 448 622 705 260 462 818 902 449 707 207 204 ...

Dernière modification par renéb (18-01-2023 20:51:26)

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 385

Re : Racine carrée, extraction à la main. inédite?

Bonjour,

La seule méthode d'extraction à la main d'une racine carrée et celle qui figurait au programme de 4e et que ne connaissent plus les nouveaux profs de Maths : ça date de, ch'sais pas - si je vais oser le dire - ... 1959. Bin voui, j'ai quelques kilomètres au compteur.
La revoilà (je l'ai déjà postée il y a quelques années) :

Cherchons la racine de 55225.
On pose :
5 52 25 |
            |-----
            |
comme une division, mais sans  diviseur : on sépare par tranches de 2 chiffres en partant des unités et on commence tout à gauche.
Question n° 1: quel est le plus grand carré parfait contenu dans 5 ?
Réponse : c'est 4 dont la racine carrée est 2.
Et on complète :
* On place 2 dans la zone "diviseur" qui devient la zone racine carrée,
* Au dessous de la racine (en zone "quotient"), on écrit le produit,
* Dans la zone reste, on écrit le reste 5 - 2 x 2 = 1
5 52 25  |2
1           |---------------------
             |2 x 2 = 4
             |----------------
             |

On abaisse les deux chiffres suivants et on double la racine provisoire que l'on pose à droite chez les "quotients"...
On met un point à côté (pour un nombre à 1 chiffre x à trouver) de 4, puis on écrit x puis le multiplicateur $\cdot$  (le même nombre à 1 chiffre). Ci-dessous j'ai mis les points.
On cherche donc  en fait le nombre x  tel que $\overline{4\cdot} \times \cdot \leqslant 152$  (avec $\overline{4\cdot}$ compris entre 40 et 49) :

5 52 25  |2
1 52       |-----
             |2 x 2 = 4
             |----------------
             |4. x . =

Question n°2. Quel est donc ce nombre "point" ?
Réponse : c'est 3.
En effet, 44 x 4 = 176 trop grand, alors que 43 x 3 = 129.
On complète : 43 x 3 = 129, on met met donc 3 à la suite du 2 (zone racine) et le reste 159 - 129 = 23 en dessous de 152 :

5 52 25  |2
1 52       |-----
   23      |2 x 2 = 4
             |----------------
             |43 x 3 = 129

On abaisse les deux chiffres suivants (ou on met une virgule et abaisse deux zéros, si on est déjà arrivé aux unités), on double la racine et on recommence :
5 52 25  |23
1 52       |-----
   23 25  |2 x 2 = 4
             |----------------
             |43 x 3 = 129
             |-----------------
             |46. x . =
Là encore on veut $\cdot$ tel que $\overline{46\cdot} \times \cdot  \leqslant 2325$, avec $\overline{46\cdot}$ compris entre 460 et 469.
Ici, c'est 5... :

5 52 25  |235
1 52       |-----
   23 25  |2 x 2 = 4
     0 00  |----------------
             |43 x 3 = 129
             |-----------------
             |465 x 5 =  2325

Donc [tex]\sqrt{55225}\,=\,235[/tex]

Mais les nombres deviennent vite très très longs et les calculs très fastidieux et "impossibles".

J'avais Pythonisé cette méthode :

#!/usr/bin/env python
# -*- coding: UTF-8 -*-
# Version 3

from time import time

def rac5(prc):
    n,reste,rac,md,finbcl=5,5,0,0,prc+1
    for j in range(finbcl):
        md=20*rac
        if (md+5)*5>reste:
            i=0
        else:
            i=5
        while (md+i)*i<=reste:
            i+=1
        i-=1
        rac=rac*10+i
        md+=i
        reste=(reste-md*i)*100
    return rac

tp_d=time()
prc=5000
racpl=(rac5(prc)+10**prc)//2
phi=str(racpl)[0]+'.'+str(racpl)[-prc:]
tp_a=time()
print ("phi =",phi)
print (tp_a-tp_d,'s')
 

La bonne vieille méthode inconnue des jeunes profs...
Je démarre avec le nombre 5, un reste de 5, un multiplicande (md) de 0 un indice de fin de boucle supérieur de 1 à la précision.

Et je fabrique ça (sans la virgule que je gère à la fin) :

 5             | 2236
 100           |------------------------------
 01600         | 2 x 2 = 4
  027100       |------------------
   0030400     | 42 x 2 = 84
     03604     | -----------------
               | 443 x 3 =1329
               |-----------------
               | 4466 x 6 = 26796

C'est très rapide, mais la méthode de Héron d'Alexandrie (adaptable pour le calcul de la racine cubique) l'est encore plus, malgré l'appel à l'incontournable module decimal qui fait les calcul avec des fractions continuées (mais ralentit sensiblement ces calculs) :

#!/usr/bin/env python
# coding: utf-8 -*-

from time import time
from decimal import Decimal as D,getcontext
getcontext().prec=50001

def rac(n):
    u,u0,i=D(2),D(1),0
    while not u0==u:
        u0=u
        u=(u*u+n)/(u*D(2))
        i+=1
    return u,i

debut=time()
radicande =5
u,i=rac(radicande)
print (u)
print("Nombre d'Itérations :", i)
print("effectuées en :",time()-debut,"s")
 

Sortie sans l'affichage de la racine. Dans l'IDLE de Python, configuré à 100 caractères par ligne : 501 lignes...

Nombre d'Itérations : 17
effectuées en : 0.94 s

J'ai aussi adapté cette méthode au calcul de la racine carrée entière d'un nombre entier naturel :

#!/usr/bin/env python
# coding: utf-8 -*-

from math import sqrt
from time import time

def racine_entière(n):
    """ Inspiré de la méthode de Heron """  
    n_str=str(n)
    ln_str=len(n_str)
    if ln_str<12:    
        return int(sqrt(n))  
    ln_utile=(ln_str-10)//2
    n_coupe =n//10**(ln_str-10)
    uu=int(sqrt(n_coupe))
    u= int(uu*10**ln_utile)
    u0=1
    while not u0==u:
        u0=u
        u=(u**2+n)//(2*u)
    return u
   
début =time()
n=2345678998765432102568712345678997845612321321458974232569874315601451123456789113245678987654321325
re = racine_entière(n)
print ('Racine entière = ',re)
print('Durée :', time()-début),'s'

J'ai choisi un nombre de 100 chiffres et j'obtiens en sortie :

Racine entière = 48432210343586757495857120903238447995010125310952
Durée : 0.012000799179077148 s

Vérification :

re**2 :
2345678998765432102568712345678997845612321321458879211337912676818137016804502614404401874691146304
print (re**2<n<(re+1)**2)
True

Ma machine n'est pas une bête de course, mais j'ai 16 Go de RAM, un processeur AMD FX 6300 six 3,5 GHz 6 cœurs de plus de 3 ans...

Maintenant je vais essayer d'éplucher ta méthode pour voir si elle diffère de la mienne à la main...

@+