Path: csiph.com!newsfeed.hal-mli.net!feeder3.hal-mli.net!newsfeed.hal-mli.net!feeder1.hal-mli.net!newsfeed.xs4all.nl!newsfeed4a.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
MIME-Version: 1.0
In-Reply-To: <CAPTjJmp-iQLL_VypbMqzgHmQHiNQU-hvAgzR-zh32h05av4p4A@mail.gmail.com>
References: <8e4c1ab1-e65d-483f-ad9d-6933ae2052c3@googlegroups.com> <CAPTjJmo4qD2B7isr8yAK2t+22KqwaoFrT5b5U66mYe+VgwDkWA@mail.gmail.com> <85r478bv99.fsf_-_@benfinney.id.au> <mailman.6735.1392194885.18130.python-list@python.org> <53153e66$0$24931$e4fe514c@dreader36.news.xs4all.nl> <mailman.7687.1393902132.18130.python-list@python.org> <59dd57ad-39b0-4c71-a58e-b4ae6517b385@googlegroups.com> <mailman.7689.1393904790.18130.python-list@python.org> <53156a42$0$2923$c3e8da3$76491128@news.astraweb.com> <CAPTjJmp-iQLL_VypbMqzgHmQHiNQU-hvAgzR-zh32h05av4p4A@mail.gmail.com>
From: Ian Kelly <ian.g.kelly@gmail.com>
Date: Tue, 4 Mar 2014 04:19:59 -0700
Subject: Re: Working with the set of real numbers (was: Finding size of Variable)
To: Python <python-list@python.org>
Content-Type: text/plain; charset=ISO-8859-1
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.7702.1393932047.18130.python-list@python.org>
Lines: 53
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:67662

On Mon, Mar 3, 2014 at 11:35 PM, Chris Angelico <rosuav@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.