Compute a square root (with restrictions)

brewbuck · 04-27-2007, 04:45 PM

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.

QuestionC · 04-27-2007, 08:47 PM

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

**Dave_Sinkula** · 04-27-2007, 09:04 PM

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

brewbuck · 04-27-2007, 10:18 PM

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.

brewbuck · 04-27-2007, 11:02 PM

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.

brewbuck · 04-28-2007, 08:39 PM

Is anybody making any progress on this?

MacGyver · 04-28-2007, 09:16 PM

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

**laserlight** · 04-28-2007, 10:09 PM

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.

brewbuck · 04-28-2007, 10:19 PM

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

MacGyver · 04-28-2007, 11:11 PM

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.

brewbuck · 04-28-2007, 11:16 PM

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

MacGyver · 04-28-2007, 11:18 PM

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.

brewbuck · 04-28-2007, 11:21 PM

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

MacGyver · 04-29-2007, 12:12 AM

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

**Salem** · 04-29-2007, 12:20 AM

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

04-27-2007, 04:45 PM	#1
brewbuck Senior software engineer Join Date: Mar 2007 Location: Portland, OR Posts: 5,381	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.
brewbuck is offline

04-27-2007, 08:47 PM	#2
QuestionC 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!
QuestionC is offline

04-27-2007, 09:04 PM	#3
Dave_Sinkula Just Lurking Join Date: Oct 2002 Posts: 4,990	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.*
Dave_Sinkula is offline

04-27-2007, 11:02 PM	#5
brewbuck Senior software engineer Join Date: Mar 2007 Location: Portland, OR Posts: 5,381	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.
brewbuck is offline

04-28-2007, 08:39 PM	#6
brewbuck Senior software engineer Join Date: Mar 2007 Location: Portland, OR Posts: 5,381	Anybody? Is anybody making any progress on this?
brewbuck is offline

04-28-2007, 09:16 PM	#7
MacGyver Deathray Engineer Join Date: Mar 2007 Posts: 3,211	About 20 people will all claim they knew it all along when you post the answer. __________________
MacGyver is offline

04-28-2007, 10:09 PM	#8
laserlight C++ Witch Join Date: Oct 2003 Location: Singapore Posts: 10,365	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. __________________ C + C++ Compiler: MinGW port of GCC Build + Version Control System: SCons + Bazaar Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
laserlight is online now

04-28-2007, 11:11 PM	#10
MacGyver Deathray Engineer Join Date: Mar 2007 Posts: 3,211	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. __________________
MacGyver is offline

04-28-2007, 11:18 PM	#12
MacGyver Deathray Engineer Join Date: Mar 2007 Posts: 3,211	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.
MacGyver is offline

04-29-2007, 12:12 AM	#14
MacGyver Deathray Engineer Join Date: Mar 2007 Posts: 3,211	With all the mistakes I've been making, I think I should finally get some sleep. Sorry to all. __________________
MacGyver is offline

04-29-2007, 12:20 AM	#15
Salem and the hat of vanishing Join Date: Aug 2001 Location: The edge of the known universe Posts: 21,214	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. Up to 8Mb PlusNet broadband from only £5.99 a month!
Salem is offline

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

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