Este posibil ca matematicienii să fi găsit cel mai rapid mod de a înmulți numere uriașe

Înmulțirea 2 x 2 este ușor. Dar înmulțirea a două numere cu mai mult de un miliard de cifre fiecare – asta necesită un calcul serios.

Tehnica înmulțirii predată în școală poate fi simplă, dar pentru numere cu adevărat mari, este prea lentă pentru a fi utilă. Acum, doi matematicieni spun că au găsit cea mai rapidă modalitate de a multiplica cifre extrem de mari.

Cei doi pretind că au atins limita maximă de viteză pentru multiplicare, sugerată pentru prima dată acum aproape 50 de ani. Acea ispravă, descrisă online pe 18 martie la arhiva de documente HAL, nu a trecut încă de mănușa evaluării inter pares. Dar dacă tehnica rezistă controlului, s-ar putea dovedi a fi cea mai rapidă modalitate posibilă de înmulțire a numerelor întregi sau întregi.

Dacă întrebi o persoană obișnuită ce fac matematicienii, „ei spun: „Oh, ei stau în biroul lor înmulțind numere mari împreună””, glumește coautorul studiului, David Harvey, de la Universitatea New South Wales din Sydney. „Pentru mine, este de fapt adevărat.”

Când faceți calcule cu numere exorbitant de mari, cea mai importantă măsură a vitezei este cât de repede crește numărul de operațiuni necesare – și, prin urmare, timpul necesar pentru a face calculul – pe măsură ce înmulțiți șiruri de cifre din ce în ce mai lungi.

Această creștere este exprimată în termeni de n, definit ca numărul de cifre din numerele înmulțite. Pentru noua tehnică, numărul de operații necesare este proporțional cu de n ori logaritmul lui n, exprimat ca O(n log n) în limbajul matematic. Asta înseamnă că, dacă dublezi numărul de cifre, numărul de operații necesare va crește puțin mai repede, mai mult decât dublând timpul de calcul.

Dar, spre deosebire de metodele mai simple de multiplicare, timpul necesar nu se multiplică de patru ori sau, altfel, nu explodează rapid, pe măsură ce numărul de cifre crește, raportează Harvey și Joris van der Hoeven de la agenția națională de cercetare franceză CNRS și École Polytechnique din Palaiseau. Această rată de creștere mai lentă face ca produsele cu numere mai mari să fie mai ușor de calculat.

Viteza maximă prezisă anterior pentru înmulțire a fost O(n log n), ceea ce înseamnă că noul rezultat îndeplinește limita așteptată. Deși este posibil să se găsească într-o zi o tehnică și mai rapidă, majoritatea matematicienilor cred că aceasta este la fel de rapidă pe cât poate fi înmulțirea.

„Am fost foarte uimit că s-a făcut”, spune informaticianul Martin Fürer de la Penn State. A descoperit o altă accelerare a înmulțirii în 2007, dar a renunțat să mai facă îmbunătățiri. „Mi s-a părut destul de fără speranță.”

Noua tehnică vine cu o avertizare: nu va fi mai rapidă decât metodele concurente, decât dacă înmulțiți cifre scandalos de uriașe. Dar nu este clar cât de mari trebuie să fie acele numere pentru ca tehnica să câștige – sau dacă este chiar posibil să se înmulțească numere atât de mari în lumea reală.

În noul studiu, cercetătorii au luat în considerare doar numere cu mai mult de aproximativ 10214857091104455251940635045059417341952 cifre atunci când sunt scrise în binar, în care numerele sunt codificate cu o secvență de 0 și 1. Dar oamenii de știință nu au efectuat de fapt nici una dintre aceste înmulțiri masive, pentru că sunt cu mult mai multe cifre decât numărul de atomi din univers. Asta înseamnă că nu există nicio modalitate de a face astfel de calcule pe computer, pentru că nu există destui atomi pentru a reprezenta numere atât de mari, cu atât mai puțin să le înmulțim împreună. În schimb, matematicienii au venit cu o tehnică despre care ar putea dovedi teoretic că ar fi mai rapidă decât alte metode, cel puțin pentru aceste cantități mari.

Există încă posibilitatea ca metoda să funcționeze pentru numere mai mici, dar încă mari. Acest lucru ar putea duce la utilizări practice, spune Fürer. Înmulțirea acestor numere colosale este utilă pentru anumite calcule detaliate, cum ar fi găsirea de noi numere prime cu milioane de cifre (SN Online: 1/5/18) sau calcularea pi cu o precizie extremă (SN Online: 12/10/02).

Chiar dacă metoda nu este utilă pe scară largă, progresul într-o problemă la fel de fundamentală precum înmulțirea este încă o realizare puternică. „Înmulțirea numerelor este ceva la care oamenii au lucrat de ceva vreme”, spune fizicianul matematician John Baez de la Universitatea din California, Riverside. „Este mare lucru, doar din cauza asta.”