Algoritmul Burnickel-Ziegler

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 19 iunie 2020; verificările necesită 4 modificări .

Algoritmul Burnickel-Ziegler ( germană: Burnikel-Ziegler-Verfahren ) este un algoritm pentru împărțirea numerelor întregi mari , descris de Christoph Burnickel și Joachim Ziegler în 1998 [1] , care vă permite să calculați eficient atât câtul cât și restul diviziunii .

Miezul metodei îl reprezintă algoritmii și , care împart numerele cu lungimi , , , . Algoritmii se apelează reciproc recursiv, fiecare pas reducând lungimea numărătorului cu 1/4 și respectiv 1/3 [1] . Algoritmul , printre altele, efectuează înmulțirea, astfel încât performanța acestuia poate fi mărită folosind metode rapide de înmulțire . $D_{2n/1n}$ $D_{3n/2n}$ $2n$ $1n$ $3n$ $2n$ $D_{3n/2n}$

Dacă în calcule se utilizează un algoritm, a cărui complexitate de calcul este , de exemplu, algoritmul Karatsuba sau Toom-Cook , atunci complexitatea algoritmului Burnickel-Ziegler va fi, de asemenea, . Dacă calculul folosește metoda de înmulțire Schönhage-Strassen cu , atunci complexitatea diviziunii va fi [1] :11 $O(n^{c})$ $O(n^{c})$ $O (n\log n\log \log n)$ $O(n\log ^{2}n\log \log n)$

În practică, algoritmul este mai rapid decât diviziunea lungă și algoritmul lui Barrett pentru numere al căror număr de zecimale se află între aproximativ 250 și 1,5 milioane [1] :22 .

Folosit în multe biblioteci software standard, cum ar fi Java versiunea 8 [2] și GMP [3] .

Note

↑ 1 2 3 4 Christoph Burnikel; Joachim Ziegler. Divizia recursiva rapidă . Max-Planck-Institut für Informatik (octombrie 1998). Data accesului: 27 iunie 2014. Arhivat din original pe 3 decembrie 2013.
↑ JDK-8014319: Împărțirea mai rapidă a numerelor întregi mari . Oracolul . Data accesului: 27 iunie 2014. Arhivat din original pe 3 decembrie 2013.
↑ Divizia Împărțiți și Cuceriți . gmplib.org. Data accesului: 27 iunie 2014. Arhivat din original pe 5 decembrie 2013.

Algoritmi teoretici numerelor
Teste de simplitate	Miller Miller - Rabin Luca - Lemaire pepina Agrawala - Kayala - Saxonia Privighetoarea - Strassen
Găsirea numerelor prime	Iterarea peste divizori Sita lui Eratosthenes sita lui Atkin Sieve Sundarama
Factorizarea	Iterarea peste divizori Metoda Fermat p −1 Metoda Pollard Algoritmul ρ al lui Pollard metoda Lehmann Metoda curbei eliptice (algoritmul lui Lenstra) algoritmul lui Dixon Sita pătrată
Logaritm discret	Algoritmul Gelfond-Shanks Algoritmul Polig-Hellman Metoda ρ a lui Pollard Algoritmul Cangurului lui Pollard Algoritmul lui Adleman Algoritmul COS
Găsirea GCD	algoritmul lui Euclid Algoritm avansat Algoritm binar
Modul de aritmetică	Algoritmul lui Montgomery Teorema chineză a restului
Înmulțirea și împărțirea numerelor	Algoritmul Karatsuba Algoritmul Toom-Cook Algoritmul Schönhage-Strassen Algoritmul Fuhrer Algoritmul Harvey-van der Hoeven Algoritmul Burnickel-Ziegler
Calcularea rădăcinii pătrate	Algoritmul Tonelli-Shanks Algoritmul Berlekamp-Rabin