Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2021 mgr Jerzy Wałaszek
I LO w Tarnowie

Całkowity pierwiastek kwadratowy

SPIS TREŚCI
Podrozdziały

Problem

Znaleźć 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

Rozwiązanie nr 1

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:

  • ciągu kwadratów i 2 → 0
  • ciągu różnic pierwszego rzędu r 1i → 1
  • ciągu różnic drugiego rzędu r 2i → 2

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.

Algorytm obliczania całkowitego pierwiastka kwadratowego – wersja nr 1

Wejście:

x  –  liczba, której pierwiastek obliczamy, x ≥ 0, xR.

Wyjście:

całkowity pierwiastek kwadratowy z x.

Zmienne pomocnicze:

i  –  numery wyrazów ciągu kwadratów, i  ∈ C.
a  – wyraz ciągu kwadratów, aC.
r 1  – różnica pierwszego rzędu, r 1   ∈ N.
r 2  – różnica drugiego rzędu, r 2   ∈ N.

Lista kroków:

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 1r 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

Przykładowe programy

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
Obliczanie całkowitego pierwiastka kwadratowego
(C)2020 mgr Jerzy Wałaszek

x =


...

Na początek:  podrozdziału   strony 

Rozwiązanie nr 2

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.

Algorytm obliczania całkowitego pierwiastka kwadratowego – wersja nr 2

Wejście:

x  –  liczba, której pierwiastek obliczamy, x ≥ 0, xC.

Wyjście:

Całkowity pierwiastek kwadratowy z x.

Zmienne pomocnicze:

p 1, p 2  –  kolejne przybliżenia pierwiastka z x, p 1, p 2   ∈ C.

Lista kroków:

K01: Jeśli x  > 1,
to idź do kroku K04
pierwiastki > 1 liczymy
K02: p 2x inne nie
K03: Idź do kroku K09  
K04: p 1 ← 0 zapewniamy |p 1 - p 2| > 1
K05: p 2x  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 1p 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 2p 2 - 1
jeśli przybliżenie było od góry, zmniejszamy je
K09: Zakończ z wynikiem p 2  

Przykładowe programy

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
Na początek:  podrozdziału   strony 

Rozwiązanie nr 3

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, xC

Wyjście:

Całkowity pierwiastek kwadratowy z x

Zmienne pomocnicze:

m b  –  zawiera maskę bitową z ustawionym jednym bitem. Maska jest 64 bitowa.
p x  – obliczana wartość pierwiastka, p x C.

Lista kroków:

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  

Przykładowe programy

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
Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2021 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.