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; The goal is to perform the function A = B + C using only multiplication and division. Assume that A ...

  1. #1
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,189

    Addition using only multiply and divide

    The goal is to perform the function A = B + C using only multiplication and division. Assume that A B and C are doubles. The limits of the inputs are
    +/- 100000.0 The entry must work with all numbers in that range.





    Rules -
    1. I will disqualify any entry that I do not feel is in the spirit of the contest with or without an explanation. This decision is final.
    2. Qualification is not commutative. Approximation of a qualifying function does not guarantee the approximation will qualify.
    3. I reserve the right to change the specific or general nature of the contest at any time.
    Until you can build a working general purpose reprogrammable computer out of basic components from radio shack, you are not fit to call yourself a programmer in my presence. This is cwhizard, signing off.

  2. #2
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,249
    Quote Originally Posted by abachler View Post
    The goal is to perform the function A = B + C using only multiplication and division. Assume that A B and C are doubles. The limits of the inputs are
    +/- 100000.0 The entry must work with all numbers in that range.
    Code:
    double sum(double b, double c)
    {
        return log(exp(b) * exp(c));
    }

  3. #3
    Registered User
    Join Date
    Sep 2001
    Posts
    752
    implementing log and exp without addition seems... non-trivial.
    Callou collei we'll code the way
    Of prime numbers and pings!

  4. #4
    Anti-Poster
    Join Date
    Feb 2002
    Posts
    1,399
    Quote Originally Posted by abachler View Post
    1. I will disqualify any entry that I do not feel is in the spirit of the contest with or without an explanation. This decision is final.
    Halloween has spirits. Contests shouldn't. Define the problem well enough and it's a non-issue.

    To what precision should we expect the inputs? From the original statement, it appeared only to matter to the first decimal place.

    Please define "the entry must work". Does this mean you will not accept any approximation?
    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

  5. #5
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,189
    The contest is to implement it using only multiplication and addition, I dont think log or exp count as either of those. I was originally going to say to do it without using addition or subtraction, but I foresaw people trying to make entries using macros and functions that themselves use those, and then arguing that the rule was vague. So I nipped it in the bud and made it multiplication and division only.
    Last edited by abachler; 07-19-2007 at 09:01 AM.
    Until you can build a working general purpose reprogrammable computer out of basic components from radio shack, you are not fit to call yourself a programmer in my presence. This is cwhizard, signing off.

  6. #6
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,189
    Quote Originally Posted by pianorain View Post
    To what precision should we expect the inputs? From the original statement, it appeared only to matter to the first decimal place.
    Im nto really sure how you came up with that idea, it clearly states ALL values, you can safely assume that means ALL values that can fit into a double.

    Please define "the entry must work". Does this mean you will not accept any approximation?
    Please define approximation and ill tell you if Ill accept it.
    Until you can build a working general purpose reprogrammable computer out of basic components from radio shack, you are not fit to call yourself a programmer in my presence. This is cwhizard, signing off.

  7. #7
    Anti-Poster
    Join Date
    Feb 2002
    Posts
    1,399
    Quote Originally Posted by abachler View Post
    Im nto really sure how you came up with that idea, it clearly states ALL values, you can safely assume that means ALL values that can fit into a double.
    Quote Originally Posted by abachler View Post
    The limits of the inputs are
    +/- 100000.0 The entry must work with all numbers in that range.
    However, your PM made it more clear.
    Quote Originally Posted by abachler
    I will not open the contest to approximations. The entry must produce the exact bit for bit result that the FPU on my computer will produce given the same inputs.
    So sum(a,b) == a + b for all a,b where a and b are doubles in the range [-100000, 100000].

    edit: I hope I'm missing something. The only operators we're allowed to use are * and / ?
    Last edited by pianorain; 07-19-2007 at 10:07 AM.
    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

  8. #8
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,189
    Thats pretty much it, multiply and divide only. Sort of a twist on the old implement multiply or divide using only additon and subtraction.
    Until you can build a working general purpose reprogrammable computer out of basic components from radio shack, you are not fit to call yourself a programmer in my presence. This is cwhizard, signing off.

  9. #9
    Anti-Poster
    Join Date
    Feb 2002
    Posts
    1,399
    I've designed a solution, but it requires the comparison and assignment operators. Are those allowable?
    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

  10. #10
    aoeuhtns
    Join Date
    Jul 2005
    Posts
    581
    And.... what decides the winner?
    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.

  11. #11
    Anti-Poster
    Join Date
    Feb 2002
    Posts
    1,399
    Quote Originally Posted by Rashakil Fol View Post
    And.... what decides the winner?
    Oh Rashakil...next you'll be asking what languages are valid for a submission.
    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

  12. #12
    aoeuhtns
    Join Date
    Jul 2005
    Posts
    581
    Will the function be required to work on denormalized values?

    Also, are arrays, and indexing thereof, allowed?

    Edit: Also, what languages are valid for a submission? Seriously.

    Edit 2: Can we use std::strings and concatenate them and then use size() to implement addition for positive integers as part of the algorithm?
    Last edited by Rashakil Fol; 07-19-2007 at 11:31 PM.
    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.

  13. #13
    Registered Abuser
    Join Date
    Jun 2006
    Location
    Toronto
    Posts
    591
    just a guess, but usually these types of problems are geared towards a solution that uses some sort of bitwise manipulations.

  14. #14
    Anti-Poster
    Join Date
    Feb 2002
    Posts
    1,399
    Quote Originally Posted by @nthony View Post
    just a guess, but usually these types of problems are geared towards a solution that uses some sort of bitwise manipulations.
    Indeed they are, but it's easier to implement addition using bit operations than it is to implement addition using multiplication.
    Quote Originally Posted by Rashakil Fol
    Edit 2: Can we use std::strings and concatenate them and then use size() to implement addition for positive integers as part of the algorithm?
    Heh, that's a unique place to look for an accumulator. I bet yours will add faster than mine.
    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

  15. #15
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,189
    Again, you can only use multiply and divide. Since this is a C programming site, id say that C is the only acceptable language. Since I speak C and assembly Ill expand it to include assembly for the Xeon.

    The impetus for this challenge is I have a GPU that for some reason is faster at multiply than it is at adds. The solution to this wont solve my problem with the GPU, it was just inspired by it. Our problem is the GPU doesnt properly parallelize the addition of all members of a vector. Its an implementation issue we are sure, but one thought we had was to switch it to multiplies. Turns otu its just that it executes operations across members of a vecvtor in series, which makes it run very slowly.
    Last edited by abachler; 07-20-2007 at 09:47 AM.
    Until you can build a working general purpose reprogrammable computer out of basic components from radio shack, you are not fit to call yourself a programmer in my presence. This is cwhizard, signing off.

Page 1 of 2 12 LastLast
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