Создан новый способ быстрого умножения огромных чисел
Умножение длинных чисел в уме — настоящая головная боль для всех детей с самой начальной школы. Однако математик разработал новый метод умножения больших чисел, который намного эффективнее привычного нам.
Василий Макаров
Дэвид Харли, доцент из Университета Нового Южного Уэльса в Сиднее обратился к алгоритму Шёнхаге – Штрассена, разработанному двумя немецкими математиками. В период с 1971 года по 2007 это был самый быстрый способ умножения чисел, пока ему на смену не пришла альтернатива (справедливости ради стоит отметить, что используют ее крайне редко).
Не занимайтесь самолечением! В наших статьях мы собираем последние научные данные и мнения авторитетных экспертов в области здоровья. Но помните: поставить диагноз и назначить лечение может только врач.
youtube
Нажми и смотри
Шенхаге и Штрассен предсказали существование алгоритма умножения n-значных чисел с использованием базовых операций формата n * log (n).
Так в чем же суть? Для примера Харви выбрал умножение чисел 314 и 159 — с подобными числами мы сталкиваемся каждый день. Обычно, чтобы решить подобное уравнение, большинство людей перемножает каждый отдельный номер, а затем складывают суммы. Так, 9 умножается на 4,1 и 3, затем 5 умножается на 4, 1 и 3, и так далее. В результате сложения всех результатов и получается искомое 9-значное число.
Этот метод называется n2, потому что число n умножается на n несколько раз. Получите ли вы правильный ответ? Безусловно. Однако еще в 1971 году немцы придумали, как ускорить процесс. Они записывали его как n * log (n). Напомним, что log — это сокращение от «логарифма», который помогает нам расшифровывать числа, возведенные в степень. Например, 2⁵ = 32, но если записать это уравнение логарифмически, то получится log₂ (32) = 5. Звучит просто, однако по-настоящему логарифмы начинают упрощать процесс в работе с крупными числами.
Харви уверен, что метод Шёнхаге-Штрассена очень практичен. По его словам, если обычному компьютеру дать задачу перемножить между собой два числа с миллиардом знаков в каждом, используя «школьный» метод — это заняло бы месяцы. А если дать ему ту же задачу, но использовать при этом подход с логарифмами, то вся операция займет… от силы секунд 30.
Впрочем, и тут есть пределы. математик отмечает, что если число знаков будет составлять триллион и больше, то здесь пригодится алгоритм, разработанный Харви и его сотрудником Йорисом ван дер Хувеном в Политехнической школе во Франции в 2007 году. «С его помощью можно будет вычислить значение числа «пи» с еще большей точностью. Человечество 50 лет охотилось за таким удобным способом работы с огромными простыми числами — и теперь он наконец в нашем распоряжении», — говорит сам Харви.
Лучше, чем в столбик: новый способ перемножать большие числа
- Технологии
- Алексей Алексенко Автор
Австралийский математик нашел максимально эффективный алгоритм перемножения больших чисел. В рубрике «Техно-уик-энд» научные разработки, далекие от практики, но позволяющие лучше понять окружающий мир
Дэвид Харви, сотрудник университета Нового Южного Уэльса в Сиднее, и его французский коллега Йорис Ван дер Хэвен решили задачу, поставленную математиками еще полвека назад. Речь идет о доказательстве гипотезы Шёнхаге — Штрассена. Согласно этой гипотезе, возможен такой алгоритм перемножения целых N-значных чисел, что число шагов алгоритма с возрастанием числа не будет увеличиваться быстрее, чем N * logN.
Закончили чтение тут
Простейший алгоритм умножения знаком всем с начальной школы, это так называемое умножение в столбик. Чтобы перемножить два числа, надо по существу умножить каждую цифру первого числа на каждую цифру второго, а потом еще выполнить несколько сложений и расположить результаты в правильном порядке. Ключевой этап — перемножение цифр: если наши числа трехзначные, придется обратиться к таблице умножения 9 раз, а если пятизначные — 25 раз. В общем случае число таких процедур увеличивается пропорционально числу знаков в перемножаемых числах, возведенному в квадрат. И если эти числа достаточно велики, то количество шагов алгоритма становится поистине огромным.
В 1950-х годах советский математик Анатолий Карацуба обнаружил способ уменьшить сложность алгоритма умножения. В его алгоритме число шагов увеличивается не быстрее, чем N1,58 — это существенно меньше, чем N2.
Впрочем, если читателю вздумается ознакомиться с алгоритмом Карацубы, он обнаружит, что при этом сам метод существенно сложнее обычного школьного умножения. Согласно оценкам, его преимущество проявляется, начиная с чисел, имеющих не менее 10 000 десятичных разрядов.
Десять лет спустя проблемой занялись два немецких математика, которые предложили еще более экономичный алгоритм — с числом шагов не больше чем N * logN * log(logN). Алгоритм Шёнхаге — Штрассена, однако, тоже не оптимален, эти же математики предположили, что возможно перемножать большие числа так, чтобы число шагов не росло быстрее чем N * logN. Однако ни предложить конкретный способ, ни даже доказать его возможность не удавалось вплоть до настоящего времени.
Насколько подобные математические приемы способны ускорить реальные вычисления? По словам Харви, чтобы перемножить два числа с миллиардом десятичных знаков, современному компьютеру понадобится около месяца.
Применение алгоритма Шёнхаге — Штрассена позволит уложиться в 30 секунд. Алгоритм, способ построения которого предлагает сам Харви, справится с задачей еще быстрее. Более того, математики предполагают, что это, вероятно, и есть теоретически возможный предел скорости умножения, хотя строго доказать эту гипотезу им пока не удалось. Однако если это так, данную математическую задачу можно считать окончательно решенной.
Насколько большим должно быть число, чтобы алгоритм Харви — Ван дер Хэвена дал преимущество в скорости вычисления? «Понятия не имею», — честно отвечает Харви, однако в своей статье он приводит в качестве примера умножение, дающее результат 10214857091104455251940635045059417341952. Это действительно очень большое число: во всей видимой Вселенной, к примеру, содержится всего порядка 1080 элементарных частиц.
Умножение — неотъемлемая часть других вычислительных процедур, таких как деление или извлечение корней. Данный результат окажется полезным и тем, кто намерен вычислить много-премного знаков числа пи или, к примеру, расширить список известных человечеству простых чисел.У этой работы есть еще одно интересное следствие. При обосновании преимуществ квантового компьютера нередко приводят в качестве примера алгоритмы шифрования. Эти алгоритмы часто построены на разложении очень больших чисел на множители. Квантовый алгоритм Шора справляется с этой задачей довольно легко, тогда как для классического алгоритма разложение достаточно большого числа потребует времени, сравнимого с возрастом Вселенной. Однако в этих примерах всегда неявно подразумевается, что эффективность классического алгоритма — величина, определенная раз и навсегда. Работа австралийского и французского математиков показывают, что это далеко не так. А вдруг математики будущего предложат настолько изящный классический способ разложения числа на множители, что существующие шифры легко можно будет взломать не только на квантовом, но и на классическом компьютере? Сравнение квантовых и классических алгоритмов некорректно, пока не показано, что и тот и другой действительно являются лучшими из теоретически возможных.
Остается добавить, что работа математиков пока опубликована онлайн, и их коллегам еще предстоит тщательно проверить все выкладки. Авторы выражают надежду, что они ничего не перепутали. Тем временем каждый из читателей имеет возможность самостоятельно проверить все вычисления и, возможно, найти в них ошибку.
Алексей Алексенко
Автор
#Техно-уик-энд
Рассылка Forbes
Самое важное о финансах, инвестициях, бизнесе и технологиях
Мы нашли более быстрый способ умножать действительно большие числа
Умножать два числа легко, верно?
В начальной школе мы учимся выполнять длинное умножение следующим образом:
Долгий путь к умножению. Дэвид ХарвиМетоды, подобные этому, насчитывают тысячи лет, по крайней мере, древние шумеры и египтяне.
Но действительно ли это лучший способ перемножить два больших числа?
Читать далее: Шесть изображений показывают, как мы «видим» данные и фиксируем невидимую науку
При длинном умножении мы должны умножить каждую цифру первого числа на каждую цифру второго числа.
Если каждое из двух чисел состоит из N цифр, то всего получается N 2 (или N x N ) умножений. В приведенном выше примере N равно 3, и нам нужно было сделать 3 2 = 9 умножений.
Примерно в 1956 году известный советский математик Андрей Колмогоров предположил, что это наилучший способ умножения двух чисел.
Другими словами, как бы вы ни организовали свои расчеты, объем работы, который вам придется сделать, будет пропорционален как минимум N 2 . Вдвое больше цифр означает, что в четыре раза больше .
Колмогоров чувствовал, что если бы был возможен короткий путь, то он бы уже наверняка был обнаружен. Ведь люди умножают числа уже тысячи лет.
Это прекрасный пример логической ошибки, известной как «аргумент от незнания».
Более быстрый способ
Всего несколько лет спустя гипотеза Колмогорова оказалась в корне неверной.
В 1960 году Анатолий Карацуба, 23-летний студент-математик из России, открыл хитрый алгебраический трюк, позволяющий сократить количество необходимых умножений.
Например, чтобы умножить четырехзначные числа, вместо 4 2 = 16 умножений метод Карацубы обходится только девятью. При использовании его метода вдвое больше цифр означает только 9.0012 три раз больше работы.
Это складывается с впечатляющим преимуществом по мере увеличения чисел. Для тысячезначных чисел метод Карацубы требует примерно в 17 раз меньше умножений, чем длинное умножение.
Но с какой стати кому-то нужно перемножать такие большие числа?
На самом деле приложений огромное количество. Одним из наиболее заметных и экономически значимых является криптография.
Большие числа в реальной жизни
Каждый раз, когда вы участвуете в зашифрованном общении в Интернете — например, заходите на веб-сайт своего банка или выполняете поиск в Интернете — ваше устройство выполняет головокружительное количество умножений, включая числа с сотнями или даже тысячами цифр.
Скорее всего, ваше устройство использует трюк Карацубы для этой арифметики.
Все это является частью удивительной программной экосистемы, которая обеспечивает максимально быструю загрузку наших веб-страниц.
Для некоторых более эзотерических приложений математикам приходится иметь дело с еще большими числами, с миллионами, миллиардами или даже триллионами цифр. Для таких огромных чисел даже алгоритм Карацубы слишком медленный.
Настоящий прорыв произошел в 1971 году благодаря работе немецких математиков Арнольда Шёнхаге и Фолькера Штрассена. Они объяснили, как использовать недавно опубликованное быстрое преобразование Фурье (БПФ) для эффективного умножения огромных чисел. Их метод обычно используется сегодня математиками для обработки чисел, состоящих из миллиардов цифр.
БПФ — один из самых важных алгоритмов 20-го века. Одним из приложений, знакомых в повседневной жизни, является цифровое аудио: всякий раз, когда вы слушаете MP3, службы потоковой передачи музыки или цифровое радио, БПФ выполняет декодирование звука за кулисами.
Еще более быстрый способ?
В своей статье 1971 года Шенхаге и Штрассен также сделали поразительное предположение.
Чтобы объяснить, мне придется на мгновение углубиться в технические подробности.
Первая половина их гипотезы заключается в том, что должно быть возможно умножать N -значных чисел, используя количество основных операций, пропорциональное не более чем N log ( N ) (это N , умноженное на натуральный логарифм N ).
Их собственный алгоритм не совсем достиг этой цели; они были слишком медленными в логарифмическом разе (log N ) (логарифм логарифма N ). Тем не менее их интуиция заставляла их подозревать, что они что-то упустили, и что N log ( N ) должно быть осуществимо.
За десятилетия, прошедшие с 1971 года, несколько исследователей нашли улучшения в алгоритме Шёнхаге и Штрассена. Примечательно, что алгоритм, разработанный Мартином Фюрером в 2007 году, был мучительно близок к неуловимому журналу N ( N ).
Вторая (и гораздо более сложная) часть их предположения состоит в том, что N log ( N ) должно быть основным ограничением скорости — ни один возможный алгоритм умножения не может работать лучше этого.
Знакомо?
Мы достигли предела?
Несколько недель назад мы с Йорисом ван дер Хувеном опубликовали исследовательскую работу, описывающую новый алгоритм умножения, который, наконец, достигает священного Грааля N log ( N ), тем самым определяя «легкую» часть уравнения Шёнхаге-Штрассена. предположение.
Статья еще не прошла рецензирование, поэтому требуется некоторая осторожность. Стандартной практикой в математике является распространение результатов исследований до того, как они подверглись рецензированию.
Вместо использования одномерных БПФ — основы всей работы над этой проблемой с 1971 года — наш алгоритм опирается на многомерных БПФ. В этих гаджетах нет ничего нового: широко используемый формат изображения JPEG зависит от 2-мерного БПФ, а 3-мерное БПФ имеет множество приложений в физике и технике.
В нашей статье мы используем БПФ с 1729 измерениями. Это сложно визуализировать, но математически это не более проблематично, чем двумерный случай.
Очень, очень большие числа
Новый алгоритм не совсем практичен в его нынешнем виде, потому что доказательство, приведенное в нашей статье, работает только для смехотворно больших чисел. Даже если бы каждая цифра была написана на атоме водорода, в наблюдаемой Вселенной не хватило бы места для их записи.
Читать далее: Зачем нам нужно знать о простых числах с миллионами цифр?
С другой стороны, мы надеемся, что с дальнейшими уточнениями алгоритм может стать практичным для чисел, состоящих всего лишь из миллиардов или триллионов цифр. Если это так, то он вполне может стать незаменимым инструментом в арсенале вычислительного математика.
Если полная гипотеза Шёнхаге–Штрассена верна, то с теоретической точки зрения новый алгоритм — это конец пути — сделать лучше уже невозможно.
Лично я был бы очень удивлен, если бы догадка оказалась неверной. Но не следует забывать, что случилось с Колмогоровым.
Математика иногда может преподносить сюрпризы.
Как быстро умножать большие числа | by Maths and Musings
Алгоритм Тум-Кука
Здесь мы узнаем об остроумном применении алгоритма «разделяй и властвуй» в сочетании с линейной алгеброй для быстрого умножения больших чисел. И введение в нотацию big-O!
На самом деле этот результат настолько нелогичен, что великий математик Колмогоров предположил, что такого быстрого алгоритма не существует.
Часть 0: Длинное умножение — это медленное умножение. (И введение в нотацию Big-O)
Все мы помним, как учились умножать в школе. На самом деле, я должен сделать признание. Помните, что это запретная зона 😉
В школе у нас были «мокрые игры», когда шел слишком сильный дождь, чтобы играть на детской площадке. В то время как другие (нормальные/веселые/положительные-прилагательные-на выбор) дети играли в игры и бездельничали, я иногда брал лист бумаги и перемножал большие числа, просто так, черт возьми.
Чистая радость вычислений! У нас даже было соревнование по умножению «Супер 144», где нам нужно было как можно быстрее умножать перемешанную сетку чисел 12 на 12 (от 1 до 12). Я практиковал это религиозно, до такой степени, что у меня были свои собственные заранее подготовленные листы практики, которые я фотокопировал, а затем использовал по очереди. В конце концов я сократил свое время до 2 минут и 1 секунды, когда был достигнут мой физический предел каракулей.
Несмотря на эту одержимость умножением, мне никогда не приходило в голову, что мы могли бы сделать это лучше. Я потратил так много часов на умножение, но никогда не пытался улучшить алгоритм .
Рассмотрим умножение 103 на 222.
Вычислим 2 раза 3 раза 1 + 2 раза 0 раз 10 + 2 раза 1 раз 100 + 20 раз 3 раза 1 + 20 раз 0 раз 10 + 20 раз 1 раз 100 = 22800
В общем случае, чтобы умножить число на n цифр, требуется O(n²) операций. Обозначение «большой-O» означает, что если бы мы построили график зависимости количества операций от n, значение n² действительно имело бы значение.
Форма 9(1/3) то же самое?», и они, вероятно, выблевывают в свою кофейную чашку, начинают плакать и бормочут что-то о топологии. По крайней мере, такова была моя реакция (сначала), а я почти ничего не смыслю в топологии.
Хорошо. Они не одинаковы. Но наш компьютер не заботится о топологии. Компьютеры различаются по производительности во многих отношениях, которые я даже не могу описать, потому что ничего не знаю о компьютерах.
Но нет смысла настраивать паровой каток. Если две функции при больших значениях их входа растут с одинаковым порядком величины, то для практических целей это содержит большую часть релевантной информации. 9х при х = 100 уже намного больше, чем количество атомов во Вселенной. (10¹⁰⁰ >>>> 10⁸⁰, что является оценкой, числом Эддингтона, числа атомов во Вселенной согласно моему поиску в Google*).
*на самом деле я использовал DuckDuckGo.
Записывать целые числа в виде многочленов одновременно очень естественно и очень неестественно. Написание 1342 = 1000 + 300 + 40 + 2 очень естественно.
Написание 1342 = x³+3x²+4x + 2, где x = 10, немного странно.
Предположим, мы хотим умножить два больших числа, записанных в системе счисления b, по n цифр каждое. Запишем каждое n-значное число в виде многочлена. Если мы разделим n-значное число на r частей, этот многочлен будет иметь n/r членов.
Например, пусть b = 10, r = 3, и наше число 142 122 912
Мы можем превратить это в
Это работает очень хорошо, когда r = 3 и наше число, записанное в системе счисления с основанием 10, имеет 9 цифр. Если r не делит n идеально, то мы можем просто добавить несколько нулей впереди. Опять же, это лучше всего иллюстрируется примером.
27134 = 27134 + 0*10⁵ = 027134, что мы представляем как
Почему это может быть полезно? Чтобы найти коэффициенты полинома P, если полином имеет порядок N, то, выбирая его в N + 1 точке, мы можем определить его коэффициенты.
Например, если полином x⁵ + 3x³ +4x-2 порядка 5 выбран из 6 точек, мы можем вычислить весь полином целиком.
Интуитивно понятно, что многочлен 5-го порядка имеет 6 коэффициентов: коэффициент при 1, x, x², x³, x⁴, x⁵. Учитывая 6 значений и 6 неизвестных, мы можем найти значения.
(Если вы знаете линейную алгебру, вы можете рассматривать различные степени x как линейно независимые векторы, составить матрицу для представления информации, инвертировать матрицу и вуаля )
Выборка полиномов для определения коэффициентов (необязательно)
Здесь мы более подробно рассмотрим логику выборки полинома для вывода его коэффициентов. Смело переходите к следующему разделу.
Мы покажем, что если два многочлена степени N совпадают по N+1 точкам, то они должны быть одинаковыми. т.е. N+1 точек однозначно определяют полином порядка N .
Рассмотрим полином второго порядка. Он имеет вид P(z) = az² +bz + c . По фундаментальной теореме алгебры — бессовестно, воткните сюда, я потратил несколько месяцев на то, чтобы собрать доказательство этого, а затем написать его, здесь — этот многочлен можно разложить на множители.
Это означает, что мы можем записать его как A(z-r)(z-w)
Обратите внимание, что при z = r и при z = w полином оценивается как 0 . Мы говорим, что w и r являются корнями многочлена.
Теперь покажем, что P(z) не может иметь более двух корней. Предположим, что у него три корня, которые мы называем 9.0012 ш, р, с . Затем факторизуем многочлен. P(z) = A(z-r)(z-w). Тогда P(s) = A(s-r)(s-w). Это делает , а не равным 0, так как умножение ненулевых чисел дает ненулевое число. Это противоречие , потому что наше первоначальное предположение состояло в том, что s было корнем многочлена P.
Этот аргумент может быть применен к многочлену порядка N практически идентичным образом.
Теперь предположим, что два многочлена P и Q заказа N согласованы на N+1 точек. Тогда, если они различны, P-Q является полиномом порядка N , который равен 0 в N+1 точках.
По предыдущему это невозможно, так как многочлен порядка N имеет не более N корней. Таким образом, наше предположение должно быть неверным, и если P и Q совпадают по N+1 точкам, то они являются одним и тем же полиномом.
Видеть значит верить: рабочий пример
Давайте посмотрим на действительно огромное число, которое мы называем p. В базе 10 p имеет длину 24 цифры (n = 24), и мы разделим его на 4 части (r = 4). n/r = 24/4 = 6
p = 292 103 243 859 143 157 364 152.
И пусть полином, представляющий его, называется P,
P(x) = 292 103 x³ + 243 859 x² +143 157 x+ 364 152
, где P(10⁶) = p.
Поскольку степень этого многочлена равна 3, мы можем вычислить все коэффициенты из выборки в 4 местах. Давайте почувствуем, что происходит, когда мы пробуем его в нескольких точках.
- P(0) = 364 152
- P(1) = 1 043 271
- P(-1) = 172 751
- P(2) = 3 962 726
Умножим p на q. Пусть q = 124 153 913 241 143 634 899 130 и
Q(x) = 124 153 x³ + 913 241 x²+143 634 x + 899 130
Вычисление t=pq может быть ужасным. Но вместо того, чтобы делать это напрямую, мы пытаемся вычислить полиномиальное представление t, которое мы обозначили как T. Поскольку P — многочлен порядка r-1=3, а Q — многочлен порядка r-1 = 3, T равно многочлен порядка 2r-2 = 6,
T(10⁶) = t = pq
T(10⁶) = P(10⁶)Q(10⁶)
Хитрость в том, что мы будем вычислять коэффициентов T вместо того, чтобы напрямую перемножать p и q вместе . Тогда вычислить T(1⁰⁶) несложно, потому что для умножения на 1⁰⁶ мы просто прикрепляем 6 нулей сзади. Подводя итог всем частям, также легко, потому что добавление — это действие с очень низкими затратами для компьютеров.
Чтобы рассчитать коэффициенты T, нам нужно выбрать его в 2r-1 = 7 точек, потому что это полином 6-го порядка. Вероятно, мы хотим выбрать небольшие целые числа, поэтому мы выбираем
- T(0)=P(0)Q(0)= 364 152*899 130
- T(1)=P(1)Q(1)= 1 043 271*2 080 158
- T(2)=P(2) Q(2)= 3 962 726*5 832 586
- T(-1)=P(-1)Q(-1)= 172751*1544584
- T(-2)=P(-2)Q(-2)= – 1 283 550*3 271 602
- T(3)=P(-3)Q(-3)= –5 757 369*5 335 266
Обратите внимание на размер P(-3), Q(-3), P(2), Q (2) и т.
д. Это все числа с приблизительно n/r = 24/4 = 6 цифр. Некоторые из них состоят из 6 цифр, некоторые из 7. По мере увеличения n это приближение становится все более и более разумным.
На данный момент мы свели задачу к следующим шагам или алгоритму:
(1) Сначала вычислить P(0), Q(0), P(1), Q(1) и т. д. (действие с низкой стоимостью )
(2) Чтобы получить наши 2r-1= 7 значений T(x), мы должны теперь умножить 2r-1 чисел приблизительного размера n/r цифр. А именно, мы должны рассчитать P(0)Q(0), P(1)Q(1), P(-1)Q(-1) и т. д. ( Высокозатратное действие )
(3) Восстановить T (x) из наших точек данных. ( Недорогое действие : будет рассмотрено позже). 9(n/r)) в общем случае для базы b и длины n]
Это приводит к анализу времени работы этого подхода.
Время выполнения
Из вышеизложенного мы выяснили, что, временно игнорируя малозатратных действий (1) и (3), стоимость умножения двух n-значных чисел алгоритмом Тума будет подчиняться:
Вот что мы видели в рабочем примере.
Умножение каждого P(0)Q(0), P(1)Q(1) и т. д. стоит T(n/r), потому что мы умножаем два числа длины приблизительно n/r. Мы должны сделать это 2r-1 раз, так как мы хотим выбрать T(x) — полином порядка 2r-2 — в 2r-1 разрядах.
Насколько это быстро? Мы можем решить такое уравнение явно.
Все, что осталось сейчас, это немного запутанной алгебры
Поскольку были некоторые другие издержки, связанные с процессом матричного умножения («повторной сборки») и сложением, мы не можем на самом деле сказать, что наше решение является точным временем выполнения, поэтому вместо этого мы заключаем что мы нашли большой-O среды выполнения
Оптимизация r
Эта среда выполнения по-прежнему зависит от r. Исправьте r, и все готово. Но наше любопытство еще не удовлетворено!
Когда n становится большим, мы хотим найти приблизительно оптимальное значение для нашего выбора r. т.е. мы хотим выбрать значение r, которое меняется для разных значений n.
Ключевым моментом здесь является то, что при изменении r нам нужно обратить внимание на стоимость повторной сборки — матрица, которая выполняет эту операцию, имеет стоимость O(r²).
Когда r было фиксированным, нам не нужно было смотреть на это, потому что по мере того, как n становилось большим при фиксированном r, именно члены, включающие n, определяли рост требуемого объема вычислений. Поскольку наш оптимальный выбор r будет увеличиваться по мере увеличения n, мы больше не можем игнорировать это.
Это различие имеет решающее значение. Первоначально наш анализ выбрал значение r, возможно, 3, возможно, 3 миллиарда, а затем рассмотрел размер большого O, когда n выросло до сколь угодно большим. Теперь посмотрим на поведение, когда n становится произвольно большим и r растет с n с некоторой скоростью, которую мы определяем . Это изменение перспективы рассматривает O(r²) как переменную, тогда как, когда r оставалось фиксированным, O(r²) было константой, хотя мы и не знали ее.
Итак, мы обновляем наш анализ по сравнению с предыдущим: 9sqrt(logN), которое было нашим приблизительным значением.
«x» заменяет «r», и на каждой из трех картинок используется разное значение N.
Это довольно убедительно для меня, что наш выбор был правильным. При таком выборе r мы можем подключить его и посмотреть, как в конечном итоге наш алгоритм дает большое значение O:
, где мы просто подставили наше значение для r и использовали приближение для log(2r-1)/log(r), которое очень точен для больших значений r.
Возможно, то, что я не заметил этот алгоритм, когда был мальчишкой, выполнявшим умножение, было разумным. На приведенном ниже графике я задаю коэффициент нашей функции большого O равным 10 (для демонстрационных целей) и делю его на x² (поскольку первоначальный подход к умножению был O(n²). Если красная линия стремится к 0, это покажет наше новое время работы асимптотически работает лучше, чем O(n²).
И действительно, в то время как форма функции показывает, что наш подход на в конечном итоге на быстрее, а в конечном итоге на намного быстрее, нам нужно подождать, пока у нас не будет почти 400-значных длинных чисел, чтобы это было так! Даже если бы коэффициент был всего 5, числа должны были бы иметь длину около 50 цифр, чтобы увидеть улучшение скорости.
Для моего 10-летнего «я» умножение 400-значных чисел было бы довольно сложной задачей! Отслеживание различных рекурсивных вызовов моей функции также было бы несколько сложной задачей. Но для компьютера, выполняющего задачу по ИИ или по физике, это обычная проблема!
Что мне нравится в этой технике, так это то, что она не ракетостроение . Это не самая ошеломляющая математика, которую когда-либо открывали. Оглядываясь назад, возможно, это кажется очевидным!
Тем не менее, это блеск и красота математики. Я читал, что Колмогоров предположил на семинаре, что умножение в основе своей равно O(n²). Колмогоров фактически изобрел множество современных теорий вероятностей и анализа. Он был одним из величайших математиков 20 века. Тем не менее, когда дело дошло до этой несвязанной области, оказалось, что существует целый корпус знаний, ожидающих своего открытия, сидящих прямо у него и у всех остальных под носом!
Фактически, алгоритмы «Разделяй и властвуй » довольно быстро приходят на ум сегодня, поскольку они так часто используются.
Но они являются продуктом компьютерной революции в том смысле, что только с огромной вычислительной мощностью человеческий разум сосредоточился конкретно на скорости вычислений как на области математики, достойной самостоятельного изучения.
Вот почему математики не готовы признать, что гипотеза Римана верна только потому, что кажется, что она может быть правдой, или что P не равно NP только потому, что это кажется наиболее вероятным. Удивительный мир математики всегда обладает способностью сбивать с толку наши ожидания.
На самом деле, вы можете найти еще более быстрые способы умножения. Текущие лучшие подходы используют быстрые преобразования Фурье. Но я оставлю это на другой день 🙂
Дайте мне знать ваши мысли внизу. Я недавно появился в Твиттере как ethan_the_mathmo , вы можете подписаться на меня здесь .
Я наткнулся на эту задачу в замечательной книге, которой пользуюсь, под названием «Природа вычислений» физиков Мура и Мертенса, где одна из задач поможет вам проанализировать алгоритм Тума.