Working with the set of real numbers

[Chris Angelico]

On Wed, Mar 5, 2014 at 6:49 AM, Marko Rauhamaa <marko at pacujo.net> wrote:
> Chris Angelico <rosuav at 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