Algorytmy i Struktury Danych - Całkowity pierwiastek kwadratowy

Problem możemy rozwiązać następująco.

Tworzymy ciąg kwadratów kolejnych liczb całkowitych począwszy od 0:

\({0^2 \; 1^2 \; 2^2 \; 3^2 \; \dots \; 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\)	\(i^2\)
0	0
1	1
2	4
3	9
4	16
5	25
6	36
7	49
8	64
9	81
10	100
11	121
12	144
…	…

Teraz policzmy ciąg różnic pierwszego rzędu:

\({r_{1i} = i^2 - (i-1)^2, \text{ dla } i > 0}\).

Różnica pierwszego rzędu powstaje przez odjęcie od wyrazu \({i{-}\text{tego}}\) jego poprzednika w ciągu, czyli wyrazu \({(i-1){-}\text{szego}}\).

\(i\)	\(i^2\)	\(r_1\)
0	0	–
1	1	1
2	4	3
3	9	5
4	16	7
5	25	9
6	36	11
7	49	13
8	64	15
9	81	17
10	100	19
11	121	21
12	144	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_1i(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{-}\text{tej}}\) różnicy pierwszego rzędu odejmujemy poprzedzającą ją, \({(i-1){-}\text{szą}}\) różnicę.

\(i\)	\(i^2\)	\(r_1\)	\(r_2\)
0	0	–	–
1	1	1	–
2	4	3	2
3	9	5	2
4	16	7	2
5	25	9	2
6	36	11	2
7	49	13	2
8	64	15	2
9	81	17	2
10	100	19	2
11	121	21	2
12	144	23	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₁ = 1, r₂ = 2, 
gdzie a₀ – pierwszy wyraz ciągu kwadratów

Dla i > 0 mamy:

r_1i = r_1(i-1)+r₂ – 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 (dla małych liczb). 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 \ge 0, x \in \mathbb{R}}\).

Wyjście:

Całkowity pierwiastek kwadratowy z \(x\).

Elementy pomocnicze:

\(i\) : numery wyrazów ciągu kwadratów; \({i \in \mathbb{Z}}\).
\(a\) : wyraz ciągu kwadratów; \({a \in \mathbb{Z}}\).
\(r_1\) : różnica pierwszego rzędu; \({r_1 \in \mathbb{N}}\).
\(r_2\) : różnica drugiego rzędu; \({r_2 \in \mathbb{N}}\).

Lista kroków:

K01: a  ← 0 ; pierwszy kwadrat 0²K02: r₁ ← 1 ; początkowa wartość różnicy pierwszego rzędu
K03: r₂ ← 2 ; wartość różnic drugiego rzędu
K04: i  ← 0 ; numer pierwszego wyrazu
K05: Dopóki a ≤ x, ; szukamy pierwszego wyrazu a większego od x
     wykonuj K06…K08
K06:   a  ← a+r₁  ; następny kwadrat
K07:   r₁ ← r₁+r₂ ; wyliczamy nową różnicę pierwszego rzędu
K08:   i  ← i+1   ; następny numer
K09: Zakończ z wynikiem i-1 ; obliczony 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

Python (dodatek)

# Całkowity pierwiastek
# Data:   19.02.2024
# (C)2024 mgr Jerzy Wałaszek
# --------------------------

x = float(input())
a, r1, r2, i = 0, 1, 2, 0
while a <= x:
    a  += r1
    r1 += r2
    i  += 1
i -= 1
print(i)
print(i*i)
print()

Wynik:

135
11
121

JavaScript

<html>
  <head>
    <title>
      Pierwiastek
    </title>
  </head>
  <body>

<div style="overflow-x: auto;"
     align="center">
  <table
  border="0"
  cellpadding="4"
  style="border-collapse:
         collapse">
    <tr>
      <td nowrap>
        <form
        name="frm"
        style="text-align: center;
               background-color:
               #E7E7DA">
          <b>
          Obliczanie całkowitego<br>
          pierwiastka kwadratowego
          </b><br/>
          &nbsp;&nbsp;(C)2026 mgr
          Jerzy	Wałaszek
          &nbsp;&nbsp;
          <hr>
          x = <input
              type="text"
              name="inp_x"
              size="16"
              value="135"
              style="text-align:
                     right">
          <hr>
          <input
          type="button"
          value="Wykonaj"
          name="B1"
          onclick="main()">
          <hr>
          <b>Wynik:</b>
          <div id="out">.</div>
        </form>
      </td>
    </tr>
  </table>
</div>

<script type=text/javascript
        language=javascript>

