Skip to content

A better 'FromContinuedFraction' procedure. Suggestion #102

@GooDgRaF

Description

@GooDgRaF

Hello, i think the FromContinuedFraction procedure could be improved.

From wiki: https://en.wikipedia.org/wiki/Simple_continued_fraction#Some_useful_theorems Theorem 2.

/// <summary>
/// Constructs rational number from sequence of continued fraction coefficients using recursive formulas for convergents.
/// <seealso cref="ToContinuedFraction" />
/// </summary>
/// <param name="continuedFraction">Input sequence of continued fraction coefficients</param>
/// <returns>Output rational number</returns>
    public static Rational FromContinuedFraction(IEnumerable<BigInteger> continuedFraction) {
        if (!continuedFraction.Any()) {
            return Zero;
        }

        BigInteger hPrev1 = 1; // h_{-1}
        BigInteger hPrev2 = 0; // h_{-2}
        BigInteger kPrev1 = 0; // k_{-1}
        BigInteger kPrev2 = 1; // k_{-2}

        foreach (BigInteger a in continuedFraction) {
            BigInteger hNext = a * hPrev1 + hPrev2; // h_i = a_i * h_{i-1} + h_{i-2}
            BigInteger kNext = a * kPrev1 + kPrev2; // k_i = a_i * k_{i-1} + k_{i-2}

            hPrev2 = hPrev1;
            hPrev1 = hNext;
            kPrev2 = kPrev1;
            kPrev1 = kNext;
        }

        return new Rational(hPrev1, kPrev1);
    }

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions