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

1What about the division operator? – st0le – 2011-02-07T13:57:46.600

3Is this codegolf or a challenge? :-\ – st0le – 2011-02-07T14:05:57.037

@st0le you are only allowed the ops I name. – Thomas O – 2011-02-07T16:53:25.820

@st0le It is a combination of both - a challenge to figure it out, as well as the smallest being considered best. – Thomas O – 2011-02-07T16:53:59.377

3I 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. – user unknown – 2012-05-16T03:22:30.927

@Thomas, You should specify if negative numbers are also to be handled...i don't think anyone is handling it at the moment. – st0le – 2011-02-08T06:58:00.877

@st0le from the question: "smallest multiplication algorithm for

positiveintegers" – Thomas O – 2011-02-08T08:03:18.3972

This question is insane as stated. The asymptotically fastest known multiplication algorithm for positive integers is Fürer's algorithm (http://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).

– D Coetzee – 2012-07-16T01:16:53.9174Fastest

ORsmalles - you can't have both, or you need a translation formular to calculate the trade off. – user unknown – 2012-01-11T02:57:08.337