Dva matematičara iz Australije i Francuske osmislila su novi način množenja brojeva, dok su rješavali algoritamsku zagonetku koja bi zbunila neke od najvećih umova matematike prije gotovo pola stoljeća.

Množenje malih brojeva može biti vrlo lako. Ali što ako se brojke povećaju? Pa, ako brojke postanu glomazne, većina nas bi prešla na dugo množenje: još jedan koristan trik koji smo naučili u školi i pouzdana tehnika za množenje dvaju brojeva. Ali postoji problem s dugim množenjem. Sporo je.

Što je još važnije, to je problem za računala, budući da su njihova uska grla u izvođenju izračuna nametnuta ograničenjima apstraktne matematike koju mi ​​sami možemo razumjeti.

U osnovi, dugo množenje je algoritam, ali nije osobito učinkovit jer je proces neizbježno naporan.

PROČITAJTE TAKOĐER: Matematika napokon ima znanstveno objašnjenje zašto vam zglobovi pucaju

Igrom slučaja, matematičari su zapravo otkrili novi način za izračunavanje koliko je dugo množenje teško.

Kao što matematičar David Harvey, s UNSW-a u Australiji, objašnjava u videu u nastavku, u množenju gdje oba broja imaju tri znamenke ( n = 3), broj uključenih zasebnih operacija množenja je uistina 9, što je n 2:

Kako brojevi rastu, povećava se i količina uključenog rada, uvijek predstavljena s n na potenciju 2.

Iako neučinkovit, algoritam dugog množenja zapravo je bio najnapredniji algoritam množenja koji smo imali do 1960-ih, kada je ruski matematičar Anatolij Karatsuba otkrio da je n 1,58 moguć.

Desetljeće kasnije, dva su njemačka matematičara došla do još jednog otkrića: algoritam Schönhage-Strassena, koji je pretpostavio – ali nikada nije dokazao – da su daljnja poboljšanja također moguća.

"Predvidjeli su da bi trebao postojati algoritam koji množi brojeve n znamenki koristeći u biti osnovne operacije n * log ( n )", objašnjava Harvey .

"Naš rad pruža prvi poznati primjer algoritma koji to postiže."

Prema istraživačima, množenje dvaju brojeva s milijardu znamenki svaki dugim procesom množenja trajalo bi nekoliko mjeseci.

Korištenjem Schönhage-Strassen algoritma, trebalo bi manje od 30 sekundi, a uz teoretski dokaz, bilo bi još brže - teoretski - i moglo bi čak predstavljati najbrži matematički mogući algoritam množenja.

PROČITAJTE I: Matematika bi mogla pomoći u predviđanju razvoja stanica raka

"U tom smislu, očekuje se da će naš rad biti kraj puta za ovaj problem, iako još uvijek ne znamo kako to rigorozno dokazati", kaže Harvey.

“Ljudi su tražili ovaj algoritam gotovo 50 godina. Nije bilo napuštenog zaključka da netko završi uspješnim.”

Vrijedno je napomenuti da bi novi algoritam bio koristan samo za množenje vrlo velikih brojeva. Koliko velik točno?

"Nemamo pojma", objašnjavaju istraživači u FAQ-u, iako je primjer koji navode u članku 10 214857091104455251940635045059417341952, što je vrlo, vrlo, vrlo velik broj. Svjetska matematička zajednica još uvijek upija nova otkrića, koja tek trebaju biti recenzirana.

Fürer je sam pokušao preformulirati Schönhage-Strassen algoritam prije više od deset godina, ali je na kraju prekinuo rad, rekao je "Činilo mi se prilično beskorisnim".

"Ako je rezultat točan, to je veliko postignuće u teoriji složenosti računanja", matematičar i računalni znanstvenik Fredrik Johansson, iz INRIA Bordeaux i Instituta za matematiku u Bordeauxu.

PROČITAJTE I: Definicija kilograma zauvijek se promijenila. A sada se temelji na kvantnoj fizici

“Nove ideje u ovom radu vjerojatno će potaknuti daljnja istraživanja i mogle bi dovesti do praktičnih poboljšanja u budućnosti”.

U međuvremenu, Harvey i njegov suistraživač, Joris van der Hoeven s École Polytechnique u Francuskoj, kažu da njihov algoritam treba optimizirati i samo se nadaju da su otkrili nešto u svojim testovima.

"Mnogo posla nas je uvjerilo da je to stvarno ispravno", rekao je Harvey za AAP. "Još uvijek se bojim da bi sve moglo poći po zlu."

Nalazi su dostupni u HAL arhivi otvorenog pristupa.

IZVOR / Znanstveno upozorenje