Двама математици измислиха нов начин за умножаване на големи числа и успяха да решат алгоритмичен проблем, занимавал най-големите математически умове в продължение на почти половин век, съобщи ScienceAlert.
Начинът, по който умножаваме сравнително малките числа, е открит от шумери и египтяни преди 4 000 години.
Но ако цифрите станат по-големи и не разполагаме с калкулатор или компютър, повечето от нас ще се захванат с дълго умножение, както ни учиха в училище, което си е надеждна техника за умножаване на всякакви числа.
Но проблемът е, че е бавно.
Причината да е толкова бавно е, че трябва да умножим всяка цифра от първото число с всяка цифра от второто число. Ако двете числа имат по N цифри, това означава N 2 (или N x N) умножения. В долния пример N е 3 и трябва да се направят 3 2 = 9 умножения.
Дългият начин на умножение. Кредит: David Harvey
Около 1956 г. известният съветски математик Андрей Колмогоров предположи, че това е най-добрият начин за умножаване на две числа. Защото ако е било възможно да се опрости, сигурно вече щеше да е било открито. В края на краищата, хората умножават числата от хиляди години.
"Това е великолепен пример за логическата заблуда, известна като „аргумент от невежество“", пише Дейвид Харви (David Harvey) в The Conversation.
По-бързият начин
Но само няколко години по-късно се оказа, че Колмогоров греши. През 1960 г. Анатолий Карацуба, 23-годишен руски студент, откри хитър алгебричен трик, който намалява броя на необходимите умножения на N 1.58.
Например, за да се умножат четирицифрени числа, вместо 4 2 = 16 броя умножения, методът на Карацуба изисква само 9. А при два пъти повече цифри работата се намалява три пъти. С нарастването на числата предимството на този метод става впечатляващо. За числа с хиляда цифри, методът на Карацуба се нуждае от около 17 пъти по-малко умножения от класическия начин.
Но кому е нужно да умножава толкова големи числа? Всъщност има огромен брой приложения. Едно от най-видимите и икономически значими е криптографията.
Големи числа в реалния живот
Всеки път, когато се занимавате с криптирана комуникация в интернет - например, влизате в банковия си акаунт или извършвате търсене в мрежата - вашето устройство изпълнява редица умножения, включващи числа със стотици или дори хиляди цифри.
Много вероятно е вашето устройство да използва примера на Карацуба за тази аритметика. Всичко това е част от невероятната софтуерна екосистема, която поддържа нашите уеб страници заредени възможно най-бързо.
За някои по-екзотични приложения математиците трябва да се справят с още по-големи числа, с милиони, милиарди или дори трилиони цифри. За такива огромни числа дори алгоритъмът на Карацуба е твърде бавен.
Истинският пробив дойде през 1971 г. с работата на германските математици Арнолд Шьонхаге (Arnold Schönhage) и Волкер Страсен (Volker Strassen). Те обясниха как да се използва наскоро публикувано бързо преобразуване на Фурие (fast Fourier transform - FFT), за да се умножават ефикасно големи числа. Техният метод се използва днес от математиците, когато работят с числа с милиарди цифри.
FFT е един от най-важните алгоритми на 20-ти век. Едно приложение, познато в ежедневието, е дигиталното аудио: всеки път, когато слушате MP3 файлове, услуги за стрийминг на музика или дигитално радио, с FFT обработват аудио декодирането.
Още по-бърз начин?
Шьонхаге и Страсен в статия от 1971 г. правят предположението, че е възможно да се умножат N- цифрени числа, като се използват редица основни операции, които са най-много N log (N) (това е N пъти естествения логаритъм на N).
Техният собствен алгоритъм не достига до тази цел, те постигат log (log N) (логаритъм на логаритъма на N). Но интуицията им ги накара да подозират, че им липсва нещо, и че N log (N) трябва да е възможно.
През десетилетията след 1971 г. няколко изследователи откриват някои подобрения в алгоритъма на Шьонхаге и Страсен. Трябва да се отбележи, че алгоритъмът, проектиран от Мартин Фюрер (Martin Fürer) през 2007 г., се доближи твърде много до неуловимото N log (N).
Втората (и много по-трудна) част от тяхното предположение е, че N log (N) трябва да бъде фундаменталното ограничение на скоростта - че не е възможна алтернатива за умножение по-добро от това.
Звучи познато, нали?
Достигнахме ли предела?
Преди няколко седмици Йорис ван дер Ховен (Joris van der Hoeven) и Дейвид Харви (David Harvey) публикуват статия, описваща нов алгоритъм за умножение, който най-накрая достига до N log (N) - Свещения Граал.
Документът все още не е разгледан от специалистите, така че е необходима известна предпазливост. Това е стандартна практика в областта на математиката за разпространение на резултатите от научните изследвания, преди те да се подложат на партньорски проверки.
Вместо да използват едномерни FFT - основната част от цялата работа по този проблем от 1971 г. насам, новият алгоритъм разчита на многоизмерни FFT. Това приложение не е нищо ново: широко използваният JPEG формат на изображението зависи от двумерните FFT, а 3-мерните FFT имат много приложения във физиката и инженерството.
В своята статия те използват FFT с 1729 измерения. Това е трудно да си представим, но математически не е по-неприятно от двумерния случай.
Наистина огромни числа
В момента алгоритъмът им не е практичен, но все още не е настроен. В началото на раздел 5 в статията си (в архива за отворен достъп HAL) те отбелязват, че техните оценки влизат в сила за N≥2d12 (2^d^12) където те използват d=1729.
Тъй като има само около 2270 частици във видимата вселена, това означава наистина големи числа.
„Дори ако всяка цифра бе написана на водороден атом, нямаше да има достатъчно място в наблюдаваната вселена, за да ги запише”, обяснява Харви.
Числото 1729 не е случайно (вижте повече по-долу за него). Това не е съвпадение. Авторите получават ограничаващ множител 36 от едно място, друг коефициент 6 от друго място и накрая коефициент 8, което прави 1728 и е равно на 123. Тогава те просто увеличават d с 1, като го представят като сума от две числа на трета степен (1729 = 13 + 123), което може да се представи и по друг начин (1729 = 93 + 103). Има много гъвкавост в този избор и авторите очертават пътя как да се подобри от 1728 до просто 8.
„От друга страна, ние се надяваме, че с по-нататъшни подобрения, алгоритъмът може да стане практичен за цифри с едва милиарди или трилиони цифри. Ако е така, той може да се превърне в незаменим инструмент в арсенала на изчислителната математика”, заявява Харви.
Ако пълната хипотеза на Шьонхаге и Страсен е вярна, то от теоретична гледна точка новият алгоритъм е краят на пътя - не е възможно да се направи по-добре.
„Лично аз бих се изненадал много, ако предположението се окаже грешно. Но не трябва да забравяме какво се случи с Колмогоров. Математиката понякога може да поднася изненади”, коментира Харви.
Дейвид Харви (вляво) и Йорис ван дер Ховен .
Дейвид Харви (вляво) и Йорис ван дер Ховен ."Вълшебното" число 1729
Числото d=1729 припомня една любопитна история за Годфри Харди и Шриниваса Рамануджан:
Британският математик Харди решил да посети индийския си колега Сриниваса Рамануджан, докато Рамануджан бил в болница. Харди разказва:
Спомням си, че веднъж отидох да го видя, когато бе болен в Пътни (югозападен квартал на Лондон). Бях взел такси с номер 1729 и отбелязах, че числото ми се стори по-скоро скучно и че се надявам, че не е неблагоприятна поличба. "Не," - отговори Рамануджан - "Това е едно много интересно число; то е най-малкото число, което може да се представи като сума от две числа на трета степен по два различни начина." (Hofstadter 1989; Kanigel 1991; Snow 1993; Hardy 1999, pp. 13 and 68).
1729 = 13 + 123
1729 = 93 + 103.
Най-малките числа, които могат да се представят като сбор от две положителни числа на трета степен по п различни начини, се наричат "номера на такситата" заради тази история.
Това свойство на 1729 е споменато от героя Робърт, луд математик, изигран от Антъни Хопкинс, през 2005 г. във филма Доказателството (Proof). Това е и част от наименованието на космическия кораб Nimbus BP-1729, появил се в Сезон 2 на анимационния сериал Futurama (вляво), както и сериен номер на робота Бендер, както и на коледна картичка в епизода Xmas Story (том 2 DVD, Georgoulias и др. 2004; вдясно).
Коментари
Моля, регистрирайте се от TУК!
Ако вече имате регистрация, натиснете ТУК!
Няма коментари към тази новина !
Последни коментари