[python] chiffre par chiffre, nombre d'or phi illimité.

karlun · 20-08-2010 15:01:53

Salut,

Nanti que de mes pauvres +-*/, et autres bricoles, je me suis lancé dans la programmation.
J'ai parcouru un peu le livre " Apprendre à programmer avec Python" (<p.100) .

Je me suis proposé de créer un programme capable d'énumérer, chiffres après chiffres, le nombre d'or.
L'idée est de partir de phi= [tex]\frac{1+\sqrt{5}}{2}[/tex].
Je transpose en programme la méthode de résolution à la main de l'extraction de racine 5 (augmentée d'une unité) et simultanément la division par 2.

Pffffff! Y a des fois où j'ai ramé.
Mais, obstiné ;-), amusé surtout, j'y suis arrivé.

Bien sûr il y aura beaucoup de remarques à faire:
temps de calcul
raccourcis de consignes,
Etc. Etc.

(J'ai laissé des #print ... ça et là qui m'ont aidé à analysé et résoudre les erreurs.)

# -*- coding: cp1252 -*-

from math import*

    #=============================================

    #  extraction à la main de phi (1.618033....)

    #=============================================

def extract_phi(w=10):

    "extraction à la main de phi (x-1=nbre de chiffre)"

    #======================================

 # 1)     extraction à la main de racine de 5

    #======================================

    def racinePlus(v,r,t):

        "place dans les listes ra,re,tot les résultats calculés" 

        ra.append(v)

        re.append(r)

        tot.append(t)

        return ra

    def racineMoins(m):

        "enlève des listes le dernier élément"

        del ra[m]

        del re[m]

        del tot[m]

        return ra

    def travRacine(ra,re,tot,z,t):

        ra[z-2]=ra[z-2]-1

        re[z-2]=re[z-2]+40

        racineMoins(z-1)

        return ra,re,tot,z          

    #première étape: amorce de l'extraction de racine 5

    v=int(sqrt(5.))

    r=10

    t,p,x=0,0,w

    ra=[]

    re=[]

    tot=[]

    racinePlus(v,r,t)

    z=len(ra)

    #Et c'est parti pour des tours.

    while(len (ra)<w):

         #calculs intérieurs => caculer t à partir des listes existantes

        p+=1

        a,b,t,=0,0,0,

        c=(z+1)/2

        if(((z)%2)):                # =>z+1 est paire

            while(a<(c-1)):

                t=t+2*(ra[c-1-a]*ra[c+b])

                a=a+1

                b=b+1

        else:                       #=> z+1 est impaire

            while(a<(c-1)):

                t=t+2*(ra[c-1-a]*ra[c+1+b])

                a=a+1

                b=b+1

            t=t+ra[c]**2

        #comparaison t doit être < que le reste: si non on dégraisse

        for i in xrange(ra[z-1],0,-1):

            if(t>re[z-1]): 

                ra[z-1]=ra[z-1]-1

                re[z-1]=re[z-1]+40

                tot[z-1]= tot[z-1]

                t=t-4

                #dégraissage accompli

                #je laisse les print d'analyse pour les amateurs

                #if (p>x-2):

                    #print "*",ra[z-5],ra[z-4],ra[z-3],ra[z-2],ra[z-1]

                    #print re[z-5],re[z-4],re[z-3],re[z-2],re[z-1],"    t:",t

                    #print tot[z-5],tot[z-4],tot[z-3],tot[z-2],tot[z-1]

                    #print"==================================================="

        if(ra[z-1]<=0):

            if(t>=re[z-1]):

                i,j=0,1

                while(i<j):

                    t=tot[z-1]-4                   #pour conserver t après travRacine 

                    travRacine(ra,re,tot,z,t)

                    z=len(ra)

                    if(ra[z-1]==0):                 #cas où 1-1=0

                        if(t>re[z-1]):

                            j=j+1

                        else:

                            j=j

                    else:

                        if(ra[z-1]==-1):            #cas où 0-1=-1

                            j=j+1

                        else:

                            j=j

                    #if (p>x-2):

                        #print "**",ra[z-5],ra[z-4],ra[z-3],ra[z-2],ra[z-1]

                        #print re[z-5],re[z-4],re[z-3],re[z-2],re[z-1],"    t:",t

                        #print tot[z-5],tot[z-4],tot[z-3],tot[z-2],tot[z-1]

                        #print"==================================================="

                    i+=1

        #if (p>x-2):

            #print "fin cycle (analyse)"

        #ajout de la nouvelle racine (ra,re,tot)

        v=(re[z-1]-t)/4

        if(v>9):

            v=9

        r=(re[z-1]-(4*v+t))*10

        racinePlus(v,r,t)

        z=len(ra)

        #if (p>x-2):

            #print "***",v,r,t

    #print "nbre de cycles:   ",p

    #print "nombre de termes:   ",len(ra)

    #print ra

    #========================================

  # 2) division à la main de (racine de 5)+1

    #========================================

    # (1+racine5)/2

    i=0

    ra[i]+=1

    quot,reste=[],[]

    def ajoutListe(q,r):

        quot.append(q)

        reste.append(r)

    q=ra[i]/2

    r=(ra[i]-q*2)*10+ra[i+1]

    i=1

    ajoutListe(q,r)

    while((len(quot)+1)<w):

        q=r/2

        r=(reste[i-1]-q*2)*10+ra[i+1]

        ajoutListe(q,r)

        i+=1

    print quot

Vos remarques, commentaires, conseils sont les bienvenus.

A+-*/

yoshi · 20-08-2010 17:43:24

Re,

Je vais regarder ça...
Déjà, 1ere question

from math import*

    #=============================================

    #  extraction à la main de phi (1.618033....)

    #=============================================

def extract_phi(w=10):

    "extraction à la main de phi (x-1=nbre de chiffre)"

    #======================================

 # 1)     extraction à la main de racine de 5

    #======================================

    def racinePlus(v,r,t):

        "place dans les listes ra,re,tot les résultats calculés" 

        ra.append(v)

        re.append(r)

        tot.append(t)

        return ra

Pourquoi cette indentation ? Tu as défini une fonction à l'intérieur d'une fonction ?
Si oui, je ne savais même pas que c'était possible. Je vais consulter la doc officielle (en anglais).
Hmmm... Si c'est une classe, ça ne va pas.

En tout état de cause, je vais réaligner tout ça, et relancer parce que là tel quel, ça ne fonctionne pas.
J'ai enregistré ton prog via un copier/coller sous le nom de karlun_phi.py.
Quand je le lance depuis l'IDLE de Python, il me rend la main tout de suite, sans message d'erreur et ne m'affiche... rien !

Donc, à revoir pour moi...
D'autre part, je ne vois aucun bout de programme principal qui appelle la ou les fonctions...

@+

karlun · 20-08-2010 18:10:04

Salut,

Dans mes script je balise mes exercices comme des def.

