Working with the set of real numbers

[Oscar Benjamin]

On 4 March 2014 19:58, Chris Angelico <rosuav at gmail.com> wrote:
> 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.

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