# Thread: Compute a square root (with restrictions)

1. ## 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.

2. I'm a little curious... I can think of two ways to do this, but neither involve using division once. (coding the 'cool' solution)

3. Portability? Underlying assumptions (such as IEEE, etc.)?

4. 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.

5. 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. ## Anybody?

Is anybody making any progress on this?

7. About 20 people will all claim they knew it all along when you post the answer.

8. 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.

9. 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).

10. 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. 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...

12. 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.

13. 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

14. With all the mistakes I've been making, I think I should finally get some sleep. Sorry to all.

15. Is it the one which involves interesting use of '0x5f3759df' ?

Popular pages Recent additions