Doi matematicieni din Australia și Franța au creat o modalitate inedită de multiplicare a numerelor, rezolvând în același timp o enigmă algoritmică care i-ar fi lăsat cel puțin nedumeriți pe unii dintre cele mai mari minți ale matematicii de acum aproape o jumătate de secol.
Înmulțirea numerelor mici poate fi foarte ușoară. Dar ce se întâmplă dacă numerele devin mai mari? Ei bine, dacă cifrele devin grele, majoritatea dintre noi ar trece la înmulțirea lungă: un alt truc util pe care l-am învățat la școală și o tehnică de încredere pentru a înmulți practic două numere împreună. Dar există o problemă cu înmulțirea lungă, este lentă.
Mai mult, este o problemă pentru calculatoare, deoarece propriile lor blocaje în efectuarea calculelor sunt impuse de limitele matematicii abstracte pe care noi înșine o putem înțelege.
Practic, înmulțirea lungă este un algoritm, dar nu este deosebit de eficient, deoarece procesul este inevitabil de laborios.
CITEȘTE ȘI: Matematica are, în sfârșit, o explicație științifică a motivului pentru care articulațiile tale crapă
De fapt, matematicienii au descoperit un nou mod de a calcula cât de dificilă este înmulțirea lungă.
După cum explică matematicianul David Harvey de la UNSW din Australia în videoclipul de mai jos, într-o înmulțire în care ambele numere au trei cifre ( n = 3), numărul de operații de înmulțire separate implicate este de fapt 9, adică n 2:
Pe măsură ce numerele cresc, crește și cantitatea de muncă implicată, care este întotdeauna reprezentată prin n la puterea 2.
Deși ineficient, algoritmul înmulțirii lungi a fost de fapt cel mai avansat algoritm de înmulțire pe care l-am avut până în anii 1960, când matematicianul rus Anatoly Karatsuba a descoperit că n 1,58 a fost posibil.
Un deceniu mai târziu, doi matematicieni germani au făcut o altă descoperire: algoritmul Schönhage-Strassen, care a presupus - dar nu a dovedit niciodată - că sunt posibile și alte rafinamente.
"Ei au prezis că ar trebui să existe un algoritm care să înmulțească numerele de la n cifre folosind în esență operațiile de bază ale n * log ( n )", explică Harvey .
"Lucrarea noastră oferă primul exemplu cunoscut de algoritm care realizează acest lucru."
Potrivit cercetătorilor, înmulțirea a două numere cu câte un miliard de cifre fiecare prin procesul lung de înmulțire ar dura luni de zile pentru a le calcula.
Folosind algoritmul Schönhage-Strassen, ar dura mai puțin de 30 de secunde, iar cu dovada teoretică , ar fi chiar mai rapid - teoretic - și ar putea reprezenta chiar cel mai rapid algoritm de înmulțire posibil din punct de vedere matematic.
CITEȘTE ȘI: Matematica poate ajuta la prezicerea modului în care se dezvoltă celulele canceroase
"În acest sens, munca noastră este, sperăm, capătul drumului pentru această problemă, deși nu știm încă cum să dovedim acest lucru în mod riguros", spune Harvey .
"Oamenii au căutat acel algoritm timp de aproape 50 de ani, nu a fost cu o concluzie de la sine înțeleasă că cineva va ajunge să aibă succes."
Este demn de remarcat faptul că noul algoritm ar fi util doar pentru înmulțirea numerelor foarte mari. Cât de mari mai exact?
"Nu avem nicio idee", explică cercetătorii într-o întrebare frecventă, deși un exemplu pe care îl dau în lucrare este 10 214857091104455251940635045059417341952 , care este un număr foarte, foarte, foarte, foarte mare. Comunitatea matematică din lume încă absoarbe noile descoperiri, care trebuie încă să fie revizuite de către colegi.
Fürer însuși a încercat să reformuleze algoritmul Schönhage-Strassen cu mai bine de un deceniu în urmă, dar în cele din urmă a renunțat la această activitate, spunând: "Părea mai degrabă inutil".
"Dacă rezultatul este corect, este o realizare majoră în teoria complexității computaționale", a declarat el a declarat pentru New Scientist o matematicianul și informaticianul Fredrik Johansson, de la INRIA Bordeaux și de la Institutul de Matematică din Bordeaux.
CITEȘTE ȘI: Definiția kilogramului s-a schimbat pentru totdeauna. Ea se bazează acum pe fizica cuantică
"Noile perspective din această lucrare sunt susceptibile de a inspira cercetări suplimentare și ar putea duce la îmbunătățiri practice în viitor."
Între timp, Harvey și colegul său de cercetare, Joris van der Hoeven, de la École Polytechnique din Franța, spun că algoritmul lor trebuie optimizat și speră doar că au descoperit ceva în testele lor.
"O mare parte din muncă a constat în a ne convinge că acest lucru este de fapt corect", a declarat Harvey pentru AAP, "Încă sunt speriat că ar putea sfârși prin a merge prost".
Rezultatele sunt disponibile în arhiva cu acces liber HAL .
SURSA / Alertă științifică
