Samuel Devulder a écrit:
La table contient les carrés des nombres à multiplier, Si les nombres sont sur 8 bits, la table contient 254 valeurs (abs(A+B) vaut 254 au max avec A/B signés sur 8 bits) et chaque valeur fait 2 octets (carré de 8bits). Occupation mémoire 2*254 octets. Avec du 16 bits cela nous ferait 65534*4 .. 128 ko .. trop gros pour thomson mais impec pour 68000 où le mul est très lent.
A noter que c'est une multiplication signée, chose que le 6809 n'a pas. Il nous faut ajouter du code autour, ce qui nous fait allégrement dépasser les 11 cycles au total:
Code:
sMUL8
STA ,-S ; 6
BGE sM1 ; 3
NEGA ; 2
sM1
TSTB ; 2
BGE sM2 ; 3
COM ,S ; 6
NEGB ; 2
sM2
MUL ; 11
TST ,S+ ; 8
BGE sM3 ; 3
NEGA ; 2
NEGB ; 2
SBCA #0 ; 2
sM3
RTS ; 5 => total = 57 cycles
Le meilleur code 6502 (C64, ORIC) fait une multiplication (signée) 8x8->16 bits entre 47 et 51 cycles avec un table précalculée de 2ko:
https://codebase64.org/doku.php?id=base ... iplicationComme quoi, même sans MUL, il y a moyen d'être rapide.
D'ailleurs en lisant
>>ceci<<, on comprends que pour multiplier x*y en signé revient à multiplier x*y en non-signé, et soustraire x de la partie haute si y<0, et soustraire y si x<0. Il y a moyen de gagner quelques cycles avec cela, mais la routine n'est plus en temps symétrique (x*y est parfois plus rapide que y*x)
Code:
sMUL8
TSTA ; 2
BGE sM1 ; 3
STB ,-S ; 6
BGE sM2 ; 3
STA ,-S ; 6
MUL ; 11
SUBA ,S+ ; 6
SUBA ,S+ ; 6
RTS ; 5 => total 48
sM1 TSTB ; 2
BGE sM3 ; 3
STA ,-S ; 6
sM2 MUL ; 11
SUBA ,S+ ; 6
RTS ; 5 => total 36 ou 38
sM3 MUL ; 11
RTS ; 5 => total 26
Le temps minimum est doublé, et le maximum est à peine plus court. Si quelqu'un veut tenter le challenge, ca serait intéressant de voir si on peut faire mieux.
(EDIT) J'arrive à un tout petit peut mieux au pire, mais beaucoup moins bon dans le cas du produit de deux nombres entre 0 et 127Code:
sMUL8
STD ,--S ; 7
BGE sM1 ; 3
TSTB ; 2
BGE sM2 ; 3
MUL ; 11
SUBA ,S+ ; 6
SUBA ,S+ ; 6
RTS ; 5 => 43
sM2
MUL ; 11
SUBA 1,S ; 5
LEAS 2,S ; 5
RTS ; 5 => 41
sM1 TSTB ; 2
BGE sM3 ; 3
MUL ; 11
SUBA ,S++ ; 7
RTS ; 5 => 38
sM3
MUL ; 11
LEAS 2,S ; 5
RTS ; 5 => 36
Ca reste quand même entre 3x et 4x la vitesse du MUL non signé.
Je sais tout cela
Pour la multiplication signée... Ya juste qu'à utiliser un drapeau 0 ou 1 pour le signé, on sait que - x - = + etc...
Désolé mais je reste sur l'instruction MUL (même sur la version 68000 etc) qui me paraissent vraiment importantes dans pas mal d'opération. Le fait que l'Hitachi 6309 puisse faite des MUL et DIV sur 32 bits, c'st vraiment top (et ça gagne x4 en vitesse comparé à la même opération sur 6809 avec les MUL)
Pour ce qui est du 6502, je le sais aussi c'est même l'objet de mon prochain cours vidéo (et division idem). C'est même grâce à cette routine que les complexité algorithmique sont largement meilleure en utilisant la multiplication (exemple, somme de (i) de 1 à B = N*(N+1)/2. J'ai vu une routine ASS 6809 qui est même plus optimale que sur le 6502 (normal!! Puisque le 6809 a 2 régistres qui, cumulées, donne le D)
Tu peux voir ce que ça donne en assembleur en faisant N sommes et en utilisant la routine de décalage des bits et addition... Ya pas photo. Et dire que le MUL du 6809 divise par 4 le temps de cet algorithme optimisé est un énorme +.
La complexité algorithmique est le sujet majeur de tous les chercheurs en informatique. Ya des cas où cette simplification est possible (notamment avec Somme(i^k)) quelle que soit le "k", il existe une formule qui simplifie le calcul avec des multiplications, et ya des cas où la simplification est impossible (quand on a des variable linéairement indépendantes, comme c'est le cas des polynomes, ou équation différentielles, c'est aussi le cas par exemple, pour la recherche chemins de labyrinthe, pas possibilité de simplifier)
On parle bcp en ce moment des ordinateurs quantiques, d'après ce que je comprends, ces ordinateur seraient capable de fare N opération parallèle sans perte de temps (ce qui n'est pas le cas avec les processeurs actuel)