Одной из вершин «арифметической премудрости» является таблица умножения. Мы учим её в начальной школе и должны помнить всю жизнь — или уже больше не должны, доверившись калькуляторам и компьютерам?
Даже простейший калькулятор легко перемножает шестизначные числа. Этого вполне достаточно не только для бытовых нужд, но и для большинства инженерных расчётов. В научных исследованиях приходится иметь дело и с более «длинными» числами — с десятками и сотнями десятичных знаков. Однако и в нашей повседневной жизни есть области, в которых совершаются арифметические действия с такими числами, хотя большинство людей об этом и не подозревает.
Пример — криптография. Когда мы делаем покупку в интернете, то, естественно, не хотим, чтобы передаваемые нами данные банковской карты стали известны ещё кому-либо, и поэтому весь обмен информацией с банком шифруется. Многие другие сетевые сервисы также используют защищённый протокол https, вместо обычного http. Шифры же часто основаны на больших простых числах.
Степень защиты информации напрямую зависит от величины используемых простых чисел. Ещё лет десять назад $128$-битные (т. е. имеющие 128 цифр в двоичной записи) простые числа обеспечивали достаточную надёжность. Сейчас, с прогрессом как вычислительной техники, так и математических методов, такие коды успешно «взламываются» и для надёжного шифрования приходится использовать $512$- и даже $1024$-битные простые числа.
Ясно, что работа с большими числами — дело компьютеров. Кажется, что нетрудно «обучить» компьютер арифметическим действиям, однако нам важно, чтобы он выполнял их не только правильно, но и быстро.
Из четырёх действий сложение и вычитание представляются более простыми, чем умножение и деление, но как сравнить их сложность (трудоёмкость) математически? Для этого можно посмотреть, как увеличивается количество выполняемых элементарных шагов с ростом длины чисел, над которыми производится действие. Шаг можно считать элементарным, если его трудность не зависит от длины чисел. Мерой трудоёмкости операции будем считать количество выполняемых элементарных шагов.
Для операции сложения элементарным шагом можно считать сложение двух цифр в одном разряде вместе с учётом переноса из предыдущего разряда и переноса в следующий разряд (представьте зрительно сложение «в столбик»). Количество таких элементарных шагов пропорционально длине складываемых чисел и, скажем, при удвоении этой длины трудоёмкость тоже удваивается.
Для операции умножения мерой трудоёмкости можно считать количество обращений к таблице умножения для цифр. При «школьном» методе перемножения двух чисел «в столбик» количество обращений к таблице умножения будет равно произведению длин чисел (каждую цифру первого числа необходимо умножить на каждую цифру второго). При удвоении длин сомножителей количество обращений к таблице увеличивается в 4 раза. Именно это отличие — возрастание трудоёмкости в 4, а не в 2 раза — делает этот алгоритм умножения намного более сложным при работе с «длинными» числами, чем алгоритм сложения.
Долгое время всем было «очевидно», что ничего лучше школьного способа для перемножения многозначных чисел быть не может. Основной аргумент был таков: если бы существовал более быстрый способ, его давно бы нашли. Полной неожиданностью стала публикация в 1961 году нового метода, найденного Анатолием Алексеевичем Карацубой, который в то время был аспирантом. Этот метод настолько прост, что о нём можно рассказывать даже школьникам.
Поясним основную идею метода Карацубы на примере перемножения двух восьмизначных чисел $a$ и $b$. Представим их в виде $$ a=10^4a_1+a_2,\quad b=10^4b_1+b_2, $$ где $a_1$, $a_2$, $b_1$, $b_2$ — четырёхзначные числа. Тогда $$ a\times b= (10^4a_1+a_2)(10^4b_1+b_2)=10^8a_1b_1+10^4(a_1b_2+a_2b_1)+a_2b_2. $$ Заметим, что произведения $a_1b_2$ и $a_2b_1$ нам нужны не сами по себе, а только в сумме. Эту сумму можно вычислить, если мы уже знаем произведения $a_1b_1$ и $a_2b_2$, ценой только одного дополнительного перемножения двух четырёхзначных чисел и нескольких «лёгких» операций сложения-вычитания, ибо $$ a_1b_2+a_2b_1=a_1b_1+a_2b_2-(a_1-a_2)(b_1-b_2). $$ Вот пример вычисления по описанной выше схеме. Пусть $$ a=63511377\quad\mbox{и}\quad b=81026989,$$ тогда $$ a_1=6351,\ a_2=1377,\quad b_1=8102,\ b2=6989. $$ Последовательно вычисляем: $$a_1−a_2=6351−1377=4974,$$ $$b_1−b_2=8102−6989=1113,$$ $$a_1b_1=6351\times 8102=51455802,$$ $$a_2b_2=1377\times 6989=9623853,$$ $$(a_1−a_2)(b_1−b_2)=4974\times 1113=5536062,$$ $$a_1b_2+a_2b_1=51455802+9623853−5536062=55543593.$$ По приведённой выше формуле произведение $a\times b$ равно $$ 5145580200000000 + 555435930000 + 9623853 = 5146135645553853 $$
Сравним на примере перемножения восьмизначных чисел трудоёмкость нового метода с трудоёмкостью традиционного.
При использовании школьного метода к таблице умножения требуется обратиться $8\times8=64$ раза.
В вычислениях по новому методу придётся найти три произведения четырёхзначных чисел. Если это делать школьным методом, то к таблице умножения придётся обратиться $3\times 4\times 4=48$ раз (умножение на степени числа 10 — это просто дописывание нулей, не требующее обращения к таблице).
Но ведь «по‐новому» можно перемножать и четырёхзначные числа, разбив каждое из них на два двузначных. По аналогии с разобранным выше примером, для перемножения четырёхзначных чисел достаточно найти три произведения двузначных чисел. Если эти произведения вычислять «по‐школьному», то потребуется $3\times (3\times 2 \times 2)=36$ обращений к таблице умножения. Ещё одно применение той же идеи уменьшит количество обращений к таблице умножения до $3^3=27$. Итог: путь вычислений будет пройден за 27 элементарных шагов вместо 64!
В общем случае при перемножении методом Карацубы двух $2^m$‐значных чисел требуется провести $3^m$ обращений к таблице умножения. Следовательно, при удвоении длин сомножителей трудоёмкость увеличивается лишь в 3 раза, а не в 4, как при «школьном» способе. Общий выигрыш тем больше, чем длиннее перемножаемые числа.
Выше длина числа измерялась по его представлению в десятичной системе счисления. При переходе к двоичному представлению длина записи чисел возрастает примерно в $3,3$ раза. По этой причине в двоичной системе счисления, в которой работают современные компьютеры, преимущества метода Карацубы проявляются начиная с меньших по значению чисел, чем в десятичной системе. Этот метод реализован во многих программах компьютерной алгебры и даёт большyю экономию времени вычислений.
В 1961 году метод Карацубы был революционным прорывом. После того, как стало ясно, что школьный метод не оптимален, многие математики задумались — а нельзя ли перемножать большие числа ещё быстрее, чем методом Карацубы? Оказалось, что можно. Например, разбивая каждый сомножитель на три части вместо двух, можно обойтись пятью перемножениями втрое более коротких чисел (найдите этот способ и оцените требуемое при этом количество элементарных шагов). Ещё эффективнее использовать меняющееся количество частей, а именно, разбивать $n$‐значное число на примерно $\sqrt{n}$ чисел такой же длины.
Удивительно, но исследование такого древнего арифметического действия, как умножение, продолжается и в наши дни. Когда же математики получат «моральное право» остановиться в поиске всё более и более быстрых способов умножения?
Давно считается правдоподобной гипотеза, что любой метод $M$ перемножения $n$‐значных чисел требует выполнения не менее, чем $C_M n \log n$ шагов, где $C_M$ — постоянная, зависящая от метода, но не от значения $n$.
Эту гипотезу пока никому доказать не удалось. Подобные результаты, называемые нижними оценками (сложности вычисления), обычно гораздо труднее верхних оценок. Для получения последних достаточно предъявить один конкретный алгоритм и оценить его трудоёмкость, в то время как для получения нижней оценки нужно суметь обозреть все мыслимые способы вычислить искомую величину.
Когда будет найден метод умножения за $C_M n \log n$ шагов (а математики к этому сейчас очень близки), а также будет доказана указанная выше гипотеза, то останется только борьба за уменьшение множителя $C_M$. С теоретической точки зрения эта задача считается малоинтересной, хотя для практического применения алгоритма значение этого множителя может оказаться критическим.
Читатель вправе спросить — а что с делением? Можно ли делить быстрее, чем учат в школе? Оказалось, что деление ненамного сложнее умножения. А именно, всякий метод перемножения $n$‐значных чисел, требующий $M(n)$ элементарных операций, можно преобразовать в метод для деления чисел такой же длины за $5 M(n)$ операций.
Среди основных арифметических действий есть сложение и вычитание — простые, «неулучшаемые», а есть умножение и деление — здесь можно бороться за уменьшение числа выполняемых операций. Быстрому умножению посвящена основная статья. Познакомимся теперь с упоминавшимся «быстрым» делением.
Следует различать две ситуации:
— деление одного целого числа на другое с получением неполного частного и остатка;
— получение приближённого значения отношения двух чисел, целых или десятичных.
Здесь мы рассмотрим вторую ситуацию.
Начнём с того, что заметим: общую операцию нахождения частного $c=a/b$ можно свести к специальному случаю — нахождению обратного числа $d=1/b$. После этого искомый ответ получается как результат (быстрого) перемножения: $c=a\times d$.
Найти число, обратное к $b$, означает: решить уравнение $by=1$.
Предположим, что выбрано начальное приближение — число $y_0$, примерно равное решению этого уравнения. Мы увидим, сколь точно это приближение, когда вычислим произведение $b\times y_0$. Оно должно быть близко к 1, что можно представить формулой $$ b\times y_0=1-\varepsilon, $$ где $\varepsilon$ — некоторое число с малой абсолютной величиной.
Домножив обе части этого равенства на $1+\varepsilon$, получим $$ b\times y_0\times (1+\varepsilon)=1-\varepsilon^2. $$ Это равенство можно интерпретировать так: если $|\varepsilon|<1$, то число $$ y_1=y_0\times (1+\varepsilon) $$ является более хорошим приближением к $1/b$, чем $y_0$, ибо $\varepsilon^2<|\varepsilon|$.
Заметим, что для вычисления $y_1$ нам не требуется предварительно находить $\varepsilon$, новое приближение можно вычислить по формуле $$ y_{1}=y_0\times(2-b\times y_0). $$ Процесс улучшения приближения можно продолжить, вычисляя последовательно $$ \eqalign{ y_2 &=y_1\times(2-b\times y_1),\cr y_3 &=y_2\times(2-b\times y_2)\cr }$$ и т. д. Легко проверить, что $$ b \times y_k=1-\varepsilon ^{2^k}, $$ так что действительно получаются всё более и более точные приближения к $1/b$.
Вот численный пример такого итерационного вычисления. Пусть $$ b=2,8062865 $$ и выбрано начальное приближение $y_0=0{,}4$. Последовательно находим: $$ \eqalign{ y_1 &=0{,}40\times(2-2{,}8\times0{,}40)=0{,}3520,\cr y_2 &=0{,}3520\times(2-2{,}806\times0{,}3520)=0{,}356325376,\cr y_3 &=0{,}35632538\times(2-2{,}8062865\times0{,}35632538)=0{,}35634280…\cr}$$ Всего три итерации, и мы получили 8 верных цифр числа $1/b$.
Обратите внимание, что на первом шаге использовались лишь 2 значащие цифры чисел $b$ и $y_0$, на втором шаге — лишь 4 значащие цифры чисел $b$ и $y_1$, и только на третьем шаге вычисления проводились с восьмизначными числами. Большая точность на начальных шагах не требуется, длина используемых там чисел должна соответствовать точности получаемых приближений. В итоге трудоёмкость последнего шага в таком итерационном процессе оказывается большей, чем трудоёмкость всех предыдущих шагов, вместе взятых. Таким образом, работа по нахождению частного $a/b$ с $n$ знаками оказывается не более сложной, чем 5 перемножений $n$‐значных чисел.
Аналогичным образом осуществляется быстрое деление целых чисел с остатком.
По аналогии с описанным выше читатель теперь может самостоятельно свести решение уравнения $by^2$=1 к последовательности умножений. Домножение полученного решения на $b$ даст, как легко понять, $\sqrt{b}$.
Гашков С. Б. Занимательная компьютерная арифметика. — М.: URSS, 2015.
Карацуба А. А. Сложность вычислений
Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. — М.: Мир, 1979.
Ахо А. В., Хопкрофт Дж. Э., Ульман Дж. Д. Структуры данных и алгоритмы. — М.—СПб.—Киев: Вильямс, 2007.
Кнут Д. Искусство программирования. — Т. 2: Получисленные алгоритмы. — М.: Мир, 1977. — [§ 4.3.3 «Насколько быстро можно выполнять умножение»].
