Problem możemy rozwiązać następująco.
Tworzymy ciąg kwadratów kolejnych liczb całkowitych począwszy od
0:
do momentu, gdy dla pewnego i otrzymamy spełnioną
nierówność i2 > x. Wtedy p = i - 1.
Pozostaje do rozwiązania efektywny sposób tworzenia kwadratów
kolejnych liczb całkowitych. Wypiszmy kilkanaście początkowych wyrazów tego
ciągu:
| i |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
... |
| i2 |
0 |
1 |
4 |
9 |
16 |
25 |
36 |
49 |
64 |
81 |
100 |
121 |
144 |
... |
Teraz policzmy ciąg różnic pierwszego rzędu:
r1i = i2 - (i-1)2,
dla i > 0.
Różnica pierwszego rzędu powstaje przez odjęcie od
wyrazu i-tego jego poprzednika w ciągu, czyli wyrazu (i - 1)-szego.
| i |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
... |
| i2 |
0 |
1 |
4 |
9 |
16 |
25 |
36 |
49 |
64 |
81 |
100 |
121 |
144 |
... |
| r1 |
|
1 |
3 |
5 |
7 |
9 |
11 |
13 |
15 |
17 |
19 |
21 |
23 |
... |
Ciekawa rzecz – różnice pierwszego rzędu dla naszego ciągu tworzą
ciąg kolejnych liczb nieparzystych. Teraz analogicznie utwórzmy ciąg różnic
drugiego rzędu:
r2i = r1i - r1(i-1), dla
i > 1
Różnice drugiego rzędu powstają w analogiczny sposób z różnic
pierwszego rzędu, jak różnice pierwszego rzędu powstają z wyrazów ciągu – od
i-tej różnicy pierwszego rzędu odejmujemy poprzedzającą ją, (i - 1)-szą różnicę.
| i |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
... |
| i2 |
0 |
1 |
4 |
9 |
16 |
25 |
36 |
49 |
64 |
81 |
100 |
121 |
144 |
... |
| r1 |
|
1 |
3 |
5 |
7 |
9 |
11 |
13 |
15 |
17 |
19 |
21 |
23 |
... |
| r2 |
|
|
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
... |
Różnice rzędu drugiego tworzą już ciąg stały o wyrazach równych
2. Nie ma sensu liczyć różnic wyższych rzędów, ponieważ otrzymamy tylko
wyrazy równe 0. W tabelce na czerwono zaznaczyliśmy pierwsze wyrazy odpowiednio:
-
ciągu kwadratów i2 → 0
-
ciągu różnic pierwszego rzędu r1i → 1
-
ciągu różnic drugiego rzędu r2i → 2
Mając te trzy wartości możemy rekurencyjnie konstruować ciąg
kolejnych kwadratów:
a = 0, r11 = 1, r2
= 2, gdzie a0 – pierwszy wyraz ciągu kwadratów
Dla i > 0 mamy:
r1i = r1(i-1) +
r2 – kolejna różnica pierwszego rzędu powstaje z poprzedniej
przez dodanie różnicy drugiego rzędu
ai = ai-1 + r1i
– kolejny kwadrat powstaje z poprzedniego przez dodanie wyliczonej różnicy
pierwszego rzędu
Zwróć uwagę, iż wykorzystujemy tylko dodawanie, dzięki czemu nasz
algorytm jest szybki. Jednakże podany algorytm nie jest stosowany w praktyce do
wyznaczania wartości pierwiastka kwadratowego. Podajemy go tutaj tylko ze
względów dydaktycznych.
Algorytm obliczania całkowitego
pierwiastka kwadratowego – wersja nr 1
Program
Ważne:
Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy
funkcje tych programów oraz sposób korzystania z nich. |
W pierwszym wierszu program odczytuje liczbę x. Następnie
wyznacza jej całkowity pierwiastek kwadratowy i wypisuje go w wierszu drugim.
Dodatkowo w wierszu trzecim program wypisuje kwadrat znalezionego pierwiastka
kwadratowego dla celów porównawczych.
| Code::Blocks |
// Całkowity pierwiastek
//---------------------------
#include <iostream>
using namespace std;
int main()
{
double x;
unsigned int i,a,r1,r2;
cin >> x;
a = 0; r1 = 1; r2 = 2;
for(i = 0; a <= x; i++)
{
a += r1; r1 += r2;
}
i--;
cout << i << endl
<< i * i << endl
<< endl;
return 0;
}
|
Druga metoda znajdowania całkowitego pierwiastka kwadratowego
pochodzi od Izaaka Newtona (chociaż
podobną metodę stosowali już starożytni Babilończycy). Jeśli mamy pewne przybliżenie p pierwiastka liczby
x, to lepsze przybliżenie otrzymamy stosując wzór:
Dlaczego to działa? Rozważmy dwa przypadki:
p < √ x
Wtedy iloraz x / p jest większy od √ x i po dodaniu go do p i podzieleniu
sumy przez 2
otrzymamy liczbę większą od poprzedniego p, która przybliża się od dołu do rzeczywistego
pierwiastka.
p > √ x
Wtedy iloraz x / p jest mniejszy od √ x
i po dodaniu go do p i podzieleniu sumy przez 2 otrzymamy liczbę mniejszą
od poprzedniego p, która
przybliża się od góry do rzeczywistego pierwiastka.
Wynika z tego, iż w każdej iteracji otrzymujemy liczbę coraz
bliższą wartości pierwiastka. Iterujemy dotąd, aż różnica pomiędzy dwoma
kolejnymi przybliżeniami będzie mniejsza lub równa założonej dokładności ε
– w przypadku pierwiastków całkowitych jest to 1.
Algorytm obliczania całkowitego
pierwiastka kwadratowego – wersja nr 2
Wejście
| x |
– |
liczba, której pierwiastek obliczamy, x ≥ 0, x
 C |
