On Mon, Mar 3, 2014 at 11:35 PM, Chris Angelico <ros...@gmail.com> wrote:
> In constant space, that will produce the sum of two infinite sequences
> of digits. (And it's constant time, too, except when it gets a stream
> of nines. Adding three thirds together will produce an infinite loop
> as it waits to see if there'll be anything that triggers an infinite
> cascade of carries.) Now, if there's a way to do that for square
> rooting a number, then the CF notation has a distinct benefit over the
> decimal expansion used here. 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.
The code for that looks like this:
def cf_sqrt(n):
"""Yield the terms of the square root of n as a continued fraction."""
m = 0
d = 1
a = a0 = floor_sqrt(n)
while True:
yield a
next_m = d * a - m
next_d = (n - next_m * next_m) // d
if next_d == 0:
break
next_a = (a0 + next_m) // next_d
m, d, a = next_m, next_d, next_a
def floor_sqrt(n):
"""Return the integer part of the square root of n."""
n = int(n)
if n == 0: return 0
lower = 2 ** int(math.log(n, 2) // 2)
upper = lower * 2
while upper - lower > 1:
mid = (upper + lower) // 2
if n < mid * mid:
upper = mid
else:
lower = mid
return lower
The floor_sqrt function is merely doing a simple binary search and
could probably be optimized, but then it's only called once during
initialization anyway. The meat of the loop, as you can see, is just
a constant amount of integer arithmetic. If it were desired to halt
once the continued fraction starts to repeat, that would just be a
matter of checking whether the triple (m, d, a) has been seen already.
Going back to your example of adding generated digits though, I don't
know how to add two continued fractions together without evaluating
them.
--
https://mail.python.org/mailman/listinfo/python-list
