Multiplication efficace en assembleur

version python

def multiplication(a, b):
    position = 0
    puissance_position = 1
    resultat = 0
    while puissance_position <= a:
        if (a & puissance_position) != 0:
            resultat = resultat + (b << position)
        position = position + 1
        puissance_position = puissance_position + puissance_position
    return resultat

print(multiplication(403000078586798780089,567687987987987987987987))

• & est l'opérateur pour le AND binaire en python : a & puissance_position != 0 est une manière de tester que le bit n°position vaut 1.
• << est l'opérateur pour le décalage binaire à gauche (LSL en assembleur). Décaler à gauche de \(n\) bits revient à multiplier par \(2^n\).

explication sur un exemple :

\(100110_2 \times 11011_2 = (2^1 + 2^2 + 2^5)\times11011_2\)

\(=2^1\times11011_2 + 2^2\times11011_2 + 2^5\times11011_2\)

\(=(11011_2 << 1) + (11011_2 << 2) + (11011_2 << 5)\)

\(=110110_2 + 1101100_2 + 1101100000_2\)

version assembleur

      INP R0,2
      INP R1,2
      MOV R3,#1
      //R4 : position, R3 : puissance_position
      //R5 : resultat
boucle:
      CMP R3,R0
      BGT fin
      AND R6,R0,R3 // R6 : variable temporaire pour (a & puissance_position)
      CMP R6,#0
      BEQ suite
      LSL R7,R1,R4 // R7 : variable temporaire pour (b << position)
      ADD R5,R5,R7
suite:
      ADD R4,R4,#1
      ADD R3,R3,R3
      B boucle
fin:
      OUT R5,4
      HALT