In article <mailman.7702.1393932047.18130.python-l...@python.org>, Ian Kelly <ian.g.ke...@gmail.com> wrote: >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.
That is highly non-trivial indeed. See the gosper.txt reference I gave in another post. Groetjes Albert -- Albert van der Horst, UTRECHT,THE NETHERLANDS Economic growth -- being exponential -- ultimately falters. albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst -- https://mail.python.org/mailman/listinfo/python-list