[Haskell-cafe] Fractional sqrt

Henning Thielemann lemming at henning-thielemann.de
Fri Jan 19 04:51:28 EST 2007


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.


More information about the Haskell-Cafe mailing list