Математиците откриха „удивителен“ нов начин за умножаване на големи числа.

Двама математици от Австралия и Франция измислили нов начин за умножаване на числата, докато решавали алгоритмичен пъзел, който не дава мира на някои от най-големите умове в математиката от почти половин век.

За повечето от нас начинът, по който умножаваме сравнително малки числа, е таблицата за умножение, невероятно удобна помощ, измислена от вавилонците преди 4 000 години.

Но ако числата са по-големи? Е, ако цифрите станат много и ако приемем, че не разполагаме с калкулатор или компютър, разбира се повечето от нас ще се обърнат към умножението, което ни научават в училище.

Има само един проблем с дълго умножение - бавно е.

Причината да е бавно е, че за всяка една цифра във всяко от числата в задачата, трябва да се извърши отделна операция умножение, преди да бъдат събрани всички резултати по вертикала.

По-важното е, че това е проблем за компютрите. По принцип алгоритъмът не е особено ефективен, тъй като процесът неизбежно е тежък. Както се случва, математиците всъщност имат начин да изчислят колко трудоемко е умножаването.

Както математикът Дейвид Харви от UNSW в Австралия обяснява във видеото по-долу, в едно умножение, където и двете числа имат 3 цифри (n = 3), броят на отделните операции за умножение всъщност е 9, което е n на втора степен.

Проблемът е, че с увеличаването на цифрите се увеличава и количеството работа, което винаги е  (n на квадрат)

Макар че е неефективен, този алгоритъм за умножение всъщност е най-развитият алгоритъм за умножение до 60-те години на миналия век, когато руският математик Анатолий Карацуба откри, че  може да бъде сведено до n^1.58.

Десетилетие по-късно, двама германски математици направиха още един пробив: алгоритъмът на Шьонхаге – Щрасен, който предполагаше, че са възможни и допълнителни подобрения.

"Те предричаха, че трябва да съществува алгоритъм, който умножава n-цифрени числа, използвайки n * log (n) основни операции", обяснява Харви.

"Нашата статия дава първия известен пример за алгоритъм, който постига това."

Според изследователите, умножаването на две числа с един милиард цифри всеко по класическия алгоритъм за умножение ще изисква компютърни месеци изчисления. 

Използвайки алгоритъма Schönhage-Strassen, това ще отнеме до 30 секунди и с новите теоретични доказателства ще бъде още по-бързо - теоретично, и може дори да представлява най-бързия алгоритъм за умножение, който е математически възможен.

"В този смисъл нашата работа се очаква да бъде краят на този проблем, въпреки че все още не знаем как да го докажем строго", казва Харви. "Хората търсят такъв алгоритъм почти 50 години."

Заслужава да се отбележи, че новият алгоритъм би бил полезен само при умножаване на много големи числа. Колко големи по-точно?

"Нямаме представа", обясняват изследователите във FAQ, макар че примерът, който дават в статията, се равнява на 10 на степен 214857091104455251940635045059417341952, което е много, много голямо число.

Световната математическа общност все още асимилира новите находки. Трудно е те да бъдат проверени (по-горе е обяснено колко ще отнеме една проверка по класическия алгоритъм), но вече има развълнувани.

"Бях много учуден, че това е направено," каза теоретичният компютърен учен Мартин Фюрер от Университета в Пенсилвания за Science News. Самият той опитал да преработи алгоритъма на Шьонхаге-Штрасен преди повече от десетилетие, но накрая прекъснал работата, като обяснява на Science News: „Изглеждаше съвсем безнадеждно за мен“.

Сега има надежда, при условие че математиците могат да проверят работата.

"Ако резултатът е правилен, това е голямо постижение в теорията на сложните изчисления", казва пред New Scientist математикът и компютърният учен Фредрик Йохансон от INRIA Bordeaux и Institut de Mathématiques de Bordeaux.

"Новите идеи в тази работа вероятно ще вдъхновят по-нататъшни изследвания и биха могли да доведат до практически подобрения".

Междувременно Харви и неговият колега-изследовател Йорис ван дер Ховен от École Polytechnique във Франция казват, че алгоритъмът им трябва да бъде оптимизиран и те се надяват, че не са пропуснали нещо в доказателствата си.

"Голяма част от работе беше да докажем на себе си, че е наистина точно", казва Харви за AAP. "Все още съм ужасен, че нещо може да излезе грешно"

Публикацията на двамата математици е в HAL open access archive.