Petit exercice avant d'aller faire dodo

Le
Jean-marc
Hello,

Comme c'est calme, j'en profite pour
poser une petite colle:

' 8<--

Option Explicit

Private Sub b(p As Double, q As Double)
Dim r As Double

r = (p + 2 / p) / 2
If q - r Then
q = r
b q, q
End If
End Sub


Private Sub Command1_Click()
Dim n As Double

b 1, n
' Que vaut n ? Pourquoi ?
End Sub

' 8<--


Bonne nuit :-o))


--
Jean-marc Noury (jean_marc_n2)
Microsoft MVP - Visual Basic
FAQ VB: http://faq.vb.free.fr/
mailto: remove '_no_spam_' ; _no_spam_jean_marc_n2@yahoo.fr
Vidéos High-Tech et Jeu Vidéo
Téléchargements
Vos réponses
Gagnez chaque mois un abonnement Premium avec GNT : Inscrivez-vous !
Trier par : date / pertinence
François Picalausa
Le #15374491
On Jan 30, 11:25 pm, "Jean-marc"
Hello,

Comme c'est calme, j'en profite pour
poser une petite colle:

' 8<-----------------------------------------

Option Explicit

Private Sub b(p As Double, q As Double)
Dim r As Double

    r = (p + 2 / p) / 2
    If q - r Then
        q = r
        b q, q
    End If
End Sub

Private Sub Command1_Click()
    Dim n As Double

    b 1, n
    ' Que vaut n ? Pourquoi ?
End Sub

' 8<-----------------------------------------

Bonne nuit :-o))



Hello,

A tout hasard, sqrt(2) ?

Il s'agit, il me semble, d'une méthode itérative d'approximation de
type Newton (remplacement de la courbe par sa tangente) appliquée au
calcul de cette racine, dont le cas particulier du calcul de la racine
carrée est attribuée à Héron d'Alexandrie

L'expression générale est :
r = p - f(p) / f'(p)
où r est l'approximation suivante, et p la précédente
et où on cherche un zéro de f(p).

Dans ce cas précis on peut exprimer x^2 - 2 = 0, et donc f'(p)=2x, ce
qui montre l'équivalence avec :
r = (p + 2 / p) / 2

Les paramètres sont donc:
p : approximation initiale
q : valeur de sqrt(2)

Les itération sont "remplacées" par une récursion de b sur base de la
nouvelle approximation comme nouvelle valeur de départ (q)
L'arrêt est du à la précision finie du type double, qui finira par
rendre la différence entre la nouvelle approximation (r) et
l'approximation précédente (q) négligeable.

François
LE TROLL
Le #15374481
Bonjour Jean-Marc,

Je n'ai pas tout compris, et je ne suis pas
certain d'avoir le niveau:

Déjà, je ne comprends pas cette expression, elle
veut dire quoi ?
If q - r... if q - r "= quoi" ???
-----------------------------
Sub Command1_Click()
Dim n As Double
Call b(1, n)
' Que vaut n ? N = 1,4142135623731
' Pourquoi ?
End Sub
'
Sub b(p As Double, q As Double)
Dim r As Double
r = (p + 2 / p) / 2
If q - r Then
q = r
Call b(q, q)
End If
End Sub
----------
1er: p = 1: r = 1,5
S'il ne remplit pas la condition ??? que je ne
comprends pas, je crois < 1:
q = r + call (début, q, q)
2eme passage
comprends pas, il me semble que p = 1 toujours ???
:o)

Peut être qu'à force de faire la même division,
avec le reste des décimales, peut être aussi
infinies, on arrive avec l'arrondi automatique de
VB au maximum de la capacité de la variable, à
faire varier le nombre ???


--
Merci beaucoup, au revoir et à bientôt :o)
------
Romans, logiciels, email, site personnel
http://irolog.free.fr/joe.htm
------------------------------------------------------------------------------------
"Jean-marc"
dans le message de news:
47a0f957$0$2945$
| Hello,
|
| Comme c'est calme, j'en profite pour
| poser une petite colle:
|
| ' 8<-----------------------------------------
|
| Option Explicit
|
| Private Sub b(p As Double, q As Double)
| Dim r As Double
|
| r = (p + 2 / p) / 2
| If q - r Then
| q = r
| b q, q
| End If
| End Sub
|
|
| Private Sub Command1_Click()
| Dim n As Double
|
| b 1, n
| ' Que vaut n ? Pourquoi ?
| End Sub
|
| ' 8<-----------------------------------------
|
|
| Bonne nuit :-o))
|
|
| --
| Jean-marc Noury (jean_marc_n2)
| Microsoft MVP - Visual Basic
| FAQ VB: http://faq.vb.free.fr/
| mailto: remove '_no_spam_' ;

