Быстрая арифметика

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

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

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

Кара­цуба А. А. Слож­ность вычис­ле­ний // Труды Матема­ти­че­ского инсти­тута имени В. А. Стек­лова. 1995. Т. 211. Стр. 169—183. — [Исто­рия вопроса].

Ахо А., Хоп­к­рофт Дж., Ульман Дж. Постро­е­ние и ана­лиз вычис­ли­тель­ных алго­ритмов. — М.: Мир, 1979.

Ахо А. В., Хоп­к­рофт Дж. Э., Ульман Дж. Д. Струк­туры дан­ных и алго­ритмы. — М.—СПб.—Киев: Вильямс, 2007.

Кнут Д. Искус­ство программи­ро­ва­ния. — Т. 2: Полу­чис­лен­ные алго­ритмы. — М.: Мир, 1977. — [§ 4.3.3 «Насколько быстро можно выпол­нять умноже­ние»].