УказательРазделыОбозначенияАвторО проекте


§

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


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

Задача. Для заданного натурального числа 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. (Другие задачи из этого источника см. ЗДЕСЬ ).


2018/12/03 10:09 редактировал au