Je lance comme une def à partir de >>>:
==============restart==============
>>>
>>> extract_phi(w=10)
après avoir, au préalable, runner le programme (F5). (question d'assimiler à prompt les changements .)

Modifier l'indentation revient à, peut-être, tout foutre en l'air sauf si ce n'est que l'indentation liée à la def extract_phi(w=10): qui lance le programme au prompt.

Les programmes principaux sont à une indentation de plus que def extract_phi(w=10):

petit exemple: les 999 premiers chiffres de phi:

>>> extract_phi(w=1000)

[1, 6, 1, 8, 0, 3, 3, 9, 8, 8, 7, 4, 9, 8, 9, 4, 8, 4, 8, 2, 0, 4, 5, 8, 6, 8, 3, 4, 3, 6, 5, 6, 3, 8, 1, 1, 7, 7, 2, 0, 3, 0, 9, 1, 7, 9, 8, 0, 5, 7, 6, 2, 8, 6, 2, 1, 3, 5, 4, 4, 8, 6, 2, 2, 7, 0, 5, 2, 6, 0, 4, 6, 2, 8, 1, 8, 9, 0, 2, 4, 4, 9, 7, 0, 7, 2, 0, 7, 2, 0, 4, 1, 8, 9, 3, 9, 1, 1, 3, 7, 4, 8, 4, 7, 5, 4, 0, 8, 8, 0, 7, 5, 3, 8, 6, 8, 9, 1, 7, 5, 2, 1, 2, 6, 6, 3, 3, 8, 6, 2, 2, 2, 3, 5, 3, 6, 9, 3, 1, 7, 9, 3, 1, 8, 0, 0, 6, 0, 7, 6, 6, 7, 2, 6, 3, 5, 4, 4, 3, 3, 3, 8, 9, 0, 8, 6, 5, 9, 5, 9, 3, 9, 5, 8, 2, 9, 0, 5, 6, 3, 8, 3, 2, 2, 6, 6, 1, 3, 1, 9, 9, 2, 8, 2, 9, 0, 2, 6, 7, 8, 8, 0, 6, 7, 5, 2, 0, 8, 7, 6, 6, 8, 9, 2, 5, 0, 1, 7, 1, 1, 6, 9, 6, 2, 0, 7, 0, 3, 2, 2, 2, 1, 0, 4, 3, 2, 1, 6, 2, 6, 9, 5, 4, 8, 6, 2, 6, 2, 9, 6, 3, 1, 3, 6, 1, 4, 4, 3, 8, 1, 4, 9, 7, 5, 8, 7, 0, 1, 2, 2, 0, 3, 4, 0, 8, 0, 5, 8, 8, 7, 9, 5, 4, 4, 5, 4, 7, 4, 9, 2, 4, 6, 1, 8, 5, 6, 9, 5, 3, 6, 4, 8, 6, 4, 4, 4, 9, 2, 4, 1, 0, 4, 4, 3, 2, 0, 7, 7, 1, 3, 4, 4, 9, 4, 7, 0, 4, 9, 5, 6, 5, 8, 4, 6, 7, 8, 8, 5, 0, 9, 8, 7, 4, 3, 3, 9, 4, 4, 2, 2, 1, 2, 5, 4, 4, 8, 7, 7, 0, 6, 6, 4, 7, 8, 0, 9, 1, 5, 8, 8, 4, 6, 0, 7, 4, 9, 9, 8, 8, 7, 1, 2, 4, 0, 0, 7, 6, 5, 2, 1, 7, 0, 5, 7, 5, 1, 7, 9, 7, 8, 8, 3, 4, 1, 6, 6, 2, 5, 6, 2, 4, 9, 4, 0, 7, 5, 8, 9, 0, 6, 9, 7, 0, 4, 0, 0, 0, 2, 8, 1, 2, 1, 0, 4, 2, 7, 6, 2, 1, 7, 7, 1, 1, 1, 7, 7, 7, 8, 0, 5, 3, 1, 5, 3, 1, 7, 1, 4, 1, 0, 1, 1, 7, 0, 4, 6, 6, 6, 5, 9, 9, 1, 4, 6, 6, 9, 7, 9, 8, 7, 3, 1, 7, 6, 1, 3, 5, 6, 0, 0, 6, 7, 0, 8, 7, 4, 8, 0, 7, 1, 0, 1, 3, 1, 7, 9, 5, 2, 3, 6, 8, 9, 4, 2, 7, 5, 2, 1, 9, 4, 8, 4, 3, 5, 3, 0, 5, 6, 7, 8, 3, 0, 0, 2, 2, 8, 7, 8, 5, 6, 9, 9, 7, 8, 2, 9, 7, 7, 8, 3, 4, 7, 8, 4, 5, 8, 7, 8, 2, 2, 8, 9, 1, 1, 0, 9, 7, 6, 2, 5, 0, 0, 3, 0, 2, 6, 9, 6, 1, 5, 6, 1, 7, 0, 0, 2, 5, 0, 4, 6, 4, 3, 3, 8, 2, 4, 3, 7, 7, 6, 4, 8, 6, 1, 0, 2, 8, 3, 8, 3, 1, 2, 6, 8, 3, 3, 0, 3, 7, 2, 4, 2, 9, 2, 6, 7, 5, 2, 6, 3, 1, 1, 6, 5, 3, 3, 9, 2, 4, 7, 3, 1, 6, 7, 1, 1, 1, 2, 1, 1, 5, 8, 8, 1, 8, 6, 3, 8, 5, 1, 3, 3, 1, 6, 2, 0, 3, 8, 4, 0, 0, 5, 2, 2, 2, 1, 6, 5, 7, 9, 1, 2, 8, 6, 6, 7, 5, 2, 9, 4, 6, 5, 4, 9, 0, 6, 8, 1, 1, 3, 1, 7, 1, 5, 9, 9, 3, 4, 3, 2, 3, 5, 9, 7, 3, 4, 9, 4, 9, 8, 5, 0, 9, 0, 4, 0, 9, 4, 7, 6, 2, 1, 3, 2, 2, 2, 9, 8, 1, 0, 1, 7, 2, 6, 1, 0, 7, 0, 5, 9, 6, 1, 1, 6, 4, 5, 6, 2, 9, 9, 0, 9, 8, 1, 6, 2, 9, 0, 5, 5, 5, 2, 0, 8, 5, 2, 4, 7, 9, 0, 3, 5, 2, 4, 0, 6, 0, 2, 0, 1, 7, 2, 7, 9, 9, 7, 4, 7, 1, 7, 5, 3, 4, 2, 7, 7, 7, 5, 9, 2, 7, 7, 8, 6, 2, 5, 6, 1, 9, 4, 3, 2, 0, 8, 2, 7, 5, 0, 5, 1, 3, 1, 2, 1, 8, 1, 5, 6, 2, 8, 5, 5, 1, 2, 2, 2, 4, 8, 0, 9, 3, 9, 4, 7, 1, 2, 3, 4, 1, 4, 5, 1, 7, 0, 2, 2, 3, 7, 3, 5, 8, 0, 5, 7, 7, 2, 7, 8, 6, 1, 6, 0, 0, 8, 6, 8, 8, 3, 8, 2, 9, 5, 2, 3, 0, 4, 5, 9, 2, 6, 4, 7, 8, 7, 8, 0, 1, 7, 8, 8, 9, 9, 2, 1, 9, 9, 0, 2, 7, 0, 7, 7, 6, 9, 0, 3, 8, 9, 5, 3, 2, 1, 9, 6, 8, 1, 9, 8, 6, 1, 5, 1, 4, 3, 7, 8, 0, 3, 1, 4, 9, 9, 7, 4, 1, 1, 0, 6, 9, 2, 6, 0, 8, 8, 6, 7, 4, 2, 9, 6, 2, 2, 6, 7, 5, 7, 5, 6, 0, 5, 2, 3, 1, 7, 2, 7, 7, 7, 5, 2, 0, 3, 5, 3, 6, 1, 4, 1, 8]

>>>

A+-*/

Dernière modification par karlun (20-08-2010 18:33:11)

yoshi · 20-08-2010 19:40:10

Re,

Ok, ça marche...
Encore fallait-il savoir que tu avais prévu ce fonctionnement...

Je t'en donne un autre plus "rationnel" (encore que aller mettre karlun_phi.py là bas où je vais le mettre, ça ne l'est pas trop...) : j'enregistre karlun_phi.py dans le sous dossier Lib (ligne modifiée --> def extract_phi(w): )

