On Tue, Mar 4, 2014 at 4:53 PM, Steven D'Aprano <st...@pearwood.info> wrote:
> On Tue, 04 Mar 2014 14:46:25 +1100, Chris Angelico wrote:
>
>> That's neat, didn't know that. Is there an efficient way to figure out,
>> for any integer N, what its sqrt's CF sequence is? And what about the
>> square roots of non-integers - can you represent √π that way? I suspect,
>> though I can't prove, that there will be numbers that can't be
>> represented even with an infinite series - or at least numbers whose
>> series can't be easily calculated.
>
> Every irrational number can be written as a
> continued fraction with an infinite number of terms, just as every
> irrational number can be written as a decimal number with an infinite
> number of digits.
It's easy enough to have that kind of expansion, I'm wondering if it's
possible to identify it directly. To render the decimal expansion of a
square root by the cut-and-try method, you effectively keep dividing
until you find that you're "close enough"; that means you (a) have to
keep the entire number around for each step, and (b) need to do a few
steps to find that the digits aren't changing. But if you can take a
CF (finite or infinite) and do an O(n) transformation on it to produce
that number's square root, then you have an effective means of
representing square roots. Suppose I make a generator function that
represents a fraction:
def one_third():
while True:
yield 3
def one_seventh():
while True:
yield 1; yield 4; yield 2; yield 8; yield 5; yield 7
I could then make a generator that returns the sum of those two:
def add_without_carry(x, y):
whiile True:
yield next(x)+next(y)
Okay, that's broken for nearly any case, but with a bit more sophistication:
def add(x, y):
prev=None
nines=0
while True:
xx,yy=next(x),next(y)
tot=xx+yy
if tot==9:
nines+=1
continue
if tot>9:
if prev is None: raise OverflowError("exceeds 1.0")
yield prev+1
tot-=10
for _ in range(nines): yield 0
nines=0
else:
if prev is not None: yield prev
prev=tot
def show(n):
return ''.join(str(_) for _ in itertools.islice(n,20))
>>> show(add(one_third(),one_seventh()))
'47619047619047619047'
>>> show(add(add(add(one_seventh(),one_seventh()),add(one_seventh(),one_seventh())),add(one_seventh(),one_seventh())))
'85714285714285714285'
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.
ChrisA
--
https://mail.python.org/mailman/listinfo/python-list
