Multiply with restricted operations

There's a 500 rep unofficial bounty for beating the current best answer.

Goal

Your goal is to multiply two numbers using only a very limited set of arithmetic operations and variable assignment.

1. Addition x,y -> x+y
2. Reciprocal x -> 1/x (not division x,y -> x/y)
3. Negation x -> -x (not subtraction x,y -> x-y, though you can do it as two operations x + (-y))
4. The constant 1 (no other constants allowed, except as produced by operations from 1)
5. Variable assignment [variable] = [expression]

Scoring: The values start in variables a and b. Your goal is to save their product a*b into the variable c using as few operations as possible. Each operation and assignment +, -, /, = costs a point (equivalently, each use of (1), (2), (3), or (4)). Constants 1 are free. The fewest-point solution wins. Tiebreak is earliest post.

Allowance: Your expression has to be arithmetically correct for "random" reals a and b. It can fail on a measure-zero subset of R2, i.e. a set that has no area if plotted in the a-b Cartesian plane. (This is likely to be needed due to reciprocals of expressions that might be 0 like 1/a.)

Grammar:

This is an . No other operations may be used. In particular, this means no functions, conditionals, loops, or non-numerical data types. Here's a grammar for the allowed operations (possibilities are separated by |). A program is a sequence of <statement>s, where a <statement> is given as following.

<statement>: <variable> = <expr>
<variable>: a | b | c | [string of letters of your choice]
<expr>: <arith_expr> | <variable> | <constant>
<arith_expr>: <addition_expr> | <reciprocal_expr> | <negation_expr>
<reciprocal_expr>: 1/(<expr>)
<negation_expr>: -<expr>
<constant>: 1


You don't actually have to post code in this exact grammar, as long as it's clear what you're doing and your operation count is right. For example, you can write a-b for a+(-b) and count it as two operations, or define macros for brevity.

(There was a previous question Multiply without Multiply, but it allowed a much looser set of operations.)

• Is this even possible? – Ypnypn Sep 1 '14 at 20:19
• @Ypnypn Yes, and I've written an example to make sure. – xnor Sep 1 '14 at 20:24
• This feels like a challenge where an optimal solution is likely to be found (once any solution has been found). So what's the tie breaker in that case? – Martin Ender Sep 1 '14 at 20:27
• @MartinBüttner Tiebreak is earliest posting in that case. I think there's a good amount of room for optimizations, so I don't think it will just be a race to find one that works and write it cleanly. At least, that's what I found in trying it; maybe someone will find a clearly minimal solution. – xnor Sep 1 '14 at 20:30
• Ok since not everyone thought my anwer was as funny as I did, I deleted it and comment here: The rule about the measure zero set is not very wisely chosen since rational numbers are a measure zero set regarding the lebesgue measure, I'd suggest using a certain percentage instead. (Or another kind) But I totally like the idea of this challenge! – flawr Sep 1 '14 at 21:43

22 operations

itx = 1/(1+a+b)     #4
nx = -1/(itx+itx)   #4
c = -( 1/(itx + itx + 1/(1+nx)) + 1/(1/(a+nx) + 1/(b+nx)) ) #14


Try it online!

The ops are 10 additions, 7 inverses, 2 negations, and 3 assignments.

So, how did I get this? I started with the promising-looking template of the sum of two double-decker fractions, a motif that had appeared in many previous attempts.

c = 1/(1/x + 1/y) + 1/(1/z + 1/w)

When we restrict the sum to x+y+z+w=0, a beautiful cancellations occur, giving:

c = (x+z)*(y+z)/(x+y),

