[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[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
        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

++ Description:  \spadtype{ContinuedFraction} implements general
++   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}
++   (i.e. \spad{sizeLess?(0, x)}). 

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

Help would be greatly appreciated!


reply via email to

[Prev in Thread] Current Thread [Next in Thread]