Boucles et fonctions – avec solutions

Pour expérimentez avec les fonctions et les boucles, mettons en œuvre une fonction de calcul de racine carrée : étant donné un nombre \(x\), nous voulons trouver le nombre \(z\) pour lequel \(z^2\) est le plus proche de \(x\).

On peut calculer \(\sqrt{x}\) en utilisant une boucle. En commençant par une estimation de \(z\), nous ajustons \(z\) en fonction de la proximité de \(z^2\) par rapport à \(x\), ce qui permet d’obtenir une meilleure estimation :

\[ z = z - \frac{z^2 - x}{2 \cdot z} \]

En répétant cette opération, on améliore de plus en plus l’estimation jusqu’à ce que l’on obtienne une réponse aussi proche que possible de la racine carrée réelle.

Implémentez ceci dans la fonction suivante :

func Sqrt(x float64) float64 {
    // TODO: Implement the square root of x using a looop
}

Indépendamment de la valeur de \(x\), vous pouvez prendre \(1\) comme estimation de départ pour \(z\). Dans un premier temps, répétez le calcul 10 fois et imprimez chaque \(z\) à chaque itération. Voyez comment vous vous rapprochez de la réponse pour différentes valeurs de \(x\) (\(1\), \(2\), \(3\), …) et à quelle vitesse l’estimation s’améliore.

Conseil

Pour déclarer et initialiser une valeur en virgule flottante, donnez-lui une syntaxe en virgule flottante ou utilisez une conversion :

z := 1.0
z := float64(1)

Solution

func Sqrt(x float64) float64 {
    res := x
    for i := 0; i < 10; i++ {
        res = res - (res*res-x)/(2*res)
    }
    return res
}

Modifiez ensuite la condition de la boucle pour qu’elle s’arrête une fois que la valeur a cessé de changer (ou ne change que très peu). Voyez si cela représente plus ou moins de 10 itérations. Essayez d’autres valeurs initiales pour \(z\), comme \(x\) ou \(\frac{x}{2}\). Dans quelle mesure les résultats de votre fonction sont-ils proches de math.Sqrt de la bibliothèque standard?

Solution

func Sqrt(x, precision float64) float64 {
    res := x
    prev := math.NaN()
    for {
        res = res - (res*res-x)/(2*res)
        if math.Abs(res-prev) <= precision {
            return res
        }
        prev = res
    }
}

ou alors (mieux ?) :

func Sqrt(x, precision float64) float64 {
    res := x
    for prev := math.NaN(); !(math.Abs(res-prev) <= precision); res -= (res*res - x) / (2 * res) {
        prev = res
    }
    return res
}

Pourquoi avoir écrit !(math.Abs(z-prev) <= precision) et non math.Abs(z-prev) > precision ? Est-ce que l’inverse de <= n’est pas > ?

Comment se comporte votre programme avec un x négatif ? avec not-a-number ? Quels autres nombres donneront un résultat faux ? Est-ce que vous pouvez calculer la racine carrée de \(10^{200}\) ?

package main

import (
    "fmt"
)

func Sqrt(x float64) float64 {
}

func main() {
    fmt.Println(Sqrt(2))
}

Remarque

Si les détails de l’algorithme vous intéressent, \(z^2 - x\) représente la distance entre \(z^2\) et le point \(x\) où il doit être. \(2 \cdot z\) est la dérivée de \(z^2\) et en divisant par cette valeur, ça nous permet d’ajuster dans quelle mesure nous modifions \(z\) en fonction de la vitesse à laquelle \(z^2\) change. Cette approche générale est appelée méthode de Newton. Elle fonctionne bien pour de nombreuses fonctions mais particulièrement bien pour la racine carrée).

Si vous voulez voir comment la bibliothèque standard de Go implémente la racine carrée, vous pouvez étudier le code source

Si vous aimez ce genre de chose, je vous invite à regarder la vidéo d’un cours sur l’algorithme de Newton donné au MIT. Attention… c’est du lourd!