Całkowity pierwiastek kwadratowy


Tematy pokrewne   Podrozdziały
Przedziały liczbowe i liczby
Liczby parzyste i nieparzyste
Liczby podzielne lub niepodzielne przez zadane podzielniki
Ciągi arytmetyczne
NWD – algorytm Euklidesa
Liczby względnie pierwsze
Najmniejsza wspólna wielokrotność
Odwrotność modulo – rozszerzony algorytm Euklidesa
Liczby pierwsze – generacja przez sprawdzanie podzielności
Liczby pierwsze – generacja sitem Eratostenesa
Liczby pierwsze – generacja sitem liniowym
Liczby pierwsze – generacja sitem Atkina-Bernsteina
Czynniki pierwsze – metoda próbnych dzieleń
Czynniki pierwsze – metoda Fermata
Pierwszość liczby naturalnej – algorytmy naiwne
Pierwszość liczby naturalnej – Chiński Test Pierwszości
Pierwszość liczby naturalnej – Małe Twierdzenie Fermata
Pierwszość liczby naturalnej – test Millera-Rabina
Liniowe generatory liczb pseudolosowych
Generator pseudolosowy Park-Miller
Generator pseudolosowy Mersenne Twister
Wbudowane generatory liczb pseudolosowych
Generowanie liczb pseudolosowych
Liczby Fibonacciego
System liczbowy Fibonacciego
Całkowity pierwiastek kwadratowy
  Rozwiązanie 1
Rozwiązanie 2
Rozwiązanie 3
 

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ść:

 

p2x

 

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 ...i2

 

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:

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

Wejście
x  –  liczba, której pierwiastek obliczamy, x ≥ 0, x R
Wyjście:

całkowity pierwiastek kwadratowy z x

Elementy pomocnicze:
i  –  numery wyrazów ciągu kwadratów, i C
a  – wyraz ciągu kwadratów, a C
r1  – różnica pierwszego rzędu, r1 N
r2  – różnica drugiego rzędu, r2 N
Lista kroków:
K01: a ← 0 ; pierwszy kwadrat 02
K02: r1 ← 1 ; początkowa wartość różnicy pierwszego rzędu
K03: r2 ← 2 ; wartość różnic drugiego rzędu
K04: i ← 0 ; numer pierwszego wyrazu
K05: Dopóki ax wykonuj K06...K08 ; szukamy pierwszego wyrazu a większego od x
K06:     aa + r1 ; następny kwadrat
K07:     r1r1 + r2 ; wyliczamy nową różnicę pierwszego rzędu
K08:     ii + 1 ; następny numer
K09: Zakończ z wynikiem i - 1 ; obliczamy pierwiastek całkowity

 

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.

 

Lazarus
// Całkowity pierwiastek
// Data:   10.05.2008
// (C)2012 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.
Code::Blocks
// Całkowity pierwiastek
// Data:   10.05.2008
// (C)2012 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;
}
Free Basic
' Całkowity pierwiastek
' Data:   10.05.2008
' (C)2012 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)2012 mgr Jerzy Wałaszek

x =


...

 

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:

 

p = 

 1  (p +   x  )
 2  p

 

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
Lista kroków:
K01: Jeśli x > 1, to idź do K04 ; pierwiastki > 1 liczymy
K02: p2x ; inne nie
K03: Idź do K09  
K04: p1 ← 0 ; zapewniamy |p1 - p2| > 1
K05: p2x shr 1 ; pierwsze przybliżenie pierwiastka
K06: Dopóki |p1 - p2| > 1, wykonuj K07...K08 ; w pętli wyliczamy kolejne przybliżenia
K07:     p1p2 ; 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 p2p2 - 1 ; jeśli przybliżenie było od góry, zmniejszamy je
K09: Zakończ z wynikiem p2  

 

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.

 

Lazarus Code::Blocks Free Basic
// Całkowity pierwiastek kwadratowy
// Data:   11.05.2008
// (C)2012 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.
// Całkowity pierwiastek kwadratowy
// Data:   11.05.2008
// (C)2012 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;
}
' Całkowity pierwiastek kwadratowy
' Data:   11.05.2008
' (C)2012 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

 

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, 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
Lista kroków:
K01: px ← 0 ; początkowa wartość pierwiastka
K02: mb ← 1 shl 62 ; maska z ustawionym drugim najstarszym bitem
K03: Dopóki mb > x, wykonuj mbmb shr 2 ; szukamy najstarszej potęgi 4, mniejszej od x
K04: Dopóki mb ≠ 0, wykonuj K05...K09 ; wyznaczamy kolejne bity pierwiastka
K05:     tpx + mb ; łączymy bit maski z przybliżeniem pierwiastka
K06:     Jeśli x < t, idź do K09 ; sprawdzamy, czy dany bit ma być ustawiony.
K07:     xx - t ; usuwamy bity z x
K08:     pxt + mb ; dodajemy bit maski do px
K09:     pxpx shr  1 ; przesuwamy bity pierwiastka o 1 w prawo
K09:     mbmb shr 2 ; bity maski przesuwamy o 2 w prawo
K10: Zakończ z wynikiem px  

 

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.

 

Lazarus Code::Blocks Free Basic
// Całkowity pierwiastek kwadratowy
// Data:   11.05.2008
// (C)2012 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.
// Całkowity pierwiastek kwadratowy
// Data:   11.05.2008
// (C)2012 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;
}
' Całkowity pierwiastek kwadratowy
' Data:   11.05.2008
' (C)2012 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

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.