Escreva o algoritmo de multiplicação mais rápido (melhor big-O) e menor para números inteiros positivos, sem usar operadores de multiplicação. Só é permitida a adição, subtração, funções lógicas (AND, OR, XOR, NOT), mudança de bits, rotação de bits, rotação / definição / limpeza de bits e teste de bits. Seu programa deve ser capaz de multiplicar números de 16 bits para produzir um resultado de 32 bits. Aceite entradas no stdin, separadas por vírgulas, espaços ou novas linhas (sua escolha), mas deixe claro como inserir os dados.

Exemplo de entrada / saída:

734 929
681886

C, 84 83 78 caracteres

m;main(a,b){for(scanf("%d%d",&a,&b);a;b+=b)a&1?m+=b:0,a>>=1;printf("%d\n",m);}

De uma forma mais legível

m;main(a,b)
{
    scanf("%d%d",&a,&b);
    while (a)
    {
        if (a&1)
           m+=b;
        a>>=1;
        b+=b;
    }
    printf("%d\n",m);
}

O algoritmo é mais conhecido como Multiplicação Etíope ou Multiplicação Camponesa Russa. Aqui está o algoritmo:

1. Deixe os dois números a serem multiplicados sejam a e b.
2. Se a for zero, interrompa e imprima o resultado.
3. Se a é ímpar, adicione b ao resultado.
4. Meia a, dupla b. Vá para a Etapa 2.

APL (5)

Recebe entrada na entrada padrão, separada por novas linhas.

+/⎕⍴⎕

Golfscript - 12 caracteres

~0\{1$+}*\;

Observe que *aqui não é o operador de multiplicação, é um operador de repetição; veja o segundo uso aqui .

Golfscript - 27 caracteres

Multiplicação de camponeses. Há primeiro * lá é uma multiplicação, mas apenas por 0 ou 1

~2base-1%{1&\..+\@*}%{+}*\;

Aqui estão 31 caracteres que não se multiplicam

~2base-1%{1&\..+\[0\]@=}%{+}*\;

Python, 64 caracteres

Provavelmente não é o mais eficiente (ou o mais compatível, mas estou "adicionando", não sou?):

a=int(raw_input())
print sum(a for i in range(int(raw_input())))

Ruby, 30

->(a){Array.new(*a).inject:+}

Baseado na resposta do GigaWat .

Golfscript - 43

~\:@;0 1{.3$&{\@+\}{}if@@+:@;.+.3$>!}do;\;

Implementação da multiplicação camponesa . Acho que vou poder jogar golfe mais tarde.

J, 18 17 caracteres

+/({.${:)".1!:1]3

A entrada precisa ser separada por espaço.

Python, também 64 caracteres

m=lambda x,n:0 if n==0 else x+m(x,n-1);print m(input(),input())

VBA, 70 caracteres

Na verdade, isso é bastante lento para grandes números, mas é pequeno. Consegui melhorar o tamanho do código e melhorar a velocidade. O tempo de cálculo varia, dependendo da posição do argumento - não apenas do tamanho. (ou seja, 1000, 5000 calcula em cerca de 4 segundos, enquanto 5000, 1000 calcula em cerca de 19). Como o OP lista tanto rápido quanto pequeno, imaginei que iria com esse. A entrada é dois argumentos numéricos, separados por vírgula.

Sub i(j,k)
For m=1 To j:n=n & String(k," "):Next
MsgBox Len(n)
End Sub

Esta versão mais longa ( 103 caracteres ) garantirá que seja executada com o mais rápido dos dois arranjos possíveis:

Sub i(j,k)
If j<k Then a=j:b=k Else b=j:a=k
For m=1 To a:n=n & String(b," "):Next
MsgBox Len(n)
End Sub

Perl: 52 caracteres

Esta é uma pergunta antiga, mas o Perl precisa ser representado:

perl -pl '($m,$n,$_)=split;$_+=$m&1&&$n,$m>>=1,$n<<=1while$m'

(Este é o algoritmo binário, além iterado é menor, mas maneira muito chato.)

Este programa inclui um recurso não intencional: se sua linha de entrada contiver um terceiro número, o programa realmente calculará A * B + C.

Uma variação no Scala, otimizada para tamanho: 48 caracteres

def m(a:Int,b:Int):Int=if(b==1)a else a+m(a,b-1)

otimizado um pouco para velocidade:

def mul (a:Int, b:Int) : Int = {
  print (".")
  if (a == 1) b
  else if (a > b) mul (b, a)
  else if (a % 2 == 0) mul (a >> 1, b << 1) 
  else b + mul (a - 1, b) 
}

Troco (a, b) se (a> b), para chegar ao fim mais rapidamente. A diferença é de 11 a 20 etapas, ao chamar mul (1023,31), em comparação com a omissão dessa linha de código.

golfed: 95 caracteres:

def m(a:Int,b:Int):Int=if(a==1)b
else if(a>b)m(b,a)
else if(a%2==0)m(a>>1,b<<1)
else b+m(a-1,b)

K, 18 16

{#,/(!y),\:/:!x}

.

k){#,/(!y),\:/:!x}[4;20]
80
k){#,/(!y),\:/:!x}[13;21]
273
k){#,/(!y),\:/:!x}[3;6]
18

Ruby, 35 caracteres

p $*.map!(&:to_i).pop*$*.inject(:+)

É um programa , que recebe entradas e saídas, não apenas uma função.

.-(~/virt)-----------------------------------------------------------------------------------------------------------------------------------------------------(ice@distantstar)-
`--> wc -c golf.rb         
35 golf.rb
.-(~/virt)-----------------------------------------------------------------------------------------------------------------------------------------------------(ice@distantstar)-
`--> ruby ./golf.rb 734 929
681886

Ruby, 35 bytes

def x(a)Array.new(*a).inject :+end

Uso: x([123, 456]) #=> 56088

Provavelmente poderia ser reduzido se os números forem lidos no ARGV, mas reclama que eles estão no formato errado (cadeias de caracteres, não ints). Qualquer sugestão seria ótima.

Mathematica 12

As seguintes somas #2instâncias de #1.

Código

#1~Sum~{#2}&

Uso

#1~Sum~{#2} &[734, 929]

(* out *)

681886

9 caracteres?

Se os parâmetros do programa, a, b, pode ser usado para a entrada, o mesmo resultado pode ser alcançado com 9 caracteres .

a~Sum~{b}

VB11, 101 Chars

   Dim m As Func(Of Integer, Integer, Integer, Integer) = Function(a, b, t) If(a = 0, t, m(a >> 1, b << 1, t + If(a Mod 2 = 1, b, 0)))