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] .
Talteoretiske algoritmer | |
---|---|
Enkelthedstest | |
At finde primtal | |
Faktorisering |
|
Diskret logaritme | |
Finder GCD | |
Modulo aritmetik | |
Multiplikation og division af tal | |
Beregning af kvadratroden |