Oscar Benjamin <oscar.j.benja...@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 -- https://mail.python.org/mailman/listinfo/python-list
