Addition using only multiply and divide

[pianorain]

If only multiplication and division are allowed, I'm willing to posit that this challenge is unsolvable. You are asking for an expression of the following form to produce addition and subtraction:

operand [*,/] operand
operand -> a constant, one of the inputs, or operand [*,/] operand 

I won't hold my breath on that one.

I will share my original thoughts. Since a double contains 11 bits of exponent, that part of a double can be used as an accumulator through multiplication. Note that not all states of the 11 bits are valid; I originally planned to only use 10 bits to avoid the NaN and infinity states. After building a 10-bit accumulator, it's a simple step to cascade five of them, add a three bit accumulator for the last three bits that the fraction part of a double can contain, and perform the addition in that context. This required the comparision operators to check to see if the initial state of the exponent was 0 since multiplying 0 by 2 wouldn't produce any usable input. The assignment operator was necessary to assign the first 1 into an empty accumulator.

Of course, with the comparision and assignment operators, you really don't need anything that convolted. A union with a bit field (with each bit as its own field) and a 64-bit integer would provide the space needed to perform the addition.

[QuestionC]

I'm inclined to say it's impossible as well... but for the life of me, I just can't prove it.

On the other hand, if you only use pow() and ln(), you can do this easily.

[brewbuck]

Originally Posted by QuestionC

I'm inclined to say it's impossible as well... but for the life of me, I just can't prove it.

On the other hand, if you only use pow() and ln(), you can do this easily.

I suppose in some very special cases, you could arrive at the right answer by using numerical overflow in a clever way. But not in general.

Take, for instance, the expression 1 - 1. There simply is no sequence of multiplication and division operations on the value 1 that will ever result in zero. (Unless you multiply by zero somewhere, but that's hardly a general method either).

[Rashakil Fol]

The proof is pretty simple: Multiplying and dividing nonzero numbers produces a nonzero result. Thus you can't get the sum of 1 and -1 with only multiplication and division, unless you multiply by zero (and then your function adds everything to zero). You need some additional features, like control structures and comparison operators, to make progress towards zero.

Edit: beaten.

Edit 2: Hey, the ICFP contest has begun.

[Differ]

Ints -> Rounding -> Zero.

[brewbuck]

Originally Posted by Differ

Ints -> Rounding -> Zero.

Where's -> Your -> Solution?

[sea_4_ever]

No Fear! I am here to save the Day!
*sea_4_ever rides up on a white horse.
I WILL ATTEMPT THIS!
so, am I allowed to use more than one variable?
I will need at least 7;

At least I think this can be solved with something similar to Pythagoras' Theorem.
A^2 + B^2 = C^2
So maybe :
((A^2)/B) * ((B^2)/A) = C
...
*sea_4_ever goes back to his notes

EDIT4:
I am inclined to give up.
EDIT5 :
maybe if I use that fibonacci series.
multiply the first number by the ratio, and then divide the answer by the third number...
erhm, what is the prize?
BUT I NEVER GIVE UP!

[zacs7]

Brute force is no way to win a contest

Just like 2 + 2 = 4, and 2 * 2 = 4, wow I did it! A * B = C, no

[mike_g]

Originally Posted by sea_4_ever

BUT I NEVER GIVE UP!

Even when the challenge is impossible?

Think of this:

Originally Posted by brewbuck

There simply is no sequence of multiplication and division operations on the value 1 that will ever result in zero.

Then give up

[Yarin]

void SubtractOne(DWORD *pdwQuery) {
   *pdwQuery *= 0.99999999999999;   }

[Differ]

Ah, I just came back and saw the "doubles" part. Many apologies; my solution will only work for integers.

[whiteflags]

Pardon me, but I don't think the type makes a difference at all. No amount of fudging can make -1 * 1 give the same result as 1 - 1. Of course abachler never said that you had to use the same terms as your input, however addition and subtraction treat the sign of a number fundamentally different than multiplication or division. If it's logically incomprehensible I doubt there is a reliable implementation that works for any combonation of 10,000 numbers. Whatever the range was.

Writing this for the fourth or fifth time now, I hope this thread has used up the last of its lives.