Envoyer un e-mail à Collection ThomsonCollection Thomson
EditoForum 2002Liens
Nanoreseau
Docs
Logiciels
Matériel
Imprimer le document
Retour à la liste

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 l’on 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 l’opé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) d’autant 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 s’effectuera d’office. 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 s’effectuer 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) d’autant 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             |
Site
Plus
Forums
Code
Créations

*Site en favoris
*Page en favoris
*Site en démarrage
*Page en démarrage


Haut de page

Collection Thomson 2015 © Ghislain Fournier & François Mouret