Working with the set of real numbers

[Oscar Benjamin]

On 4 March 2014 21:05, Marko Rauhamaa <marko at pacujo.net> wrote:
> Oscar Benjamin <oscar.j.benjamin at 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