Addition using only multiply and divide

This is a discussion on Addition using only multiply and divide within the Contests Board forums, part of the Community Boards category; If only multiplication and division are allowed, I'm willing to posit that this challenge is unsolvable. You are asking for ...

  1. #16
    Anti-Poster
    Join Date
    Feb 2002
    Posts
    1,399
    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:
    Code:
    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.
    If I did your homework for you, then you might pass your class without learning how to write a program like this. Then you might graduate and get your degree without learning how to write a program like this. You might become a professional programmer without knowing how to write a program like this. Someday you might work on a project with me without knowing how to write a program like this. Then I would have to do you serious bodily harm. - Jack Klein

  2. #17
    Registered User
    Join Date
    Sep 2001
    Posts
    752
    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.
    Callou collei we'll code the way
    Of prime numbers and pings!

  3. #18
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,249
    Quote Originally Posted by QuestionC View Post
    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).

  4. #19
    aoeuhtns
    Join Date
    Jul 2005
    Posts
    581
    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.
    There are 10 types of people in this world, those who cringed when reading the beginning of this sentence and those who salivated to how superior they are for understanding something as simple as binary.

  5. #20
    </3 Segfaults
    Join Date
    Jul 2007
    Posts
    27
    Ints -> Rounding -> Zero.

  6. #21
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,249
    Quote Originally Posted by Differ View Post
    Ints -> Rounding -> Zero.
    Where's -> Your -> Solution?

  7. #22
    Registered User
    Join Date
    Aug 2007
    Location
    Barbados
    Posts
    31
    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!
    Last edited by sea_4_ever; 08-28-2007 at 02:05 PM.

  8. #23
    Woof, woof! zacs7's Avatar
    Join Date
    Mar 2007
    Location
    Australia
    Posts
    3,459
    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

  9. #24
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218
    Quote Originally Posted by sea_4_ever
    BUT I NEVER GIVE UP!
    Even when the challenge is impossible?

    Think of this:
    Quote 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

  10. #25
    Unregistered User Yarin's Avatar
    Join Date
    Jul 2007
    Posts
    1,665

    Code:
    void SubtractOne(DWORD *pdwQuery) {
       *pdwQuery *= 0.99999999999999;   }
    A class that doesn't overload all operators just isn't finished yet. -- SmugCeePlusPlusWeenie
    A year spent in artificial intelligence is enough to make one believe in God. -- Alan J. Perlis

  11. #26
    </3 Segfaults
    Join Date
    Jul 2007
    Posts
    27
    Ah, I just came back and saw the "doubles" part. Many apologies; my solution will only work for integers.

  12. #27
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,738
    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.

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Faster way to divide numbers
    By scwizzo in forum C++ Programming
    Replies: 3
    Last Post: 04-29-2009, 11:45 AM
  2. Overflow and range checking for mul/div
    By Elysia in forum C++ Programming
    Replies: 28
    Last Post: 06-06-2008, 02:09 PM
  3. working with rotation matrices
    By hannibar in forum Game Programming
    Replies: 23
    Last Post: 03-30-2005, 12:10 PM
  4. How to multiply and Divide Huge int numbers
    By Dewayne in forum C++ Programming
    Replies: 3
    Last Post: 10-21-2004, 08:41 PM
  5. calculator in c++
    By gamer in forum C++ Programming
    Replies: 11
    Last Post: 02-19-2003, 09:46 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21