# Compute a square root (with restrictions)

Show 80 post(s) from this thread on one page
Page 1 of 4 1234 Last
• 04-27-2007
brewbuck
Compute a square root (with restrictions)

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.
• 04-27-2007
QuestionC
I'm a little curious... I can think of two ways to do this, but neither involve using division once. (coding the 'cool' solution)
• 04-27-2007
Dave_Sinkula
Portability? Underlying assumptions (such as IEEE, etc.)?
• 04-27-2007
brewbuck
Quote:

Originally Posted by Dave_Sinkula
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.
• 04-27-2007
brewbuck
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.
• 04-28-2007
brewbuck
Anybody?
Is anybody making any progress on this?
• 04-28-2007
MacGyver
About 20 people will all claim they knew it all along when you post the answer. :p
• 04-28-2007
laserlight
shh... MacGyver, don't spoil it for the other 20 of us :p

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.
• 04-28-2007
brewbuck
Quote:

Originally Posted by laserlight
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).
• 04-28-2007
MacGyver
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. ;)
• 04-28-2007
brewbuck
Quote:

Originally Posted by MacGyver
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...
• 04-28-2007
MacGyver
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.
• 04-28-2007
brewbuck
Quote:

Originally Posted by MacGyver
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 ;)
• 04-29-2007
MacGyver
With all the mistakes I've been making, I think I should finally get some sleep. Sorry to all. :(
• 04-29-2007
Salem
Is it the one which involves interesting use of '0x5f3759df' ?
Show 80 post(s) from this thread on one page
Page 1 of 4 1234 Last