Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

#1 21-08-2019 10:40:44

Cédrix
Membre
Inscription : 15-08-2019
Messages : 77

Méthode par balayage avec Python

Bonjour,
dans un livre de Seconde, je trouve la méthode de balayage suivante pour déterminer une valeur approchée de la racine carrée de 2 avec EduPython.

from lycee import *
def approx_sqrt2(n):
    l=1
    for i in range(n+1):
        while l**2<2:
            l=l+10**-n
    return round(l-10**-n,n)

J'ai plusieurs questions, étant novice en PYTHON :
1) la ligne "for i in range(n+1):" est à supprimer, non ? puisqu'il y a une boucle TANT QUE.
D'ailleurs, je ne comprends pas pourquoi l'algorithme fonctionne quand même et qu'on obtient bien :
approx_sqrt2(3)=1,414 et approx_sqrt2(6)=1,414213 par exemple.

Bref, est-il bien plus correct d'écrire l'algorithme suivant :

from lycee import *
def approx_sqrt2(n):
    l=1
    while l**2<2:
            l=l+10**-n
    return round(l-10**-n,n)

2) Pourquoi ne peut-on écrire :

from lycee import *
def approx_sqrt2(n):
    l=1
    while l**2<2:
            l=l+10**-n
    return l-10**-n

En effet, les valeurs de l se font bien de 0,001 en 0,001 pour n=3 par exemple alors pourquoi obtient-on un nombre qui comporte plus de 3 décimales avec cet algorithme :
approx_sqrt(3)=1.4139999999999544

Merci d'avance !
C.

Hors ligne

#2 21-08-2019 13:09:15

freddy
Membre chevronné
Lieu : Paris
Inscription : 27-03-2009
Messages : 7 457

Re : Méthode par balayage avec Python

Salut,

sur Python, je ne suis pas encore compétent, mais sur les racines carrées de 3 et de 6, je suis certain qu'elles sont distinctes de la racine carré de 2 qui est proche de 1,414 !!! Fais attention à ce que tu écris :-)

PS vu, Ok et merci (c'était la précision ...) Lu trop vite, pardon !
je m'enduis la tête de cendre et baisse les yeux, toute honte bue :-) !

Dernière modification par freddy (21-08-2019 16:41:59)


De la considération des obstacles vient l’échec, des moyens, la réussite.

Hors ligne

#3 21-08-2019 15:16:04

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 907

Re : Méthode par balayage avec Python

B'jour,

@freddy : tu as trop survolé l'ami...

les racines carrées de 3 et de 6

3 et 6 c'était la précision...
@Cédrix
J'ai mis un moment avant de comprendre : la boucle for ne sert à rien. La preuve, on s'en passe très bien...
Elle est censée augmenter la précision de la racine...
Si n=6, par exemple
la boucle commence à i=0, la précision sera de $10^0$, l'unité
et là on calcule racine carrée de 2 à 1 unité près dans la boucle while...
Nouvelle itération x =1
précision $10^{-1}=0,1$
Et on rentre dans la boucle while censée fournir cette fois la racine à 0,1 près...
Sauf que...
Toute petite gaffe... De l'auteur ? en recopiant ?
Si je regarde la ligne
l=l+10**-n
cette ligne se fiche pas mal de la valeur de i...
Pour que ce soit cohérent,
la boucle for devrait être  : for i in range(n+1):
et surtout la ligne incriminée devrait être :
l=l+10**-i

Je te propose une autre approche : calcul par dichotomie (en principe expliqué en 2nde)...
je passe en paramètre à la fonction la variable n dont la valeur sera celle de la précision souhaitée
Je sais que $1<\sqrt 2<2$, je pose a=1 et b=2 au départ.
Donc je vais travailler dans l'intervalle $]a\,;\,b[$ que je vais "rétrécir" à chaque itération.
Puis je choisis comme condition de sortie de boucle, que b-a soit inférieur ou égal à $10^{-n}$
Donc la ligne d'entrée en boucle est :
Tant que b-a est strictement supérieur à $10^{-n}$
Puis
je calcule la moyenne arithmétique m=(a+b)/2
et je teste :
si $m^2>2$ c'est que m est trop grand, donc on rétrécit $]a\,;\,b[$  en posant que b=m
sinon
si $m^2<=2$ c'est que m est trop petit, donc on rétrécit $]a\,;\,b[$  en posant que a=m
et on revient vérifier b-a, calculer m etc..

C'est le jeu du : c'est +, c'est -...

def Racde2(n):
    a,b=1,2
    while b-a>10**-n:        
        m=(a+b)/2
        if m**2>2:
            b=m
        else:
            a=m
    return round(m,n)

           
Voilà ce que me donne n=15 :
>> print(Racde2(15))
1.414213562373095

Le mieux, c'est encore la méthode de Héron d'Alexandrie : couplée au module decimal de Python, tu peux obtenir 20000 décimales en 15 itérations :

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

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

N=5  # Recherche de la racine carrée de 5
u=D(2)
for i in range(15):
    u=(u**2+D(N))/(u*D(2))

print (u)

getcontext().prec est renseigné par le nombre de décimales voulu...
Hors module decimal, en standard, Python t'offre seulement 15/16 décimales...
J'ai 20000 décimales en moins d'une seconde

As-tu trouvé réponses à tes questions ?

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#4 21-08-2019 19:35:04

Cédrix
Membre
Inscription : 15-08-2019
Messages : 77

Re : Méthode par balayage avec Python

Merci pour les explications et les prolongements.
Par contre, pourriez-vous répondre également à ma question 2) à savoir pourquoi y a-t-il plus de 3 décimales alors que si on effectuait l'algorithme à la main il n'y en aurait que 3.
C.

