CODINGAMSLIVE ★ AMSLIVE n°16 - MULTIPLICATION SAIGNEE A MORT ★

AMSLIVE n°14 - Multiplication Saignee a MortCoding Amslive

"Dieu Lapinou dit aux lapinoux : mangez, respirez, et multipliez vous. Alors les lapinoux mangèrent, respirèrent et surtout, se multiplièrent. Ils y prirent beaucoup de plaisir, et se signèrent pour remercier Dieu Lapinou."

Nous touchons au but ! Jusqu'alors, pour multiplier DE par 7(111 en binaire), on aurait bêêêtement additionné DE, 2*DE et 4*DE. Mais maintenant que vous maîtrisez tout ce qui concerne les bits, une idée peut naître.

L'IDEE NEE.

Cette fois, l'astuce est de dire que 7 égale 8 - 1. Il devient alors plus rapide d'ajouter 8*DE et de retrancher DE. Pour remplacer un multiplicateur quelconque par ce genre d'expression, et de la façon la plus concise possible, il convient de repérer les paquets de bits à 1. On a effectivement les correspondances suivantes :

x*1       =x*1
x*11      =x*10 + x*l = x*100-x*l
x*111     =x*1000-x*l
x*1111    =x*10000-x*l
….

Vous aurez remarqué que pour 2 bits à 1 de suite, l'une et autre expressions sont équivalentes (au niveau du nombre de termes). Cependant, on choisira quand même d'utiliser la soustraction, afin de faciliter le traitement.

Eh oui, il suffira de lire les bits (du poids faible au poids fort), et dès la rencontre d'un 1, tester le bit suivant pour décider s'il faut additionner ou retrancher DE avec le poids en cours. Si il y a un 0 avant, le 1 est isolé, et représente un terme à additionner. Si
c'est un 1, c'est le début d'une série de 1 (dont on ne connait pas encore la longueur), et c'est plus ou aussi avantageux d'utiliser la soustraction.

QUAND LES BITS S'AMASSENT

En en restant là, x*01110111 se traduira x*10000000 - x*10000 + x*1000 - x*1, soit en hexa x*80 - x*10 + x*8 - x*1. Ce n'est pas, comme vous pouvez le constater, la meilleure solution. Il vaut mieux écrire x*80 -x*8-x*1.

D'une manière générale, quand un bit à 0 interrompt une série de 1, il est plus efficace de soustraire.

Ne capitulez pas, on va récapituler :

  1. on part du bit 0. Tant que les bits sont nuls, on ne fait rien (à part augmenter le poids du facteur de départ, en lui faisant goûter un pâté de pomme de terre maison)
  2. Dès qu'on rencontre un bit 1, on teste le bit suivant. S'il est à 0, on additionne notre terme, et on continue l'exploration : GOTO 1
  3. Sinon, on soustrait notre terme.
  4. Maintenant, c'est quand les bits sont à 1 qu'on ne fait rien, et on attend un bit 0.
  5. Ce bit nul trouvé, on teste le suivant. Et là encore, s'il est à 0, on additionne et on retourne en 1. Sinon, on soustraire et GOTO 4

La question que vous vous posez tous présentement est : "Si on en est déjà au bit 7, comment diantre tester le bit suivant ?". En supposant que notre coefficient est un binaire pur, les bit 8, 9, et tous les suivants sont considérés nuls.
Alors donc ainsi, par conséquent, si une série de bits à 1 atteint le bit 7, il faudra rajouter #100*DE (256*DE).

Dans un élan de bonté dont l'ampleur n'a d'égale que celle du grand cataclysme de l'ère quaternaire, je vous ai représenté tout ça sur un petit organigramme, et voici le source correspondant :

         ;LD B,8
WAIT1    RRA
         ;JR NC,ZERO
         ;DEC B
modif1   JR Z,FIN1
NEXTBIT  RRA
         ;JR C,SOUSTRA
         ;ADD HL,DE
         ;SLA E
         ;RL D
         ;SLA E
         ;RL D
         ;DEC B
         ;JR NZ,WAIT1
