19 Jan
2007
19 Jan
'07
4:51 a.m.
On Thu, 18 Jan 2007, Novák Zoltán wrote:
I have to admit that I do not fully understand the Haskell numerical tower... Now I'm using the Newton method:
mysqrt :: (Fractional a) => a -> a mysqrt x = (iterate (\y -> (x / y + y) / 2.0 ) 1.0) !!2000
But I want a faster solution. (Not by replacing 2000 with 100... :)
Newton method for sqrt is very fast. It converges quadratically, that is in each iteration the number of correct digits doubles. The problem is to find a good starting approximation. What about comparing powers of two and their squares against 'x' and use an appropriate power of two as starting value? Sure, this will require Real instance and won't work on complex numbers.