Working with the set of real numbers
Marko Rauhamaa
marko at pacujo.net
Tue Mar 4 22:05:06 CET 2014
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
More information about the Python-list
mailing list