Ratio.prototype.simplify() is too slow!!!

[LarryBattle]

Please optimize the function Ratio.prototype.simplify(). Calls to .simplify() could slow down Ratio.js by OVER 9000%!!!!!.

Around ~75,000% to be more exact. (68,633/90.88 * 100%)

Benchmark from jsperf.com

http://jsperf.com/convert-a-rational-number-to-a-babylonian-fractions/12

Name: Ratio.js

for (var i in test_cases) {
    ratio_1 = Ratio(test_cases[i][0], test_cases[i][1]);
    ratio_2 = ratio_2.subtract(ratio_1).simplify().multiply(ratio_1).simplify().add(ratio_1).simplify().divide(ratio_1).simplify();
}

90.88 ±0.75%100% slower

---

Name: Ratio.js - only simplify once

for (var i in test_cases) {
    ratio_1 = Ratio(test_cases[i][0], test_cases[i][1]);
    ratio_2 = ratio_2.subtract(ratio_1).multiply(ratio_1).add(ratio_1).divide(ratio_1).simplify();
}

399 ±0.91%100% slower

---

Name: Ratio.js - no call to simplify

for (var i in test_cases) {
    ratio_1 = Ratio(test_cases[i][0], test_cases[i][1]);
    ratio_2 = ratio_2.subtract(ratio_1).multiply(ratio_1).add(ratio_1).divide(ratio_1);
}

68,633 ±3.44%81% slower

---

[acerix]

Cool project, dude!

I wrote this jsperf test, but it's more experimental than scientific, so take the results with a grain of salt. For example, I noticed the test case numbers were way too big, so the actually results are bogus if you check them (except for bigrat, since it doesn't lose precision with huge integers). I used smaller test cases in the most recent revision.

I suggest putting the last 2 lines of simplify() into a separate function, since the components should be divided by the GCD after every operation (ie. normalized), but parsing is unnecessary in that case (they are already parsed). That should be a big speedup

Also, GCD() is inevitably expensive, so it’s best to skip that when possible (eg. if either of n/d is 0, or n==d). I have a few such optimizations here: https://github.com/acerix/rational.js/blob/master/src/rat.js#L404

Cheers!

[LarryBattle]

Thanks. I'll check this out later.

Ratio.gcd = function (a, b) {
    if(a == b){
        return a;
    }
    if(a/b === 0){
        return 0;
    }
    var c;
    b = (+b && +a) ? +b : 0;
    a = b ? a : 1;
    while (b) {
        c = a % b;
        a = b;
        b = c;
    }
    return Math.abs(a);
};

[LarryBattle]

The problem seems to be with Ratio.prototype.getRepeatProps(). It might have to be rewritten to improving the speed.

I need to check out the response from these stackoverflow quesitons.

Daniel Fischer's response http://stackoverflow.com/questions/8946310/how-to-know-the-repeating-decimal-in-a-fraction

Daniel Brückner's response http://stackoverflow.com/questions/1315595/algorithm-for-detecting-repeating-decimals

[acerix]

getRepeatProps() is an interesting function, but I think it should be removed from simplify(). (I'm not sure what it's doing there)

Since the nominator/denominator are already integers, the only simplification is to divide both by their GCD. In case the denominator is negative, you can multiply both by -1.

[LarryBattle]

The goal of .getRepeatProps() is to return the elements needed to convert a repeating decimal to a fraction. Here's a simple guide. http://www.basic-mathematics.com/converting-repeating-decimals-to-fractions.html

You might be right. Maybe simplifying repeating decimals should be a different function call.

Here are a few problems with Ratio.simplify() and Ratio.protoype.simplify():

• Needs to avoid calling Ratio.parse() from Ratio.protoype.simplify()
• The conversion from repeating decimals to a fraction should be a separate function

Something like this might work.