Puis je crée un petit programme "principal" :

# -*- coding: cp1252 -*-

from math import*

from karlun_phi import extract_phi

extract_phi(100)

que j'enregistre sous le nom de phi.py.

Puis c'est lui que je lance via F5...

Bon, alors je vais tâcher de pondre ma version... Patience !

@+

karlun · 20-08-2010 22:22:34

'soir,

Un peu présomptueux sans doute....

Karlun a écrit :

Je transpose en programme la méthode de résolution à la main de l'extraction de racine 5 (augmentée d'une unité) et simultanément la division par 2.

Là, un peu dans les nuages, j'émerge et me rends compte que, tel le cheval de retour à l'écurie, j'ai foncé vers la solution; le simultanément était mon idée mais il en est tout autre dans le prog. transmis. J'ai opéré la division après avoir calculé la racine; sans doute, tenir compte de cette remarque fera gagner du temps.

A+-*/

yoshi · 20-08-2010 23:34:44

Bonsoir,

Si par simultanément, tu entends : à chaque chiffre calculé, sur 1000 par ex, tu effectues la division par 2, alors tu as 1000 divisions au lieu d'une...
Pas très rentable...

Je te propose une version dont je vais chercher à améliorer la vitesse (mais je pense qu'il y aura très peu à "gratter") :

#!/usr/bin/env python

# -*- coding: cp1252 -*-

# Version 1

from __future__ import division

def rac5(nbz):

    rac=2

    for j in xrange(2,nbz,2):

        n=5*10**j

        rac=rac*10       

        if (rac+5)*(rac+5)>n:

            deb,fin=0,5

        else:

            deb,fin=5,10

        while (rac+deb)**2<=n:

            deb+=1

        rac+=deb-1

    return rac

# Précision attendue en nombre de chiffres après la virgule

prc=1000

# *****************************

nbz=2*prc

rac="3"+str(rac5(nbz))[-prc+1:]

racpl=int(rac)//2

phi=str(racpl)[0]+'.'+str(racpl)[-prc+1:]

print "phi =",phi

Etant donnée une précision souhaitée prc, :
j'extrais la racine carrée entière de 5*10**(2*prc)
Je la transforme en chaîne de caractères et je remplace le 2 initial par 3.
Je divise cette chaîne retransformée en entier par 2.
Je retransforme en chaîne et j'insère le point décimal après le 1.
J'affiche le résultat...
Je vais de 2 zéros en 2 zéros : 500, 50000, 5000000, 500000000...
Et à chaque tour de boucle, je multiplie l'ancienne racine par 10 et je teste le nombre d'unités nécessaires à cette racine, pour que le résultat élevé au carré devienne supérieur à 500, 50000, 5000000, 500000000...
Après quoi, j'ajoute réellement à la racine le nombre d'unités diminué de 1.

@+

karlun · 21-08-2010 09:22:08

Bonjour,

Merci pour ta version; elle est beaucoup plus légère, limpide et 1000 fois (*20?) plus rapide.

Par simultanément j'entendais que la transposition de la "division à la main" en programme serait insérée de manière à être exécutée et le résultat placé dans la liste dès que un chiffre de la racine tombe .
C'est ce que je n'ai pas fait trop pressé d'arriver au but. J'ai repris chaque chiffre de la racine et l'ai traité par la "division à la main" => perte de rendement.

En outre, j'ai placé un compteur de cycle interne... C'est que ça travaillait là dedans.
Pour 999 chiffres de phi, 26519 cycles...

Je m'étais astreint à transposer en programme la méthode de résolution à la main de l'extraction de racine 5 et simultanément de la division par 2, histoire de me familiariser avec les conditionnelles (y a des fois où pfff! j'étais perdu... alors j'effaçais et je reprenais.) alors, forcément, le programme ne pouvait être rapide.

A la différence de ton programme, Yoshi, je pars de listes vides (sauf quand le cheval sent l'écurie) qui s'incrémentent d'une valeur (et augmente leur longueur d'une unité) à chaque chiffre calculé (comme la méthode à la main).

Merci.

A+-*/

yoshi · 21-08-2010 09:42:00

Re,

Alors, ça m'est venu cette nuit, voilà une version plus "resserrée" et 20% (!) plus rapide (1.1 s contre 1.4 s pou 2000 décimales)
...

#!/usr/bin/env python

# -*- coding: cp1252 -*-

# Version 2

from __future__ import division

def rac5(prc):

    n,rac=5,2

    for j in xrange(prc):

        n*=100

        rac*=10       

        if (rac+5)*(rac+5)>n:

            deb,fin=0,5

        else:

            deb,fin=5,10

        while (rac+deb)**2<=n:

            deb+=1

        rac+=deb-1

    return rac

prc=2000

racpl=(rac5(prc)+10**prc)//2

phi=str(racpl)[0]+'.'+str(racpl)[-prc:]

print "phi =",phi

"Comme à la main" : j'avais fait ça, il y a 20 ans avec un CPC 6128 pour quelqu'un qui voulait avoir le nombre d'or (déjà) avec 100 décimales...
Hélas, je ne pouvais avoir cet ordi que 8 chiffres décimaux significatifs et 12 avec une calculette...
j'avais donc stocké chaque chiffre dans un tableau (j'en manipulais 3 ), et j'avais récrit la multiplication, l'addition, la soustraction...
Résultat des courses : 100 décimales --> 1 h !!!

