Serwis Edukacyjny w I-LO w Tarnowie ![]() Materiały dla uczniów liceum |
Wyjście Spis treści Wstecz Dalej Autor artykułu: mgr Jerzy Wałaszek |
©2023 mgr Jerzy Wałaszek |
ProblemZnaleźć kwadratowy pierwiastek całkowity nieujemnej liczby rzeczywistej x. Całkowity pierwiastek kwadratowy (ang. integer square root) jest największą liczbą całkowitą p, która spełnia nierówność: p 2 ≤ x |
Problem możemy rozwiązać następująco.
Tworzymy ciąg kwadratów kolejnych liczb całkowitych począwszy od 0:
02 12 22 32 ... i 2
do momentu, gdy dla pewnego i otrzymamy spełnioną nierówność i 2 > 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 | ... |
i 2 | 0 | 1 | 4 | 9 | 16 | 25 | 36 | 49 | 64 | 81 | 100 | 121 | 144 | ... |
Teraz policzmy ciąg różnic pierwszego rzędu:
r 1i = i 2 - ( 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 | ... |
i 2 | 0 | 1 | 4 | 9 | 16 | 25 | 36 | 49 | 64 | 81 | 100 | 121 | 144 | ... |
r 1 | 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:
r 2i = r 1i - r 1 ( 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 | ... |
i 2 | 0 | 1 | 4 | 9 | 16 | 25 | 36 | 49 | 64 | 81 | 100 | 121 | 144 | ... |
r 1 | 1 | 3 | 5 | 7 | 9 | 11 | 13 | 15 | 17 | 19 | 21 | 23 | ... | |
r 2 | 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:
Mając te trzy wartości możemy rekurencyjnie konstruować ciąg kolejnych kwadratów:
a = 0, r 11 = 1, r 2 = 2, gdzie a 0 – pierwszy wyraz ciągu kwadratów
Dla i > 0 mamy:
r 1i = r 1 ( i - 1 ) + r 2 – kolejna różnica pierwszego rzędu powstaje z poprzedniej przez dodanie różnicy drugiego rzędu
a i = a i - 1 + r 1i – 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.
x | – | liczba, której pierwiastek obliczamy, x ≥ 0, x ∈ R. |
całkowity pierwiastek kwadratowy z x.
i | – | numery wyrazów ciągu kwadratów, i ∈ C. |
a | – | wyraz ciągu kwadratów, a ∈ C. |
r 1 | – | różnica pierwszego rzędu, r 1 ∈ N. |
r 2 | – | różnica drugiego rzędu, r 2 ∈ N. |
K01: | a ← 0 | pierwszy kwadrat 0 2 |
K02: | r 1 ← 1 | początkowa wartość różnicy pierwszego rzędu |
K03: | r 2 ← 2 | wartość różnic drugiego rzędu |
K04: | i ← 0 | numer pierwszego wyrazu |
K05: | Dopóki a ≤ x, wykonuj K06...K08 |
szukamy pierwszego wyrazu a większego od x |
K06: | a ← a + r 1 | następny kwadrat |
K07: | r 1 ← r 1 + r 2 | wyliczamy nową różnicę pierwszego rzędu |
K08: | i ← i + 1 | następny numer |
K09: | Zakończ z wynikiem i - 1 | obliczamy pierwiastek całkowity |
Uwaga:
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. |
Pascal// Całkowity pierwiastek // Data: 10.05.2008 // (C)2020 mgr Jerzy Wałaszek //--------------------------- program prg; var x : double; i, a, r1, r2 : longword; begin readln ( x ); a := 0; r1 := 1; r2 := 2; i := 0; while a <= x do begin inc ( a, r1 ); inc ( r1, r2 ); inc ( i ); end; dec ( i ); writeln ( i ); writeln ( i * i ); writeln; end. |
C++// Całkowity pierwiastek // Data: 10.05.2008 // (C)2020 mgr Jerzy Wałaszek //--------------------------- #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; } |
Basic' Całkowity pierwiastek ' Data: 10.05.2008 ' (C)2020 mgr Jerzy Wałaszek '--------------------------- Dim As Double x Dim As Uinteger i, a, r1, r2 Input x a = 0: r1 = 1: r2 = 2: i = 0 While a <= x a += r1: r1 += r2: i += 1 Wend i -= 1 Print i Print i * i Print End |
Wynik: |
135 11 121 |
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:
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.
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.
x | – | liczba, której pierwiastek obliczamy, x ≥ 0, x ∈ C. |
Całkowity pierwiastek kwadratowy z x.
p 1, p 2 | – | kolejne przybliżenia pierwiastka z x, p 1, p 2 ∈ C. |
K01: | Jeśli x > 1, to idź do kroku K04 |
pierwiastki > 1 liczymy |
K02: | p 2 ← x | inne nie |
K03: | Idź do kroku K09 | |
K04: | p 1 ← 0 | zapewniamy |p 1 - p 2| > 1 |
K05: | p 2 ← x shr 1 | pierwsze przybliżenie pierwiastka |
K06: | Dopóki | p
1 - p 2 | > 1, wykonuj kroki K07...K08 |
; w pętli wyliczamy kolejne przybliżenia |
K07: | p 1 ← p 2 | zapamiętujemy bieżące przybliżenie |
K08: | p 2 ← ( p 2 + x div p 1 ) shr 1 | wyliczamy nowe przybliżenie |
K09: | Dopóki p 2 ×
p 2
> x, wykonuj p 2 ← p 2 - 1 |
jeśli przybliżenie było od góry, zmniejszamy je |
K09: | Zakończ z wynikiem p 2 |
Uwaga:
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. |
Pascal// Całkowity pierwiastek kwadratowy // Data: 11.05.2008 // (C)2020 mgr Jerzy Wałaszek //--------------------------------- program prg; var x, p1, p2 : longint; begin readln ( x ); if x <= 1 then p2 := x else begin p1 := 0; p2 := x shr 1; while abs ( p1 - p2 ) > 1 do begin p1 := p2; p2 := ( p2 + x div p2 ) shr 1; end; while p2 * p2 > x do dec ( p2 ); end; writeln ( p2 ); writeln ( p2 * p2 ); writeln; end. |
C++// Całkowity pierwiastek kwadratowy // Data: 11.05.2008 // (C)2020 mgr Jerzy Wałaszek //--------------------------------- #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; } |
Basic' Całkowity pierwiastek kwadratowy ' Data: 11.05.2008 ' (C)2020 mgr Jerzy Wałaszek '--------------------------------- Dim As Integer x, p1, p2 Input x If x <= 1 Then p2 = x Else p1 = 0: p2 = x Shr 1 While Abs ( p1 - p2 ) > 1 p1 = p2 p2 = ( p2 + x \ p2 ) Shr 1 Wend While p2 * p2 > x: p2 -= 1: Wend End If Print p2 Print p2 * p2 Print End |
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.
x | – | liczba, której pierwiastek obliczamy, x ≥ 0, x ∈ C |
Całkowity pierwiastek kwadratowy z x
m b | – | zawiera maskę bitową z ustawionym jednym bitem. Maska jest 64 bitowa. |
p x | – | obliczana wartość pierwiastka, p x ∈ C. |
K01: | p x ← 0 | początkowa wartość pierwiastka |
K02: | m b ← 1 shl 62 | maska z ustawionym drugim najstarszym bitem |
K03: | Dopóki m b
> x, wykonuj m b ← m b shr 2 |
szukamy najstarszej potęgi 4, mniejszej od x |
K04: | Dopóki m b
≠ 0, wykonuj kroki K05...K09 |
wyznaczamy kolejne bity pierwiastka |
K05: | t ← p x + m b | łączymy bit maski z przybliżeniem pierwiastka |
K06: | Jeśli
x <
t, idź do kroku K09 |
sprawdzamy, czy dany bit ma być ustawiony. |
K07: | x ← x - t | usuwamy bity z x |
K08: | p x ← t + m b | dodajemy bit maski do p x |
K09: | p x ← p x shr 1 | przesuwamy bity pierwiastka o 1 w prawo |
K09: | m b ← m b shr 2 | bity maski przesuwamy o 2 w prawo |
K10: | Zakończ z wynikiem p x |
Uwaga:
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. |
Pascal// Całkowity pierwiastek kwadratowy // Data: 11.05.2008 // (C)2020 mgr Jerzy Wałaszek //--------------------------------- program prg; var x, px, mb, t : qword; begin readln ( x ); px := 0; mb := 1 shl 62; while mb > x do mb := mb shr 2; while mb <> 0 do begin t := px + mb; if x >= t then begin dec ( x, t ); px := t + mb; end; px := px shr 1; mb := mb shr 2; end; writeln ( px ); writeln ( px * px ); writeln; end. |
C++// Całkowity pierwiastek kwadratowy // Data: 11.05.2008 // (C)2020 mgr Jerzy Wałaszek //--------------------------------- #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; } |
Basic' Całkowity pierwiastek kwadratowy ' Data: 11.05.2008 ' (C)2020 mgr Jerzy Wałaszek '--------------------------------- Dim As Ulongint x, px, mb, t Input x px = 0: mb = 1 Shl 62 While mb > x: mb = mb Shr 2: Wend While mb t = px + mb If x >= t Then x -= t: px = t + mb End If px = px Shr 1: mb = mb Shr 2 Wend Print px Print px * px Print End |
![]() |
Zespół Przedmiotowy Chemii-Fizyki-Informatyki w I Liceum Ogólnokształcącym im. Kazimierza Brodzińskiego w Tarnowie ul. Piłsudskiego 4 ©2023 mgr Jerzy Wałaszek |
Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.
Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.