Задача. Для заданного натурального числа $ B_{} $ установить является ли оно полным квадратом и в этом случае определить $ \sqrt{B} $.

Теорема [1]. Пусть $ B_0 $ — произвольное целое такое, что $ B_0^2>B $. Последовательность

$$ B_j = \begin{array}{c} \left\lfloor \begin{array}{c} B_{j-1}+ \left\lfloor \displaystyle \frac{B}{B_{j-1}} \right\rfloor_{} \\ \hline 2 \end{array} \right\rfloor \\ \end{array} \quad npu \ \ j\in \{1,2,\dots \ \} \ , $$ монотонно убывая, сойдется за конечное число шагов к значению $ \left\lfloor\sqrt{B} \right\rfloor $, если только число $ B+1 $ не является полным квадратом. Здесь $ \lfloor \ \ \ \rfloor $ означает целую часть числа.

Пример. Вычислить $ \left\lfloor\sqrt{611524} \right\rfloor $.

Решение. $ B_0=203842 $. Далее последовательность из теоремы:

$$ B_1= 101922 \, ,\ B_2=50963 \, ,\ B_3=25487 \, , \ B_4=12755 \, \ , B_5=6401 \, ,$$ $$ \ B_6=3248\, , \ B_7=1718 \, ,\ B_8=1036 \, ,\ B_9=813\, , \ B_{10}=782\, , B_{11}=782\, , \dots $$ выходит на стационарное значение. Здесь $ 782^2=611524 $, т.е. исходное число — полный квадрат.

Пример. Вычислить $ \left\lfloor\sqrt{10414} \right\rfloor $.

Решение. Возьмем $ B_0=\lfloor B/3 \rfloor +1 =3472 $. $$ B_1=1737,\ B_2=871,\ B_3=441,\ B_4=232,\ B_5=138,\ B_6=106,\ B_7=102,\ B_8=102,\dots $$ Здесь $ 102^2=10404 $ и $ 102= \left\lfloor\sqrt{10414}\right\rfloor $.

Пример. Вычислить $ \left\lfloor\sqrt{80} \right\rfloor $.

Решение. $$ B_0=27\, ,\ B_1=14 \, ,\ B_2=9\, ,\ B_3=8 \, ,\ B_4=9\, ,\ B_5=8\, , \dots $$ Видим, что если число $ B+1 $ является полным квадратом, то последовательность $ \{ B_j \} $ из теоремы, начиная с какого-то места, становится циклической — она «прыгает» между числами $ \left\lfloor\sqrt{B} \right\rfloor $ и $ \left\lfloor\sqrt{B} \right\rfloor+1 $.

[2]. Написано число $ 49 $. Между цифрами $ 4 $ и $ 9 $ вставили $ 48 $, в полученное число $ 4489 $ между цифрами $ 4 $ и $ 8 $ опять вписали $ 48 $ и т.д. Доказать, что все полученные таким образом числа будут точными квадратами.

Разумеется, идею метода Ньютона можно использовать и для решения более сложных задач, например, для вычисления $ \left\lfloor\sqrt[n]{B}\right\rfloor $ при $ n>2 $. Приведем соответствующий результат для случая $ n_{}=3 $.

Теорема. Пусть $ B_{0} $ — произвольное целое такое, что $ B_0^3>B>1 $. Последовательность

$$ B_j = \left\{\left\lfloor \frac{2}{3}B_{j-1} + \frac{B}{3B_{j-1}^2} \right\rfloor \right\}_{j=1}^{\infty} \, , $$ монотонно убывая, сойдется за конечное число шагов к значению $ \left\lfloor\sqrt[3]{B} \right\rfloor $.

[1]. Нодден П., Китте К. Алгебраическая алгоритмика. М.Мир. 1999.

[2]. Шмулевич П.К. Сборникъ задачъ, предлагавшихся на конкурсныхъ экзаменахъ при поступленiи въ спецiaльныя высшiя учебныя заведенiя. Часть II. Алгебра. Изданiе VIII. С.-Петербург. 1915. (Другие задачи из этого источника см. ☞ ЗДЕСЬ ).