On 4 March 2014 21:05, Marko Rauhamaa <ma...@pacujo.net> wrote: > 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).
x**2 is just a multiplication which can be done in better than O(N**2): http://en.wikipedia.org/wiki/Multiplication_algorithm#Fast_multiplication_algorithms_for_large_inputs Oscar -- https://mail.python.org/mailman/listinfo/python-list