Burnickel-Ziegler algoritme

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 19. juni 2020; checks kræver 4 redigeringer .

Burnickel-Ziegler-algoritmen ( tysk :  Burnikel-Ziegler-Verfahren ) er en algoritme til at dividere store heltal , beskrevet af Christoph Burnickel og Joachim Ziegler i 1998 [1] , som giver dig mulighed for effektivt at beregne både kvotienten og resten af ​​divisionen .

Kernen i metoden er algoritmer og , som deler tal med længder , , , . Algoritmerne kalder hinanden rekursivt, hvor hvert trin reducerer længden af ​​tælleren med henholdsvis 1/4 og 1/3 [1] . Algoritmen udfører blandt andet multiplikation, så dens ydeevne kan øges ved hjælp af hurtige multiplikationsmetoder .

Hvis der anvendes en algoritme i beregningerne, hvis beregningsmæssige kompleksitet er for eksempel Karatsuba eller Toom-Cook algoritmen, så vil kompleksiteten af ​​Burnickel-Ziegler algoritmen også være . Hvis beregningen bruger Schönhage-Strassen multiplikationsmetoden med , så vil divisionskompleksiteten være [1] :11

I praksis er algoritmen hurtigere end lang division og Barretts algoritme for tal, hvis antal decimaler ligger mellem cirka 250 og 1,5 millioner [1] :22 .

Anvendes i mange standardsoftwarebiblioteker, såsom Java version 8 [2] og GMP [3] .

Noter

  1. 1 2 3 4 Christoph Burnikel; Joachim Ziegler. Hurtig rekursiv division  . Max-Planck-Institut für Informatik (oktober 1998). Dato for adgang: 27. juni 2014. Arkiveret fra originalen 3. december 2013.
  2. JDK-8014319: Hurtigere division af store  heltal . Oracle . Dato for adgang: 27. juni 2014. Arkiveret fra originalen 3. december 2013.
  3. Divide and Conquer  Division . gmplib.org. Dato for adgang: 27. juni 2014. Arkiveret fra originalen 5. december 2013.