18 °C

Математици откриха "удивителен" начин за умножаване на големи числа (видео)

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

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

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

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

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

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

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

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

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

Макар че е неефективен, този алгоритъм за умножение всъщност е най-развитият алгоритъм за умножение до 60-те години на миналия век, когато руският математик Анатолий Карацуба откри, че  може да бъде сведено до n1.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.

Facebook коментари

Коментари в сайта

Хороскоп за 21.09.2019

Хороскоп за Овен

Овен
Дайте възможност на любимите ви хора да се погрижат за вас. Денят не носи проблеми. Починете си. Не прибързвайте със съветите към близките ви. Без да искате ги натоварвате излишно. Занимавайте се със свои неща, които ви помагат да се откъснете от натоварващи мисли.
21.09.2019

Хороскоп за Телец

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

Хороскоп за Близнаци

Близнаци
Душевната ви хармония се отразява чудесно и на външността ви. Ако съумеете де преодолеете дребните недоразумения в отношенията с интимния партньор, денят обещава да бъде много приятен. Отделете време за приятелите си.
21.09.2019

Хороскоп за Рак

Рак
За предпочитане е да се включите в изпълнение на обща задача, отколкото да се опитвате сами да я свършите. Екипната работа ще бъде резултатна и ще ви остане време за по-приятни неща. С партньора си ще говорите за намеренията си и ще търсите мнението му по всички общи въпроси. Вечерта ви ще е различна, но и вълнуваща.
21.09.2019

Хороскоп за Лъв

Лъв
Натоварванията днес не са препоръчителни, погрижете се за здравето си. Също така не допускайте дребни сплетни да развалят настроението ви. В добро разположение на духа сте и всичко, което измислите сега ще ви се отдава с лекота за напред. Въпреки това не се надценявайте.
21.09.2019

Хороскоп за Дева

Дева
Радвате се на много добро здраве днес. Настроението ви е приповдигнато и с лекота разведрявате атмосферата у дома. Може би ще бъдете заинтригувани от плановете на ваш приятел. Предложението му ще ви се стори доста привлекателно и едва ли ще се колебаете дълго преди да приемете. Нямате много време за да довършите ангажимент, по който отдавна работите.
21.09.2019

Хороскоп за Везни

Везни
Покажете на хората, които имат очаквания към вас, че държите на обещанията си. Бъдете коректни и в отношенията си с онези, с които работите. Не всичко е бизнес, по-важни са човешките взаимоотношения, стига да го разбирате и вие така. Никой не е застрахован от грешки, важно е да ги осъзнаем и избягваме за в бъдеще.
21.09.2019

Хороскоп за Скорпион

Скорпион
Работата ще ви наложи да вземете неотложни мерки, но помислете дали не пропускате важни неща. Вслушвайте се в градивната критика, полезно е. У дома ви очаква спокойствие. То все повече ви привлича и ви се иска да не ви напуска.
21.09.2019

Хороскоп за Стрелец

Стрелец
Не бъдете предубедени към хора, които ви предлагат партньорството си. Проверявайте собствената си информация и не предприемайте рисковани действия. Използвайте почтени средства и дайте изява на опита и авторитета си. Настроението ви ще се повиши от вниманието на скъп за вас човек. Пътуване или друго вълнуващо преживяване за някои от вас.
21.09.2019

Хороскоп за Козирог

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

Хороскоп за Водолей

Водолей
Ще си поставите цел и ще я следвате до края. Така ще постигнете бърз напредък и ще останете доволни от себе си. Изградили сте си авторитет на отговорен човек и това ще ви донесе поръчки и нови бизнес-взаимоотношения. Ще впечатлите някого с непрекъснатото си желание да сте интересни и загадъчни.
21.09.2019

Хороскоп за Риби

Риби
Предпочитате да сте сами днес и да размишлявате, но не се обграждайте с бариери. Приемете доброто отношение на всички и се опитайте да се впишете в обстановката. Така най-бързо ще преодолеете кризата си и ще продължите напред. И щом веднъж сте поели в правилната посока, няма да има какво да ви спре.
21.09.2019
Последни новини