|
|
|
|
jean-marc
Le #15374471
"LE TROLL" news:
Bonjour Jean-Marc,

Je n'ai pas tout compris, et je ne suis pas
certain d'avoir le niveau:

Déjà, je ne comprends pas cette expression, elle
veut dire quoi ?
If q - r... if q - r "= quoi" ???



Hello,

la bonne réponse est celle de François, voir
mail précédent.

C'est un calcul de racine de 2 qui utilise
le fait que la fonction
f(x) = 1/2 (x + 2/x) à une dérivée qui s'annule
pour x = racine(2).

L'autre propriété intéressante est que
f(racine de 2) = racine de deux.

De la, on définit une suite tq:
U(0) = 1
U(n+1)=f(U(n))

Qui a la propriété amusante suivante:

u(0)<Racine(2)<...<U(n+1)<U(n)<..

Donc elle converge (rapidement) vers racine de deux.

la sub utilise un accumulateur (q) pour stocker le
résultat de la dernière itération.
Le test d'arret est:

If q - r Then
Qui est syntaxiquement équivalent à
If (q - r)=0.0 Then

Un joli exemple d'utilisation d'une sub récursive
avec utilisation d'un accumulateur.

Bcp de problèmes en algorithmique numérique peuvent
se résoudre ou se modéliser par des suites convergentes,
mon exemple est une illustration de la facilité de
codage de ce genre de choses.

On pourra lire ou relire avec intérêt:
http://faq.vb.free.fr/index.php?question9

Bonne journée à tous;

--
Jean-marc Noury (jean_marc_n2)
Microsoft MVP - Visual Basic
FAQ VB: http://faq.vb.free.fr/
mailto: remove '_no_spam_' ;
jean-marc
Le #15374461
>
"François Picalausa" news:
On Jan 30, 11:25 pm, "Jean-marc"

Hello,

A tout hasard, sqrt(2) ?



Et oui :-)

Il s'agit, il me semble, d'une méthode itérative d'approximation de
type Newton (remplacement de la courbe par sa tangente) appliquée au
calcul de cette racine, dont le cas particulier du calcul de la racine
carrée est attribuée à Héron d'Alexandrie



Et peut être même au babyloniens :-)
J'avais appris ce truc sous le nom "d'algorithme de Babylone".

L'expression générale est :
r = p - f(p) / f'(p)
où r est l'approximation suivante, et p la précédente
et où on cherche un zéro de f(p).

Dans ce cas précis on peut exprimer x^2 - 2 = 0, et donc f'(p)=2x, ce
qui montre l'équivalence avec :
r = (p + 2 / p) / 2

Les paramètres sont donc:
p : approximation initiale
q : valeur de sqrt(2)



Oui c'est l'idée. Cf mon autre réponse :-)

Les itération sont "remplacées" par une récursion de b sur base de la
nouvelle approximation comme nouvelle valeur de départ (q)
L'arrêt est du à la précision finie du type double, qui finira par
rendre la différence entre la nouvelle approximation (r) et
l'approximation précédente (q) négligeable.



Yeap! Amusante utilisation d'une fonction récursive
avec accumulateur.

En fait, derrière l'exo, je voulais montrer qu'il est très facile
d'implémenter un calcul de suites (ou de séries d'ailleurs) avec
ce type de construction (récursivité + accumulateur).

