Cтр. 86

Быстрая арифметика
Поделиться…

Одной из вершин «арифметической премудрости» является таблица умножения. Мы учим её в начальной школе и должны помнить всю жизнь — или уже больше не должны, доверившись калькуляторам и компьютерам?

Даже простейший калькулятор легко перемножает шестизначные числа. Этого вполне достаточно не только для бытовых нужд, но и для большинства инженерных расчётов. В научных исследованиях приходится иметь дело и с более «длинными» числами — с десятками и сотнями десятичных знаков. Однако и в нашей повседневной жизни есть области, в которых совершаются арифметические действия с такими числами, хотя большинство людей об этом и не подозревает.

Пример — криптография. Когда мы делаем покупку в интернете, то, естественно, не хотим, чтобы передаваемые нами данные банковской карты стали известны ещё кому–либо, и поэтому весь обмен информацией с банком шифруется. Многие другие сетевые сервисы также используют защищённый протокол 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$–значных числа можно перемножить, выполнив $f(n) n\log n$ элементарных операций, где $f(n)$ — функция, растущая с ростом $n$ настолько медленно, что для практических целей её можно считать константой (постоянной).

Правдоподобной считается гипотеза, что два $n$–значных числа нельзя перемножить быстрее, чем за $Cn\log n$ шагов, где $C$ — постоянная, но пока никому это доказать не удалось. Такие результаты, называемые нижними оценками (сложности вычисления), обычно гораздо труднее верхних оценок. Для получения верхней оценки достаточно предъявить конкретный алгоритм и оценить его трудоёмкость, в то время как для получения нижней оценки нужно суметь обозреть все мыслимые способы вычисления искомой величины.

Читатель вправе спросить — а что с делением? Можно ли делить быстрее, чем учат в школе? Оказалось, что деление ненамного сложнее умножения. А именно, всякий метод перемножения $n$–значных чисел, требующий $M(n)$ элементарных операций, можно преобразовать в метод для деления чисел такой же длины за $5 M(n)$ операций.

Удивительно, но исследование такой древней задачи, как перемножение чисел, продолжается до сих пор — последнее улучшение было получено в 2014 году.

Когда же математики «получат моральное право» больше не пытаться улучшить алгоритм умножения? Тогда, когда полученные верхние и нижние оценки фактически совпадут, т. е. будут различаться лишь на постоянный множитель. Это будет означать, что существенное дальнейшее ускорение уже невозможно.

Дополнение для заинтересованного читателя. Среди основных арифметических действий есть простые — сложение и вычитание (об этом уже говорилось), быстро умножать мы уже научились. Приведём для полноты схематическое описание упоминавшегося «быстрого» деления.

Следует различать две ситуации:

 — деление одного целого числа на другое с получением неполного частного и остатка;

 — получение приближённого значения отношения двух чисел, целых или десятичных.

Здесь мы рассмотрим вторую ситуацию.

Начнём с того, что заметим: общую операцию нахождения частного $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-\smash{\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-\smash{\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.