Co to jest algorytm babiloński?

Apr 27 2023

Algorytm babiloński to starożytna metoda znajdowania pierwiastka kwadratowego z liczby. Jest to jeden z najstarszych algorytmów, jakie kiedykolwiek znaleziono, datowany na 1700 pne.

Algorytm babiloński opiera się na założeniu, że jeśli „x” jest przybliżeniem pierwiastka kwadratowego z „n” , to lepsze przybliżenie daje średnia „x” i „n/x”.

Na przykład, jeśli chcemy znaleźć pierwiastek kwadratowy z 25 ( n ), możemy zacząć od dowolnej liczby dodatniej x , powiedzmy x = 10. Następnie możemy zastosować algorytm babiloński w następujący sposób:

Krok 1: Oblicz n/x = 25/10 = 2,5
Krok 2: Oblicz średnią z x i n/x = (10 + 2,5)/2 = 6,25
Krok 3: Powtórz kroki 1 i 2 z nową wartością x = 6,25
Krok 4: Oblicz n/x = 25/6,25 = 4
Krok 5: Oblicz średnią z x i n/x = (6,25 + 4)/2 = 5,125
Krok 6: Powtórz kroki 4 i 5 z nową wartością x = 5,125
Krok 7: Oblicz n/x = 25/5,125 = 4,878
Krok 8: Oblicz średnią z x i n/x = (5,125 + 4,878)/2 = 5,0015
Krok 9: Powtórz kroki 7 i 8 z nową wartością x = 5,0015

Pseudokod :

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

Metoda babilońska polega na wielokrotnym obliczaniu średniej z x i n/x , gdzie x to wstępne przypuszczenie, a n to liczba, z której chcemy znaleźć pierwiastek kwadratowy. Algorytm zatrzymuje się, gdy różnica między x i n/x jest mniejsza niż dany błąd m . Złożoność czasowa algorytmu zależy od tego, jak szybko x i n/x zbiegają się do pierwiastka kwadratowego z n .

Aby przeanalizować złożoność czasową, musimy spojrzeć na błąd względny na każdym kroku, który jest zdefiniowany jako e_k = (x_k — sqrt( n )) / sqrt( n ), gdzie x_k jest wartością x w kroku k .

Możemy pokazać, że e_k < 2^(-f(k)) , gdzie f(k) jest funkcją rosnącą wykładniczo wraz z k . Oznacza to, że błąd maleje bardzo szybko wraz ze wzrostem k .

Algorytm zakończy się, gdy e_k * n < m , co oznacza , że błąd bezwzględny jest mniejszy niż m . Stanie się tak, gdy 2^(-f(k)) * n < m.

Podziel obie strony przez n . Daje to 2^(-f(k)) < m/n .

Weź podstawę logarytmu 2 z obu stron. Daje to -f(k) < log_2(m/n) .

Pomnóż obie strony przez -1 . Daje to f(k) > -log_2(m/n) .

Użyj właściwości logarytmów, że log_2(a/b) = log_2(a) — log_2(b) . Daje to f(k) > -log_2(m) + log_2(n) .

Użyj właściwości logarytmów, że -log_2(a) = log_2(1/a). Daje to f(k) > log_2(1/m) + log_2(n).

Użyj właściwości logarytmów, że log_2(a) + log_2(b) = log_2(ab). Daje to f(k) > log_2(n/m) .

Ponieważ przez indukcję f(k) = 3 * 2^(k-1) — 1 , możemy rozwiązać dla k i otrzymać k > log_2((log_2(n/m) — 1)/3) + 1 . Oznacza to, że liczba kroków k jest ograniczona logarytmem z logarytmu n/m .

Co to jest algorytm babiloński?

Pseudokod :

Bibliografia