Working with the set of real numbers (was: Finding size of Variable)
Albert van der Horst
albert at spenarnc.xs4all.nl
Wed Mar 5 03:27:51 CET 2014
In article <mailman.7702.1393932047.18130.python-list at python.org>,
Ian Kelly <ian.g.kelly at gmail.com> wrote:
>On Mon, Mar 3, 2014 at 11:35 PM, Chris Angelico <rosuav at 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 at spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst
More information about the Python-list
mailing list