On 4 March 2014 19:58, Chris Angelico <[email protected]> wrote:
> On Wed, Mar 5, 2014 at 6:49 AM, Marko Rauhamaa <[email protected]> wrote:
>> Chris Angelico <[email protected]>:
>>
>>> 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
--
https://mail.python.org/mailman/listinfo/python-list