FIN2     RET
;
SOUSTRA  OR A
         ;SBC HL,DE
         ;SLA E
         ;RL D
WAIT0    SLA E
         ;RL D
         ;DEC B
modif2   JR Z,FIN1
         ;RRA
         ;JR C, WAIT0
         ;DEC B
         ;JR NZ,NEXTBIT
FINI     ADD HL,DE
         ;RET
;
ZERO     SLA E
         ;RL D
         ;DEC B
         ;JR NZ,WAIT1
FIN3     RET
FIN4     OR A
         ;SBC HL,BC
         RET

QUEL BIT !

Soient 4 amortisseurs à 100 Fr. Ca fait 400 Fr. Ajoutez à ce prix 160 Fr. On obtient 560 Fr. Maintenant, annoncez que le 4ème amortisseur est gratuit, et vendez le tout 420 Fr.

Tout ceci pour vous rappeler de bien vous méfier des garagistes.

Dans notre routine, DE peut être aussi bien vu en tant que binaire pur que binaire signé. Ca marche pareillement dans les deux cas. Maintenant, je vous propose de "signer" A. Dans ce cas, ainsi que nous l'avons vu la fois précédente, les bit 8, 9, etc, reprennent le bit 7. Dans le source, cela implique les changements suivants :

  • modif1 :JR Z,FIN1  devient JR Z,FIN4
  • modif2:JR Z,FIN1  devient RETZ

Petite vérification : dans la première version, 11111111 donne -1 *DE + 100000000*DE, càd 255*DE, et dans la deuxième, -1*DE. Ca roule !

Je l'avoue, cette routine n'est pas performante pour un sou. Le décompte des bits fait perdre beaucoup de temps, et la mise à plat (recopie de la routine pour justement enlever les boucles) n'est pas très évidente. Pour me faire pardonner, voici ze méthode.

ULTIMES RETRANCHEMENTS

La meilleure solution est sans aucun doute de concevoir, à l'instar de ZIK, 256 petites routines, 1 par facteur, et y inclure toutes les astuces qu'on a vu. L'optmisation de ces routines dépend du contexte : suivant par exemple si HL contient déjà un terme à ajouter au produit ou non.
Dans le premier cas, une multiplication par 4 se fera :

SLA E
RL D
SLA E
RL D
ADD HL,DE

et dans l'autre cas :

LD L,E
LD H,D
ADD HL,HL
ADD HL,HL

Pour une multiplication par 23, on pourra écrire :

LD L,E
LD H,D
ADD HL,HL
ADD HL,DE
ADD HL,HL
ADD HL,HL
ADD HL,HL
OR A
SBC HL,DE

Une table réunira les adresses de chacune des routines. Pensez aux JP (HL), JP (IX) et autres JP (IY) pour y sauter rapidement.

LA CONCLUSION

Cet été sur la plage, plutôt que de faire des mots croisés, vous aurez 256 petits casse-tête à résoudre. Multipliez vos essais pour obtenir les routines parfaites.

AMSLIVE n°14

» A lire : AMSLIVE n°05 - MULTIPLICATION DE SOLUTIONS

★ ANNÉE: ???
★ AUTEUR: MADRAM

Page précédente : AMSLIVE n°14 - 3D est-ce l'amour ?

CPCrulez[Content Management System] v8.7-desktop/cache
Page créée en 101 millisecondes et consultée 1146 fois

L'Amstrad CPC est une machine 8 bits à base d'un Z80 à 4MHz. Le premier de la gamme fut le CPC 464 en 1984, équipé d'un lecteur de cassettes intégré il se plaçait en concurrent  du Commodore C64 beaucoup plus compliqué à utiliser et plus cher. Ce fut un réel succès et sorti cette même années le CPC 664 équipé d'un lecteur de disquettes trois pouces intégré. Sa vie fut de courte durée puisqu'en 1985 il fut remplacé par le CPC 6128 qui était plus compact, plus soigné et surtout qui avait 128Ko de RAM au lieu de 64Ko.