Algoritmo de multiplicación más rápido de 16 bits para MCU de 8 bits
Estoy buscando un algoritmo para multiplicar dos números enteros que sea mejor que el siguiente. ¿Tienes una buena idea al respecto? (El MCU - AT Tiny 84/85 o similar - donde se ejecuta este código no tiene operador mul / div)
uint16_t umul16_(uint16_t a, uint16_t b)
{
uint16_t res=0;
while (b) {
if ( (b & 1) )
res+=a;
b>>=1;
a+=a;
}
return res;
}
Este algoritmo, cuando se compila para AT Tiny 85/84 usando el compilador avr-gcc, es casi idéntico al algoritmo __mulhi3 que genera avr-gcc.
algoritmo avr-gcc:
00000106 <__mulhi3>:
106: 00 24 eor r0, r0
108: 55 27 eor r21, r21
10a: 04 c0 rjmp .+8 ; 0x114 <__mulhi3+0xe>
10c: 08 0e add r0, r24
10e: 59 1f adc r21, r25
110: 88 0f add r24, r24
112: 99 1f adc r25, r25
114: 00 97 sbiw r24, 0x00 ; 0
116: 29 f0 breq .+10 ; 0x122 <__mulhi3+0x1c>
, 118: 76 95 lsr r23
11a: 67 95 ror r22
11c: b8 f3 brcs .-18 ; 0x10c <__mulhi3+0x6>
11e: 71 05 cpc r23, r1
120: b9 f7 brne .-18 ; 0x110 <__mulhi3+0xa>
122: 80 2d mov r24, r0
124: 95 2f mov r25, r21
126: 08 95 ret
algoritmo umul16_:
00000044 <umul16_>:
44: 20 e0 ldi r18, 0x00 ; 0
46: 30 e0 ldi r19, 0x00 ; 0
48: 61 15 cp r22, r1
4a: 71 05 cpc r23, r1
4c: 49 f0 breq .+18 ; 0x60 <umul16_+0x1c>
4e: 60 ff sbrs r22, 0
50: 02 c0 rjmp .+4 ; 0x56 <umul16_+0x12>
52: 28 0f add r18, r24
54: 39 1f adc r19, r25
56: 76 95 lsr r23
58: 67 95 ror r22
5a: 88 0f add r24, r24
5c: 99 1f adc r25, r25
5e: f4 cf rjmp .-24 ; 0x48 <umul16_+0x4>
60: c9 01 movw r24, r18
62: 08 95 ret