Was ist der babylonische Algorithmus?

Apr 27 2023

Der babylonische Algorithmus ist eine alte Methode zum Ermitteln der Quadratwurzel einer Zahl. Es handelt sich um einen der ältesten jemals gefundenen Algorithmen, der auf das Jahr 1700 v. Chr. zurückgeht.

Der babylonische Algorithmus basiert auf der Idee, dass, wenn „x“ eine Näherung der Quadratwurzel von „n“ ist , eine bessere Näherung durch den Durchschnitt von „x“ und „n/x“ gegeben ist.

Wenn wir beispielsweise die Quadratwurzel aus 25 ( n ) ermitteln möchten, können wir mit einer beliebigen positiven Zahl x beginnen , beispielsweise x = 10. Dann können wir den babylonischen Algorithmus wie folgt anwenden:

Schritt 1: Berechnen Sie n/x = 25/10 = 2,5
Schritt 2: Berechnen Sie den Durchschnitt von x und n/x = (10 + 2,5)/2 = 6,25
Schritt 3: Wiederholen Sie die Schritte 1 und 2 mit dem neuen Wert x = 6,25
Schritt 4: Berechnen Sie n/x = 25/6,25 = 4
Schritt 5: Berechnen Sie den Durchschnitt von x und n/x = (6,25 + 4)/2 = 5,125
Schritt 6: Wiederholen Sie die Schritte 4 und 5 mit dem neuen Wert x = 5,125
Schritt 7: Berechnen Sie n/x = 25/5,125 = 4,878
Schritt 8: Berechnen Sie den Durchschnitt von x und n/x = (5,125 + 4,878)/2 = 5,0015
Schritt 9: Wiederholen Sie die Schritte 7 und 8 mit dem neuen Wert x = 5,0015

Pseudocode :

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

Die babylonische Methode funktioniert, indem sie wiederholt den Durchschnitt von x und n/x ermittelt , wobei x eine anfängliche Schätzung und n die Zahl ist, deren Quadratwurzel wir ermitteln möchten. Der Algorithmus stoppt, wenn die Differenz zwischen x und n/x kleiner als ein gegebener Fehler m ist . Die zeitliche Komplexität des Algorithmus hängt davon ab, wie schnell x und n/x zur Quadratwurzel von n konvergieren .

Um die Zeitkomplexität zu analysieren, müssen wir den relativen Fehler bei jedem Schritt betrachten , der als e_k = (x_k — sqrt( n )) / sqrt( n ) definiert ist, wobei x_k der Wert von x bei Schritt k ist .

Wir können zeigen, dass e_k < 2^(-f(k)) ist , wobei f(k) eine Funktion ist, die exponentiell mit k wächst . Das bedeutet, dass der Fehler sehr schnell abnimmt, wenn wir k erhöhen .

Der Algorithmus wird beendet, wenn e_k * n < m ist, was bedeutet, dass der absolute Fehler kleiner als m ist . Dies geschieht, wenn 2^(-f(k)) * n < m.

Teilen Sie beide Seiten durch n . Dies ergibt 2^(-f(k)) < m/n .

Nehmen Sie den Logarithmus zur Basis 2 beider Seiten. Dies ergibt -f(k) < log_2(m/n) .

Multiplizieren Sie beide Seiten mit -1 . Dies ergibt f(k) > -log_2(m/n) .

Verwenden Sie die Eigenschaft von Logarithmen, dass log_2(a/b) = log_2(a) — log_2(b) . Dies ergibt f(k) > -log_2(m) + log_2(n) .

Verwenden Sie die Eigenschaft von Logarithmen, dass -log_2(a) = log_2(1/a). Dies ergibt f(k) > log_2(1/m) + log_2(n).

Verwenden Sie die Eigenschaft von Logarithmen, dass log_2(a) + log_2(b) = log_2(ab). Dies ergibt f(k) > log_2(n/m) .

Da durch Induktion f(k) = 3 * 2^(k-1) — 1 gilt , können wir nach k auflösen und erhalten k > log_2((log_2(n/m) — 1)/3) + 1 . Dies bedeutet, dass die Anzahl der Schritte k durch den Logarithmus eines Logarithmus von n/m begrenzt ist .

Was ist der babylonische Algorithmus?

Pseudocode :

Verweise