Avec le prog ci-dessus, je calcule 2000 décimales en 1.1 s...
Les temps ont changé...

Bon, je vais voir pour réinventer la roue et refaire ce que j'ai fait, il y a 20 ans...

@+

Dernière modification par yoshi (21-08-2010 13:45:12)

karlun · 21-08-2010 13:00:46

r'lut,

J'ai épluché ta dernière mouture:

Un calcul de départ est réalisé en posant n,rac=5,2 bien vu.
(2 est la plus grande racine entière <5.)

J'imagine que (nbz) pourrait devenir (prc).

For et while font tout le boulot ensuite...
(J'ai essayé de placer un compteur (p+=1) dans while(): mais un message TypeError: can only concatenate tuple (not "long") to tuple.)
ensuite tu divises un nombre de 2000 chiffres augmenté d'un autre de 2000 chiffres en deux.
(Heureusement que Python à les capacités pour faire cela)

Pour ce qui est de str() j'vai aller voir car j'connais pas encore; mais ça semble ne faire qu'ajouter une virgule.

A+-*/

Dernière modification par karlun (21-08-2010 15:03:54)

yoshi · 21-08-2010 13:44:14

Ave Karlum gratium plenum,

Le script qui tue...
J'ai renoncé aux listes au profit des entiers très, très, très long...
Avec le précédent 12 s (hors affichage) pour calculer 5000 décimales..
Maintenant 23/100e pour ces 5000 décimales et 0,875 s pour 10000 !!!

#!/usr/bin/env python

# -*- coding: cp1252 -*-

# Version 3

from __future__ import division

from time import time

def rac5(prc):

    n,reste,rac,md,finbcl=5,5,0,0,prc+1

    for j in xrange(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'

T'avais raison !
La bonne vieille méthode inconnue des jeunes (<40 ans) profs de maths (plus dans les programmes officiels) d'extraction des racines via papier + crayon est de loin supérieure...
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 vigule que je gère à la fin):

5             | 2236

100           |------------------------------

01600         | 2 * 2 = 4

 027100       |------------------

  0030400     | 42 *2 = 84

    03604     | -----------------

              | 443 *3 =1329

              |-----------------

              | 4466 * 6 = 26796

Les multiplicandes sont respectivement donc de 0 (à l'initialisation), 40, 440 ,4460...

@+

PS
Au moment de poster, je vois une tienne réponse...
Donc qq infos à propos de ce matin et des chaînes...
Le str(5), par exemple) renvoie 5 qui n'est plus un nombre mais une chaîne de caractères (un string en anglais, nerosson y verrait immédiatement autre chose)
Avec 2236 (prc =3) j'ajoute 100 et je divise par 2, oui (J'avais revérifié que Python pouvait le faire).
Après j'en fais une chaîne qui se manipule comme une liste, à cette différence près que pour insérer une sous-chaîne, il faut couper avant, concaténer la sous-chaîne et ajouter la suite de la chaîne de départ...
Je ne peux pas non plus remplacer directement un élément précis d'une chaîne...

Donc, je suis obligé de sortir ma paire de ciseaux...
Avec nb=1618
str(nb) --> renvoie "1618"
Je coupe :
nb[0] --> "1"
J'ajoute le '.'
nb[0]+'.' --> "1."
J'ajoute la suite :
nb[0]+'.' +nb[-3:] --> phi = '1'+'.'+'618" --> '1.618'

Manipulation chaîne :
nb[1:3] = '61', nb[0:3]='161' ou nb[2:4]= '18'
Et nb[-2:] = '18' aussi plus subtil : -2 donc négatif, on part donc de la fin et on recule de 2, puis on va jusqu'à la fin = la machine se dém... toute seule, inutile de connaître le nombre de caractères...

Quant à nb[:-2], sans surprise, on part du début et on va jusqu'à la fin-2, et c'est encore python qui gère tout seul l'indice de fin de liste...

J'imagine que (nbz) pourrait devenir (prc).

Erreur dans la 2e version que j'ai corrigée : ce n'est pas def rac5(nbz): mais def rac5(prc): faut que j'arrête de modifier les variables à la dernière minute...
La première version dhier soir utilisait nbz (nombre de zéros) : j'utilisais un script péché chez un membre de developpez.net...
Pour une précision de 100 chiffres, il fallait chercher la racine 5*10**200...
Ce matin, je m'étais rendu compte que compter de 2 à 200 et de 2 en 2, pouvait se résumer à compter de 1 à 100, en multipliant le nombre 5 par 100 à chaque tour et non plus le fabriquer à chaque tour par 5*10**j...

Le compteur dans while (prog n° 2) y est c'est deb --> deb+=1
En fait je teste avec 5, si avec 5 le résultat du produit dépasse 500...0, je pars de deb = 0, sinon de deb = 5..
Et tant que je ne dépasse pas la valeur, j'incrémente de 1...
En sortie de boucle while, il faut que je décrémente le deb de 1: il est forcément trop grand...

karlun · 21-08-2010 15:02:44

r'lut,

Karlun a écrit :

(J'ai essayé de placer un compteur (p+=1) dans while(): mais un message TypeError: can only concatenate tuple (not "long") to tuple.)

Ce p ajouté, je voulais pouvoir le sortir de def rac5() et le lire afin de connaître le nombre d'opération effectuée dans while. (je m'emmêle les pinceaux avec les return x,y )

J'examine ta nouvelle version.

A+-*/

yoshi · 21-08-2010 15:18:58

Re,

Ce p ajouté, je voulais pouvoir le sortir de def rac5() et le lire afin de connaître le nombre d'opération effectuée dans while. (je m'emmêle les pinceaux avec les return x,y )

Le nombre d'opérations à chaque tour ? Maximum 5 : deb --> soit 0, 1, 2, 3 ou 4, soit 5, 6, 7, 8 ou 9...
Le nombre d'opérations total en sortie du def ?
Alors modifier le def comme ça :

def rac5(prc):

    n,rac=5,2

    p=0                        # Initialisation du compteur

    for j in xrange(prc):

        n*=100

        rac*=10       

        if (rac+5)*(rac+5)>n:

            deb,fin=0,5

        else:

            deb,fin=5,10

        while (rac+deb)**2<=n:

            p+=1              # Mise en place du compteur

            deb+=1

        rac+=deb-1

    print 'Le compteur :',p   # Affichage du compteur

    return rac

Au pire, tu définissais ton p comme une variable globale, et tu récupérais sa valeur en tapant p au prompt revenu.
@+

yoshi · 21-08-2010 20:01:00

Re,