// Całkowity pierwiastek
// Data:   10.05.2008
// (C)2008 mgr Jerzy Wałaszek
//---------------------------

function main()
{
  var x,i,a,r1,r2,t;

  x = parseFloat(document.frm
      .inp_x.value);
  if(!isNaN(x))
  {
    a  = 0;
    r1 = 1;
    r2 = 2;
    for(i = 0; a <= x; i++)
    {
      a  += r1;
      r1 += r2;
    }
    i--;
    t = i + "<br/>" + (i * i);
  }
  else
    t = "Złe dane wejściowe!";
  document.getElementById("out")
  .innerHTML = t;
}

</script>

  </body>
</html>

do podrozdziału do strony

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 = \dfrac{p+\dfrac{x}{p}}{2}\)

Dlaczego to działa? Rozważmy dwa przypadki:

\(p < \sqrt{x}\)

Wtedy iloraz \(\frac{x}{p}\) jest większy od \(\sqrt{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 > \sqrt{x}\)

Wtedy iloraz \(\frac{x}{p}\) jest mniejszy od \(\sqrt{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 \(\varepsilon\) – 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 \ge 0, \; x \in \mathbb{Z}}\).

Wyjście:

Całkowity pierwiastek kwadratowy z \(x\).

Elementy pomocnicze:

\(p_1, p_2\) : kolejne przybliżenia pierwiastka z \(x\); \({p_1, p_2 \in \mathbb{Z}}\).

Lista kroków:

K01: Jeśli x > 1,  ; pierwiastki > 1 liczymy
     to idź do kroku K04
K02: p₂ ← x ; inne nie
K03: Idź do kroku K09
K04: p₁ ← 0 ; zapewniamy |p₁-p₂| > 1
K05: p₂ ← x shr 1 ; pierwsze przybliżenie pierwiastka
K06: Dopóki |p₁-p₂| > 1: ; w pętli wyliczamy kolejne przybliżenia
     wykonuj kroki K07…K08
K07:   p₁ ← p₂ ; zapamiętujemy bieżące przybliżenie
K08:   p₂ ← (p₂+x div p₁) shr 1 ; wyliczamy nowe przybliżenie
K09: Dopóki p₂×p₂ > x: ; jeśli przybliżenie było od góry, 
     wykonuj p₂ ← p₂-1 ; zmniejszamy je
K09: Zakończ z wynikiem p₂

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.

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

Python (dodatek)

# Całkowity pierwiastek kwadratowy
# Data:   19.02.2024
# (C)2024 mgr Jerzy Wałaszek
# --------------------------

x = int(input())
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 -= 1
print(p2)
print(p2*p2)
print()

do podrozdziału do strony

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 \ge 0, \; x \in \mathbb{Z}}\).

Wyjście:

Całkowity pierwiastek kwadratowy z \(x\).

Elementy pomocnicze:

\(m_b\) : zawiera maskę bitową z ustawionym jednym bitem. Maska jest 64 bitowa.
\(p_x\) : obliczana wartość pierwiastka; \({p_x \in \mathbb{Z}}\).

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: ; szukamy najstarszej potęgi 4, mniejszej od x
     wykonuj m_b ← m_b shr 2
K04: Dopóki m_b ≠ 0: ; wyznaczamy kolejne bity pierwiastka
     wykonuj kroki K05…K09
K05: t ← p_x+m_b; łączymy bit maski z przybliżeniem pierwiastka
K06: Jeśli x < t, ; sprawdzamy, czy dany bit ma być ustawiony.
     idź do kroku K09
K07: x ← x-t  ; usuwamy bity z x
K08: p_x ← t+m_b; dodajemy bit maski do p_xK09: 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.

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

Python (dodatek)

# Całkowity pierwiastek kwadratowy
# Data:   19.02.2024
# (C)2024 mgr Jerzy Wałaszek
# --------------------------

x = int(input())
px = 0
mb = 1 << 62
while mb > x: mb >>= 2
while mb:
    t = px+mb
    if x >= t:
        x -= t
        px = t+mb
    px >>= 1
    mb >>= 2
print(px)
print(px*px)
print()

do podrozdziału do strony

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.

Całkowity pierwiastek kwadratowy

Problem

Rozwiązanie nr 1

Algorytm obliczania całkowitego pierwiastka kwadratowego – wersja nr 1

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy

Rozwiązanie nr 2

Algorytm obliczania całkowitego pierwiastka kwadratowego – wersja nr 2

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy

Rozwiązanie nr 3

Algorytm obliczania całkowitego pierwiastka kwadratowego – wersja nr 3

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy