浮点数转换为分数办法

[toxic-johann]

浮点数转换为分数

浮点数转换为分数是一个不算常见的需求。其中涉及的数学原理也不算十分复杂。这里简单讲述两种方法。

辗转相除法求公约数

首先，浮点数均为有理数。所以其实可以将问题简单转化为有理数转分数。

假设我们有浮点数 2.33，即可知道其能转化为 233/100。也就是我们需要求出 233 与 100 的最大公约数简化分数即可。

而求公约数比较通用有效的方法就是辗转相除法，计算公式gcd(a,b) = gcd(b,a mod b)。

JavaScript 算法如下：

function gcd(a, b) {
    let temp;
    if (a < b) {
        temp = a;
        a = b;
        b = temp;
    }
    while(b !== 0) {
        temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

那么我们这个转化方法就很简单了。

1. 首先将浮点数转为整数 a 与 10 的 n 次方 b 相除的结果
2. 求 a, b 的最大公约数 c
3. 即可化简得到最终的分数 (a / c) / (b / c)

示例如下：https://codepen.io/anon/pen/ajYyXd

使用连分数转换分数

求公约数的方法的好处就是能够保证精确度。但是有的时候太过精确并不是一件好事。

例如 0.33333333333，1/3 会是比 33333333333/100000000000 更符合人类的习惯。

这个时候我们就要使用连分数这个概念。详情可见 wiki。https://zh.wikipedia.org/zh-hans/%E8%BF%9E%E5%88%86%E6%95%B0

关键的原理如下：

• 一个数的连分数表示是有限的，当且仅当这个数是有理数。
• “简单”有理数的连分数表示是简短的。
• 任何有理数的连分数表示是唯一的，如果它没有尾随的1。（[a0; a1, ... a**n, 1] = [a0; a1, ... a**n + 1]）
• 无理数的连分数表示是唯一的。
• 连分数的项会循环，当且仅当它是一个二次无理数（即整数系数的二次方程的实数解）的连分数表示[1][2]。
• 数x的截断连分数表示很早产生x的在特定意义上“最佳可能”的有理数逼近（参阅下述定理5推论1）。

鉴于此，我们可以利用其进行浮点数转分数。

关键算法如下：

要计算实数r的连分数表示，写下r的整数部分（技术上floor）。从r减去这个整数部分。如果差为0则停止；否则找到这个差的倒数并重复。这个过程将终止，当且仅当r是有理数。

我们可以得出如下 JavaScript 代码：

/**
* 通过连分数原理计算可选的分数选项
* @param {number} number 浮点数
* @param {object} option 选项
* @param {number} option.maxDenominatorLength 分母最大位数
* @returns {Object} 将返回最贴近的分数
*/
function getApproximateFractionsByContinuedFraction(num, { maxDenominatorLength = 7 }) {
    const numerators = [0, 1];
    const denominators = [1, 0];
    const decimalPart = num - parseInt(num);
    const maxNumerator = parseInt(decimalPart.toString().replace('0.', ''));
    let currentDigits = num;
    let currentResult;
    let previousResult = NaN;
    const ret  = {numerators, denominators};
    // 为避免较长时间的运算，我们设定最多一千次的限制
    for (let i = 2; i < 1000; i++)  {
        const integerPart = Math.floor(currentDigits);
        const currentNumerator = integerPart * numerators[i-1] + numerators[i-2];
        // 用于排除整数
        if (Math.abs(numerators[i]) > maxNumerator) break;
        const currentDenominator = integerPart * denominators[i - 1] + denominators[i - 2];
        if (maxDenominatorLength && currentDenominator.toString().length > maxDenominatorLength) break;
        numerators[i] = currentNumerator;
        denominators[i] = currentDenominator;

        currentResult = numerators[i] / denominators[i];
        if (currentResult === previousResult || currentResult === num) break;

        previousResult = currentResult;
        // 找到这个差的倒数并重复。
        currentDigits = 1 / (currentDigits - integerPart);
    }

    const lastIndex = numerators.length - 1;
    // 证明是整数
    if (lastIndex < 2) {
        return {
            numerator: num,
            denominator: 1,
        }
    }
    return {
        numerator: numerators[lastIndex],
        denominator: denominators[lastIndex],
    }
}

可见 demo 如下 http://www.mindspring.com/~alanh/fracs.html