Division binaire
La division binaire est l'opération arithmétique permettant de calculer le quotient et, dans la plupart des cas, le reste de la division entre deux nombres représentés en base 2. À l'instar de la division décimale enseignée à l'école, elle repose sur une succession de comparaisons, de soustractions et de décalages. Bien que les ordinateurs manipulent uniquement les chiffres 0 et 1, le principe général demeure identique : déterminer combien de fois le diviseur peut être contenu dans le dividende, puis poursuivre le calcul sur le reste obtenu.
La division est généralement considérée comme l'une des opérations arithmétiques les plus complexes à réaliser matériellement. Contrairement à l'addition et à la soustraction, qui peuvent être exécutées très rapidement à l'aide de quelques portes logiques, la division nécessite plusieurs étapes successives. Pour cette raison, les processeurs modernes utilisent des algorithmes spécialisés permettant d'accélérer le calcul ou disposent d'unités matérielles dédiées capables d'effectuer les divisions de manière efficace.
Principe
La division binaire suit exactement le même principe que la division décimale.
À chaque étape :
- Une partie du dividende est examinée.
- Cette valeur est comparée au diviseur.
- Si elle est supérieure ou égale au diviseur, celui-ci est soustrait.
- Le quotient reçoit alors un bit égal à 1.
- Sinon, le quotient reçoit un bit égal à 0.
- L'opération est répétée jusqu'à ce que tous les bits aient été traités.
Le résultat d'une division comprend généralement :
- le quotient ;
- le reste.
Mathématiquement, cela s'écrit :
| Dividende = Quotient × Diviseur + Reste |
où le reste est toujours inférieur au diviseur.
Exemple
Calculons :
| 11002 ÷ 102 |
En décimal :
|
11002 = 12 102 = 2 |
Le calcul donne :
| 12 &divise; 2 = 6 |
En binaire :
| 1102 |
Le résultat devient donc :
| 11002 ÷ 102 = 1102 |
Exemple avec reste
Considérons maintenant :
| 11112 ÷ 102 |
En décimal :
| 15 ÷ 2 |
Le quotient vaut :
| 7 |
Le reste vaut :
| 1 |
En binaire :
|
11112 ÷ 102 Quotient = 1112 Reste = 12 |
Division posée
Comme en base décimale, la division peut être effectuée sous forme de division posée.
Exemple :
|
110 ------- 10 ) 1100 10 -- 10 10 -- 0 |
Le quotient est :
| 1102 |
Aucun reste n'est présent dans cet exemple.
Algorithme naïf
Une première méthode consiste à effectuer des soustractions répétées.
L'algorithme est très simple :
|
MODULE Division(a,b) quotient ← 0 TANT QUE a ≥ b a ← a - b quotient ← quotient + 1 FIN TANT QUE reste ← a RETOURNER quotient, reste |
Cette méthode est facile à comprendre mais devient très lente lorsque le quotient est important.
Par exemple :
| 1000000 ÷ 2 |
nécessiterait des centaines de milliers de soustractions.
Division par décalages
Une méthode beaucoup plus efficace consiste à utiliser les décalages de bits.
L'idée est de rechercher le plus grand multiple du diviseur pouvant être obtenu grâce à un décalage vers la gauche.
Par exemple :
|
1012 << 1 = 10102 1012 << 2 = 101002 |
Ces multiples sont ensuite soustraits progressivement du dividende.
Cette technique est très proche de la méthode utilisée par les processeurs modernes.
Algorithme classique
Une représentation simplifiée est la suivante :
|
MODULE Division(a,b) quotient ← 0 reste ← 0 POUR chaque bit du dividende Décaler reste vers la gauche Ajouter le bit courant SI reste ≥ b ALORS reste ← reste - b Ajouter 1 au quotient SINON Ajouter 0 au quotient FIN SI FIN POUR RETOURNER quotient, reste |
Cet algorithme est appelé division binaire restauratrice (Restoring Division).
Division restauratrice
La division restauratrice est l'un des premiers algorithmes utilisés dans les processeurs.
À chaque étape :
- une soustraction est tentée ;
- si elle produit un résultat négatif, celui-ci est annulé ("restauré") ;
- sinon, le quotient reçoit un bit égal à 1.
Cette méthode est simple à implémenter mais effectue parfois des opérations inutiles.
Division non restauratrice
Une amélioration consiste à utiliser la division non restauratrice.
Au lieu d'annuler immédiatement une soustraction négative, l'algorithme poursuit directement le calcul en effectuant une addition lors de l'itération suivante.
Cette technique réduit le nombre d'opérations nécessaires.
De nombreux processeurs ont utilisé cette méthode pendant plusieurs décennies.
Division de SRT
Les processeurs modernes utilisent souvent une variante appelée division SRT, développée par :
- Sweeney,
- Robertson,
- Tocher.
Cette méthode autorise plusieurs valeurs intermédiaires du quotient :
|
-2 -1 0 1 2 |
Elle permet de produire plusieurs bits du quotient plus rapidement et améliore les performances des unités de division matérielles.
Division de Newton-Raphson
Pour les calculs scientifiques, il est souvent plus rapide de calculer :
| 1 / b |
puis de multiplier :
| a × (1 / b) |
L'inverse est obtenu grâce à une méthode d'approximation appelée Newton-Raphson.
Cette technique est particulièrement utilisée dans :
- les processeurs modernes ;
- les coprocesseurs mathématiques ;
- les bibliothèques multiprécision.
Complexité
Les principales méthodes possèdent les complexités suivantes :
| Algorithme | Complexité approximative |
|---|---|
| Soustractions répétées | O(q) (q = quotient) |
| Division restauratrice | O(n2) |
| Division non restauratrice | O(n2) |
| Newton-Raphson | O(M(n)) |
| Burnikel-Ziegler | O(M(n)) |
Dans ce tableau, M(n) représente la complexité de la multiplication utilisée.
Ainsi, si la multiplication est accélérée par Karatsuba, Toom-Cook ou une FFT, la division bénéficie automatiquement de cette amélioration.
Exemple en Java
Résultat :
20 / 4 = 515 / 2 = 7
15 % 2 = 1
Dans cet exemple, l'opérateur / effectue une division entière puisque les deux opérandes sont des entiers, tandis que l'opérateur % retourne le reste de la division.
Avantages
La division binaire présente plusieurs avantages :
- elle constitue la base de toutes les divisions réalisées par les processeurs ;
- elle permet de calculer simultanément le quotient et le reste ;
- elle est adaptée aux calculs sur les très grands entiers ;
- elle bénéficie directement des progrès réalisés sur les algorithmes de multiplication ;
- elle est utilisée dans la plupart des bibliothèques d'arithmétique multiprécision.
Inconvénients
La division demeure néanmoins plus complexe que les autres opérations arithmétiques :
- elle nécessite davantage d'étapes que l'addition ou la soustraction ;
- les circuits matériels sont plus complexes ;
- certaines méthodes exigent des approximations successives ;
- la gestion des dépassements et des divisions par zéro doit être assurée ;
- plusieurs algorithmes sont nécessaires selon la taille des opérandes.
Applications
La division binaire est utilisée dans pratiquement tous les domaines de l'informatique :
- processeurs et microcontrôleurs ;
- unités arithmétiques et logiques (ALU) ;
- calcul scientifique ;
- bibliothèques multiprécision ;
- cryptographie ;
- systèmes embarqués ;
- compilateurs ;
- moteurs graphiques ;
- logiciels de simulation numérique.
Elle intervient également dans de nombreux algorithmes plus complexes, notamment le calcul des fractions, des nombres rationnels, des fonctions mathématiques, des inverses modulaires et des opérations de cryptographie à clé publique.
Remarque
Dans les langages de programmation modernes, une simple instruction telle que :
| A / B |
cache souvent un traitement beaucoup plus élaboré que ce que laisse supposer sa syntaxe. Selon le type des données (entiers, nombres à virgule flottante ou grands entiers), le compilateur ou la bibliothèque d'exécution choisira un algorithme adapté. Pour des entiers de taille machine, une instruction matérielle de division est généralement utilisée. En revanche, pour les bibliothèques de calcul multiprécision, des algorithmes spécialisés comme Burnikel-Ziegler, Newton-Raphson ou Barrett peuvent être employés afin d'obtenir les meilleures performances possibles.