Великие люди-счетчики
Стивен Смит. 1983

Извлечение корней

В последние годы вычислители демонстрируют извлечение корней больших степеней, и успехи в данном виде заинтересовали Книгу Рекордов Гиннесса. В 11 издании (1972:43) было сообщено, что 5 Октября 1970 года, Герберт Б. дэ Грот из Мехико извлек в уме корень 13-й степени из 100-значного числа за 23 минуты.

С тех пор извлечение корней высоких степеней стало чрезвычайно популярно, без сомнения благодаря доступности компьютеров, как для производства данных с которыми вычислители могут создать алгоритмы так и для предоставления самих заданий для выступлений.

В 16-м издании (1977), был представлен рекорд Вима Клейна из Нидерландов, который извлек корень 23-й степени из 200-значного числа за 10.5 минут. В издании 1978 года сообщено что Клейн извлек корень 73-степени из 500-значного числа за 2 минуты 43 секунды.

Трудности с извлечением точных корней мало зависят от величины степени. Гораздо более важно количество цифр в ответе и конкретные особенности выбранных степеней (отметим, что ни в одном из случаев не использовались четные степени). Митчелл (1907, стр. 94) замечает: "в основном, большие степени облегчают проблему, и квадратные или кубические корни наиболее часто используются." В этом отношении времена изменились.

Книга Рекордов Гиннеса сейчас считает корень 13-й степени из 100-значного числа как стандартный тест возможностей по извлечению точных корней. Вим Клейн держит рекорд в этом упражнении со временем менее чем две минуты. Клейн комментирует: "Проблема тем сложнее, чем больше цифр в ответе. Корень 23-й степени из 200-значного числа имеет девять цифр в результате, и это столько же, сколько корень седьмой степени из 63-значного числа. Корень 13-й степени из 100 цифр имеет 8 знаков, а корень 19-й степени из 133 цифр и 73-й степени из 500 цифр имеют только семь знаков. Я не вижу дальнейшего интереса в семизначных ответах. Для меня сейчас это просто игра."

"С восьмью знаками, одна цифра сложно распознаваема, и это требует использования специальных тестов. С девятью знаками уже две неизвестных в середине, что делает работу значительно более жесткой. Кубический корень из 30 цифр дает десять знаков - и это просто адова работа."

Метод Клейна по извлечению корня 13-й степени может быть проиллюстрирован на следующем числе: 14762420839370760705665953772022217870318956930659
27236796230563061507768203333609354957218480390144

Первые пять знаков корня находятся с помощью логарифмов. Клейн помнит до пятого знака логарифмы всех натуральных чисел до 150, что в паре с его способностью разлагать на множители большие числа позволяет ему аппроксимировать логарифмы первых пяти знаков степени, что обычно достаточно для определения первых пяти цифр корня, хотя, как он сам замечает "пятая цифра немного рискованная."

Клейн начинает с разложения 1476 на произведение 36 на 41 и использования логарифма (десятичного) каждого из них: log(36)=1.55630, а log(41)=1.61278; суммирование мантисс дает 0.16908, но этого, конечно, мало. Используя различные интерполяции Клейн выясняет, что мантисса логарифма числа 147624 равна 0.16925 (это почти 0.16916).

Таким образом Клейн получает приближение логарифма 100-значного числа полностью - 99.16925. Это число должно быть разделено на 13 для получения логарифма ответа. Поскольку 99=13X7 с остатком 8, чтобы получить мантиссу антилогарифма 13-го корня он делит 8.16925 на 13, что приблизительно дает 0.62840. Оценив антилогарифм как половину между 4.2 и 4.3 он решил попробовать 4.25. Результат был точен, и получилось, что первые пять цифр корня должны быть 42500, как и оказалось на самом беле.

Теперь необходимо определить последние три цифры корня. Это он делает исследуя последние три цифры степени. В случае с нечетным числом, они однозначно определяют последние три цифры корня, но в случае четных корней, как здесь, этот метод предлагает четыре возможности; в случае с 144 возможны ответы 014, 264, 514 и 764. (Они всегда отличаются друг от друга на 250) Для выбора правильного варианта Клейн делит исходное число на 13 и запоминает остаток. В случае с 13-й степенью, остаток корня и степени должны быть одинаковыми. Остаток степени 7; только 764 как окончание корня дает в остатке 7. Таким образом искомый корень 13-й степени определяется как 42.500.764.

Как вариант нечетного числа возьмем:
75185285487713563581947553291145079861723813162341
53935861550997297991815299022662358976308065985831

Первые пять цифр степени 75185, что близко к 7519, а 7519 можно представить как 73 на 103. Мантисса логарифма 73 равна 0.86332, а 103 - 0.01284. Их сумма 0.87616. Деление 8.87616 на 13 дает 0.68278. Это расположено между мантиссой логарифмов 48 и 49, но гораздо ближе к 48. Поскольку 481 это 13 (мантисса 0.11394) на 37 (мантисса 0.56820), мантисса их логарифмов будет 0.68214; сделано но слишком приближенно; 4816 может быть разложено на 16 (мантисса 0.20412) помноженное на 7 (мантисса 0.84510) и на 43 (мантисса 0.63347). Это дает мантиссу 0.68269. 4818 раскладывается на 66 (мантисса 0.81954) умноженное на 73 (мантисса 0.86332), что дает мантиссу 0.68286. Таким образом, интерполируя мы хотим получить 9/17 от 20, что приблизительно 10?. Первые пять цифр корня должны быть 48170 (48160 + 10). И действительно это так.

Когда Клейн действительно делал вычисления то сделал небольшую ошибку (он искал антилогарифм 0.68277 вместо 0.68278) и сначала взял 48169 для первых пяти цифр корня. В этом случае, однако, раз корень нечетный, последние три цифры имеют уникальное соответствие и поскольку степень оканчивается на 831, корень должен оканчиваться на 311. При делении степени на 13 Клейн получает остаток 7. Но деление 48169311 на 13 дает остаток 8. Для приведения обоих остатков в соответствие он меняет результат на 48170311, что является правильным ответом.