RatioToFraction.cs

public class RatioToFraction
{
    /// <summary>
    /// Converts a ratio to a fraction with the specified accuracy.
    ///  Accuracy = .0001 will make 1/1000 return correctly, but Accuracy = .001 return as 1/9991
    /// </summary>
    /// <param name="ratio">The ratio.</param>
    /// <param name="accuracy">Accuracy is the maximum relative error; convert to absolute maxError</param>
    /// <returns>Tuple in the form of (numerator, denominator)</returns>
    public static (decimal, decimal) NormalizeFraction(decimal ratio, decimal accuracy)
    {
        var sign = Math.Sign(ratio);

        if (sign == -1)
        {
            ratio = Math.Abs(ratio);
        }

        var maxError = sign == 0 ? accuracy : ratio * accuracy;

        var n = (int) Math.Floor(ratio);
        ratio -= n;

        if (ratio < maxError)
        {
            return (sign * n, 1);
        }

        if (1 - maxError < ratio)
        {
            return (sign * (n + 1), 1);
        }

        // The lower fraction is 0/1
        var lowerN = 0;
        var lowerD = 1;

        // The upper fraction is 1/1
        var upperN = 1;
        var upperD = 1;

        while (true)
        {
            // The middle fraction is (lower_n + upper_n) / (lower_d + upper_d)
            var middleN = lowerN + upperN;
            var middleD = lowerD + upperD;
            
            if (middleD * (ratio + maxError) < middleN)
            {
                // real + error < middle : middle is our new upper
                // upperN = middleN;
                // upperD = middleD;
                Seek(ref upperN, 
                    ref upperD, 
                    lowerN, 
                    lowerD, 
                    (un, ud) => (lowerD + ud) * (ratio + maxError) < lowerN + un);
            }
            else if (middleN < (ratio - maxError) * middleD)
            {
                // middle < real - error : middle is our new lower
                // lowerN = middleN;
                // lowerD = middleD;
                Seek(ref lowerN, 
                    ref lowerD, 
                    upperN, 
                    upperD, 
                    (ln, ld) => ln + upperN < (ratio - maxError) * (ld + upperD));
            }
            else
            {
                // Middle is our best fraction
                return ((n * middleD + middleN) * sign, middleD);
            }
        }
    }

    /// <summary>
    /// Binary seek for the value where f() becomes false.
    /// </summary>
    private static void Seek(ref int a, ref int b, int ainc, int binc, Func<int, int, bool> f)
    {
        a += ainc;
        b += binc;

        if (!f(a, b)) 
        {
            return;
        }

        var weight = 1;

        do
        {
            weight *= 2;
            a += ainc * weight;
            b += binc * weight;
        }
        while (f(a, b));

        do
        {
            weight /= 2;

            var adec = ainc * weight;
            var bdec = binc * weight;

            if (!f(a - adec, b - bdec))
            {
                a -= adec;
                b -= bdec;
            }
        }
        while (weight > 1);
    }
}