Continued Fraction

Here are some notes from my program XMCalc - Extra Precision Floating-Point Matrix Calculator http://www.oocities.org/hjsmithh/download.html#XMCalc :

ContFrac(X) = Continued fraction expansion of x:

Computes the terms of the continued fraction that represents the real number x. This is computed as an n element row vector of integers {a[0], a[1], a[2], ..., a[n-1]}, where x = a[0] + 1/(a[1] + 1/(a[2] + 1/(a[3] + ... + 1/a[n-1]))).

ContFrac(X, Y) = Continued fraction expansion of x with y terms:

This is the same as ContFrac(X) except at most y terms/elements are computed.

ContFrac(Pi, 21) = {3, 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, 2, 1, 1, 2, 2, 2, 3}

ContFrac(e, 21) = {2, 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, 1, 1, 10, 1, 1, 12, 1, 1, 14}

ContFrac(Sqrt(2), 21) = {1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2}

ContFrac(Phi, 21) = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2}

ContFracV(X) = Value of continued fraction x:

This is the inverse of the ContFrac() function. The row (or column) vector x is interpreted as a continued fraction and converted to a real value.

a ContFrac(x, n)
{ // a = x as continuous fraction row vector {a[0], a[1], a[2],..., a[n-1]}
    n = Floor(n);
    if (n < 1)
        n = 32767;
    a.rows = 1;
    a.columns = n;
    temp = Floor(x);
    a[0] = temp;
    for (c = 1; c < n; c++)
    {
        if (c == 1)
        {
            aM1 = 1;
            bM1 = 0;
            aK = temp;
            bK = 1;
            x1 = 0;
        }
        x -= temp;
        if (x == 0)
            break;
        x = 1 / x
        temp = Floor(x);
        y[c] = temp;
        aM2 = aM1;
        bM2 = bM1;
        aM1 = aK;
        bM1 = bK;
        aK = temp * aM1 + aM2;
        bK = temp * bM1 + bM2;
        x2 = aK / bK;           // x2 is the reconstructed x from a
        if (x1 == x2)
            break;              // quit when x2 stop changing
        x1 = x2;
    }
    if (c < n)
        a.columns = c;
    n = a.columns;
    if (n > 1 && a[n - 1] == 1) // a never ends with 1 if n > 1
    {
        a[n - 2] += 1;
        a.columns--;
    }
}
	
x ContFracV(a)
// x = Value of continuous fraction a
{
    n = a.columns;
    aM1 = 1;
    bM1 = 0;
    aK = a[0];
    bK = 1;
    for (int i = 1; i < n; i++)
    {
        aM2 = aM1;
        bM2 = bM1;
        aM1 = aK;
        bM1 = bK;
        aK = a[i] * aM1 + aM2;
        bK = a[i] * bM1 + bM2;
    }
    x = aK / bK;
}

And: Wolfram Mathematica -- ContinuedFraction

Return to Number Theory, Algorithms, and Real Functions
Return to Harry's Home Page

---

This page accessed times since April 24, 2005.
Page created by: hjsmithh@sbcglobal.net
Changes last made on Monday, 05-May-08 15:52:30 PDT

---