Burnickel-Ziegler algoritm

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 19 juni 2020; kontroller kräver 4 redigeringar .

Burnickel-Ziegler-algoritmen ( tyska: Burnikel-Ziegler-Verfahren ) är en algoritm för att dividera stora heltal , beskrev av Christoph Burnickel och Joachim Ziegler 1998 [1] , som gör att du effektivt kan beräkna både kvoten och resten av divisionen .

Kärnan i metoden är algoritmer och , som delar tal med längder , , , . Algoritmerna anropar varandra rekursivt, där varje steg minskar längden på täljaren med 1/4 respektive 1/3 [1] . Algoritmen utför bland annat multiplikation , så dess prestanda kan ökas med snabba multiplikationsmetoder . $D_{2n/1n}$ $D_{3n/2n}$ $2n$ $1n$ $3n$ $2n$ $D_{3n/2n}$

Om en algoritm används i beräkningarna, vars beräkningskomplexitet är till exempel Karatsuba- eller Toom-Cook- algoritmen, så kommer komplexiteten för Burnickel-Ziegler-algoritmen också att vara . Om beräkningen använder Schönhage-Strassen multiplikationsmetoden med , så blir divisionskomplexiteten [1] :11 $O(n^{c})$ $O(n^{c})$ $O(n\log n\log \log n)$ $O(n\log ^{2}n\log \log n)$

I praktiken är algoritmen snabbare än långdivision och Barretts algoritm för tal vars antal decimaler ligger mellan cirka 250 och 1,5 miljoner [1] :22 .

Används i många standardprogrambibliotek, som Java version 8 [2] och GMP [3] .

Anteckningar

↑ 1 2 3 4 Christoph Burnikel; Joachim Ziegler. Snabb rekursiv division . Max-Planck-Institut für Informatik (oktober 1998). Datum för åtkomst: 27 juni 2014. Arkiverad från originalet 3 december 2013.
↑ JDK-8014319: Snabbare uppdelning av stora heltal . Oracle . Datum för åtkomst: 27 juni 2014. Arkiverad från originalet 3 december 2013.
↑ Dela och erövra division . gmplib.org. Datum för åtkomst: 27 juni 2014. Arkiverad från originalet 5 december 2013.

Talteoretiska algoritmer
Enkelhetstest	Mjölnare Miller - Rabin Luca - Lemaire pepina Agrawala - Kayala - Sachsen Nightingale - Strassen
Hitta primtal	Itererar över divisorer Sil av Eratosthenes Atkins såll Sikt Sundarama
Faktorisering	Itererar över divisorer Fermat-metoden p −1 Pollardmetoden Pollards ρ-algoritm Lehmanns metod Elliptisk kurvmetod (Lenstras algoritm) Dixons algoritm Fyrkantig sil
Diskret logaritm	Gelfond-Shanks algoritm Polig-Hellman algoritm Pollards ρ-metod Pollards kängurualgoritm Adlemans algoritm COS-algoritm
Hitta GCD	Euklids algoritm Avancerad algoritm Binär algoritm
Modulo aritmetik	Montgomerys algoritm Kinesisk restsats
Multiplikation och division av tal	Karatsuba algoritm Toom-Cook algoritm Schönhage-Strassen algoritm Fuhrer algoritm Harvey-van der Hoevens algoritm Burnickel-Ziegler algoritm
Beräkna kvadratroten	Tonelli-Shanks algoritm Berlekamp-Rabin algoritm