On 4 March 2014 19:58, Chris Angelico <ros...@gmail.com> wrote: > On Wed, Mar 5, 2014 at 6:49 AM, Marko Rauhamaa <ma...@pacujo.net> wrote: >> Chris Angelico <ros...@gmail.com>: >> >>> As far as I know, there's no simple way, in constant space and/or >>> time, to progressively yield more digits of a number's square root, >>> working in decimal. >> >> I don't know why the constant space/time requirement is crucial. Anyway, >> producing more digits simple: <URL: http://nrich.maths.org/5955>. >> >> I believe producing the nth digit is O(n) in time and space. > > The reason for striving for constant space/time is because the obvious > method (cut-and-try) is already O(n) for the nth digit, which means > it's quadratic on the number of digits desired. That gets pretty > nasty.
I don't quite follow your reasoning here. By "cut-and-try" do you mean bisection? If so it gives the first N decimal digits in N*log2(10) iterations. However each iteration requires a multiply and when the number of digits N becomes large the multiplication is worse than linear. So the result is something like N**2 log(N)log(log(N)), 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)) Some modification would be required to handle a situation where it ends in a run of nines or zeros if you really care about the exact digits rather than having a bounded error. Oscar -- https://mail.python.org/mailman/listinfo/python-list