Pour ceux que ça intéresse, il y a un bon moment déjà, j'avais explicité la méthode de calcul d'une racine carrée avec crayon+papier. Là revoici :

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 2 ?
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 * 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 * (la mutiplication) puis le multiplicateur x 'le même nombre). Ci-dessous j'ai mis des points
On cherche donc en fait le nombre x tel que 4x * x <= 152 (avec 4x 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 x ?
Réponse : c'est 3.
En effet, 44 x 4 = 176 trop grand, alors que 43 x 3 = 129.
On complète : 43 * 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 |23
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 x tel que 46x* x ? <= 2325, avec 46x 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".

La méthode implémentée dans ma version 3 du calcul du nombre d'or, n'est donc autre que cet algorithme, qui se révèle d'une rapidité déconcertante...

@+

karlun · 22-08-2010 10:43:31

Bonjour,

Impressionnante ta version 3, quelle rapidité.

La méthode de calcul de la racine carrée de 5 (avec crayon+papier) que j'ai utilisée diffère un peu.; elle ne prend qu'un chiffre à la fois ("chiffre par chiffre") et analyse si son "corps intérieur" ne dépasse pas le reste (c'est finalement une gestion des restes...)
Mais lorsque ça dépasse il faut que la machine puisse faire marche arrière et sans se tromper => travail sur les éléments des listes; on décrémentes, on delete,... mais une autre difficulté apparaîtt lorsqu'il s'agit des passages de dizaines à rebour car il y a plusieurs cas de figures.
Arrivé à 100 chiffres de phi je croyais être arrivé au bout de mes peines... que nenni! Poussant la machine à 200 chiffres je trouve un '-1'
pffffffff! allez! courage..
Et puis bingo... j'ai réinventé l'eau chaude ;-)

Merci pour les bonnes leçons de programmation.

A+-*/

yoshi · 22-08-2010 11:42:08

Re,

La méthode de calcul de la racine carrée de 5 (avec crayon+papier) que j'ai utilisée diffère un peu.; elle ne prend qu'un chiffre à la fois ("chiffre par chiffre") et analyse si son "corps intérieur" ne dépasse pas le reste (c'est finalement une gestion des restes...)

Ah bin, voilà une méthode que je connaissais pas...
Tu peux l'expliquer en détail ? Ça correspond à ça : http://serge.bertorello.free.fr/math/racine.html ?

L'algorithme de mes versions 1 et 2, n'est rien d'autre que le "bête" jeu : c'est plus, c'est moins !
A chaque étape, je cherche le nombre a, tel que a²<=b<(a+1)²..
Dès que j'ai trouvé a+1, j'en déduis a et je repars pour un tour.
La version 0 (bêta comme disent les informaticiens), m'obligeait à chercher la racine de 5 suivi de 2n zéros, afin que la racine obtenue ait n chiffres significatifs, et de rentrer 5*10**2n d'entrée de jeu... : la méthode calcul de la racine utilisée a été trouvée sur le net...
Puis je me suis dit que ce n'était pas nécessaire, donc que j'allais calculer ce nombre impressionnant au fur et à mesure avec 5*10**j et une boucle de 2 à nbz (nb de zéros par pas de 2)...
La nuit portant conseil, le lendemain, j'ai pensé que reconstruire 5*10**j à chaque fois en partant de 5 était trop gourmand : il suffisait de faire une boucle de 1 à prc (précision) de partir de nb=5, et de multiplier ce nombre par 100, puis le résultat par 100 au tour suivant, j'ai pensé que ça devait être plus rapide : effectivement gain de 20 %.
Dans la version 3, l'algorithme utilisé est radicalement différent et incroyablement plus rapide puisque je divise les temps par un facteur 50...

La méthode calcul crayon/papier que j'ai décrite est celle que j'ai apprise lorsque, il y a bien longtemps, j'étais en 4e au Lycée : ça faisait partie des savoirs exigibles...
Maintenant, avec l'avènement des calculettes et des ordis personnels, pffuitt... dispaus les calculs de racines carrées à la main...
A noter, que lorsque je repense aux difficultés sans noms que beaucoup d'élèves, même en 4e, aujourd'hui ont à faire une simple division avec des décimaux, je me dis qu'enseigner ça : ce doit être un véritable tour de force...

Pour tes difficultés de programmation, rassure-toi, j'ai aussi galéré une bonne heure pour ma version 3, jusqu'à ce que décide de décrire les calculs en langage presque courant (et les faire en parallèle) avec stylo et papier...

Courage !!!

@+

karlun · 22-08-2010 18:45:04

'soir,

Yoshi a écrit :

Ah bin, voilà une méthode que je connaissais pas...
Tu peux l'expliquer en détail ? Ça correspond à ça : http://serge.bertorello.free.fr/math/racine.html ?

Cette méthode est déduite d'une manière originale de multiplier tirée d'un petit fascicule dû à notre ami M. H.-E. CLAES dont j'ai déjà abordé et présenté une autre trouvaille.

J'ajoute donc cette méthode de multiplication à ce sujet (http://www.bibmath.net/forums/viewtopic.php?id=3733).

Voici une manière de calculer une racine carrée en s'appuyant sur cette méthode.

A+-*/

Dernière modification par karlun (23-08-2010 21:41:42)

yoshi · 22-08-2010 19:24:32

Re,

Cette méthode est déduite de ... dis-tu.
C'est toi qui l'a déduite, ou ce M. Henri Claes l'avait-il explicitée ,

Si c'est toi, alors chapeau bas ! Je ne crois pas que j'aurais pu avoir cette idée...

Je pense avoir compris. Je vais réfléchir à ça, mais pour moi, dans ton programme tu gigotes beaucoup trop. Et je reviens sur ce que j'ai dit : je ne suis plus aussi sûr, qu'avec un code bien optimisé cette méthode soit aussi lente que ça...

Bravo jeune-homme ! C'est joli et même probablement plus plus rapide que la multiplication du même tonneau...

@+

PS

J'ai déjà un souci...
J'essaie 3 :

3 | 1
- 1 (1*1) |----------------
------------
2 0 Et là si, j'ai bien compris tu fais 1 x
\ /
/ \
1 x

Mon problème : 2x = 20 d'où x = 10, ça ne devrait pas arriver...
Qu'est-ce que j'ai raté ?
Bon, après cet appel, j'y retourne...

PS2
10 induit un reste de 0 et un nombre négatif après, donc j'essaie ton "marche arrière toute"...
Mais en lisant attentivement, je vois que tu écris :

marche arrière toute : 4-=3 et le reste 20 devient 20 - 2*2*3 = 16 (soit -4 constante)

Qu'est-ce que tu veux dire par là ? Parce que 2*2*3 = 12 et 20 - 12 = 8...
Vous avez dit bizarre ?

Sinon, j'ai une idée générale de la façon dont je vais procéder:
Une première boucle :
for j in xrange(1,prc):
somme =0
Puis une deuxième où je somme les produits 2 à 2 (les "chiffres étant stockés dans une liste L
for i in xrange(1,j):
somme+=L[i]*L[j-i+1]

Avec j = 4
L[1] L[2] L[3] L[4]
L[1] L[2] L[3] L[4]
Pour i de 1 à 4 on associe 1 et 4-1+1 = 4, 2 et 4-2+1 = 3, 3. et 4-3+1 =2 et 4 et 4-4+1 = 1 j pair...

Et si j impair ? On s'en fout, ça croise quand même comme il faut :
Avec j = 5
L[1] L[2] L[3] L[4] L[5]
L[1] L[2] L[3] L[4] L[5]
L[1] L[2] L[3] L[4]
Pour i de 1 à 5 on associe 1 et 5+1-1 = 5, 2 et 5-2+1 = 4, 3 et 5-3+1 = 3, 4 et 5-4+1 = 2 et 5 et 5-5 + 1 =1
C'est à l'intérieur de cette somme que je place 1 en L[j, puis que je somme pour trouver ensuite ton reste.
Le bon chiffre trouvé, je remplace 1 dans L[j] par celui-ci, je multiplie la racine provisoire par 10 et je lui ajoute la valeur rangée dans L[j]...
Voilà, c'est sur cette base que je vais bosser quand j'aurais compris où est l'erreur dans mon exemple avec racioe de 3...

Dernière modification par yoshi (22-08-2010 20:43:05)

yoshi · 23-08-2010 21:01:31

Re,

J'ai bien avancé...
Mais, je bute sur une erreur à partir de la 4e décimale, preuve que ce que fais Aux 2e et 3e décimales donnent un résultat exact, ce n'est qu'un hasard...
Si je levais cette indétermination alors mon programme fonctionnerait...

Donc tu arrives à un reste de 2 en faisant 10-8. ok.
Tu multiplies ce reste par 10. Tu obtiens reste = 20. C'est clair.

Là, tu te trouves avec :
2 |2| x
2 |2| x
---
|
so = 4
Tu cherches x tel que 2x + 2x + 4 <= 20, soit 4x + 4 <= 20. Dorénavant ce 4 on le retrouvera toujours devant x, c'est une constante... Je pose c = 4
D'accord.
Tu trouves x <= (20 - so )//c soit x = 4...
Et tu calcules reste = reste-(c*x+so) avec reste = 20, c = 4, x = 4 et so = 4. donc le reste obtenu est 0.
Toujours d'accord.
La liste des restes des restes est donc [10,20,0]
La lite des chiffres de la racine est donc [2,2,4]
Si moi, je suis d'accord avec tes calculs, toi par contre, tu ne vois pas de faute de méthode ?
Et tu pars à la chasse de la 3e décimale.
2 | 2 4| x
2 | 2 4| x
-------
|
so = 16

Tu as donc 4x + 16 <= 0, soit x = (0 - 20)//4, x = (reste- so)//c = -4
Négatif...
Donc tu reprends le x précédent, soit +4, et tu lui enlèves 1, donc x = 3.
Tu corriges la liste des chiffres de la racine en [2,2,3].
Mais, là ça dérape...
Comment exactement dans ce cas (et dans le suivant quand tu retrouves un reste de 0 avec x =7), comment calcules-tu le nouveau reste correspondant [10,20,..] ?
Je vois que tu soustrais 16 à 20. Ce 16 est-il so ? ou 4x avec l'ancien x ?

Mettons que je mets 40 --> [10,20,40]
Je recalcule :

2 | 2 3| x
2 | 2 3| x
-------
|
so = 12

Là, 4x + 12 <= 40, soit x = (40 - 12)//4 = 7... ça, j'ai trouvé...
Tu calcules le reste 40 - (4*7 + 12) = 0, j'ai trouvé aussi...
racines [2,2,3,7]
Restes [10,20,40,0]

2 | 2 3 7| x
2 | 2 3 7| x
-------
|
so = 37

Là, 4x + 37 <= 0, soit x = (0 - 37)//4 --> x = -9 négatif... ok.
Tu corriges 7 - 1 = 6... ok
Et maintenant tu écris : reste change... voui... Comment ? Par quoi remplaces-tu 0 ? comment le calcules-tu ?
Nanti de ces réponses (mais aussi du pb de racine de 3 : comment passer de x = 10 que j'ai trouvé, à x = 7 ?), je serai en mesure de boucler assez vite une version qui marche...
Après, ce sera la phase d'optimisation...

@+

karlun · 23-08-2010 21:31:47

R'venu du boulot, 'soir,

Bien vu Yoshi... encore une erreur.
fallait bien entendu remettre 3 dans le calcul du reste "t-1' et j'ai oublier d'écrire "+(2*2)" mais le résultat est bon... Mea culpa. (histoire de cheval et d'écurie).

Pour ce qui est de la méthode:

ayant visualisé la méthode (ces tracés de flèches de droite à gauche), j'ai de suite imaginé son rebours sans plus.
Le calcul, suivant cette méthode, d'un carré symétrisait aussi les données (horizontalement)...
Delà, ça découlait de source... (non?)

Notre amis, M. CLAES à évidemment abordé le carré d'un nombre et sa racine aussi suivant sa méthode... mais je n'en sais pas plus sur elle que sur d'autres méthodes (comme celle que tu nous a exposé).

Là haut, sur la montagne, j'ai essayer sur mon calepin quelque calcul de racine et ...

Encore une fois, dans le thème proposé, il s'agissait pour moi de me familiariser avec les "conditionnelles" en programmation (une fois assurée "ma "" méthode").

Yoshi a écrit :

3 | 1
- 1 (1*1) |----------------
------------
2 0 Et là si, j'ai bien compris tu fais 1 x
\ /
/ \
1 x
Mon problème : 2x = 20 d'où x = 10, ça ne devrait pas arriver...
Qu'est-ce que j'ai raté ?

Bof!, me connaissant un peu, tu ne t'étonneras pas que j'accepte de poursuivre avec 10.

alors:

3 | 1 "10"
- 1 (1*1) |----------------
------------
2 0 Et là si, j'ai bien compris tu fais 1 x
2 0 \ /
---------- / \
0 0 1 x

Alors 1 "10" xx

1 "10" xx
et donc 2*x+10*10<0 2x< -100 !!!négatif!!! alors rebours. reste=
3 | 1 9
- 1 (1*1) |----------------
------------
2 0 Et là si, j'ai bien compris tu fais 1 x
1 8 \ /
---------- / \
2 0 1 x
Alors 1 9 xx

1 9 xx
et donc 2*x+9*9<20 2x< -61 !!!négatif!!! alors rebours. reste=

3 | 1 8
- 1 (1*1) |----------------
------------
2 0 Et là si, j'ai bien compris tu fais 1 x
1 6 \ /
---------- / \
4 0 1 x
Alors 1 8 x

1 8 x
et donc 2*x+8*8<40 2x< --24 !!!négatif!!! alors rebours. reste=

3 | 1 7
- 1 (1*1) |----------------
------------
2 0 Et là si, j'ai bien compris tu fais 1 x
1 4 \ /
---------- / \
6 0 (table de 20) 1 x
Alors 1 7 xx

1 7 xx
et donc 2*x+7*7<60 2x< 11 alors 11/2=5,......reste= 59

3 | 1 7 5
- 1 (1*1) |----------------
------------
2 0 1 7 5 x
1 4
---------- 1 7 5 x
6 0
5 9
---------
10 mais 2*35 (calculs internes) trop grand rapport au reste => etc. etc.

La méthode que j'ai appliquée consiste à diviser en 2 la longueur de la chaine et selon qu'elle est paire ou pas, il faudra pas ou il faudra ajouter le carré du central à la somme du double produit des termes (pris 2à2) depuis le centre jusqu'aux 2 (bords-1)... gesticulation j'en conviens.

Je suis lent et je vois ton dernier post à l'instant d'envoyer le mien.
Je te l'envoie sec il illustre quelques questions que tu poses, je pense.

A+-*/

PS. j'ai corrigé l'exposé de la méthode. ouf!

Dernière modification par karlun (23-08-2010 21:43:16)

yoshi · 24-08-2010 12:02:00

Re,

Merci M'sieu...
Oui, tu as éclairci pas mal de points...
Voilà donc une version avec calcul de racine façon Henri Claes.

Hélas, c'est très lent...
19 s chez moi pour 100 décimales...

#!/usr/bin/env python

# -*- coding: cp1252 -*-

from __future__ import division

from math import sqrt

from time import time

def somme(L,j):

    so=0

    for i in xrange(1,j):

        so+=L[i]*L[j-i]

    return so

def rac5(prc):

    L,rst,rac=[],0,0

    x=int(sqrt(5))

    rac=x                   

    rst=(5-rac**2)*10       

    L.append(x)             

    # 1ere décimale

    c=2*x

    x=rst//c                

    rst=10*(rst%c )               

    L.append(x)             

    rac=rac*10+x               

    # Calculs en boucle à partir de la 2e décimale

    for j in xrange(2,prc):

        so=somme(L,j)

        if so>rst:

            # Rectifications pour j-1

            while so>rst:

                x=L[j-1]-1

                L[j-1]=x

                rst+= c*10

                rac-=1

                so=somme(L,j)

            # Mises à jour pour la bonne valeur de x

        x=(rst-so)//c

        rst=10*(rst-(so+c*x))

        rac=rac*10+x

        L.append(x)

    return rac

tp_d=time()        

# ********************

# Nombre de décimales

prc=100

# ********************

racpl=(rac5(prc+2)+10**(prc+1))//2

phi=str(racpl)[0]+'.'+str(racpl)[1:prc]

tp_a=time()

print "phi=",phi

print

print tp_a-tp_d,'s'

Au lieu de tester x<0, ce qui se produit si cx+so <= rst soit si so > rst !!
Donc, au lieu de calculer x pour voir s'il est négatif, je compare so et rst...

selon qu'elle est paire ou pas, il faudra pas ou il faudra ajouter le carré du central à la somme du double produit des termes (pris 2à2) depuis le centre jusqu'aux 2 (bords-1)

La parité ? Aucune importance ! ...
C'est le rôle de ma fonction somme de faire le calcul sans se soucier de pair/impair, automatiquement ...

Maintenant, je vais essayer d'optimiser pour gagner du temps, parce que je suis très déçu...

@+

PS.

Bon, alors je viens de remarquer ça :

|a b c x |.. a étant la première décimale
|a b c x | ..
mon calcul de so donne 2ax+2bc
Diminuons x de 1 :
so1 = 2a(x-1)+2bc = 2ax-2a+2bc = (2ax+2bc)-2a = so-2a
A chaque fois que je diminue x de 1, le so du cœur diminue de de 2a...
Donc dans le prog
- Je pose cc=2*x, x étant la 2e décimale.
- A chaque rectification de x (pour cause de x négatif), au lieu de recalculer so via la fonction somme, je fais so-=cc.
L'intérêt est que avec j=100 (par ex) j'évite100 multiplications et additions par tour de rectification...
Donc nouvelle version :

#!/usr/bin/env python

# -*- coding: cp1252 -*-

from __future__ import division

from math import sqrt

from time import time

def somme(L,j):

    so=0

    for i in xrange(1,j):

        so+=L[i]*L[j-i]

    return so

def rac5(prc):

    L,rst,rac=[],0,0

    x=int(sqrt(5))

    rac=x                   

    rst=(5-rac**2)*10       

    L.append(x)

    c=2*x

    # 1ere décimale

    x=rst//c

    cc=2*x

    rst=10*(rst%c )               

    L.append(x)             

    rac=rac*10+x               

    # Calculs en boucle à partir de la 2e décimale

    for j in xrange(2,prc):

        so=somme(L,j)

        if so>rst:

            # Rectifications pour j-1

            while so>rst:

                x=L[j-1]-1

                L[j-1]=x

                rst+= c*10

                rac-=1

                so-=cc

        x=(rst-so)//c

        # Mises à jour pour la bonne valeur de x

        rst=10*(rst-(so+c*x))

        rac=rac*10+x

        L.append(x)

    return rac

tp_d=time()        

# ********************

# Nombre de décimales

prc=100

# ********************

racpl=(rac5(prc+2)+10**(prc+1))//2

phi=str(racpl)[0]+'.'+str(racpl)[1:prc]

tp_a=time()

print "phi=",phi

print

print tp_a-tp_d,'s'

Rien que ces 2 modifs fait que pour 100 décimales, je descends de 19,125 s à 0,594 s....
Encore trop lent (13.25 s pour 120 décimales, mais 46 min 34 s pour 150 !!!), mais le gain relatif est énorme : le temps est divisé par 30 !

Dernière modification par yoshi (24-08-2010 13:00:02)

karlun · 24-08-2010 20:08:22

Salut,

Ah oui, ça c'est lent de chez lent... ;-)

J'ai pompé tes codes "temps " et les ai insérés dans mon programme du début ...

Pour 498 décimales : 0.904 s.
Pour 1000 décimales : 5.648 s.
Pour 2000 décimales : 45.56 s. avec 102338 cycles internes.

Les raccourcis (logiques) que tu as fait, j'en ai également abusés.
Par ex.: si x>9 alors 9 et puis aussi directement ajouter au reste 40 à chaque débordement et -4 au calcul interne.

N'as tu pas rencontré de difficultés avec les rebours à la dizaine inférieure?

Courage. ;-)

A+-*/

yoshi · 24-08-2010 20:33:30

Re,

Bon, j'ai une idée d'amélioration, je l'ai mise en pratique, mais ça plante division par zéro !
J'ai trouvé une astuce qui devrait permettre en cas de "somme intérieure" supérieure au reste de ne pas utiliser une boucle while, mais de trouver tout de suite le bon chiffre et le bon reste : j'arrive jusqu'à 2236, après crac !
Mais pour savoir, si je gagne du temps, j'ai besoin que mon astuce fonctionne...
Hélas, ce n'est pas le cas pour l'instant.
Je m'en vais donc reprendre un papier et un crayon et refaire manuellement le déroulement des opérations pour trouver l'erreur...

Bon, il n'empêche que ma v3 avec l'algo que j'ai appris en 4e, est encore loin d'être détrôné :
Pour 2000 décimales tu m'annonces 45.56 s..., ma version v3 me donne 5/100e s par excès (0.046999.. s) ça va être dur de faire mieux.

J'y retourne.

@+

karlun · 24-08-2010 20:45:22

R'lut,

2 2 3 6 et puis zéro...

Ah ça j'ai que trop connu...

Sacrés zéros.

Ta version 3? un bijou.

A moi d'en pondre un autre?
Faut que j'y pense.

A+-*/

yoshi · 25-08-2010 11:36:02

Re,

Ah, mais !
Ca y est j'ai corrigé...
Et la vitesse attendue est au rendez-vous : 0.65 s pour 2000 décimales...
J'ai aussi rectifié le calcul de la somme : je me suis aperçu qu'il fallait gagner là-dedans aussi.
Tu avais encore vu juste, je dois faire le distinguo pair/impair : j'ai donc calculé la somme de la moitié des produits que je multiplie par 2 ensuite et si le nombre de chiffres est impair je rajoute le carré central.
Sur une précision de 2000 chiffres, je dois économiser plus de 1 000 000 d'opérations...
Hélas, ça me génère un autre souci...

Si je compare cette dernière version avec ma version 3, les décimales divergent après la 1856e décimale !
Hmmmm...
Y a une version qui a tort... Mais laquelle ?
Après vérification, c'est cette dernière version...
Qu'est-ce qui peut bien se passer à la 1857e décimale pour qu'elle soit fausse ?
Là, ça m'en bouche un coin...
Un cas particulier doit se produire, mais quoi ????

Y a là de quoi phosphorer...

Outre la somme, l'astuce est celle-ci :
Dans le cas où la somme est supérieure au reste, si j'augmente le reste de 40 et que dans le même temps, je diminue la somme de 4, je gagne 44. Il me faut donc savoir combien de fois je dois renouveler l'opération : c'est le rôle du coefficient n.
Exemple (farfelu) : reste = 10, somme = 95, 1+(95-10)//44 =2
Vérification : reste = 10+40*2 = 90 et 95-4*2 = 87...
Je diminue la racine calculée avec le "mauvais chiffre" de n, je diminue le mauvais chiffre de n (fin de la phase rectification), et je reprends les calculs sur les "bonnes" bases avant de m'attaquer au j suivant _- i.e. le j suivant esti le n° de la décimale suivante - (fin de la phase des mises à jour).

Pt'êt bin qu'un cas où x > 9 fout la pagaille s'il est assez grand : c'est le problème de la méthode : elle accepte - provisoirement certes - le cas x >9... Et alors avec ma façon d'écrire la racine, c'est gênant...

A voir.
Je te tiens au courant.

@+

PS
Après vérification, ça se produit bien à cause de ça... Et même avant, sans incidence sur la racine !!!
Diantre fichtre, bigre !

Dernière modification par yoshi (25-08-2010 12:00:15)

yoshi · 25-08-2010 21:40:50

RE,

Bon, j'ai trouvé pourquoi, mais je ne sais pas le corriger encore...
Ma méthode informatique est conforme maintenant à ce que je fais à la main et j'ai un souci.
Peux-tu me donner la liste de tes 10 premiers restes, pour la racine de 5, s'il te plaît...
C'est là que git le hic !
Je trouve bien pour la racine 223606 puis maintenant 10, mais ma méthode ne le corrige qu'en 8 alors que ce devrait être un 7.

Merci d'avance.
J'arrête pour ce soir.
Je reprends demain avec un cerveau reposé...

@+

Forum de mathématiques - Bibm@th.net

#1 20-08-2010 15:01:53

[python] chiffre par chiffre, nombre d'or phi illimité.

#2 20-08-2010 17:43:24

Re : [python] chiffre par chiffre, nombre d'or phi illimité.

#3 20-08-2010 18:10:04

Re : [python] chiffre par chiffre, nombre d'or phi illimité.

#4 20-08-2010 19:40:10

Re : [python] chiffre par chiffre, nombre d'or phi illimité.

#5 20-08-2010 22:22:34

Re : [python] chiffre par chiffre, nombre d'or phi illimité.

#6 20-08-2010 23:34:44

Re : [python] chiffre par chiffre, nombre d'or phi illimité.

#7 21-08-2010 09:22:08

Re : [python] chiffre par chiffre, nombre d'or phi illimité.

#8 21-08-2010 09:42:00

Re : [python] chiffre par chiffre, nombre d'or phi illimité.

#9 21-08-2010 13:00:46

Re : [python] chiffre par chiffre, nombre d'or phi illimité.

#10 21-08-2010 13:44:14

Re : [python] chiffre par chiffre, nombre d'or phi illimité.

#11 21-08-2010 15:02:44

Re : [python] chiffre par chiffre, nombre d'or phi illimité.

#12 21-08-2010 15:18:58

Re : [python] chiffre par chiffre, nombre d'or phi illimité.

#13 21-08-2010 20:01:00

Re : [python] chiffre par chiffre, nombre d'or phi illimité.

#14 22-08-2010 10:43:31

Re : [python] chiffre par chiffre, nombre d'or phi illimité.

#15 22-08-2010 11:42:08

Re : [python] chiffre par chiffre, nombre d'or phi illimité.

#16 22-08-2010 18:45:04

Re : [python] chiffre par chiffre, nombre d'or phi illimité.

#17 22-08-2010 19:24:32

Re : [python] chiffre par chiffre, nombre d'or phi illimité.

#18 23-08-2010 21:01:31

Re : [python] chiffre par chiffre, nombre d'or phi illimité.

#19 23-08-2010 21:31:47

Re : [python] chiffre par chiffre, nombre d'or phi illimité.

#20 24-08-2010 12:02:00

Re : [python] chiffre par chiffre, nombre d'or phi illimité.

#21 24-08-2010 20:08:22

Re : [python] chiffre par chiffre, nombre d'or phi illimité.

#22 24-08-2010 20:33:30

Re : [python] chiffre par chiffre, nombre d'or phi illimité.

#23 24-08-2010 20:45:22

Re : [python] chiffre par chiffre, nombre d'or phi illimité.

#24 25-08-2010 11:36:02

Re : [python] chiffre par chiffre, nombre d'or phi illimité.

#25 25-08-2010 21:40:50

Re : [python] chiffre par chiffre, nombre d'or phi illimité.

Réponse rapide

Pied de page des forums