Hors ligne

#5 21-08-2019 20:30:17

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 907

Re : Méthode par balayage avec Python

Re,

En principe, ma description du fonctionnement attendu et de l'erreur devrait expliquer ça.
Je n'ai pas vérifié (je contrôle ça demain matin) : mais si on reproduit à la main, la même gaffe que dans l'algorithme, il n'y aucune raison que le résultat soit différent à l'ordi...
Ce serait inquiétant : comment trouver une erreur dans ce cas ?
Avec n=5, sur ma machine j'avais 5 décimales assez vite...
Par contre, dès la demande de 6 décimales, ça prenait un temps fou ce qui m'a déterminé à faire des essais en ayant ajouté des "mouchards" pour pouvoir suivre le déroulement des calculs...
J'étais intrigué de voir une variable i de 0 à n (à n-1 en réalité) dans la boucle for et qui n'était plus utilisée après dans la boucle while...

Pour moi, en attendant de le faire à ma main, la seule explication est que tu as probablement cru faire comme la machine...
Mais je ne suis pas infaillible...
En tout cas avec le code dichotomie : à la main ou à la machine rien ne change...
Enfin si... en Python ça va plus vite, et c'est moins fatiguant surtout avec 15 décimales ;-)

Réponse demain.

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#6 22-08-2019 07:10:37

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 907

Re : Méthode par balayage avec Python

Bonjour,

J'ai vu...
Rien à voir avec ce que je pensais...
Çà se produirait avec n'importe quel langage, n'importe quel ordinateur.
C'est un problème qui est dû au mode de représentation en mémoire des nombres à virgule flottante...
Essaie :
>>> print (0.4-0.2)
0.2
>>> print (0.3-0.1)
0.19999999999999998

ll y en a un ici qui ayant découvert cela a développé une théorie du complot tournant autour de la conclusion qu'il a tirée : il y a des nombres interdits !  ^_^

Explications
https://www.supinfo.com/articles/single … grammation
https://fr.wikibooks.org/wiki/Fonctionn … es_nombres

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#7 22-08-2019 09:45:11

Cédrix
Membre
Inscription : 15-08-2019
Messages : 77

Re : Méthode par balayage avec Python

Merci car je faisais allusion à l'algorithme suivant où j'ai enlevé le ROUND :
from lycee import *
def approx_sqrt2(n):
    l=1
    while l**2<2:
            l=l+10**-n
    return l-10**-n

Merci infiniment pour tout : tout est clair !!!
C.

Hors ligne

Pied de page des forums