Multiply without multiply [closed]

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 78 Characters

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

In a more readable form

m;main(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

APL (5)

Takes input on standard input separated by newlines.

+/⎕⍴⎕

Answer 3

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 4

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 5

Python, 64 chars

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 6

Ruby, 30

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

Based on GigaWat answer.

Answer 7

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 8

J, 18 17 characters

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

Input needs to be space separated.

Answer 9

Python, also 64 chars

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

Answer 10

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 11

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 12

A variation in Scala, optimized for size: 48 chars

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

optimized for speed a bit:

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: 95 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)

Answer 13

K, 18 16

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

.

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

Answer 14

Ruby, 35 chars

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

It's a program, which takes input and outputs, not just a function.

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

Answer 15

Ruby, 35 bytes

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 16

Mathematica 12

The following sums #2 instances of #1.

Code

#1~Sum~{#2}&

Usage

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

(* out *)

681886

---

9 chars?

If program parameters, a, b, may be used for input, the same result can be achieved with 9 chars.

a~Sum~{b}

Answer 17

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