(et puis il y a la VRAIE raison: les mahs, c'est cool!)

Bonne journée !




--
Jean-marc Noury (jean_marc_n2)
Microsoft MVP - Visual Basic
FAQ VB: http://faq.vb.free.fr/
mailto: remove '_no_spam_' ;
LE TROLL
Le #15374451
Ah oui, mais c'est sous un aspect très
mathématique que tu aborde ça dans la faq... Tu
aurais mis:

dim a = 0
sub b()
a = a + 1
if a > 9 then exit sub
call b
end sub

Peut être que pour le profane ça serait mieux
passé...

A part ça, j'ai eu, une fois un débordement de
pile, y a longtemps, c'était avec une utilisation
à outrance de dim x as string * x
Il me semble avoir lu ? Que justement *x était
aussi empilé, a contrario des variables classique
(sous réserve)...

J'ai eu un second problème non signalé dans la
FAQ, c'est un coincement du programme avec les
fonction récursives, qui certes, dépilaient, mais
faisait du ping-pong entre procédure, et donc, ne
répondait plus, faute de condition de sortie...
D'où l'utilisation d'espions dans un fichier log,
pour localiser le point de ping-pong...

--
Romans, logiciels, email, site personnel
http://irolog.free.fr/joe.htm
------------------------------------------------------------------------------------
"jean-marc" écrit dans le message de news:
47a183c9$0$2947$
| "LE TROLL" | news:
| > Bonjour Jean-Marc,
| >
| > Je n'ai pas tout compris, et je ne suis pas
| > certain d'avoir le niveau:
| >
| > Déjà, je ne comprends pas cette expression,
elle
| > veut dire quoi ?
| > If q - r... if q - r "= quoi" ???
|
| Hello,
|
| la bonne réponse est celle de François, voir
| mail précédent.
|
| C'est un calcul de racine de 2 qui utilise
| le fait que la fonction
| f(x) = 1/2 (x + 2/x) à une dérivée qui s'annule
| pour x = racine(2).
|
| L'autre propriété intéressante est que
| f(racine de 2) = racine de deux.
|
| De la, on définit une suite tq:
| U(0) = 1
| U(n+1)=f(U(n))
|
| Qui a la propriété amusante suivante:
|
| u(0)<Racine(2)<...<U(n+1)<U(n)<..
|
| Donc elle converge (rapidement) vers racine de
deux.
|
| la sub utilise un accumulateur (q) pour stocker
le
| résultat de la dernière itération.
| Le test d'arret est:
|
| If q - r Then
| Qui est syntaxiquement équivalent à
| If (q - r)=0.0 Then
|
| Un joli exemple d'utilisation d'une sub
récursive
| avec utilisation d'un accumulateur.
|
| Bcp de problèmes en algorithmique numérique
peuvent
| se résoudre ou se modéliser par des suites
convergentes,
| mon exemple est une illustration de la facilité
de
| codage de ce genre de choses.
|
| On pourra lire ou relire avec intérêt:
| http://faq.vb.free.fr/index.php?question9
|
| Bonne journée à tous;
|
| --
| Jean-marc Noury (jean_marc_n2)
| Microsoft MVP - Visual Basic
| FAQ VB: http://faq.vb.free.fr/
| mailto: remove '_no_spam_' ;

|
|
Patrice Henrio
Le #15374441
Jean-marc a écrit :
Hello,

Comme c'est calme, j'en profite pour
poser une petite colle:

' 8<-----------------------------------------

Option Explicit

Private Sub b(p As Double, q As Double)
Dim r As Double

r = (p + 2 / p) / 2
If q - r Then
q = r
b q, q
End If
End Sub


Private Sub Command1_Click()
Dim n As Double

b 1, n
' Que vaut n ? Pourquoi ?
End Sub

' 8<-----------------------------------------


Bonne nuit :-o))




Intéressant certe (là c'est le matheux qui parle) mais sur le plan
programmation, je regrette
1) n est implicitement valué à 0 dans la sub
2) les paramètres de b sont implicitement byRef
3) le prédicat q-r est implicitement transformé en booléen (0 -> faux,
<>0 -> vrai)

Enfin la réponse qui sera une valeur approchée de type double de la
racine carrée de 2 dépendra bien sûr du nombre de bits sur lesquels ces
double sont codés et de l'algorithme de représentation des décimaux en
binaire.
Ainsi si les nombres sont représentés en précision infinie (par exemple
sous forme de chaînes numériques) la fonction boucle sans fin.
En effet la sortie nécessite
p=(p+2/p)/2 donc p²=2


La récursivité par contre est mon dada et c'est pour ça que LISP reste
mon langage préféré en théorie.
Patrice Henrio
Le #15374431
François Picalausa a écrit :
On Jan 30, 11:25 pm, "Jean-marc"
Hello,

Comme c'est calme, j'en profite pour
poser une petite colle:

' 8<-----------------------------------------

Option Explicit

Private Sub b(p As Double, q As Double)
Dim r As Double

r = (p + 2 / p) / 2
If q - r Then
q = r
b q, q
End If
End Sub

Private Sub Command1_Click()
Dim n As Double

b 1, n
' Que vaut n ? Pourquoi ?
End Sub

' 8<-----------------------------------------

Bonne nuit :-o))



Hello,

A tout hasard, sqrt(2) ?

