Working with the set of real numbers

[Marko Rauhamaa]

Oscar Benjamin <oscar.j.benjamin at gmail.com>:

> To me the obvious method is Newton iteration which takes O(sqrt(N))
> iterations to obtain N digits of precision. This brings the above
> complexity below quadratic:
>
> #!/usr/bin/env python
>
> from decimal import Decimal as D, localcontext
>
> def sqrt(y, prec=1000):
>     '''Solve x**2 = y'''
>     assert y > 0
>     eps = D(10) ** -(prec + 5)
>     x = D(y)
>     with localcontext() as ctx:
>         ctx.prec = prec + 10
>         while x ** 2 - y > x * eps:
>             x = (x + y/x) / 2
>     return x
>
> print(sqrt(2))

At a quick glance, I believe x ** 2 is O(N²) and so the total complexity
should be O(N ** 2.5).


Marko