A multiplicação russa é conhecida no submundo do assembly para 6502 como "shift and add", porque ela reduz a multiplicação a essas duas operações.
Um cidadão inglês chamado Booth notou que quando há sequências de 1s no multiplicador pode-se reduzir o número de operações.
Em poucas palavras, multiplicar x por 15 é igual a multiplicar x por 16 e subtrair x.
1111 * x = x<<3 + x<<2 + x<<1 + x
1111 * x = x<<4 - x
Podem existir várias sequências de 1s no multiplicador.
1110111 * x = x<<6 + x<<5 + x<<4 + x<<2 + x<<1 + x
1110111 * x = (x<<7 - x<<4) + (x<<3 - x)
A implementação é ineficiente e não vale a pena no 6502, talvez porque ele só tenha instruções para fazer um shift por vez. É um milagre que alguém consiga fazer algo com esse processador, mas Turing garante que tudo é possível.
Deve ser por terem convivido com tantas limitações que os criadores do ARM criaram instruções condicionais que fazem aritmética e shifts ao mesmo tempo, tudo numa só instrução.
Mas o que achei curiosa é a possibilidade de usar isso com o sistema decimal.
993.006 * x = 900.000*x + 90.000*x + 3.000*x + 6*x
993.006 * x = (1.000.000*x - 7.000*x) + 6*x
Operando manualmente, o número de adições reduz bastante:
993.006*123 => 123000000
161000 -
738 +
122139738 =
Esse algoritmo é muito mais interessante no binário, porque a probabilidade de um bit ser zero ou um é de 50%, e, portanto, só vai realmente ajudar com uma classe específica de números decimais, mas é uma maneira interessante de ver a multiplicação.
