[Haskell-cafe] Fractional sqrt

[Henning Thielemann]

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.