factorial olympics

JavaScript performance comparison

Revision 4 of this test case created

Info

compare imperative vs. recursive factorial vs. continuation-passing vs. tail-recursive vs. tail-recursive-cp vs. caching

Preparation code

<script>
//assumes n is a non-negative integer
function factorial1(n) {
  var r = 1;
  while (n>1) {
    r = r * n--;
  }
  return r;
}

//assumes n is a non-negative integer
function factorial2(n) {
  return (n<2) ? 1 : factorial2(n-1) * n;
}

function factorial3(n,ret) {
  if (n == 0)
    ret(1) ;
  else
    factorial3(n-1, function (t0) {
     ret(n * t0) }) ;
}

function factorial4(n) {
  return tail_fact(n,1) ;
}
 
function tail_fact(n,a) {
  if (n == 0)
    return a ;
  else
    return tail_fact(n-1,n*a) ;
}

function factorial5(n,ret) {
  tail_fact2(n,1,ret) ;
}
 
function tail_fact2(n,a,ret) {
  if (n == 0)
    ret(a) ;
  else
    tail_fact2(n-1,n*a,ret) ;
}

// Lifted from http://jsperf.com/factorial-cache
function factorial_cache(n) {
  factorial_cache.cache = factorial_cache.cache || [1]
  return factorial_cache.cache[n] || (factorial_cache.cache[n] = n * factorial_cache(n - 1))
}

var kmath = new Kmath();

function Kmath() {

    var self = this;
/*------------------------------------------------------*/
    // factorials
    /*------------------------------------------------------*/
    var factorials = new Int32Array(171);


    /*------------------------------------------------------*/
    // factorial(x)
    /*------------------------------------------------------*/
    this.factorial = function (x) {
        v = x;
        // If x is an integer
        if (x % 1 === 0) {
            if (factorials[x]) {
                return factorials[x];
            }
            // Empty product
            if (x === 0) {
                return factorials[x] = v = 1;
            }    // Complex Infinity
            else if (x > 170 || x < 0) {
                return factorials[x] = v = Infinity;
            }    // Factor
            else
                while (x > 1)
                    v *= --x;
        }  
        return v;
    };
}
</script>

Test runner

Warning! For accurate results, please disable Firebug before running the tests. (Why?)

Java applet disabled.

Testing in unknown unknown
Test Ops/sec
imperative 20
factorial1(20);
pending…
imperative 170
factorial1(170);
pending…
recursive 20
factorial2(20);
pending…
recursive 170
factorial2(170);
pending…
CP 20
factorial3(20,function(){});
pending…
CP 170
factorial3(170,function(){});
pending…
tail-factorial 20
factorial4(20);
pending…
tail-factorial 170
factorial4(170);
pending…
tail-factorial-cp 20
factorial5(20,function(){});
pending…
tail-factorial-cp 170
factorial5(170,function(){});
pending…
factorial-cache 20
factorial_cache(20);
pending…
factorial-cache 170
factorial_cache(170);
pending…
kmath.factorial(170);
kmath.factorial(170);
pending…

Compare results of other browsers

Revisions

You can edit these tests or add even more tests to this page by appending /edit to the URL. Here’s a list of current revisions for this page:

0 comments

Add a comment