Il s'agit, il me semble, d'une méthode itérative d'approximation de
type Newton (remplacement de la courbe par sa tangente) appliquée au
calcul de cette racine, dont le cas particulier du calcul de la racine
carrée est attribuée à Héron d'Alexandrie

L'expression générale est :
r = p - f(p) / f'(p)
où r est l'approximation suivante, et p la précédente
et où on cherche un zéro de f(p).

Dans ce cas précis on peut exprimer x^2 - 2 = 0, et donc f'(p)=2x, ce
qui montre l'équivalence avec :
r = (p + 2 / p) / 2

Les paramètres sont donc:
p : approximation initiale
q : valeur de sqrt(2)

Les itération sont "remplacées" par une récursion de b sur base de la
nouvelle approximation comme nouvelle valeur de départ (q)
L'arrêt est du à la précision finie du type double, qui finira par
rendre la différence entre la nouvelle approximation (r) et
l'approximation précédente (q) négligeable.

François




tout à fait d'accord sauf la conclusion. Les itérations font converger
q-r vers 0. Pour une valeur suffisamment petite de q-r (inférieur en
valeur absolue à 2 puissance - 63 de mémoire), cette valeur (en type
double) est nulle.
Un nombre dans un type est en fait une classe de nombres.
jean-marc
Le #15374421
>"Patrice Henrio" >news:



Hello,

Intéressant certe (là c'est le matheux qui parle) mais sur le plan
programmation, je regrette
1) n est implicitement valué à 0 dans la sub
2) les paramètres de b sont implicitement byRef
3) le prédicat q-r est implicitement transformé en booléen (0 -> faux,
<>0 -> vrai)



C'est tout à fait juste. L'exercice était plus mathématique
que programmatique.

Dans une version plus propre, on devrait écrire
(par exemple) :

' 8<---------------------------------------------
Option Explicit

Private Const C_EPSILON As Double = 1E-20
'
'

Private Sub b(ByVal p As Double, _
ByRef q As Double, _
Optional ByVal epsilon As Double = C_EPSILON)

Dim r As Double

r = (p + 2 / p) / 2
If Abs(q - r) >= epsilon Then
q = r
Call b(q, q, epsilon)
End If

End Sub

Private Sub Command1_Click()
Dim n As Double, epsilon As Double

epsilon = 0.00000001
n = 0#
Call b(1, n, epsilon) ' Que vaut n ? Pourquoi ?
Debug.Print n

' ou alors :

n = 0#
Call b(1, n) ' Que vaut n ? Pourquoi ?
Debug.Print n
End Sub

' 8<---------------------------------------------



Ca ressemble déjà plus à du code de production :-)



Mais dans du vrai code de prod bien conçu, on
se prémunirait aussi de tout éventuel débordement
de pile par récursivité inifinie, en ajoutant un safety
check, comme il se doit :


Private Const SAFETY_LIMIT As Long = 20

Private Sub b(ByVal p As Double, _
ByRef q As Double, _
Optional ByVal epsilon As Double = C_EPSILON)

Dim r As Double
Static safety_check As Long

safety_check = safety_check + 1
If safety_check > SAFETY_LIMIT Then
' Debug.Print "max recusrion depth reached. abort"
Exit Sub
End If
r = (p + 2 / p) / 2
If Abs(q - r) >= epsilon Then
q = r
Call b(q, q, epsilon)
End If
safety_check = 0
End Sub

Cette fois, tu peux aller en prod avec ça, c'est okay et
safe dans tous les cas
(pour une valeur de SAFETY_LIMIT bien choisie bien sur).


Bref, c'est clair que mon petit exercice n'avait pas la prétention
d'être un exemple de bonne pratique de programmation :-)


Enfin la réponse qui sera une valeur approchée de type double de la racine
carrée de 2 dépendra bien sûr du nombre de bits sur lesquels ces double
sont codés et de l'algorithme de représentation des décimaux en binaire.



C'est tout à fait exact, bien sur.

Ainsi si les nombres sont représentés en précision infinie (par exemple
sous forme de chaînes numériques) la fonction boucle sans fin.
En effet la sortie nécessite
p=(p+2/p)/2 donc p²=2



Tout à fait. C'est corrigé dans l'implémentation ci-dessus.

La récursivité par contre est mon dada et c'est pour ça que LISP reste mon
langage préféré en théorie.



En théorie, c'est effectivement défendable :--))


--
Jean-marc Noury (jean_marc_n2)
Microsoft MVP - Visual Basic
FAQ VB: http://faq.vb.free.fr/
mailto: remove '_no_spam_' ;
Publicité
Poster une réponse
Anonyme