var _simplify = function(obj){
    var top = obj._n,
    bottom = top || !obj._d ? obj._d : 1,
    arr = (top % bottom) ? Ratio.getRepeatProps(top / bottom) : [],
    factor;
    if (arr.length) {
        top = Number(arr.join('')) - Number(arr[0] + String(arr[1]));
        bottom = Math.pow(10, arr[1].length) * (Math.pow(10, arr[2].length) - 1);
    }
    factor = Ratio.gcd(top, bottom);
    return [top / factor, bottom / factor];
};
Ratio.simplify = function (obj, obj2) {
    return _simplify(
        Ratio.parse(obj, obj2)
    );
};
...
simplify : function () {
    var arr = _simplify(this);
    return this.clone(arr[0], arr[1]);
},
...

[LarryBattle]

Here's a particle rewrite of Ratio.getRepeatProps().

splitPattern() eliminates most of the RegExp and Array involvement from .getRepeatProps(). The key is to refactor Ratio.regex.repeatingDecimals and Ratio.regex.repeatingNumbers into this RegExp /(\d+?)(?:\1+?)\d?$/.

Ratio.regex = {
    ...
    repeatingDecimals : /[^\.]+\.\d*(\d{2,})+(?:\1)$/,
    repeatingNumbers : /^(\d+)(?:\1)$/
    ...
}

splitPattern() only works with whole numbers right now but can be easily adapted for decimals.

var splitPattern = function (val) {
    if (!val || typeof +val !== "number") {
        return [];
    }
    val = String(val);
    var re = /(\d+?)(?:\1+?)\d?$/;
    var match = val.match(re);
    if (!match) {
        return [];
    }
    var r = match[1];
    var x = val.replace(new RegExp("(" + r + ")+$"), "");
    if (!x || !x.length || x.length < Math.round(val.length / 2)) {
        return [x, r];
    } else {
        return [];
    }

};

// ### Test cases
if (!test || !deepEqual || !equal) {
    var test = function (str, fn) {
        console.log("\n%s", str);
        fn();
    };
    var deepEqual = function (a, b, str) {
        equal(a, b, str);
    };
    var equal = function (a, b, str) {
        a = String(a);
        b = String(b);
        str = str || "";
        if (a == b) {
            console.log("Pass:" + str);
        } else {
            console.log("Fail: %s want:`%s` !== got:`%s`", str, a, b);
        }
    };
}

var makePattern = function (prefix, pattern, count, suffix) {
    var str = "";
    while (count--)
        str += pattern;
    return prefix + str + (suffix || "");
};
var makeTestWithValidInput = function (prefix, pattern, count, suffix, fn) {
    var str = makePattern(prefix, pattern, count, suffix);
    equal([prefix, pattern], fn(str), "Testing with `" + str + "`");
};
var makeTestWithInvalidInput = function (str, fn) {
    equal([], fn(str), "Testing with `" + str + "`");
};

test("Testing fn() with invalid values", function () {
    var fn = splitPattern;
    makeTestWithInvalidInput("1234", fn);
    makeTestWithInvalidInput("12343333", fn);
    makeTestWithInvalidInput("00002411", fn);
    makeTestWithInvalidInput("9999971", fn);
    makeTestWithInvalidInput("44449999971", fn);
});
test("Testing fn() with valid values", function () {
    var fn = splitPattern;
    makeTestWithValidInput("", "3", 6, "", fn);
    makeTestWithValidInput("", "1", 15, "", fn);
    makeTestWithValidInput("", "12", 6, "", fn);
    makeTestWithValidInput("", "166", 3, "", fn);
    makeTestWithValidInput("", "98765", 2, "", fn);

    makeTestWithValidInput("234", "3", 6, "", fn);
    makeTestWithValidInput("0", "1", 15, "", fn);
    makeTestWithValidInput("30124", "12", 6, "", fn);
    makeTestWithValidInput("12", "166", 3, "", fn);
    makeTestWithValidInput("98", "98765", 2, "", fn);
});

Will work on this more later.

[acerix]

Interesting, I'm curious how this compares to the previous version in speed.

