Multiply without multiply

Question

Write the fastest (best big-O) and smallest multiplication algorithm for positive integers, without using multiplication operators. You are only allowed addition, subtraction, logical functions (AND, OR, XOR, NOT), bit shift, bit rotate, bit flip/set/clear and bit test. Your program should be capable of multiplying 16-bit numbers to produce a 32-bit result. Take input on stdin, separated by commas, spaces or new lines (your choice), but make it clear how to input the data.

Example input/output:

734 929
681886

Answer 1

C 84 83 Characters

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

In a more readable form

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

The algorithm is better known as the Ethiopian Multiplication or the Russian Peasant Multiplication.Here’s the algorithm :

1. Let the two numbers to be multiplied be a and b.
2. If a is zero then break and print the result.
3. If a is odd then add b to the result.
4. Half a, Double b. Goto Step 2.

Answer 2

Golfscript - 12 characteres

~0\{1$+}*\;

Please note that * here is not the multiplication operator, it's instead a repetition operator, see the second use here.

Answer 3

Golfscript - 27 chars

Peasants multiplication. There first * in there is a multiply, but only by 0 or 1

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

Here's on at 31 chars that doesn't multiply at all

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

Answer 4

Python - 64 characters

Probably not the most efficient though (or the most compliant, but I'm "adding", aren't I?):

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

Answer 5

Golfscript - 43

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

Implementation of the peasant multiplication. I think I may be able to golf it some more later on.

Answer 6

Python, also 64 chars

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

Answer 7

Ruby, 35

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

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

Could probably be shortened if the numbers are read from ARGV, but it complains about them being the wrong format (strings, not ints). Any suggestions would be great.

Answer 8

Ruby, 30

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

Based on GigaWat answer.

Answer 9

J, 18 17 characters

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

Input needs to be space separated.

Answer 10

Perl: 52 chars

This is an old question, but Perl needs to be represented:

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

(This is the binary algorithm; iterated addition is smaller but way too boring.)

This program includes an unintentional feature: if your input line contains a third number, the program will actually calculate A*B+C.

Answer 11

A variation in Scala:

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) 
}

I swap (a, b) if (a > b), to reach the end more fast. The difference is 11 to 20 steps, when calling mul (1023,31), compared with omitting that line of code.

golfed: 117 chars:

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)}
m(readInt,readInt)

Answer 12

VBA, 70 chars

This is actually quite slow for large numbers, but it's small. I managed to improve the code size while improving speed. Calculation time varies, depending on argument position - not just size. (i.e. 1000, 5000 computes in about 4 seconds while 5000, 1000 calculates in about 19) Since the OP lists both fast and small, I figured I'd go with this one. Input is two numeric args, comma separated.

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

This longer version (103 chars) will ensure it runs with the faster of the two possible arrangements:

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

Answer 13

K,18

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

.

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