Triceraprog
La programmation depuis le Crétacé

Les trois derniers articles sur la division on permit de s'attarder sur trois manière de diviser un nombre entier par 3.

• la première méthode effectuait une série de soustractions,
• la seconde méthode utilisait la méthode scolaire,
• la troisième méthode se servait de divisions par 4.

La méthode de cet article, qui sera le dernier avant de revenir à l'affichage d'un point, va diviser grâce à, globalement, une seule addition. Oui ! Une seule addition.

L'idée

Au tout début de la série d'articles sur la division, j'ai mis en place un système de tests pour m'assurer que mes bouts d'assembleurs faisaient ce qu'il étaient censés faire. Et pour cela, je comparais une série de divisions avec un tableau de résultats.

Mais alors, pourquoi ne pas utiliser un tableau de résultats directement ? On stock quelque part le résultat de toutes les divisions par 3 des nombres entiers de 0 à 255, et on va piocher dedans. Facile à implémenter, ultra rapide.

La contrepartie, évidemment, c'est que cela va prendre un peu de place. Mais voyons ce que cela donne.

Le code

Nul besoin d'une longue explication pour cette méthode. L'entier à diviser (le dividende) est dans le registre A, on l'ajoute à l'adresse du tableau des résultats pré-calculés, on récupère la valeur dans A et voilà !

div3_5:                         ; Entrée: registre A, Sortie: valeur divisée par 3, dans A
        exx                     ; Utilisation des registres secondaires
        ld      hl,div3_table   ; Chargement dans HL de l'adresse de la table des résultats
        ld      b,0             ; Mise à 0 de B
        ld      c,a             ; Placement de la valeur de A dans C
                                ; On a donc à présent le registre BC qui contient le dividende
        add     hl,bc           ; Addition du dividende et de l'adresse du tableau
        ld      a,(hl)          ; Récupération du résultat

        exx                     ; Échange des registres secondaires
        ret                     ; Retour à l'appelant.

div3_table:                     ; La table des résultats
        defb    0,0,0,1,1,1,2,2,2,3,3,3,4,4,4,5,5,5
        defb    6,6,6,7,7,7,8,8,8,9,9,9,10,10,10,11,11,11
        defb    12,12,12,13,13,13,14,14,14,15,15,15,16,16,16,17,17,17
        defb    18,18,18,19,19,19,20,20,20,21,21,21,22,22,22,23,23,23
        defb    24,24,24,25,25,25,26,26,26,27,27,27,28,28,28,29,29,29
        defb    30,30,30,31,31,31,32,32,32,33,33,33,34,34,34,35,35,35
        defb    36,36,36,37,37,37,38,38,38,39,39,39,40,40,40,41,41,41
        defb    42,42,42,43,43,43,44,44,44,45,45,45,46,46,46,47,47,47
        defb    48,48,48,49,49,49,50,50,50,51,51,51,52,52,52,53,53,53
        defb    54,54,54,55,55,55,56,56,56,57,57,57,58,58,58,59,59,59
        defb    60,60,60,61,61,61,62,62,62,63,63,63,64,64,64,65,65,65
        defb    66,66,66,67,67,67,68,68,68,69,69,69,70,70,70,71,71,71
        defb    72,72,72,73,73,73,74,74,74,75,75,75,76,76,76,77,77,77
        defb    78,78,78,79,79,79,80,80,80,81,81,81,82,82,82,83,83,83
        defb    84,84,84,85,85,85

Les instructions utilisées

Il n'y a pas vraiment de nouvelles instructions utilisées ici, mais de nouvelles formes :

• Comme on ne peut pas additionner directement les registres HL et A, on doit passer la valeur de A dans un registre 16 bits. BC est souvent utilisé, mais ça aurait pu être DE.
• Comme on ne peut pas charger le contenu de A directement dans BC, on le fait en deux étapes. Le registre 16 bits BC est constitué des deux registres 8 bits B et C. On place donc 0 dans B et C prend la valeur de A.
• LD A,(HL) récupère la valeur pointée par le registre HL, plutôt que la valeur de HL. C'est-à-dire que l'octet à l'adresse mémoire pointée par HL est récupérée, puis chargé dans A.

C'est mieux du coup ?

D'un point de vu code de la fonction elle-même, c'est nettement mieux, 11 octets seulement. Par contre suivi d'un tableau de 255 octets. C'est donc à la fois le code le plus concis jusqu'à maintenant, mais aussi la fonction la plus grosse dans sa globalité.

Il est possible cependant de la réduire dans le cas présent. En effet, comme on ne divise que des numéros de lignes, on pourrait s'arrêter à 75 résultats. Cela donne 86 octets, c'est toujours plus imposant que les autres versions, mais un peu mieux.

Attention aussi, l'accès au tableau n'est pas protégé. S´il est plus petit que 255, rien n'empêche l'appelant de passer une valeur qui va déborder. Cela donnera des résultats faux.

D'un point de vu rapidité c'est constant et rapide : 15 cycles. Comme c'est une fonction très courte, il est possible aussi, au besoin, de l'inliner, c'est-à-dire de faire l'opération à l'endroit où elle est nécessaire plutôt que d'appeler une fonction. Cela économise le temps de mise en place et de retour de la fonction (les EXX et RET). On tombe alors à 10 cycles, que l'on peut potentiellement améliorer en utilisant les valeurs de registres au moment de l'appel.

Difficile de faire plus rapide comme méthode (à quelques astuces potentielles prêt).

Que choisir ?

C'est la question. Nous voici avec quatre méthodes pour diviser par trois. Deux sont des méthodes générales de division, deux sont spécialisées dans la division par 3. La première question à se poser est donc de savoir de quoi on a besoin.

Ensuite, nous avons des fonctions qui ont des compromis en terme de taille et de rapidité.

C'est ici qu´utiliser une fonction s'avère utile. Pour le moment, le choix n'a pas d'importance. Les quatre fonctions demandent un dividende dans A et retournent le résultat dans A. Il est donc possible de remplacer l'une par l'autre et de continuer le développement de l'affichage du point.

Il sera temps, ensuite, de choisir quelle méthode sera la plus adéquate.

Spoiler : probablement aucune de celles-ci en l'état, car nous allons avoir besoin du reste de la division par 3...

À la prochaine !