Here's another test I made a while ago (it uses Ratio 0.3.11) which compares methods of converting a decimal number to a fraction, maybe that will be useful in checking the performance.

http://jsperf.com/rational-js-vs-fraction-js/4

It makes sense to do this conversion in parse(), but simplify() should require that the numbers are already converted to fractions, so parse() only gets called when creating the Ratio, instead of every time it's simplified.

Also, I noticed that the different methods of getting the fraction can have quite different results. Take a look at this fiddle which compares the results:

http://jsfiddle.net/JU6r3/10/

For example, when the input decimal is Math.PI (3.141592653589793)

• rational.js gives 245850922/78256779
• fraction.js gives 3 70796327/500000000
• and Ratio.js gives 3141592653589793/1000000000000000

fraction.js is simply less accurate, but in my opinion the rational.js result is more preferable in this case, even though they are equivalent if they are turned back into a decimal (with the same precision as the input).

Cheers!

[LarryBattle]

Rational.js looks pretty cool, but after a few experiments it turns out to be unstable. Here's a simple test that passes the decimal values 1/i where i starts at 1 and ends at 156. The goal of the test is to see if the decimal value gets reduced to the original fraction, 1/i. Rational.js seems to have a issue with converging.

Sorry for the awful code. It was a quick write up.

var checkRatioSimplify = function (min, max) {
    var badValues = [],
    x = [],
    expect,
    output;

    if (max <= min) {
        throw new Error("Min is too high");
    }
    for (var i = min, len = max; i < len; i++) {
        expect = "1/" + i;
        x = rat.fromDecimal(1 / i);
        output = x ? x[0] + "/" + x[1] : "null";
        if (expect !== output) {
                var a = 1 / i;
                var b = x[0] / x[1];
                badValues.push([expect, output, a, b, (a == b) ? "same" : "diff"]);
        }
    }
    return badValues;
};
var x = checkRatioSimplify(1, 156);
clear();
console.log(JSON.stringify(x, null, 2));

Oh and I found it interesting how Rational.js was unable to produce 245850922/78256779 from Math.PI. I need to read up on the Stern-Brocot tree.

245850922/78256779 == Math.PI 3141592653589793/1000000000000000 == Math.PI 245850922/78256779 ?= 3141592653589793/1000000000000000 // Nope. There two different fractions. Blame the rounding error on float64 numbers.

[acerix]

I got the idea for using the Stern-Brocot tree from this YouTube series: (highly recommended)

http://www.youtube.com/watch?v=CiO8iAYC6xI&list=SP5A714C94D40392AB

It's still quite experimental, and sometimes this method takes a huge number of iterations. This freezes the browser, etc, so for now I added RAT_MAX_LOOPS which exits the function after 16777216 loops.

I copied your code to a JSfiddle to help me find a fix for this. http://jsfiddle.net/9pZrX/1/ Increasing RAT_MAX_LOOPS would fix these cases, but there must be better ways to optimize that process.

Also, here's Ratio.js in the same example: http://jsfiddle.net/5sKX7/1/

About the rounding, the ratios are equivalent as far as JavaScript is concerned, but the first one is actually a closer approximation and of course it's better to work with smaller numbers.

console.log( 245850922/78256779 === 3141592653589793/1000000000000000 ); true

[acerix]

I tracked down the problem, this is what JavaScript calculates: 1 / 49 * 49 = 0.9999999999999999

Since (1 / 49 * 49 !== 1), my algorithm would skip the correct solutions and end up reaching the MAX_LOOPS.

I fixed this by checking for a difference less than 0.0000000000000002

https://github.com/acerix/rational.js/commit/5dfa96758dcb65a849984517e6562522e7a86da5

Thanks for pointing this out!

[LarryBattle]

Fixed in beta release, version 0.4.2.js. .simplify() is still slow. Added Ratio.getApprox() and Ratio.prototype.approx() to get the approximate values for speed.