- Înmulțirea numerelor mari este dificilă. În 1971, doi profesori germani au prezis un algoritm care ar face-o mai ușoară, dar nimeni nu l-a demonstrat vreodată.
- Până acum.
- Matematicienii din Australia și Franța spun că algoritmul lor poate face înmulțirea și alte tipuri de aritmetică mult mai eficiente.
De la școala primară încoace, înmulțirea complexă a fost o bătaie de cap. Dar un profesor asistent de la Universitatea New South Wales Sydney din Australia a dezvoltat o nouă metodă de înmulțire a numerelor gigantice împreună, care este mai eficientă decât „înmulțirea lungă” pe care atât de mulți sunt învățați de mici.
„Mai mult din punct de vedere tehnic, am demonstrat o conjectură din 1971 a lui Schönhage și Strassen despre complexitatea înmulțirii numerelor întregi”, spune profesorul asociat David Harvey în videoclipul de mai jos.
Algoritmul Schönhage-Strassen, dezvoltat de doi matematicieni germani, a fost de fapt cea mai rapidă metodă de înmulțire din 1971 până în 2007. Deși în 2007 a fost dezvoltată o metodă mai rapidă, aceasta este rar folosită astăzi.
Schönhage și Strassen au prezis că ar trebui să existe un algoritm care să înmulțească numere de n cifre folosind n * log(n) operații de bază, spune Harvey. Lucrarea sa este prima dovadă cunoscută că acesta există.
Harvey alege exemplul lui 314 înmulțit cu 159 – o ecuație mare, desigur, dar ecuații mult mai mari sunt folosite în fiecare zi în scenarii din viața reală. Pentru a rezolva problema, majoritatea oamenilor sunt învățați să înmulțească fiecare număr în parte și apoi să adune sumele:
9 se înmulțește cu 4, 1 și 3; apoi 5 se înmulțește cu 4, 1 și 3, și așa mai departe. Rezultatul se încheie cu 9 produse cifră cu cifră.
Această metodă se numește n2 sau n la pătrat, deoarece trebuie să se multiplice n cu n de mai multe ori. Ea va obține răspunsul corect, dar Schönhage și Strassen au conceput o metodă mai rapidă. Aceasta a fost capabilă să treacă dincolo de n2 și să ajungă la ceva mai mic, dar încă se prezenta o provocare sub forma lui n * log(n).
Pentru unii, să vadă un cuvânt în mijlocul unei probleme de matematică ar putea fi suficient pentru a le face ochii să se blocheze, așa cum au făcut-o la ora de algebră. Ca o reîmprospătare: log este prescurtarea de la logaritm, care îi ajută pe oameni să descifreze exponenții care fac numerele la pătrat sau la cub sau chiar ceva mai mare. Așadar, 2⁵ este 32, dar exprimat logaritmic, ar arăta ca log₂(32)=5. Deși poate părea o vorbă lungă, logaritmii sunt cruciali atunci când numerele devin mult mai mari.
Metoda Schönhage-Strassen este foarte rapidă, spune Harvey. Dacă un computer ar trebui să folosească metoda pătratului predată la școală pe o problemă în care două numere au câte un miliard de cifre fiecare, ar dura luni de zile. Un computer care folosește metoda Schönhage-Strassen ar putea face acest lucru în 30 de secunde.
Dar dacă numerele continuă să crească până la trilioane și mai departe, algoritmul dezvoltat de Harvey și colaboratorul Joris van der Hoeven de la École Polytechnique din Franța ar putea găsi soluții mai repede decât algoritmul Schönhage-Strassen din 1971.
„Înseamnă că se pot face tot felul de calcule aritmetice mai eficient, de exemplu diviziunea și rădăcinile pătrate”, spune el. „De asemenea, ați putea calcula cifrele lui pi mai eficient decât înainte. Are chiar și aplicații la probleme care implică numere prime uriașe.
„Oamenii au vânat un astfel de algoritm timp de aproape 50 de ani”, continuă el. Nu era o concluzie de la sine înțeleasă că cineva va reuși în cele din urmă. S-ar fi putut dovedi că Schönhage și Strassen s-au înșelat și că un astfel de algoritm nu este posibil.
„Dar acum știm mai bine”, spune el.
.