L'algorithme babylonien est une ancienne méthode pour trouver la racine carrée d'un nombre. C'est l'un des algorithmes les plus anciens jamais trouvés, datant de 1700 av.

L'algorithme babylonien est basé sur l'idée que si 'x' est une approximation de la racine carrée de 'n' , alors une meilleure approximation est donnée par la moyenne de 'x' et 'n/x'.

Par exemple, si nous voulons trouver la racine carrée de 25 ( n ), nous pouvons commencer par n'importe quel nombre positif x , disons x = 10. Ensuite, nous pouvons appliquer l'algorithme babylonien comme suit :

• Étape 1 : Calculer n/x = 25/10 = 2,5
• Étape 2 : Calculer la moyenne de x et n/x = (10 + 2,5)/2 = 6,25
• Étape 3 : Répétez les étapes 1 et 2 avec la nouvelle valeur de x = 6,25
• Étape 4 : Calculer n/x = 25/6,25 = 4
• Étape 5 : Calculer la moyenne de x et n/x = (6,25 + 4)/2 = 5,125
• Étape 6 : Répétez les étapes 4 et 5 avec la nouvelle valeur de x = 5,125
• Étape 7 : Calculer n/x = 25/5,125 = 4,878
• Étape 8 : Calculer la moyenne de x et n/x = (5,125 + 4,878)/2 = 5,0015
• Étape 9 : Répétez les étapes 7 et 8 avec la nouvelle valeur de x = 5,0015

Pseudo-code :

* Set x = n / 2                            // initial guess
    * Repeat
        * Set y = n / x                  // compute the reciprocal
        * Set x = (x + y) / 2           // compute the average
    * Until x and y are close enough   // some termination criterion
* Return x

// A function that takes a positive number n and 
// returns an approximation of its square root

double babylonian_sqrt(double n) {
  double e = 0.000001;                    // error tolerance
  double x = n / 2;                      // initial guess
  double y = 0;                         // reciprocal

  do {
    y = n / x;                       // compute the reciprocal
    x = (x + y) / 2;                // compute the average
  } while (abs(x - y) > e);        // repeat until x and y are close enough

  return x;                      // return the approximation
}

La méthode babylonienne fonctionne en prenant à plusieurs reprises la moyenne de x et n/x , où x est une estimation initiale et n est le nombre dont nous voulons trouver la racine carrée. L'algorithme s'arrête lorsque la différence entre x et n/x est inférieure à une erreur m donnée . La complexité temporelle de l'algorithme dépend de la vitesse à laquelle x et n/x convergent vers la racine carrée de n .

Pour analyser la complexité temporelle, nous devons examiner l' erreur relative à chaque étape, qui est définie comme e_k = (x_k — sqrt( n )) / sqrt( n ), où x_k est la valeur de x à l'étape k .

Nous pouvons montrer que e_k < 2^(-f(k)) , où f(k) est une fonction qui croît exponentiellement avec k . Cela signifie que l'erreur diminue très rapidement à mesure que nous augmentons k .

L'algorithme se terminera lorsque e_k * n < m , ce qui signifie que l'erreur absolue est inférieure à m . Cela se produira lorsque 2^(-f(k)) * n < m.

Diviser les deux côtés par n . Cela donne 2^(-f(k)) < m/n .

Prendre la base logarithmique 2 des deux côtés. Cela donne -f(k) < log_2(m/n) .

Multipliez les deux côtés par -1 . Cela donne f(k) > -log_2(m/n) .

Utilisez la propriété des logarithmes selon laquelle log_2(a/b) = log_2(a) — log_2(b) . Cela donne f(k) > -log_2(m) + log_2(n) .

Utilisez la propriété des logarithmes selon laquelle -log_2(a) = log_2(1/a). Cela donne f(k) > log_2(1/m) + log_2(n).

Utilisez la propriété des logarithmes selon laquelle log_2(a) + log_2(b) = log_2(ab). Cela donne f(k) > log_2(n/m) .

Puisque par induction, f(k) = 3 * 2^(k-1) — 1 , nous pouvons résoudre pour k et obtenir k > log_2((log_2(n/m) — 1)/3) + 1 . Cela signifie que le nombre de pas k est borné par un logarithme d'un logarithme de n/m .

Par conséquent, la complexité temporelle de la méthode babylonienne est O(log(log(n/m))) .

Les références

• Méthodes de calcul des racines carrées — Wikipédia
• https://stackoverflow.com/questions/12309432/time-complexity-for-babylonian-method