La division en question
Généralement, lorsque l'on veut effectuer une division, on soustrait le diviseur au dividende en augmentant le quotient tant
que la soustraction est possible. Le reste de la division se trouve alors dans le registre du dividende.
Cette méthode est acceptable tant que les dividendes et les diviseurs sont
de tailles approximativement égales. Mais pour la division de grands nombres par des petits nombres,
l'opération risque de prendre beaucoup de temps, le programme se comportant comme une boucle de temporisation.
Il faut alors se résoudre à effectuer une division binaire.
Lorsque lon effectue une division en décimal sur papier, on soustrait
le diviseur au poids le plus fort du nombre. Si le diviseur est supérieur, on prend alors le chiffre
de poids inférieur. Si la soustraction est possible, on met à jour le quotient, puis on renouvelle lopération
jusquà la précision souhaitée. Effectuons, par exemple, la division en décimal de 775749 par 7 en imitant
la méthode de division binaire :
Dividende Diviseur Quotient
Valeurs de départ 775749 000007 000000
Ajustement du diviseur 775749 700000 000000
Le diviseur a donc été « calé à gauche », pour être sûr que le diviseur est, au
départ, supérieur, égal ou immédiatement inférieur au dividende. Puisque le diviseur a été « décalé »
de 5 zéros, il y aura donc 5 « décalages » à faire. Le diviseur est inférieur au dividende donc
soustraction préalable ce qui donne 775749-(1*700000)=075749 et le quotient est mis à jour, soit :
075749 700000 000001
« Décalage » 1 du dividende 0<757490 700000 000001
Le chiffre sortant est égal à 0, mais le dividende est supérieur au diviseur. La soustraction
est donc effectuée ce qui donne 757490-(1*700000)=057490 et le quotient est mis à jour, soit:
057490 700000 000011
« Décalage » 2 du dividende 0<574900 700000 000110
Le chiffre sortant étant à 0 et le dividende étant inférieur au diviseur,
pas de soustraction. « Décalage » du quotient.
« Décalage » 3 du dividende 5<749000 700000 000110
Le chiffre sortant étant différent de 0, le dividende est forcément supérieur au diviseur. La
soustraction est donc effectuée ce qui donne 5749000-(8*700000)=149000 et le quotient est mis à jour,
soit:
149000 700000 001108
« Décalage » 4 du dividende 1<490000 700000 001108
Le chiffre sortant étant différent de 0, le dividende est forcément supérieur au diviseur. La
soustraction est donc effectuée ce qui donne 1490000-(2*700000)=90000 et le quotient est mis à jour,
soit:
090000 700000 011082
« Décalage » 5 du dividende 0<900000 700000 011082
Le chiffre sortant est égal à 0, mais le dividende est supérieur au diviseur. La soustraction
est donc effectuée ce qui donne 900000-(1*700000)=200000 et le quotient est mis à jour, soit:
200000 700000 110821
Il ne reste plus quà décaler le reste (le dividende) dautant de chiffres vers
la droite que le diviseur a été décalé de chiffres vers la gauche au départ, soit de 5 chiffres :
000002 700000 110821
Pour la division de 775749 par 7, nous avons donc un quotient de 110821 et un reste de 2.
De la même façon, la division binaire nécessitera donc une petite préparation:
le diviseur doit être calé à gauche pour effectuer les opérations de soustraction et être certain que
le diviseur est bien, au départ, supérieur, égal ou immédiatement inférieur au dividende. Le dividende,
lui, sera décalé bit par bit vers la gauche pendant le calcul. Ainsi, si le bit sortant du dividende
est à 0, on vérifiera si le diviseur peut lui être retranché. Si le bit sortant du dividende est à 1,
le dividende sera alors forcément supérieur au diviseur et la soustraction seffectuera doffice.
En admettant que l'on ait à diviser 121 par 7 sur des registres 8 bits, on a 121=%01111001 pour le dividende
et 7=%00000111 pour le diviseur:
Dividende Diviseur Quotient
Valeurs de départ 01111001 00000111 00000000
Ajustement du diviseur 01111001 11100000 00000000
Le diviseur a donc été calé à gauche pour être sûr que le diviseur est bien supérieur,
égal ou immédiatement inférieur au dividende. Puisque le diviseur a été décalé de 5 bits, il y aura
donc 5 décalages à faire. Le diviseur est supérieur au dividende, donc pas de soustraction préalable.
Décalage 1 du dividende 0<-11110010 11100000 00000000
Le bit sortant est à 0 mais la soustraction peut seffectuer puisque le dividende est
supérieur au diviseur. Le quotient est mis à jour et on a donc :
00010010 11100000 00000001
Décalage 2 du dividende 0<-00100100 11100000 00000010
Le bit sortant étant à 0 et le dividende est inférieur au diviseur, pas de soustraction.
Décalage du quotient.
Décalage 3 du dividende 0<-01001000 11100000 00000100
Le bit sortant étant à 0 et le dividende est inférieur au diviseur, pas de soustraction.
Décalage du quotient.
Décalage 4 du dividende 0<-10010000 11100000 00001000
Le bit sortant étant à 0 et le dividende est toujours inférieur au diviseur, pas de
soustraction. Décalage du quotient.
Décalage 5 du dividende 1<-00100000 11100000 00010001
Le bit sortant étant à 1, le dividende est forcément supérieur au diviseur.
La soustraction est donc effectuée ce qui donne %00100000-%11100000=%01000000 puisque seuls les 8
derniers bits nous intéressent, et le quotient est décalé et augmenté, soit:
01000000 11100000 00010001
Il ne reste plus quà décaler le reste (le dividende) dautant de bits vers
la droite que le diviseur a été décalé de bits vers la gauche au départ, soit de 5 bits :
00000010 11100000 00010001
Pour la division de 121 par 7, nous avons donc un quotient de %00010001 soit 17 et un reste de %00000010 soit
2.
Ci-après, une routine de division entière 16 bits avec reste, extraite de ASSEMBLER
2.0 et aménagée pour la circonstance. En entrée, le diviseur dans D et le dividende dans X. En sortie,
le quotient dans D et le reste de la division dans X:
DIV LEAS -6,S Fait de la place dans la pile
STD 4,S Ecrit le diviseur
* Cale le diviseur à gauche
LDD #$0011 16 bits maximum
DIV0 INCA Compteur + 1
DECB Décompteur - 1
BEQ DIV5 Si pas de bits, erreur "division par 0"
ASL 5,S |
ROL 4,S | Décale le diviseur jusqu'au premier bit à 1
BCC DIV0 |
ROR 4,S | Rétablit le
ROR 5,S | débordement
* Prépare à la division
TFR A,B | Empile les
STD 2,S | compteurs
CLR ,S | Efface le
CLR 1,S | quotient
TFR X,D Dividende dans D
* Effectue la division
DIV1 BCS DIV2 Si le bit sortant est à 1, soustraction effectuée
CMPD 4,S | Si le dividende est inférieur
BLO DIV3 | au diviseur, passe
DIV2 SUBD 4,S Soustrait le diviseur au dividende
ORCC #$01 Retenue forcée à 1
FCB $7D |
DIV3 ANDCC #$FE Retenue forcée à 0
ROL 1,S | Décale le quotient en
ROL ,S | récupérant la retenue
ASLB | Décale le reste
ROLA | (le dividende)
DEC 2,S | Opération
BNE DIV1 | suivante
* Rétablit le reste en n'oubliant pas de récupérer le bit sortant
DIV4 RORA | Décale le
RORB | reste
ANDCC #$FE Retenue forcée à 0
DEC 3,S | Positionne en réponse
BNE DIV4 | au décalage du début
* Sortie du programme - Restitution des registres
TFR D,X Reste de la division dans X
CLRA Pas d'erreur dans CC (C=0)
PULS A,B Charge le quotient
LEAS 4,S Rétablit la pile
RTS |
* Sortie si division par 0
DIV5 LEAS 6,S Rétablit la pile
COMA Erreur dans CC (C=1)
RTS |
|