Инструменты сайта


§

Вспомогательная страница к разделу НАЧАЛА ТЕОРИИ ЦЕЛЫХ ЧИСЕЛ


Извлечение корней из целых чисел

Задача. Для заданного натурального числа $ 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 $ означает целую часть числа.

§

В качестве стартового значения можно брать $ B_0=\lfloor B/3 \rfloor +1 $.

П

Пример. Вычислить $ \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 $ и т.д. Доказать, что все полученные таким образом числа будут точными квадратами.

§

Идейной основой алгоритма, изложенного в теореме, является метод Ньютона решения нелинейного уравнения $ f_{}(x)=0 $. При некоторых условиях на функцию $ f_{}(x) $ и стартовое значение $ x_{0} $ итерационная последовательность $$ x_j = x_{j-1} - \frac{f(x_{j-1})}{f^{\prime}(x_{j-1})} \quad npu \ \ j\in \{1,2,\dots \ \} $$ будет монотонно сходиться к корню уравнения. Легко проверить, что последовательность из теоремы является просто «округлением до целого» последовательности метода Ньютона, составленной для решения уравнения $ x^2-B=0 $. Почти всегда такое усечение происходит безнаказанно; однако иногда все же приводит к цикличности итерационной последовательности.

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

Т

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

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

Источники

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

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

numtheory/issquare.txt · Последние изменения: 2020/04/28 23:36 — au