Wyjście:
Całkowity pierwiastek kwadratowy z x
Elementy pomocnicze:
| p1, p2 |
– |
kolejne przybliżenia pierwiastka z x, p1, p2
C |
| K01: |
Jeśli x > 1, to idź do K04 |
; pierwiastki > 1 liczymy |
| K02: |
p2 ← x |
; inne nie |
| K03: |
Idź do K09 |
|
| K04: |
p1 ← 0 |
; zapewniamy |p1 - p2| >
1 |
| K05: |
p2 ← x shr 1 |
; pierwsze przybliżenie pierwiastka |
| K06: |
Dopóki |p1 - p2|
> 1, wykonuj K07...K08 |
; w pętli wyliczamy kolejne
przybliżenia |
| K07: |
p1 ← p2 |
; zapamiętujemy bieżące przybliżenie |
| K08: |
p2 ← (p2
+ x div p1) shr 1 |
; wyliczamy nowe przybliżenie |
| K09: |
Dopóki p2 × p2
> x, wykonuj p2 ← p2
- 1 |
; jeśli przybliżenie było od góry, zmniejszamy
je |
| K09: |
Zakończ z wynikiem p2 |
|
Program
W pierwszym wierszu program odczytuje liczbę x. Następnie wyznacza jej całkowity pierwiastek kwadratowy i wypisuje go w wierszu drugim. Dodatkowo w wierszu trzecim program wypisuje kwadrat znalezionego pierwiastka kwadratowego dla celów porównawczych.
| Code::Blocks |
// Całkowity pierwiastek kwadratowy
//---------------------------------
#include <iostream>
using namespace std;
int main()
{
int x,p1,p2;
cin >> x;
if(x <= 1) p2 = x;
else
{
p1 = 0; p2 = x >> 1;
while(abs(p1 - p2) > 1)
{
p1 = p2;
p2 = (p2 + x / p2) >> 1;
}
while(p2 * p2 > x) --p2;
}
cout << p2 << endl
<< (p2 * p2) << endl
<< endl;
return 0;
}
|
Istnieje bardzo szybki algorytm wyznaczania wartości całkowitego
pierwiastka kwadratowego, który wykorzystuje binarną reprezentację liczb – czyli
idealnie nadaje się do zastosowania dla danych komputerowych, które przecież są
liczbami binarnymi. Algorytm wywodzi się z chińskiego abakusa i nie wymaga
skomplikowanych działań arytmetycznych – jedynie dodawania oraz przesuwania
bitów. Dzięki tym zaletom może być z powodzeniem stosowany w prostych systemach
mikrokontrolerów jednoukładowych.
Algorytm obliczania całkowitego
pierwiastka kwadratowego – wersja nr 3
Wejście
| x |
– |
liczba, której pierwiastek obliczamy, x ≥ 0, x
C |
Wyjście:
Całkowity pierwiastek kwadratowy z x
Elementy pomocnicze:
| mb |
– |
zawiera maskę bitową z ustawionym jednym bitem. Maska jest 64 bitowa. |
| px |
– |
obliczana wartość pierwiastka, px
C |
| K01: |
px ← 0 |
; początkowa wartość pierwiastka |
| K02: |
mb ← 1 shl 62 |
; maska z ustawionym drugim najstarszym bitem |
| K03: |
Dopóki mb > x, wykonuj
mb ← mb shr 2 |
; szukamy najstarszej potęgi 4, mniejszej od x |
| K04: |
Dopóki mb ≠ 0, wykonuj
K05...K09 |
; wyznaczamy kolejne bity pierwiastka |
| K05: |
t ← px +
mb |
; łączymy bit maski z przybliżeniem pierwiastka |
| K06: |
Jeśli x <
t, idź do K09 |
; sprawdzamy, czy dany bit ma być
ustawiony. |
| K07: |
x ← x - t |
; usuwamy bity z x |
| K08: |
px ← t +
mb |
; dodajemy bit maski do px |
| K09: |
px ← px
shr 1 |
; przesuwamy bity pierwiastka o 1 w prawo |
| K09: |
mb ← mb
shr 2 |
; bity maski przesuwamy o 2 w prawo |
| K10: |
Zakończ z wynikiem px |
|
Program
W pierwszym wierszu program odczytuje liczbę x. Następnie wyznacza jej całkowity pierwiastek kwadratowy i wypisuje go w wierszu drugim. Dodatkowo w wierszu trzecim program wypisuje kwadrat znalezionego pierwiastka kwadratowego dla celów porównawczych.
| Code::Blocks |
// Całkowity pierwiastek kwadratowy
//---------------------------------
#include <iostream>
using namespace std;
int main()
{
unsigned long long x,px,mb,t;
cin >> x;
px = 0; mb = 1; mb <<= 62;
while(mb > x) mb >>= 2;
while(mb)
{
t = px + mb;
if(x >= t)
{
x -= t; px = t + mb;
}
px >>= 1; mb >>= 2;
}
cout << px << endl
<< (px * px) << endl << endl;
return 0;
}
|
Wróć do spisu tematów