Triceraprog
La programmation depuis le Crétacé

Dans le dernier article, j'avais cherché une version plus rapide pour effectuer une division par 3, toujours dans l'optique d'afficher un point à l'écran en transcrivant la routine écrite en BASIC vers de l'assembleur Z80.

Le résultat était mitigé : une routine en moyenne plus rapide et plus stable, mais sur le domaine de définition considéré (le nombre de lignes graphiques du VG5000µ), pas entièrement gagnante.

Dans cet article, je vais donc étudier une autre manière de faire, un peu différente. Alors que les deux premières implémentations permettait de diviser par n'importe quel nombre de 1 à 255, cette nouvelle version est spécialisée dans la division par 3.

Est-ce que cette spécialisation permettra de gagner en performance et/ou en taille ?

L'idée

Le Z80 n'a pas d'instruction pour diviser de manière générale, cela a déjà été mentionné dans les articles précédents. Par contre, il est tout à fait possible de diviser par des multiples de 2. Il suffit de décaler un nombre d'un bit vers la droite pour diviser un nombre entier codé en binaire par 2.

Exemple :

$00010010_{2}$ (18 en base 10) décalé vers la droite une fois donne $00001001_{2}$ (9 en base 10).

Il faut donc trouver une manière d'exprimer une division par trois à partir de divisions par des multiples de 2 aidées d’additions ou soustractions.

Le calcul est le suivant : on remarque tout d'abord que n'importe quel nombre entier n peut s'écrire sous la forme $n = 4\times a + b$, avec $b$ inférieur à 4. Autrement dit, sous forme d'une division par 4 plus le reste de la division entière. Trouver $a$ et $b$ est donc simple. $a$ est le résultat de la division entière (quotient) de $n$ par $4$. $b$ le reste de la division entière de $n$ par $4$.

Sous cette forme, par exemple, $15$ s'écrit $4\times3 + 3$.

Puisque l'on veut diviser n par 3, écrivons le résultat à partir de cette forme $\frac{n}{3} = \frac{4\times a + b}{3}$

On n'est pas très avancé, il faudrait trouver dans l'expression un terme ou une forme que l'on connaît déjà qui nous permettrait de converger vers le résultat.

Sortons $a$ de la fraction : $\frac{n}{3} = \frac{3\times a}{3} + \frac{a + b}{3} = a + \frac{a + b}{3}$.

Ça c'est intéressant. Le résultat que l'on cherche est égal à $a$, donc le résultat de la division par $4$ additionné à... un quelque chose. Et ce quelque chose est un nombre que l'on voudrait diviser par 3 !

Appelons ce nombre $n_{1}$, cela donne : $\frac{n}{3} = a + \frac{n_{1}}{3}$.

Ce terme $\frac{n_{1}}{3}$ peut lui-même être écrit sous la forme : $\frac{n_{1}}{3} = \frac{4\times a_{1} + b_{1}}{3} = a_{1} + \frac{a_{1} + b_{1}}{3}$, c'est-à-dire sous la forme d'une division par 4 de $n_{1}$ et d'un quelque chose d'autre.

Et ainsi de suite... Jusqu'à ce que $n_{i}$ soit inférieur ou égal à 3. Dans ce cas, il y a deux cas : soit $n_{i} = 3$ et diviser ce nombre par $3$ donne $1$. Soit $n_{i} < 3$ et ce nombre divisé par $3$ donne $0$.

Exemple

Revoyons l'exemple avec 15 (pour plus de cohérence, j'ajoute l'indice 0 aux premiers termes) :

$\frac{15}{3} = \frac{4\times a_{0} + b_{0}}{3}$. On trouve les termes de la division par 4 : $a_{0} = 3$, $b_{0} = 3$

Donc $\frac{15}{3} = 3 + \frac{3 + 3}{3} = 3 + n_{1}$.

Il s'agit donc à présent de trouver $\frac{n_{1}}{3} = \frac{3 + 3}{3} = \frac{6}{3} = \frac{4 \times a_{1} + b_{1}}{3}$.

Comme $6 = 4 \times 1 + 2$, on a $a_{1} = 1$ et $b_{1} = 2$.

Donc $\frac{n_{1}}{3} = 1 + \frac{1 + 2}{3} = 1 + \frac{3}{3}$. On est dans le cas où le nombre restant est égal à $3$, on sait calculer facilement sa division par $3$, c'est $1$.

Si on remonte tout ça dans l'expression initiale on a donc :

$\frac{15}{3} = 3 + (1 + (1)) = 5$

L'implémentation

Pour cette implémentation, mis à part le dividende, nous avons besoin :

• d'un résultat intermédiaire dans lequel on va additionner les différents termes $a_{i}$ au fur et à mesure des itérations
  • dans l'exemple précédent, on y mettra la première fois $3$, puis on y additionnera $1$
  • j'utiliserai pour ça le registre E.
