Triceraprog
La programmation depuis le Crétacé

À présent que j'ai un garde fou pour vérifier que je ne fais pas d'erreur d'inattention, me voilà près à diviser des nombres. Pour rappel j'ai besoin de diviser des nombres afin de faire les calculs permettant d'affiche le bon pixel à l'écran.

Pour second rappel, le Z80, au cœur du VG5000µ (et de beaucoup d'autres ordinateurs de l'époque) n'a pas d'instruction de division.

La division

Lorsque je divise de manière entière a par b, je veux trouver le nombre c tel quel $c * b = a$. Comme la division ne tombe pas toujours juste, j'ai aussi un reste r tel que $c * b + r = a$.

Autrement dit, combien de fois dois-je additionner b pour obtenir a (au reste près). Une manière de trouver le résultat est de soustraire b à a autant de fois que l'on peut sans passer sous 0.

Par exemple, $\frac{21}{7}$ se trouve comme ceci :

21 - 7 = 14
14 - 7 =  7
 7 - 7 =  0

Il y a trois soustractions, et donc $\frac{21}{7} = 3$

Un autre exemple avec $\frac{17}{3}$ :

17 - 3 = 14
14 - 3 = 11
11 - 3 = 8
 8 - 3 = 5
 5 - 3 = 2

Il y a cinq soustractions, et il reste 2 à la fin, dont la soustraction de 5 donnerait -3. On s'arrête donc et $\frac{17}{3} = 5 + \frac{2}{3}$

Un problème majeur de cette façon de faire est que plus le résultat est grand, plus il a fallu de calculs pour le trouver. Si on divise de grands chiffres par de petits, cet algorithme est lent.

Il est par contre très facile à programmer. La séquence donne ceci :

• Mettre le dividende (le nombre à diviser) dans A
• Mettre le diviseur dans C
• Mettre 0 dans B
• Tant que A est supérieur à C
  • Soustraire C à A et mettre le résultat dans A
  • Ajouter 1 à B
• Le quotient (le résultat de la division entière) est dans B
• Le reste de la division entière est dans A

Implémentation par soustractions

Il y a des limitations bien entendu à faire cette division sur des registres 8 bits. Je ne pourrai pas traiter des nombres supérieurs à 255. Pour afficher un point, je n'en ai pas besoin, c'est donc très bien.

Tout d'abord, je renseigne mon système de tests avec mes nouvelles informations :

div3_input_data:
        defb    0,2,10,21,255
div3_reference_data:
        defb    0,0,3,7,85

div3_params:
        defw    div3_input_data
        defw    div3_reference_data
        defw    div3
        defm    "DIV3\0"

Et j'ajoute le test à la liste :

test_suite:
        ld      hl,id_params
        call    prepare_test

        ld      hl,div2_params
        call    prepare_test

        ld      hl,div3_params
        call    prepare_test

        ret

Ce qui me permet de mettre au point le code et le vérifier :

div3:                   ; Entrée: registre A, Sortie: valeur divisée par 3, dans A
        push    bc              ; J'utilise les registres B et C, je les préserve
                                ; Le temps de l'opération
        ld      c,3             ; Le registre C contient le diviseur
        ld      b,0             ; Le compteur B est préparé pour retenir
                                ; Le nombre de soustractions effectuées

div3_loop:
        cp      c               ; A et C sont comparés
        jr      c,div3_end      ; Si A était plus petit que C, alors une retenue a eu lieu
                                ; le calcul est terminé
                                ; Attention, ici C signifie Carry (retenue)

        sub     c               ; C est soustrait de A
        inc     b               ; B est augmenté de 1
        jr      div3_loop       ; La boucle est relancée

div3_end:
        ld      a,b             ; Le résultat de la division est dans B, il est placé dans A
                                ; À noter que A contenait le reste de la division.
                                ; Cela pourra être intéressant pour plus tard.

        pop     bc              ; Les registres B et C sont restaurés
        ret                     ; Et la fonction est terminée

Les instructions utilisées

Les instructions déjà utilisées dans les articles précédents ne sont pas répétées ici, les nouvelles sont :

• cp: permet de comparer le registre A (qui est implicite et donc non noté) et le registre indiqué (ici, C). La comparaison se fait par soustraction de A et du registre, mais le résultat n'est pas retenu, seuls les drapeaux de résultat de l'opération le sont. Ainsi, en cas d'égalité par exemple, le drapeau Z sera à 1 (Zéro, car la soustraction de deux nombres égaux donne zéro). Ici, on cherche s'il y a eu une retenue, ce qui indique que le nombre dans le registre spécifié était plus grand que le nombre dans A, et donc le résultat de la soustraction était négatif.
• sub: effectue une soustraction simple. On avait précédemment vu sbc, qui faisait une soustraction en tenant compte de la retenue du calcul précédent. sub n'en tient pas compte et soustrait simplement le registre mentionné du registre A, qui est implicite.

Résultat

Voici donc une première implémentation de division par 3, qui peut être généralisée à une division par n'importe quel nombre (inférieur à 255)

Pour référence futur, le code de la fonction nécessite 15 octets de langage machine. L'exécution de la fonction nécessite $15 + 8 * q$ cycles processeur, où $q$ est le quotient, résultat de la division. Au pire, pour $\frac{255}{3}$, la fonction prend donc 695 cycles. Ce qui n'est pas négligeable.

Nous verrons plus tard si l'on peut faire mieux.