javascript - 如何使此代码适用于更大的数字？

Question

此代码本应简化分数并将小数转换为分数，但当我输入具有较大被除数(超过 7 或 8 位数字的数字)的分数时，它会滞后很多。

http://jsfiddle.net/SuperBoi45/vQjgx/

var fraction = {};

fraction.simplify = function( frac ) {
    if ( frac.indexOf('/') < 0 ) return frac;
    var numbers = frac.split('/'),
        factor = null,
        parsed = null;

    return (function run( nums ) {
        factor = fraction.factor( nums[0], nums[1] );

        if ( factor === 1 ) {
            parsed = [ Math.abs(nums[0]), Math.abs(nums[1]) ];

            if ( nums[1] === 1 ) return nums[0];
            else if ( nums[1] === -1 ) return -nums[0];
            else if ( nums[0] < 0 && nums[1] < 1 ) return parsed[0] + '/' + parsed[1];
            else if ( nums[0] < 0 || nums[1] < 0 ) return '-' + parsed[0] + '/' + parsed[1];
            else return nums[0] + '/' + nums[1];
        }

        return run( [ nums[0] / factor, nums[1] / factor ] );
    })( numbers );
};
fraction.convert = function( decimal ) {
    var j = decimal.length - 1,
        b = "1";

    if ( decimal.indexOf(".") >= 0 && decimal.length > 1 ) {

        while ( decimal.charAt( j ) != "." ) {
            b += "0";
            j--;
        }

        decimal *= b;
        decimal += "/" + b;

    }

    return decimal;

};
fraction.factor = (function() {

    var greater = function( a, b ) {
        return a > b ? a : b;
    };

    return function( x, y ) {
        x = Math.abs( x );
        y = Math.abs( y );

        var a = greater( x, y ),
            i = a,
            b = ( i === x ) ? y : x;

        for ( ; i >= 1; i-- ) {
            if ( a % i === 0 && b % i === 0 ) return i;
        }

        return 1;
    };

})();​

我试图让它像 Wolfram Alpha 一样工作，因为您可以输入具有大除数的分数，并且在向您显示其快速渲染结果时它不会卡住一位。

http://wolframalpha.com/

任何人都可以修复此代码以处理更大的数字吗？我认为您必须使用与我不同的算法。另一方面，有没有人知道 WA 的算法或者可以指导我到一个我可以找到的网站？

Answer 1

将 fraction.factor() 替换为:

function gcd(a, b) {
    if (b > a) return gcd(b, a);
    if (b === 0) return a;
    return gcd(b, a % b);
};

这就是欧几里得算法，它可以作为数论的一个很好的介绍。它会比您的迭代方法运行得更快方式。