• d'un dividende intermédiaire à diviser par 3 (les termes $n_{i}$)
  • ce nombre est le dividende donné au début
  • puis il est remplacé par la somme du quotient et du reste de la division par 4 du dividende actuel
  • j'utiliserai pour ça le registre A.

J'aurai aussi besoin d'autres registres pour la division intermédiaire par 4.

Les opérations seront :

• Tant que le dividende actuel (A) est supérieur à 3 :
  • On sauve le dividende dans B.
  • On divise A par 4 (stocké temporairement dans D)
  • On ajoute A au résultat intermédiaire E
  • On récupère le dividende depuis B vers A
  • On prend le reste de la division de A par 4, qui reste dans A
  • On ajoute D à A, ce qui donne le nouveau dividende A
• Si A est égal à 3, on ajoute 1 au résultat E. Sinon rien.

Cette valse des registres est nécessaire car quelques opérations opérations utilisées ne sont possible, sur Z80, que sur l'accumulateur, et pas sur les autres registres.

Le code

div3_4:                         ; Entrée: registre A, Sortie: valeur divisée par 3, dans A
        exx                     ; Utilisation des registres secondaires
        ld      c,3             ; Initialisation du diviseur
                                ; Il est fixe dans cette implémentation
                                ; mais est nécessaire pour la comparaison
        ld      e,0             ; Initialisation du résultat

div3_4_loop:
        cp      c               ; Comparaison de `C` et `A`
                                ; le registre `A` est implicite, le Z80
                                ; ne peut comparer qu'avec le registre A
        jr      c,div3_4_exit   ; Branchement si A est inférieur à C (donc A < 3)
        jr      z,div3_4_end    ; Branchement si A est égal à C (donc A = 3)

div3_4_cont:
        ld      b,a             ; A est sauvé dans B
        srl     a               ; A est décalé d'un bit vers la droite
        srl     a               ; A est décalé d'un bit vers la droite
                                ; Ces deux décalages forment une division par 4
        ld      d,a             ; Le résultat de la division entière est
                                ; stockée dans D
        ld      a,e             ; A prend la valeur du résultat intermédiaire A
                                ; C'est nécessaire pour faire l'addition suivante.
                                ; Le Z80 ne sait additionner qu'avec l'accumulateur
                                ; quand on traite des valeurs sur 8 bits.
        add     a,d             ; On ajoute le résultat de la division et
                                ; le résultat intermédiaire.
        ld      e,a             ; Ce résultat intermédiaire et remis dans E
        ld      a,b             ; Le dividende actuel est mis dans A afin de faire
                                ; l'opération suivante.
        and     $03             ; Calcul du reste de la division par 4
        add     a,d             ; On ajoute à ce reste le quotient de la division
                                ; Et donc A contient le nouveau dividende.
        jr      div3_4_loop     ; C'est donc reparti pour un tour.

div3_4_end:
        inc     e               ; On arrive ici si le dernier dividende est 3.
                                ; dans ce cas, on ajoute 1 au résultat final.
div3_4_exit:
        ld      a,e             ; Le résultat final est stocké dans A
        exx                     ; Échange des registres secondaires
        ret                     ; Retour à l'appelant.

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 :

• srl décale le registre indiqué de 1 bit vers la droite. Le bit sortant est stocké dans le drapeau de retenu, mais ici, on ne l'utilise pas.
• and effectue une opération bit à bit entre l'accumulateur et l'opérande. Le résultat de chaque bit est 1 uniquement si les bits de chaque terme étaient 1 sur la même position.
  • Exemple : 11111000 and 00011111 donne 00011000, car seuls le 2 bits centraux sont à 1 dans les deux termes.
  • Ici, on s'en sert pour prendre le reste de la division par 4. Pourquoi est-ce que ça donne ce résultat est laissé en exercice.

Bon alors, c'est mieux ?

Un petit calcul donne pour cette troisième version :

• 29 octets. Encore plus grand.
• Le nombre d'étapes maximum à faire donne 84 cycles. C'est un peu mieux. Dans le domaine de définition de l'affichage d'un point, le nombre à diviser le plus grand est 75, et cela donne alors 56 cycles.

Ce qui fait que la première version n'est plus rapide que pour les nombres jusqu'à 5. Cette version est intéressante et offre un bon compromis entre taille du code et vitesse d'exécution. Au détriment de la flexibilité, puisque le calcul n'est valable que pour une division par 3.

Le principe de l'algorithme pourrait être étendu à plus de nombres, mais au prix d'un taille plus grande et d'un fonctionnement un petit peu plus long. De toute façon ici, on ne s’intéresse qu'à une division par 3.

La fois prochaine, on verra une dernière manière de faire, et puis on reviendra à l'étape suivante de l'affichage d'un point.