L'algoritmo babilonese è un antico metodo per trovare la radice quadrata di un numero. È uno degli algoritmi più antichi mai trovati, risalente al 1700 a.C.

L'algoritmo babilonese si basa sull'idea che se 'x' è un'approssimazione della radice quadrata di 'n' , allora un'approssimazione migliore è data dalla media di 'x' e 'n/x'.

Ad esempio, se vogliamo trovare la radice quadrata di 25 ( n ), possiamo iniziare con qualsiasi numero positivo x , diciamo x = 10. Quindi possiamo applicare l'algoritmo babilonese come segue:

• Passaggio 1: calcola n/x = 25/10 = 2,5
• Passaggio 2: calcola la media di x e n/x = (10 + 2,5)/2 = 6,25
• Passaggio 3: ripetere i passaggi 1 e 2 con il nuovo valore di x = 6,25
• Passaggio 4: calcola n/x = 25/6,25 = 4
• Passaggio 5: calcola la media di x e n/x = (6,25 + 4)/2 = 5,125
• Passaggio 6: ripetere i passaggi 4 e 5 con il nuovo valore di x = 5,125
• Passaggio 7: calcola n/x = 25/5,125 = 4,878
• Passaggio 8: calcola la media di x e n/x = (5,125 + 4,878)/2 = 5,0015
• Passaggio 9: ripetere i passaggi 7 e 8 con il nuovo valore di x = 5,0015

pseudocodice :

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

Il metodo babilonese funziona prendendo ripetutamente la media di x e n/x , dove x è un'ipotesi iniziale e n è il numero di cui vogliamo trovare la radice quadrata. L'algoritmo si interrompe quando la differenza tra x e n/x è minore di un dato errore m . La complessità temporale dell'algoritmo dipende dalla velocità con cui x e n/x convergono alla radice quadrata di n .

Per analizzare la complessità temporale, dobbiamo esaminare l' errore relativo ad ogni passo, che è definito come e_k = (x_k — sqrt( n )) / sqrt( n ), dove x_k è il valore di x al passo k .

Possiamo dimostrare che e_k < 2^(-f(k)) , dove f(k) è una funzione che cresce esponenzialmente con k . Ciò significa che l'errore diminuisce molto velocemente all'aumentare di k .

L'algoritmo terminerà quando e_k * n < m , il che significa che l'errore assoluto è minore di m . Questo accadrà quando 2^(-f(k)) * n < m.

Dividi entrambi i lati per n . Questo dà 2^(-f(k)) < m/n .

Prendi il logaritmo in base 2 di entrambi i lati. Questo dà -f(k) < log_2(m/n) .

Moltiplica entrambi i membri per -1 . Questo dà f(k) > -log_2(m/n) .

Usa la proprietà dei logaritmi che log_2(a/b) = log_2(a) — log_2(b) . Questo dà f(k) > -log_2(m) + log_2(n) .

Usa la proprietà dei logaritmi che -log_2(a) = log_2(1/a). Questo dà f(k) > log_2(1/m) + log_2(n).

Usa la proprietà dei logaritmi che log_2(a) + log_2(b) = log_2(ab). Questo dà f(k) > log_2(n/m) .

Poiché per induzione, f(k) = 3 * 2^(k-1) — 1 , possiamo risolvere per k e ottenere k > log_2((log_2(n/m) — 1)/3) + 1 . Ciò significa che il numero di passaggi k è limitato da un logaritmo di un logaritmo di n/m .

Pertanto, la complessità temporale del metodo babilonese è O(log(log(n/m))) .

Riferimenti

• Metodi di calcolo delle radici quadrate - Wikipedia
• https://stackoverflow.com/questions/12309432/time-complexity-for-babylonian-method