El algoritmo babilónico es un método antiguo para encontrar la raíz cuadrada de un número. Es uno de los algoritmos más antiguos jamás encontrados, que data del 1700 a.

El algoritmo babilónico se basa en la idea de que si 'x' es una aproximación de la raíz cuadrada de 'n' , entonces se obtiene una mejor aproximación mediante el promedio de 'x' y 'n/x'.

Por ejemplo, si queremos encontrar la raíz cuadrada de 25 ( n ), podemos comenzar con cualquier número positivo x , digamos x = 10. Luego podemos aplicar el algoritmo babilónico de la siguiente manera:

• Paso 1: Calcule n/x = 25/10 = 2,5
• Paso 2: Calcule el promedio de x y n/x = (10 + 2,5)/2 = 6,25
• Paso 3: Repita los pasos 1 y 2 con el nuevo valor de x = 6,25
• Paso 4: Calcule n/x = 25/6.25 = 4
• Paso 5: Calcule el promedio de x y n/x = (6,25 + 4)/2 = 5,125
• Paso 6: Repita los pasos 4 y 5 con el nuevo valor de x = 5.125
• Paso 7: Calcule n/x = 25/5.125 = 4.878
• Paso 8: Calcule el promedio de x y n/x = (5,125 + 4,878)/2 = 5,0015
• Paso 9: Repita los pasos 7 y 8 con el nuevo valor de x = 5.0015

Pseudocódigo :

* 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
}

El método babilónico funciona tomando repetidamente el promedio de x y n/x , donde x es una suposición inicial y n es el número cuya raíz cuadrada queremos encontrar. El algoritmo se detiene cuando la diferencia entre x y n/x es menor que un error m dado . La complejidad temporal del algoritmo depende de qué tan rápido x y n/x convergen a la raíz cuadrada de n .

Para analizar la complejidad del tiempo, debemos observar el error relativo en cada paso, que se define como e_k = (x_k — sqrt( n )) / sqrt( n ), donde x_k es el valor de x en el paso k .

Podemos demostrar que e_k < 2^(-f(k)) , donde f(k) es una función que crece exponencialmente con k . Esto significa que el error disminuye muy rápido a medida que aumentamos k .

El algoritmo terminará cuando e_k * n < m , lo que significa que el error absoluto es menor que m . Esto sucederá cuando 2^(-f(k)) * n < m.

Divide ambos lados por n . Esto da 2^(-f(k)) < m/n .

Saca el logaritmo en base 2 de ambos lados. Esto da -f(k) < log_2(m/n) .

Multiplica ambos lados por -1 . Esto da f(k) > -log_2(m/n) .

Usa la propiedad de los logaritmos que log_2(a/b) = log_2(a) — log_2(b) . Esto da f(k) > -log_2(m) + log_2(n) .

Usa la propiedad de los logaritmos que -log_2(a) = log_2(1/a). Esto da f(k) > log_2(1/m) + log_2(n).

Usa la propiedad de los logaritmos que log_2(a) + log_2(b) = log_2(ab). Esto da f(k) > log_2(n/m) .

Dado que por inducción, f(k) = 3 * 2^(k-1) — 1 , podemos despejar k y obtener k > log_2((log_2(n/m) — 1)/3) + 1 . Esto significa que el número de pasos k está acotado por un logaritmo de un logaritmo de n/m .

Por lo tanto, la complejidad temporal del método babilónico es O(log(log(n/m))) .

Referencias

• Métodos para calcular raíces cuadradas — Wikipedia
• https://stackoverflow.com/questions/12309432/time-complexity-for-babylonian-method