Найден самый быстрый способ умножать огромные числа

Казалось бы, что еще нового можно открыть в школьной математике. Оказывается, можно. Ведь скорость умножения что людей, что компьютерных систем, сильно страдает. И хоть компьютеры способны производить вычисления за доли секунды, когда количество необходимых вычислений переваливает за несколько миллионов в секунду, алгоритмам становится труднее. И вот ученые нашли способ ускорить умножение больших чисел в несколько раз.

Побить рекорд

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

Если вы думаете, что умножить числа друг на друга так легко, то задумайтесь, сколько будет, если 10^{2148570911044552519406} умножить на 5^{568337392843819273}. Непростой вопрос. Даже ваш калькулятор не сможет это посчитать. Почему? Потому что с каждым новым знаком в степени числа, сложность алгоритма и затраты времени на вычисление существенно возрастают. Все потому, что для вычисления машины используют специальные суммы, на которые раскладывается каждое число. Затем эти суммы перемножаются, давая в итоге конечный результат.

Для самых больших

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

Для проверки алгоритма ученые проводили вычисления на возмутительно огромных числах. Больших, чем количество атомов во Вселенной. Это означает, что на компьютере нет способа делать такие вычисления, потому что для того, чтобы их закодировать, требуется слишком много памяти. Вместо прямого умножения, математики придумали методику, которая теоретически могла бы быть быстрее, чем другие методы, по крайней мере для этих больших массивов цифр. И она показала поистине грандиозные результаты, разгромив оппонентов в пух и прах. Этот новый метод можно будет использовать в разных программах при работе с большими объемами данных, чтобы ускорить процессы их систематизации.

Читать еще: Научный писатель объясняет суть математики

Источник: Science News