48
\$\begingroup\$

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> 
<addition_expr>: <expr> + <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.)

\$\endgroup\$
20
  • 4
    \$\begingroup\$ Is this even possible? \$\endgroup\$
    – Ypnypn
    Sep 1, 2014 at 20:19
  • 1
    \$\begingroup\$ @Ypnypn Yes, and I've written an example to make sure. \$\endgroup\$
    – xnor
    Sep 1, 2014 at 20:24
  • 2
    \$\begingroup\$ 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? \$\endgroup\$ Sep 1, 2014 at 20:27
  • 1
    \$\begingroup\$ @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. \$\endgroup\$
    – xnor
    Sep 1, 2014 at 20:30
  • 3
    \$\begingroup\$ 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! \$\endgroup\$
    – flawr
    Sep 1, 2014 at 21:43

5 Answers 5

34
\$\begingroup\$

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.

\$\endgroup\$
5
  • \$\begingroup\$ 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. \$\endgroup\$ Jan 27, 2017 at 10:51
  • \$\begingroup\$ 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)) \$\endgroup\$ Jan 27, 2017 at 10:57
  • 3
    \$\begingroup\$ Ah, both of those optimisations fail because the supported operation is reciprocal rather than division. \$\endgroup\$ Jan 27, 2017 at 11:01
  • \$\begingroup\$ If a and b are only one apart, then either a + nx = 0 or b + nx = 0, causing your solution to divide by zero. \$\endgroup\$ Mar 17, 2019 at 2:14
  • 1
    \$\begingroup\$ @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. \$\endgroup\$
    – xnor
    Mar 17, 2019 at 2:18
26
+50
\$\begingroup\$

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 = +
\$\endgroup\$
8
  • \$\begingroup\$ Congrats on the shortest solution! \$\endgroup\$
    – xnor
    Sep 11, 2014 at 4:04
  • \$\begingroup\$ @xnor thanks for giving me my first accepted answer and my first bounty! \$\endgroup\$ Sep 11, 2014 at 5:33
  • \$\begingroup\$ 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? \$\endgroup\$
    – tfitzger
    May 2, 2015 at 17:51
  • \$\begingroup\$ @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) \$\endgroup\$ May 2, 2015 at 17:53
  • \$\begingroup\$ Wolfram Alpha has a 7-day free trial, fyi. \$\endgroup\$ Nov 27, 2015 at 18:05
13
\$\begingroup\$

29 operations

Does not work for the set \$\{(a,b) \in \mathbb{R}^2 : a\pm b=0 \text{ or } a\pm 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.
\$\endgroup\$
6
  • 2
    \$\begingroup\$ +1, I was in the middle of finishing up this identical calculation \$\endgroup\$ Sep 1, 2014 at 21:19
  • 1
    \$\begingroup\$ That's definitely measure zero; it's a union of lines. \$\endgroup\$
    – xnor
    Sep 1, 2014 at 21:54
  • \$\begingroup\$ 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? \$\endgroup\$
    – flawr
    Sep 2, 2014 at 12:31
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ Sep 2, 2014 at 15:22
  • \$\begingroup\$ Since you use -1 three times in rfc, couldn't you golf a character out by assigning it to a variable? \$\endgroup\$
    – isaacg
    Sep 2, 2014 at 18:23
9
\$\begingroup\$

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

\$\endgroup\$
1
  • \$\begingroup\$ Your tmp is actually 23, making your score 27. Nice find, though. \$\endgroup\$ Sep 2, 2014 at 15:29
3
\$\begingroup\$

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

Proof by Wolfram|Alpha:

> simplify c = 1/(1/(a+b) + -1/(a+b+2)) + 1/(-1/a + 1/(a+2)) + 1/(-1/b + 1/(b+2))
c = ab
\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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