Compute a square root (with restrictions)

This is a discussion on Compute a square root (with restrictions) within the Contests Board forums, part of the Community Boards category; Some of you may know the solution to this problem already. If you do, please wait to post your answer ...

  1. #1
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,274

    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 06: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,006
    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
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,274
    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
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,274
    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
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,274

    Anybody?

    Is anybody making any progress on this?

  7. #7
    Deathray Engineer MacGyver's Avatar
    Join Date
    Mar 2007
    Posts
    3,211
    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
    22,274
    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
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  9. #9
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,274
    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,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.

  11. #11
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,274
    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,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-29-2007 at 12:20 AM.

  13. #13
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,274
    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,211
    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
    32,834
    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.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

Page 1 of 4 1234 LastLast
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, 01:53 PM
  2. Forced moves trouble!!
    By Zishaan in forum Game Programming
    Replies: 0
    Last Post: 03-27-2007, 07: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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21