O que é algoritmo babilônico?

Apr 27 2023

O algoritmo babilônico é um método antigo para encontrar a raiz quadrada de um número. É um dos algoritmos mais antigos já encontrados, datado de 1700 AC.

O algoritmo babilônico é baseado na ideia de que se 'x' é uma aproximação da raiz quadrada de 'n' , então uma aproximação melhor é dada pela média de 'x' e 'n/x'.

Por exemplo, se quisermos encontrar a raiz quadrada de 25 ( n ), podemos começar com qualquer número positivo x , digamos x = 10. Em seguida, podemos aplicar o algoritmo babilônico da seguinte maneira:

Etapa 1: calcular n/x = 25/10 = 2,5
Etapa 2: calcular a média de x e n/x = (10 + 2,5)/2 = 6,25
Passo 3: Repita os passos 1 e 2 com o novo valor de x = 6,25
Etapa 4: calcular n/x = 25/6,25 = 4
Etapa 5: calcular a média de x e n/x = (6,25 + 4)/2 = 5,125
Etapa 6: Repita as etapas 4 e 5 com o novo valor de x = 5,125
Etapa 7: calcular n/x = 25/5,125 = 4,878
Passo 8: Calcule a média de x e n/x = (5,125 + 4,878)/2 = 5,0015
Passo 9: Repita os passos 7 e 8 com o novo 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
}

O método babilônico funciona tomando repetidamente a média de x e n/x , onde x é uma estimativa inicial e n é o número do qual queremos encontrar a raiz quadrada. O algoritmo para quando a diferença entre x e n/x é menor que um dado erro m . A complexidade de tempo do algoritmo depende de quão rápido x e n/x convergem para a raiz quadrada de n .

Para analisar a complexidade do tempo, precisamos observar o erro relativo em cada etapa, que é definido como e_k = (x_k — sqrt( n )) / sqrt( n ), onde x_k é o valor de x na etapa k .

Podemos mostrar que e_k < 2^(-f(k)) , onde f(k) é uma função que cresce exponencialmente com k . Isso significa que o erro diminui muito rapidamente à medida que aumentamos k .

O algoritmo terminará quando e_k * n < m , o que significa que o erro absoluto é menor que m . Isso acontecerá quando 2^(-f(k)) * n < m.

Divida ambos os lados por n . Isso dá 2^(-f(k)) < m/n .

Pegue o logaritmo de base 2 de ambos os lados. Isso dá -f(k) < log_2(m/n) .

Multiplique ambos os lados por -1 . Isso dá f(k) > -log_2(m/n) .

Use a propriedade dos logaritmos que log_2(a/b) = log_2(a) — log_2(b) . Isso dá f(k) > -log_2(m) + log_2(n) .

Use a propriedade dos logaritmos que -log_2(a) = log_2(1/a). Isso dá f(k) > log_2(1/m) + log_2(n).

Use a propriedade dos logaritmos que log_2(a) + log_2(b) = log_2(ab). Isso dá f(k) > log_2(n/m) .

Como por indução, f(k) = 3 * 2^(k-1) — 1 , podemos resolver k e obter k > log_2((log_2(n/m) — 1)/3) + 1 . Isso significa que o número de passos k é limitado por um logaritmo de um logaritmo de n/m .

O que é algoritmo babilônico?

Pseudocódigo :

Referências