8
\$\begingroup\$

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
\$\endgroup\$

closed as off-topic by lirtosiast, GamrCorps, Zach Gates, Mego, steve Dec 10 '15 at 8:05

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Questions without an objective primary winning criterion are off-topic, as they make it impossible to indisputably decide which entry should win." – lirtosiast, GamrCorps, Zach Gates, Mego
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    \$\begingroup\$ What about the division operator? \$\endgroup\$ – st0le Feb 7 '11 at 13:57
  • 3
    \$\begingroup\$ Is this codegolf or a challenge? :-\ \$\endgroup\$ – st0le Feb 7 '11 at 14:05
  • 4
    \$\begingroup\$ Fastest OR smalles - you can't have both, or you need a translation formular to calculate the trade off. \$\endgroup\$ – user unknown Jan 11 '12 at 2:57
  • 3
    \$\begingroup\$ I marked for closing as "not a real question", since there still isn't given a solution, how to compare the fastest and the shortest code. Which is of priority? Or in what relation is the trade off? It could be healed if a some comparison algo in a portable lang was given - for example: if the std-algo reaches 500k operations in C, and your algo reaches 50k, you have to multiply the codelength *10. That way everybody could choose whether to shorten the code or to make it faster. The winner needn't be winner in both categories, but the winning criteria would be far more objective. \$\endgroup\$ – user unknown May 16 '12 at 3:22
  • 2
    \$\begingroup\$ This question is insane as stated. The asymptotically fastest known multiplication algorithm for positive integers is Fürer's algorithm (en.wikipedia.org/wiki/F%C3%BCrer%27s_algorithm) and it's ridiculously complex and would take thousands of lines to implement in any language. I assume he actually just means your algorithm has to be O(n^2) (long multiplication). \$\endgroup\$ – D Coetzee Jul 16 '12 at 1:16

17 Answers 17

11
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ not working without initializing m=0 (atleast for me) \$\endgroup\$ – st0le Feb 7 '11 at 14:04
  • \$\begingroup\$ @st0le It will work now, I have moved 'm' to begining in the main function. See here: ideone.com/XCz8C \$\endgroup\$ – fR0DDY Feb 7 '11 at 14:09
  • \$\begingroup\$ Forgot about this one, here's a shorter one for(;(a&1&&m+=b)|a;a>>=1,b<<=1); Yes, i'm very ashamed. :) \$\endgroup\$ – st0le Feb 7 '11 at 14:10
  • \$\begingroup\$ for(m=0;(a&1&&m+=b)|a;a/=2,b*=2); why use shift,right? \$\endgroup\$ – st0le Feb 7 '11 at 14:14
  • 2
    \$\begingroup\$ @fR0DDY: You could say b+=b instead of b*=2 . Of course, you'll still need the right shift. \$\endgroup\$ – Joey Adams Feb 7 '11 at 22:01
7
\$\begingroup\$

APL (5)

Takes input on standard input separated by newlines.

+/⎕⍴⎕
\$\endgroup\$
5
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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\]@=}%{+}*\;
\$\endgroup\$
4
\$\begingroup\$

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())))
\$\endgroup\$
  • 7
    \$\begingroup\$ You could use input() in place of int(raw_input()) to save 18 characters. You might consider this cheating, but print sum([input()]*input()) also works (* is being used for repetition, not multiplication). \$\endgroup\$ – James Apr 16 '12 at 10:23
  • \$\begingroup\$ r=input;a=r();print sum(map(lambda x:a,range(r()))) is much shorter \$\endgroup\$ – Joel Cornett May 15 '12 at 8:31
  • \$\begingroup\$ @JoelCornett r=input;a=r();r(sum(a for b in range(r()))) is even shorter (43 vs 51 bytes) \$\endgroup\$ – FatalError Sep 27 '18 at 21:49
3
\$\begingroup\$

Ruby, 30

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

Based on GigaWat answer.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

J, 18 17 characters

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

Input needs to be space separated.

\$\endgroup\$
2
\$\begingroup\$

Python, also 64 chars

m=lambda x,n:0 if n==0 else x+m(x,n-1);print m(input(),input())
\$\endgroup\$
  • 1
    \$\begingroup\$ You could shorten it by assigning i=input and using i() \$\endgroup\$ – st0le Feb 8 '11 at 6:55
  • 3
    \$\begingroup\$ actually that works out to be exactly the same number of characters \$\endgroup\$ – Doug T. Feb 8 '11 at 13:41
  • 2
    \$\begingroup\$ could replace 0 if n==0 else with n and \$\endgroup\$ – recursive Feb 11 '11 at 18:53
1
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ You can loose quite a few bytes by removing whitespace before To and in concatenation, as well as by outputiing to the VBE immediate window via Debug.? \$\endgroup\$ – Taylor Scott May 31 '17 at 15:16
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ How fast is it? \$\endgroup\$ – user unknown May 16 '12 at 3:24
  • \$\begingroup\$ It runs in O(log n), naturally. Are you asking about its actual speed? On my machine I measure roughly 2-3 times slower than Perl's builtin multiply, but I don't know how significant that is. \$\endgroup\$ – breadbox May 16 '12 at 6:05
1
\$\begingroup\$

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)
\$\endgroup\$
1
\$\begingroup\$

K, 18 16

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

.

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

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
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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}
\$\endgroup\$
0
\$\begingroup\$

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)))
\$\endgroup\$
  • 1
    \$\begingroup\$ You used a few disallowed operations... \$\endgroup\$ – Gaffi May 26 '12 at 8:15
  • \$\begingroup\$ I don't think this uses disallowed operations (unless control flow is disallowed; the question is unclear on that, which is part of the reason it's on hold). "mod 2" is a bit test operation. I guess comparisons (==) aren't allowed by the question, but plenty of answers are using them. \$\endgroup\$ – user62131 Jun 3 '17 at 5:15

Not the answer you're looking for? Browse other questions tagged or ask your own question.