Algorithme de Burnikel-Ziegler
L'algorithme de Burnikel-Ziegler est un algorithme de division rapide de grands entiers publié en 1998 par Christoph Burnikel et Joachim Ziegler. Il a été conçu pour accélérer les divisions de nombres contenant plusieurs centaines ou plusieurs milliers de chiffres, domaine dans lequel les méthodes classiques deviennent progressivement inefficaces. Aujourd'hui, cet algorithme est largement utilisé dans les bibliothèques d'arithmétique multiprécision et constitue l'une des méthodes de référence pour effectuer des divisions sur des entiers de très grande taille.
Contrairement aux algorithmes de division binaire traditionnels, qui traitent les bits un à un, Burnikel-Ziegler adopte une approche fondée sur le principe «diviser pour régner» (Divide and Conquer). Les nombres sont découpés en plusieurs blocs de taille fixe, puis la division est réalisée récursivement sur ces blocs. Cette stratégie permet de réduire considérablement le nombre d'opérations nécessaires et d'exploiter efficacement les algorithmes modernes de multiplication rapide tels que Karatsuba, Toom-Cook ou les méthodes basées sur la Transformée de Fourier Rapide (FFT).
Historique
Pendant longtemps, les ordinateurs ont utilisé des méthodes relativement simples pour effectuer les divisions, comme les divisions restauratrices ou non restauratrices. Ces techniques sont bien adaptées aux entiers de la taille d'un registre processeur, mais deviennent coûteuses lorsque les nombres comportent plusieurs milliers de bits.
À la fin des années 1990, l'utilisation croissante de la cryptographie, du calcul scientifique et des bibliothèques multiprécision a créé un besoin pour des algorithmes plus performants. C'est dans ce contexte que Christoph Burnikel et Joachim Ziegler publièrent un nouvel algorithme permettant d'effectuer des divisions récursives en utilisant des blocs de grande taille plutôt que des bits individuels.
Depuis, leur méthode est devenue un composant essentiel de nombreuses bibliothèques spécialisées dans le calcul sur grands entiers.
Principe
Le principe fondamental de l'algorithme consiste à découper les opérandes en blocs de même taille.
Par exemple, le dividende :
| 12345678901234567890 |
peut être représenté sous la forme :
| [12345][67890][12345][67890] |
Le diviseur est découpé selon le même principe.
L'algorithme effectue ensuite plusieurs divisions partielles entre ces blocs avant de reconstruire progressivement le quotient complet.
Cette méthode ressemble à la division posée enseignée à l'école, mais elle est appliquée sur des blocs de plusieurs dizaines ou centaines de bits plutôt que sur un seul chiffre.
Le principe « Diviser pour régner »
Burnikel-Ziegler applique le même principe que Karatsuba ou Toom-Cook.
Au lieu de résoudre directement une grande division :
| A ÷ B |
l'algorithme :
- découpe les nombres ;
- effectue plusieurs divisions plus petites ;
- combine les résultats.
Cette stratégie récursive réduit fortement le coût des calculs lorsque les nombres deviennent très grands.
Les différentes étapes
Le fonctionnement général peut être résumé de la manière suivante :
- Découper le dividende et le diviseur en blocs de taille identique.
- Normaliser les opérandes afin de simplifier les calculs.
- Effectuer plusieurs divisions partielles.
- Corriger le quotient lorsque cela est nécessaire.
- Reconstituer progressivement le quotient complet.
- Calculer le reste final.
L'ensemble de ces étapes est exécuté récursivement jusqu'à ce que les blocs deviennent suffisamment petits pour utiliser une méthode de division classique.
Algorithme simplifié
Une représentation simplifiée est la suivante :
|
MODULE BurnikelZiegler(A,B) SI les nombres sont petits ALORS RETOURNER DivisionClassique(A,B) FIN SI Découper A en blocs Découper B en blocs Effectuer les divisions récursives Corriger le quotient Calculer le reste RETOURNER quotient, reste |
Naturellement, l'algorithme réel est beaucoup plus élaboré et comporte plusieurs traitements intermédiaires destinés à optimiser les performances.
Pourquoi est-il rapide ?
La rapidité de Burnikel-Ziegler provient principalement de deux caractéristiques :
- il traite plusieurs centaines de bits simultanément ;
- il utilise des multiplications rapides pour accélérer certaines étapes de la division.
Autrement dit, les performances de cet algorithme dépendent directement de celles de la multiplication utilisée.
Si la bibliothèque emploie Karatsuba, Toom-Cook ou une FFT, Burnikel-Ziegler profite automatiquement de cette amélioration.
Complexité
La division classique possède généralement une complexité proche de :
| O(n2) |
L'algorithme de Burnikel-Ziegler atteint une complexité de :
| O(M(n)) |
où :
| M(n) |
désigne la complexité de la multiplication utilisée.
Ainsi :
- avec Karatsuba, la division bénéficie de la complexité de Karatsuba ;
- avec Toom-Cook, elle bénéficie de Toom-Cook ;
- avec une multiplication FFT, elle profite également de cette amélioration.
Cette propriété explique pourquoi Burnikel-Ziegler est aujourd'hui l'une des méthodes privilégiées dans les bibliothèques multiprécision.
Exemple conceptuel
Supposons que l'on souhaite calculer :
|
98765432109876543210 ÷ 1234567890 |
L'algorithme commence par découper le dividende en plusieurs blocs :
| [98765][43210][98765][43210] |
Le diviseur est également découpé.
Des divisions sont ensuite réalisées bloc par bloc.
Les quotients intermédiaires sont progressivement assemblés afin de produire le quotient final.
Cette méthode évite d'effectuer une très longue division sur l'ensemble des chiffres.
Avantages
L'algorithme de Burnikel-Ziegler présente de nombreux avantages :
- il est très performant sur les grands entiers ;
- il exploite efficacement les processeurs modernes ;
- il bénéficie automatiquement des progrès des algorithmes de multiplication ;
- il réduit fortement le temps nécessaire aux divisions multiprécision ;
- il est largement utilisé dans les bibliothèques spécialisées.
Inconvénients
Cette méthode présente néanmoins quelques limites :
- elle est beaucoup plus complexe qu'une division classique ;
- son implémentation est relativement difficile ;
- elle nécessite davantage de mémoire temporaire ;
- elle devient intéressante uniquement lorsque les nombres sont suffisamment grands ;
- pour les petits entiers, une division classique reste généralement plus rapide.
Applications
L'algorithme de Burnikel-Ziegler est utilisé dans de nombreux domaines :
- bibliothèques multiprécision ;
- cryptographie (RSA, ECC, Diffie-Hellman) ;
- calcul scientifique ;
- calcul formel ;
- logiciels de mathématiques ;
- démonstrations assistées par ordinateur ;
- recherche en théorie des nombres ;
- logiciels manipulant des entiers comportant plusieurs milliers de chiffres.
Il est notamment employé dans des bibliothèques telles que GNU Multiple Precision (GMP), Java BigInteger, OpenJDK, ainsi que dans plusieurs systèmes de calcul symbolique.
Comparaison avec les autres méthodes
| Algorithme | Utilisation principale |
|---|---|
| Division par soustractions répétées | Enseignement |
| Division restauratrice | Circuits électroniques simples |
| Division non restauratrice | Microprocesseurs |
| Division SRT | Processeurs modernes |
| Newton-Raphson | Calcul scientifique et virgule flottante |
| Burnikel-Ziegler | Division multiprécision de très grands entiers |
Chaque méthode possède son domaine d'application. Burnikel-Ziegler se distingue particulièrement lorsqu'il s'agit de manipuler des entiers beaucoup plus grands que ceux pouvant être représentés par les types numériques standards d'un langage de programmation.
Remarque
L'algorithme de Burnikel-Ziegler est aujourd'hui considéré comme l'un des piliers de l'arithmétique multiprécision moderne. Son approche récursive, fondée sur le découpage des opérandes en blocs, permet de réaliser des divisions très efficaces tout en tirant parti des meilleurs algorithmes de multiplication disponibles. Pour cette raison, de nombreuses bibliothèques spécialisées utilisent automatiquement Burnikel-Ziegler dès que les entiers dépassent un certain seuil de taille, puis reviennent à des méthodes plus simples lorsque les nombres sont plus petits. Cette sélection dynamique garantit les meilleures performances dans un très large éventail d'applications scientifiques, cryptographiques et informatiques.