which contains a product. (It's often easier to get t*u/v rather than t*u because the first has degree 1.)

There's a more symmetric way to think about this expression. With the restriction x+y+z+w=0, their values are specified by three parameters p,q,r of their pairwise sums.

 p = x+y
-p = z+w
q = x+z
-q = y+w
r = x+w
-r = y+z


and we have c=-q*r/p. The sum p is distinguished as being in the denominator by corresponding to the pairs (x,y) and (z,w) of variables that are in the same fraction.

This is a nice expression for c in p,q,r, but the double-decker fraction is in x,y,z,w so we must express the former in terms of the latter:

x = ( p + q + r)/2
y = ( p - q - r)/2
z = (-p + q - r)/2
w = (-p - q + r)/2


Now, we want to choose p,q,r so that c=-q*r/p equals a*b. One choice is:

p = -4
q = 2*a
r = 2*b


Then, the doubled values for q and r are conveniently halved in:

x = -2 + a + b
y = -2 - a - b
z =  2 + a - b
w =  2 - a + b


Saving 2 as a variable t and plugging these into the equation for c gives a 24-op solution.

#24 ops
t = 1+1   #2
c = 1/(1/(-t+a+b) + 1/-(t+a+b))  +  1/(1/(-b+t+a) + 1/(-a+b+t)) #1, 10, 1, 10


There's 12 additions, 6 inverses, 4 negations, and 2 assignments.

A lot of ops are spent expressing x,y,z,w in terms of 1,a,b. To save ops, instead express x in p,q,r (and thus a,b,1) and then write y,z,w in terms of x.

y = -x + p
z = -x + q
w = -x + r


Choosing

p = 1
q = a
r = b


and expressing c with a negation as c=-q*r/p, we get

x = (1+a+b)/2
y = -x + 1
z = -x + a
w = -x + b


Unfortunately, halving in x is costly. It needs to be done by inverting, adding the result to itself, and inverting again. We also negate to produce nx for -x, since that's what y,z,w use. This gives us the 23-op solution:

#23 ops
itx = 1/(1+a+b)     #4
nx = -1/(itx+itx)   #4
c = -( 1/(1/(-nx) + 1/(1+nx))  +  1/(1/(a+nx) + 1/(b+nx)) ) #15


itx is 1/(2*x) and nx is -x. A final optimization of expressing 1/x as itx+itx instead of the templated1/(-nx) cuts a character and brings the solution down to 22 ops.

• There's an easy optimisation to 21 operations. itx + itx occurs twice, but itx doesn't occur in any other context. Define instead ix = (1+1)/(1+a+b) and you replace two additions with one. – Peter Taylor Jan 27 '17 at 10:51
• And by extracting m = -1 it's possible to get 20: nx = (1+a+b)/(m+m); c = m/(m/nx + 1/(1+nx)) + m/(1/(a+nx) + 1/(b+nx)) – Peter Taylor Jan 27 '17 at 10:57
• Ah, both of those optimisations fail because the supported operation is reciprocal rather than division. – Peter Taylor Jan 27 '17 at 11:01
• If a and b are only one apart, then either a + nx = 0 or b + nx = 0, causing your solution to divide by zero. – MooseOnTheRocks Mar 17 '19 at 2:14
• @MooseOnTheRocks That's fine, see the "allowance" in the challenge that the code can fail on a measure-zero subset. I think the challenge is impossible otherwise. – xnor Mar 17 '19 at 2:18

23 operations

z = 1/(1/(1/(1/(a+1)+1/(b+1))-1+1/(a+b+1+1))-(1/a+1/b))
res = z+z


proof by explosion:

z = 1/(1/(1/(1/(a+1)+1/(b+1))-1+1/(a+b+1+1))-(1/a+1/b))
1/(a+1)+1/(b+1)                            == (a+b+2) / (ab+a+b+1)
1/(1/(a+1)+1/(b+1))                           == (ab+a+b+1) / (a+b+2)
1/(1/(a+1)+1/(b+1))-1                         == (ab - 1) / (a+b+2)
1/(1/(a+1)+1/(b+1))-1+1/(a+b+1+1)             == ab / (a+b+2)
1/(1/(1/(a+1)+1/(b+1))-1+1/(a+b+1+1))            == (a+b+2) / ab
1/a+1/b   == (a+b) / ab
1/(1/(1/(a+1)+1/(b+1))-1+1/(a+b+1+1))-(1/a+1/b)  == 2 / ab
1/(1/(1/(1/(a+1)+1/(b+1))-1+1/(a+b+1+1))-(1/a+1/b)) == ab / 2

z = ab / 2 and therefore z+z = ab


I abused wolfram alpha to get this beautiful image (wolfram alpha tried to get me to subscribe to pro to save it, but then ctrl-c ctrl-v ;-)):

score (with added + on subtraction):

z = ////++/++-+/++++-/+/
res = +

• Congrats on the shortest solution! – xnor Sep 11 '14 at 4:04
• @xnor thanks for giving me my first accepted answer and my first bounty! – proud haskeller Sep 11 '14 at 5:33
• Not to be nit-picky, but shouldn't ...(b+1))-1+1... and ...1))-(1/a+... be ...(b+1))+-1+1... and ...1))+-(1/a+... respectively? – tfitzger May 2 '15 at 17:51
• @tfitzger I think it's easier that way. The question does say that it doesn't matter. Note I do count the score correctly (Every minus is a two) – proud haskeller May 2 '15 at 17:53
• Wolfram Alpha has a 7-day free trial, fyi. – ghosts_in_the_code Nov 27 '15 at 18:05

