A idéia é simples:
- Crie uma coluna para cada número (maior à esquerda, menor à direita);
- Divida o número maior por dois até chegar a 1;
- Multiplique o número menor por dois o mesmo número de vezes;
- Descarte as linhas em que o número da esquerda for par;
- Some os números que restavam à direita.
Por exemplo, 3 * 18:
18 3
9 6
4 12
2 24
1 48
Resultado= 6+48=54
Ela fica mais divertida em base 2:
00010010 00000011
00001001 00000110
00000100 00001100
00000010 00011000
00000001 00110000
Resultado = 00000110+00110000= 110110
Ou seja, basta ir fazendo shifts.
Uma otimização óbvia é pegar a maior potência de dois para dividir o problema. As multiplicações por potências de dois sempre acabam com apenas uma linha sendo considerada: a maior do lado direito (porque todos os números do lado esquerdo são pares, exceto a última).
8 3
4 6
2 12
1 24
A resposta é 24. nenhuma soma é precisa, porque 8*3=3*2*2*2
E se eu repetir esse processo de sempre pegar a maior potência? Nesse caso, vou poder descrever sucintamente o processo como: para multiplicar m por n, percorro os bits de m e, para cada bit 1, adiciono n deslocado à esquerda pela posição desse bit.
Sucintamente, em Perl (devia ser assembly!), seria algo assim:
#!/usr/bin/perl
use strict;
use warnings;
use integer;
my $n=$ARGV[0];
my $m=$ARGV[1];
my $p=0;
my $total=0;
do {
$total+=$m<<$p if $n&1;
$p++;
} while ($n>>=1);
print $total;
Ou seja, se quero multiplicar 46 por 5, como cinco é 101, executo 46<<2 + 46<<0 (46*4+46*1 para os binário-deficientes). A respostá é óbvia, dado que 46*5=46*(4+1).
Uma solução alternativa um pouco mais elegante é essa função recursiva:
#!/usr/bin/perl
use strict;
use warnings;
use integer;
my $n=$ARGV[0];
my $m=$ARGV[1];
sub mult {
my ($n, $m)=@_;
return $m if $n==1;
my $d=0;
$d=$m if $n&1;
return $d + mult($n>>1, $m<<1);
}
print mult($n, $m);
