axiom-math
[Top][All Lists]

[Axiom-math] continued fractions

 From: Martin Rubey Subject: [Axiom-math] continued fractions Date: 06 Dec 2007 09:48:26 +0100 User-agent: Gnus/5.09 (Gnus v5.9.0) Emacs/21.4

```Does anybody here know how the arithmetic for continued fractions in CONTFRAC
is supposed to work?

More precisely, it does work for CONTFRAC INT, but not for

CONTFRAC UnivariatePolynomial(x, Fraction Integer)

(in the following: CONTFRAC UP(x, FRAC INT)

but I'm not even sure, whether it *should* work.

Stephen: since you are mentioned as author, is there anything where I can read
about it?  Maybe the following hint helps to refresh memory (after all, it's
from 1991):

the main routine is (I believe)

genFromSequence: Stream Q -> %

which takes a stream of approximants and returns (I believe: ) a reduced
continued fraction:

eucWhole(a: Q): R == numer a quo denom a

eucWhole0(a: Q): R ==
isOrdered =>
n := numer a
d := denom a
q := n quo d
r := n - q*d
if r < 0 then q := q - 1
q
eucWhole a

genFromSequence apps ==
lo := first apps; apps := rst apps
hi := first apps; apps := rst apps
while eucWhole0 lo ^= eucWhole0 hi repeat
lo := first apps; apps := rst apps
hi := first apps; apps := rst apps
wh := eucWhole0 lo
[[wh, genReducedForm(wh::Q, apps, moebius(1,0,0,1))], canReduce?]

genReducedForm(wh0, apps, mt) ==
lo: Q := first apps - wh0; apps := rst apps
hi: Q := first apps - wh0; apps := rst apps
lo = hi and zero? eval(mt, lo) => empty()
mt  := recip mt
wlo := eucWhole eval(mt, lo)
whi := eucWhole eval(mt, hi)
while wlo ^= whi repeat
wlo := eucWhole eval(mt, first apps - wh0); apps := rst apps
whi := eucWhole eval(mt, first apps - wh0); apps := rst apps
concat([1,wlo], delay genReducedForm(wh0, apps, shift(mt, -wlo::Q)))

In the introduction it says

++   continued fractions.  This version is not restricted to simple,
++   finite fractions and uses the \spadtype{Stream} as a
++   representation.  The arithmetic functions assume that the
++   approximants alternate below/above the convergence point.
++   This is enforced by ensuring the partial numerators and partial
++   denominators are greater than 0 in the Euclidean domain view of \spad{R}

but that would make any reduced continued fraction in UP(x, FRAC INT) illegal:
the Euclidean size of any rational number, in particular of 1, is zero in that
domain.

Help would be greatly appreciated!

Martin

```