Thread: Compute a square root (with restrictions)

  1. #1
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396

    Compute a square root (with restrictions)

    Some of you may know the solution to this problem already. If you do, please wait to post your answer until other people have had a chance.

    Challenge: Write a function which computes the square root of a double precision value. RESTRICTION: You may execute the division operator ONE TIME at the most. I don't mean that it can only appear in one place in the code, I mean that it cannot happen more than once, period.

    RESTRICTION 2: This should be obvious, but I'll spell it out. You cannot use any function declared in math.h. In fact, you may not use any functions whatsoever (except for the function you are writing).

    Accuracy requirement: When the value returned by your function is squared, the resulting value must not differ from the original by more than 1 part in 100000.

    You may assume that the values passed to your function will never exceed 1e9. (This used to be 1e20, but I realized that is probably too difficult)

    Be as efficient as possible.
    Last edited by brewbuck; 04-27-2007 at 05:56 PM.

  2. #2
    Registered User
    Join Date
    Sep 2001
    Posts
    752
    I'm a little curious... I can think of two ways to do this, but neither involve using division once. (coding the 'cool' solution)
    Callou collei we'll code the way
    Of prime numbers and pings!

  3. #3
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,005
    Portability? Underlying assumptions (such as IEEE, etc.)?
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  4. #4
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by Dave_Sinkula View Post
    Portability? Underlying assumptions (such as IEEE, etc.)?
    I'll leave the particular floating point representation up to the coder. Just make sure you specify the requirements in the solution.

  5. #5
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    And let me just say, for the sake of clarification, that you are not required to use the division operator at all. But if you DO use it, you can only use it once.

  6. #6
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396

    Anybody?

    Is anybody making any progress on this?

  7. #7
    Deathray Engineer MacGyver's Avatar
    Join Date
    Mar 2007
    Posts
    3,210
    About 20 people will all claim they knew it all along when you post the answer.

  8. #8
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    shh... MacGyver, don't spoil it for the other 20 of us

    Well, honestly, I cannot think of an efficient way to find a square root of a double given the restriction of not more than one division operation.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  9. #9
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by laserlight View Post
    Well, honestly, I cannot think of an efficient way to find a square root of a double given the restriction of not more than one division operation.
    If there are no submissions by tomorrow noon (my time, which is about 15 hours from now), I'll drop a huge hint. 24 hours after that I'll post my solution (which probably isn't the only possible one).

  10. #10
    Deathray Engineer MacGyver's Avatar
    Join Date
    Mar 2007
    Posts
    3,210
    I just realized that on the system I'm on, the sqrt() function in math.h isn't as accurate as you're asking us to be.

    Code:
    sqrt(79)        =       8.888194        =       sqrt(78.999994)
    LOL..... Nice.

  11. #11
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by MacGyver View Post
    I just realized that on the system I'm on, the sqrt() function in math.h isn't as accurate as you're asking us to be.

    Code:
    sqrt(79)        =       8.888194        =       sqrt(78.999994)
    LOL..... Nice.
    Are you sure this isn't just an artifact of printf() not printing all the digits? I'm able to meet my own accuracy requirement with my solution...

  12. #12
    Deathray Engineer MacGyver's Avatar
    Join Date
    Mar 2007
    Posts
    3,210
    Edited....

    Bleh, nevermind. Somehow in copying/pasting a bunch of other stuff, I screwed up and managed to convert it to a float before printing. Converting to double produces perfect results.

    I'll take my Idiot of the Year award anytime this weekend.
    Last edited by MacGyver; 04-28-2007 at 11:20 PM.

  13. #13
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by MacGyver View Post
    Code:
    sqrt(79)        =       8.888194        =       sqrt(78.9999940778)
    Hrm. 79 - 78.9999940778 = 0.0000059222, which is 1 part in about 168000. So you're just barely in range

  14. #14
    Deathray Engineer MacGyver's Avatar
    Join Date
    Mar 2007
    Posts
    3,210
    With all the mistakes I've been making, I think I should finally get some sleep. Sorry to all.

  15. #15
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Is it the one which involves interesting use of '0x5f3759df' ?
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. program to calculate the square root
    By saszew in forum C Programming
    Replies: 7
    Last Post: 10-28-2008, 12:53 PM
  2. Forced moves trouble!!
    By Zishaan in forum Game Programming
    Replies: 0
    Last Post: 03-27-2007, 06:57 PM
  3. Bisection Method function value at root incorrect
    By mr_glass in forum C Programming
    Replies: 3
    Last Post: 11-10-2005, 09:10 AM
  4. Square Root ?!?
    By Tm687 in forum C++ Programming
    Replies: 1
    Last Post: 02-29-2004, 04:38 PM
  5. Templated Binary Tree... dear god...
    By Nakeerb in forum C++ Programming
    Replies: 15
    Last Post: 01-17-2003, 02:24 AM