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. So what I was asking was: By representing values as continued fractions rather than as decimal digits, are you able to perform a straight-forward transformation that produces the square root, in constant time (which means linear in the length)? And I guess the answer's no. CF representation doesn't have the advantage I was wondering about. ChrisA -- https://mail.python.org/mailman/listinfo/python-list