29 operations

Does not work for the set { (a,b) ∈ R2 | a+b = 0 or a+b = -1 or a-b = 0 or a-b = -1 }. That's probably measure zero?

sum = a+b
nb = -b
diff = a+nb
rfc = 1/(1/(1/sum + -1/(sum+1)) + -1/(1/diff + -1/(diff+1)) + nb + nb)  # rfc = 1/4c
c = 1/(rfc + rfc + rfc + rfc)

# sum  is  2: =+
# nb   is  2: =-
# diff is  2: =+
# rfc  is 18: =///+-/++-//+-/+++
# c    is  5: =/+++
# total = 29 operations


The structure of rfc (Reciprocal-Four-C) is more evident if we define a macro:

s(x) = 1/(1/x + -1/(x+1))              # //+-/+ (no = in count, macros don't exist)
rfc = 1/(s(sum) + - s(diff) + nb + nb) # =/s+-s++ (6+2*s = 18)


Let's do the math:

• s(x), mathematically, is 1/(1/x - 1/(x+1)) which is after a bit of algebra is x*(x+1) or x*x + x.
• When you sub everything into rfc, it's really 1/((a+b)*(a+b) + a + b - (a-b)*(a-b) - a + b + (-b) + (-b)) which is just 1/((a+b)^2 - (a-b)^2).
• After difference of squares, or just plain expansion, you get that rfc is 1/(4*a*b).
• Finally, c is the reciprocal of 4 times rfc, so 1/(4/(4*a*b)) becomes a*b.
• +1, I was in the middle of finishing up this identical calculation – Eric Tressler Sep 1 '14 at 21:19
• That's definitely measure zero; it's a union of lines. – xnor Sep 1 '14 at 21:54
• Not gonna make a comment about union of lines... @algorithmshark Can you tell us more how you did come up with this identity? How did you aproach the problem? – flawr Sep 2 '14 at 12:31
• @flawr I recalled that the properties of s(x) fit the requirements of the question, from calculus, so that meant I had a square function. After some faffing about, I found I could get an a*b term with the difference of squares trick. Once I had that, it was a matter of trying out which assignments saved operations. – algorithmshark Sep 2 '14 at 15:22
• Since you use -1 three times in rfc, couldn't you golf a character out by assigning it to a variable? – isaacg Sep 2 '14 at 18:23

27 operations

tmp = 1/(1/(1+(-1/(1/(1+(-a))+1/(1+b))))+1/(1/(1/b+(-1/a))+1/(a+(-b))))
res = tmp+tmp+(-1)

# tmp is 23: =//+-//+-+/++///+-/+/+-
# res is 4: =++-


There is no theory behind this. I just tried to get (const1+a*b)/const2 and started with (1/(1-a)+1/(1+b)) and (-1/a+1/b).

• Your tmp is actually 23, making your score 27. Nice find, though. – algorithmshark Sep 2 '14 at 15:29

25 operations

two = 1+1
c = 1/(1/(a+b) + -1/(a+b+two)) + 1/(-1/a + 1/(a+two)) + 1/(-1/b + 1/(b+two))


Definitely not optimal, but probably optimal when restricted to only two levels of nested inversions (i.e. not using 1/(1/(1/...). There might be ways to optimize this...

Uses the property

$$\frac{1}{\frac{1}{x}-\frac{1}{x+2}} = \frac{x(x+2)}{2} = \frac{x^2}{2}+x$$

If we substitute $$\x\$$ with $$\a+b, a, b\$$ respectively:

\begin{align} \frac{1}{\frac{1}{a+b}-\frac{1}{a+b+2}} &= \frac{(a+b)^2}{2}+(a+b) = \frac{a^2}{2} + ab + \frac{b^2}{2} + a + b \tag1 \\ \frac{1}{\frac{1}{a}-\frac{1}{a+2}} &= \frac{a^2}{2}+a \tag2 \\ \frac{1}{\frac{1}{b}-\frac{1}{b+2}} &= \frac{b^2}{2}+b \tag3 \\ \end{align}

We can easily see that $$\(1)-(2)-(3)\$$ conveniently gives $$\ab\$$.

> simplify c = 1/(1/(a+b) + -1/(a+b+2)) + 1/(-1/a + 1/(a+2)) + 1/(-1/b + 1/(b+2))
c = ab