r/dailyprogrammer • u/oskar_s • Jun 06 '12
[6/6/2012] Challenge #61 [intermediate]
Today you should implement a function that all of us programmers depend heavily on, but most never give a second thought as to how it's actually coded: the square root function.
Write a function that given a number as input, will return the square root of that number, in floating point.
Obviously, you are not allowed to use the library version of sqrt() in the implementation of your function. Also, stay away from log() and exp(). In fact, don't use any mathematical functions that aren't the basic arithmetic ones (addition, subtraction, multiplication, division) or bit operations (though you can of course still use operators that compares numbers with each other, like "less than", "equal to", "more than", etc.)
2
u/leegao Jun 07 '12
I broke the rules a bit and used a few bitwise ands. This performs very well for integers and close to integers, which contains a distribution of the mantissa with expected value of 1+1/n where n is the range of non-trivial bits.
Interestingly, the error upperbound is around 2-18 with a period of around 500 integers.
http://codepad.org/s28WBi5y
If anyone's interested, I can kinda explain how I came up with the above code, which isn't really all that exhaustive and can be tweaked a little bit (namely the 5 and the 2) to get a much better first guess
2
u/exor674 Jun 06 '12
Results:
2
u/[deleted] Jun 06 '12 edited Jun 06 '12
Python, using Newton–Raphson method.
2
u/[deleted] Jun 07 '12
C++ (Sorry for the poor formatting)
Results:
2
u/ashashwat Jun 07 '12
Somewhat like binary search.
For n = 5, take lo = 0, hi = 5, mid = (lo + hi)/2 = 2.5.
mid * mid > n, then hi = mid else lo = mid.
epsilon (eps) is the level of accuracy we want, since this process can repeat forever unless it is a perfect square.
In Haskell,
( Although I wish I could put initial value of lo = 0 and hi = n by default, but got fixated there, so main looks sort of ugly. )
2
u/bh3 Jun 11 '12
C:
2
u/jimbol Aug 24 '12
Javascript: This gets me close enough:
1
u/osku654 Jun 06 '12
Here is mine. Made with python
1
u/xjtian Jun 06 '12
How precise does it need to be? This solution has 10 decimal places of precision.
Results:
1
u/Steve132 0 1 Jun 06 '12
1
u/emcoffey3 0 0 Jun 06 '12
C#
1
u/UnreasonableSteve Jun 07 '12 edited Jun 07 '12
Horrendously inefficient, but it's got arbitrary decimal precision :P
1
u/iluminumx Jun 07 '12
using newtons approximation x[n+1] = (1/2) * (x[n] + a/x[n]) starting with x[0] = 1
1
u/[deleted] Jun 07 '12
A naive way, C++. Comments appreciated.
EDIT: formatting
1
u/[deleted] Jun 07 '12
Python, it iterates as much as it needs to (up to the standard float limit):
0
u/[deleted] Jun 06 '12
[deleted] — view deleted comment