## 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 templated`1/(-nx)`

cuts a character and brings the solution down to 22 ops.

@xnor Currently, I have the answer which works best without assignment allowed (assignment used only once, and will only double it (approximately)). Does that count for the optimal result without assignment, or does it need to be proven to be the optimal result? – proud haskeller – 2015-05-02T17:58:13.477

@proudhaskeller No, I'm looking for a proof of optimality. (Sorry, I had missed your comment in my feed.) – xnor – 2015-05-07T20:30:01.683

4Is this even possible? – Ypnypn – 2014-09-01T20:19:44.460

1@Ypnypn Yes, and I've written an example to make sure. – xnor – 2014-09-01T20:24:15.563

2This 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 – 2014-09-01T20:27:27.033

1@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 – 2014-09-01T20:30:39.550

2Ok 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 – 2014-09-01T21:43:54.903

1@flawr I was imagining the fake language to express arithmetic formulas for real numbers, not act on bits or any sort of finite representation, so I think the measure requirement over the real plane (a,b) ∈ R^2 works fine. But if you actually think it's unclear, I'll edit it. – xnor – 2014-09-01T21:45:41.183

1Of course it is clear what you mean but I think it does not help using precisely defined technical terminology for something that does not meet the definition. Sorry for being a stickler! In my opinion you can also write

`I know what you mean`

or (`most as in common sense`

). – flawr – 2014-09-01T21:47:41.510@flawr I was typing up the same stuff when I saw your comments. Exactly, the set of IEEE floating point numbers is measure zero, and so is all pairs of them. And so is the set of all numbers representable on any machine. – Eric Tressler – 2014-09-01T21:51:08.407

1OK, thanks for the feedback, I guess I should have realize that coders would interpret numbers as stored in bits. I edited it to try to make clear I'm requiring arithmetically correct results for all but a measure-zero set of pairs of real numbers. – xnor – 2014-09-01T21:53:17.723

@xnor How much operations you got when you solved this question? – proud haskeller – 2014-09-04T05:17:33.703

@proudhaskeller 33 :-P It was basically a worse version of algorithmshark's answer. – xnor – 2014-09-04T05:23:17.213

1I don't know that there's a better choice for an algorithmic search other than brute force... And if the actual best solution is, say, 22 operations, that's not really feasible for a brute force search. – rationalis – 2014-09-04T23:57:58.867

I will give a bounty of 300 rep to anyone who posts an optimal solution with proof. A brute force search can be a proof if you explain how it checks everything needed. An optimal result restricted not to use variable assignment will be given 150 rep. Other partial bounties may be given for partial results. – xnor – 2014-10-27T17:45:08.997

@xnor What do you mean by optimal here ? less than 23 operations ? – Optimizer – 2014-10-27T17:50:58.243

@Optimizer No, the best theoretically possible. It might be 23, it might be less. A solution of 22 operations with no proof of optimality would not suffice. (Clarified in the post, thanks.) – xnor – 2014-10-27T17:52:21.707

You mean 22 operations (instead of chars), right ? Also, if someone posts a 24 operations solution, will that count ? – Optimizer – 2014-10-27T17:56:52.140

@Optimizer Yes, operations, thanks. Not sure what you mean about a 24 op solution -- it can't be optimal because there's a 23. If you mean for the no-assignment half-prize, yes, I'd count an optimal solution for that that's more than 23 ops. – xnor – 2014-10-27T17:58:51.777

I see. So the existing 23 operations won't get 300 if no one else posts, right ? Also, are you really sure an answer less than 23 exists ? – Optimizer – 2014-10-27T17:59:53.983