Working with the set of real numbers
Oscar Benjamin
oscar.j.benjamin at gmail.com
Tue Mar 4 23:08:44 CET 2014
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
More information about the Python-list
mailing list