.
Z treści zadania wiemy, że ciąg
xn jest zbieżny do wartości pierwiastka kwadratowego liczby
x. Jeśli pierwiastek z
x nie jest liczbą całkowitą, wówczas zbieżność ciągu
xn do √
x gwarantuje, że dla odpowiednio dużych
n wartość
xn znajduje się pomiędzy zaokrągleniem √
x w dół
do liczby całkowitej a zaokrągleniem √
x w górę do liczby całkowitej. Wykorzystując tę obserwację, rozwiązanie moglibyśmy uzyskać w poniższy sposób:
xi ←
x/2
dopóki prawda wykonuj
Rozwiązanie takie może jednak nie zadziałać poprawnie w sytuacji, gdy √x jest liczbą całkowitą. (A przynajmniej poprawność powyższego rozwiązania nie wynika z tego, że ciąg xn
zbiega do √x). W takiej sytuacji możliwe jest, że xn < √x dla wszystkich dużych n (dających
dobre przybliżenie √x). To z kolei oznacza, że dla p równego zaokrągleniu xn w dół mamy
(p + 1)⋅ (p + 1) ≤ x. W rezultacie nigdy nie będzie spełniony warunek zakończenia powyższej
pętli (p ⋅ p ≤ x oraz (p + 1)⋅ (p + 1) > x). Dla ilustracji tej sytuacji wyobraźmy sobie, że ciąg xn
dla x = 16 zbiega od dołu do 4, tzn. jego kolejne wartości są coraz bliższe 4, ale mniejsze niż 4.
(W rzeczywistości taka sytuacja nie ma miejsca dla x = 16, ale w oparciu o wiedzę szkolną nie
możemy wykluczyć podobnej sytuacji dla większego x, będącego kwadratem liczby naturalnej). Na przykład xn = 4 – 1/n. Wówczas w każdym obrocie powyższej pętli dopóki mamy
p = 3 i warunek p ⋅ p ≤ x oraz (p + 1)⋅ (p + 1) > x nie jest spełniony (mamy wtedy p = 3, x = 16).
Poniżej prezentujemy pełny algorytm uwzględniający sytuację, gdy √x jest liczbą całkowitą.
xi ← x/2
kontynuacja ← prawda
dopóki kontynuacja wykonuj