Ученые создали действенный алгоритм: решили загадку полувека

Ученые из Франции и Австралии создали высокоэффективный алгоритм, который позволяет быстро и легко умножать слишком большие для обычных способов числа. Математики искали этот метод достаточно долго – на протяжении почти полувека. С тех пор, как в 1971 году был предложен алгоритм Шенхаге-Штрассена, который основан на быстром преобразовании Фурье. Об этом сообщает издание Science Alert.

Новый алгоритм выполняется за время, равное О(n log n), где n – это порядок числа. Он может выполнять операцию умножения с числами, которые состоят из более чем миллиарда знаков, в течение менее 30 секунд.

Другие стандартные методы выполняют это действие, равное n в степени 1.58-2. У компьютеров вычисление результата с большими множителями может занять месяцы. Это происходит по причине того, что, например, умножение двух трехзначных чисел требует 9 операций (каждая цифра одного числа перемножается с цифрами другого числа), а двух четырехзначных чисел – уже 16 операций.

Высокоэффективный алгоритм, созданный математиками, полезен для вычисления произведений лишь очень больших чисел, к примеру, 214857091104455251940645045059417341952.

По скорости он теоретически превосходит известный метод Шенхаге-Штрассена. Математики размышляют над тем, не были ли допущены в доказательства их методы ошибки. Поэтому алгоритм нуждается в дальнейших проверках, которые подтвердят его правильность и способность выполнять нужные задачи.

Ранее портал "Знай.ua" роботы научились распознавать человеческие эмоции, результат точен на 98%, ученые в восторге

Напомним: этим "гаджетом" гордился каждый бухгалтер и математик 60-х, история дедушки современного калькулятора. Аарифмометр позволял быстро и безошибочно производить основные математические действия

Читайте также: нейросеть научилась предсказывать смерть человека с точностью до секунды. В качестве материала для исследования были выбраны истории болезни полумиллиона британцев в возрасте от 40 до 69 лет