Implement a Function to Return a Ratio

Solution: Continued Fractions

function decimalToFraction(decimal, tolerance = 0.01) {
    if (Math.abs(decimal - Math.round(decimal)) < tolerance) {
        return { numerator: Math.round(decimal), denominator: 1 };
    }

    const sign = decimal < 0 ? -1 : 1;
    decimal = Math.abs(decimal);

    // Use continued fractions
    let num0 = 0, num1 = 1;
    let den0 = 1, den1 = 0;
    let value = decimal;

    const maxIterations = 20;

    for (let i = 0; i < maxIterations; i++) {
        const integer = Math.floor(value);

        // Update numerator and denominator
        const numNew = integer * num1 + num0;
        const denNew = integer * den1 + den0;

        // Check if approximation is good enough
        const approximation = numNew / denNew;
        if (Math.abs(approximation - decimal) < tolerance) {
            return {
                numerator: sign * numNew,
                denominator: denNew
            };
        }

        // Prepare for next iteration
        num0 = num1;
        num1 = numNew;
        den0 = den1;
        den1 = denNew;

        // Get fractional part and invert
        const fractional = value - integer;
        if (fractional < 1e-10) break;  // Close enough to integer

        value = 1 / fractional;
    }

    return {
        numerator: sign * num1,
        denominator: den1
    };
}

// Tests
console.log(decimalToFraction(0.25, 0.01));      // 1/4
console.log(decimalToFraction(0.24, 0.01));      // 1/4
console.log(decimalToFraction(0.333, 0.01));     // 1/3
console.log(decimalToFraction(0.666, 0.01));     // 2/3
console.log(decimalToFraction(3.14159, 0.001)); // 22/7 or 355/113
console.log(decimalToFraction(-0.5, 0.01));     // -1/2

Alternative: Brute Force (Simpler)

function decimalToFractionBruteForce(decimal, tolerance = 0.01, maxDenom = 1000) {
    const sign = decimal < 0 ? -1 : 1;
    decimal = Math.abs(decimal);

    let bestNum = 0, bestDen = 1;
    let bestError = Math.abs(decimal);

    for (let den = 1; den <= maxDenom; den++) {
        const num = Math.round(decimal * den);
        const approximation = num / den;
        const error = Math.abs(approximation - decimal);

        if (error < bestError) {
            bestError = error;
            bestNum = num;
            bestDen = den;

            if (error < tolerance) {
                break;  // Good enough
            }
        }
    }

    return {
        numerator: sign * bestNum,
        denominator: bestDen
    };
}

console.log(decimalToFractionBruteForce(0.25, 0.01));  // 1/4

With Simplification (GCD)

function gcd(a, b) {
    a = Math.abs(a);
    b = Math.abs(b);

    while (b !== 0) {
        [a, b] = [b, a % b];
    }

    return a;
}

function simplifyFraction(num, den) {
    const divisor = gcd(num, den);
    return {
        numerator: num / divisor,
        denominator: den / divisor
    };
}

function decimalToFractionSimplified(decimal, tolerance = 0.01) {
    const result = decimalToFraction(decimal, tolerance);
    return simplifyFraction(result.numerator, result.denominator);
}

console.log(decimalToFractionSimplified(0.5, 0.01));    // 1/2
console.log(decimalToFractionSimplified(0.66, 0.01));   // 2/3
console.log(decimalToFractionSimplified(0.125, 0.01));  // 1/8

Step-by-Step Example: 0.75

decimal = 0.75, tolerance = 0.01

Iteration 0:
  integer = floor(0.75) = 0
  numNew = 0 * 1 + 0 = 0
  denNew = 0 * 0 + 1 = 1
  approx = 0/1 = 0
  error = 0.75 > 0.01, continue
  fractional = 0.75
  value = 1/0.75 = 1.333...

Iteration 1:
  integer = floor(1.333) = 1
  numNew = 1 * 1 + 0 = 1
  denNew = 1 * 0 + 1 = 1
  approx = 1/1 = 1
  error = 0.25 > 0.01, continue
  fractional = 0.333
  value = 1/0.333 = 3

Iteration 2:
  integer = floor(3) = 3
  numNew = 3 * 1 + 1 = 4
  denNew = 3 * 1 + 0 = 3
  error (actually) = 1 * 1 / 3 = 1/3 (need recalc)

Actually simpler: 3/4 = 0.75 exactly!
Result: 3/4

Handling Edge Cases

function decimalToFractionRobust(decimal, tolerance = 0.01) {
    // Handle special cases
    if (!isFinite(decimal)) {
        throw new Error('Invalid decimal');
    }

    if (decimal === 0) {
        return { numerator: 0, denominator: 1 };
    }

    const result = decimalToFraction(decimal, tolerance);

    // Simplify
    const divisor = gcd(result.numerator, result.denominator);

    return {
        numerator: result.numerator / divisor,
        denominator: result.denominator / divisor
    };
}

Complexity

Continued fractions: O(log n) iterations where n is denominator
Brute force: O(n) where n is max denominator
Space: O(1) for both

Why Continued Fractions Are Optimal

Each convergent is the best rational approximation with that denominator size. No other fraction with smaller denominator can be closer.

Example: For π, 22/7 is the best approximation with denominator ≤ 7.

Common Mistakes

• Not simplifying: Returning 2/8 instead of 1/4
• Tolerance misunderstanding: Checking absolute vs relative error
• Infinite loops: Not handling when fractional part is tiny
• Overflow: Denominators growing too large

Follow-Up Questions

Q: How to find all fractions within tolerance?
A: Stern-Brocot tree or Farey sequence

Q: What about irrational numbers?
A: Continued fractions never terminate, keep best approximation

Q: How to format as mixed number?
A: Extract integer part, keep fractional part as fraction

Related Problems

• int atoi( char* pStr ) - Number conversion
• Compute X^Y For Floats and Negative Values - Floating point operations
• Prime number problem - Mathematical algorithms