Harvey-van der Hoeven algoritmus

A Harvey-van der Hoeven  algoritmus kétbites egész számok időbonyolultságú szorzására szolgáló algoritmus a többszalagos Turing-gép modellben . David Harvey matematikusok, az Új-Dél-Wales Egyetemről és Joris van der Hoeven , a Francia Nemzeti Tudományos Kutatási Központtól javasolták . 2020-tól ez a leggyorsabb ismert algoritmus a számok szorzására ebben a modellben, míg a szorzóalgoritmusok időbonyolultságának becslése javíthatatlannak tűnik.

Történelem

Az egész számok szorzására szolgáló gyors algoritmusok létezésének kérdése fontos helyet foglal el a számítási komplexitás elméletében . A legismertebb szorzási módszerek, mint például a halmozott szorzás, számtani műveleteket igényelnek. Ezt a becslést először 1960-ban Anatolij Karatsuba javította , aki egy algoritmust javasolt a futásidővel való szorzáshoz [1] . 1971-ben Schönhage és Strassen egy olyan algoritmust javasolt, amely a gyors Fourier-transzformáción alapul [2] . Ugyanebben a munkában azt a hipotézist állítottak fel, hogy az optimális szorzási algoritmushoz elemi műveletek szükségesek. A Schönhage és Strassen algoritmus által megadott felső korlát azonban sokáig javulás nélkül maradt. Csak 2007-ben, 36 évvel később Martin Fuhrer javasolt egy algoritmust futási idővel egy meghatározatlan állandóhoz , ahol  egy iterált logaritmus [3] . Ezt követően Harvey és van der Hoeven ezt a becslést először [4] -re , majd -ra javította, ezzel megerősítve a Schönhage és Strassen [5] sejtésében felállított felső korlátot . Az algoritmusnak nagy elméleti jelentősége van, mivel a többszalagos Turing-gép modellben a számszorzó algoritmusok futásidejének hipotetikus alsó korlátját éri el. Gyakorlati gyorsulás azonban csak olyan számokon érhető el, amelyek bináris hossza meghaladja a bitet, míg a részecskék számát a megfigyelhető univerzumban [6] -ra becsülik .

Jegyzetek

  1. A. Karatsuba, Y. Offman. Többértékű számok szorzása automatákon  // Dokl. A Szovjetunió Tudományos Akadémia. - 1962. - február 9. ( 145. köt. , 2. szám ). - S. 293-294 .
  2. A. Schönhage, V. Strassen. Schnelle Multiplikation großer Zahlen  (német)  // Számítástechnika. — 1971-09-01. — bd. 7 , H. 3 . – S. 281–292 . — ISSN 1436-5057 . - doi : 10.1007/BF02242355 .
  3. Martin Furer. Gyorsabb egész szám szorzás  (angol)  // SIAM Journal on Computing. — 2009-01. — Vol. 39 , iss. 3 . — P. 979–1005 . - ISSN 1095-7111 0097-5397, 1095-7111 . - doi : 10.1137/070711761 .
  4. David Harvey, Joris van der Hoeven. Gyorsabb egész számok szorzása rövid rácsvektorok segítségével  //  The Open Book Series. — 2019-01-28. — Vol. 2 , iss. 1 . — P. 293–310 . — ISSN 2329-9061 2329-907X, 2329-9061 . - doi : 10.2140/obs.2019.2.293 .
  5. David Harvey, Joris Van Der Hoeven. Egész szám szorzása O(n log n  ) időben . — 2019. Archiválva : 2019. április 8. a Wayback Machine -nél
  6. Erica Klarreich. A szorzás elérte a sebességkorlátozást  //  Az ACM kommunikációja. - 2019. - december 20. - doi : 10.1145/3371387 . Archiválva az eredetiből: 2020. június 30.