Collatz Conjecture

JavaScript performance comparison

Test case created by Ian Cervantez

Info

Consider the following algorithm

  1. Input n
  2. If n = 1 then stop
    • If n is odd, then n = 3n + 1
    • If n is even, then n = n / 2
  3. GOTO 2

It is conjectured that the Collatz Algorithm will terminate for any positive integer input. The functions below count the number of iterations it takes for a given (random) input. This makes for an interesting study on the effect of function calls, mathematical operators, and caching.

I find that iteration is generally faster than recursion. This is because as the program recurses, it bogs down the program stack. In order to optimize the recursive process you must first figure out how to reduce the number of recursive calls. Thankfully, for this problem, that's an easy task - yay math. 3n+1 always results in an even number, so you can instantly divide by 2 without issuing a new function call, which pretty reliably cuts the number or recursive calls down by between a third and a half. Additionally (when caching is involved) recursion turns out to be better because as you rollback through the program stack you cache the result of every single value you've touched.

Something else that's pretty interesting is how much slower these test cases go when using jQuery to get input and print output. This likely has to do with the DOM lookups. Uncomment some of the code I left in there to see just how much jQuery calls impact the performance

I realize this can be further improved upon by using a binary tree structure to cache, but the technique exceeds the depth of this study.

I also realize that the results of each of these test cases are often times more about "luck of the draw" than anything else. If the random number that gets generated is a 1 or a 2, pretty much all of these will execute with the same (ridiculously fast) speed. If you want to test this across multiple browsers, you should force the input to be the same rather than randomized.

Preparation code

<script src="//ajax.googleapis.com/ajax/libs/jquery/1/jquery.min.js">
</script>
<script type="text/javascript">
  var testcases = [];
  for (var i = 0; i < 100; i++) {
    testcases[i] = Math.floor(Math.random() * 1000000) + 1;
  }
  var input = Math.floor(Math.random() * 1000000) + 1;
  //$("#collatz-input").val(input);

  var collatz_cache = [1000000];
  // Be fair to the cache tests, clear the cache between cases
  // Prefill the cache with the known multiples of 2.
  ui.benchmarks[4].setup = function() {
    var collatz_cache_counter = 0;
    for (var i = 1; i < 1000000; i <<= 1) {
      collatz_cache[i] = collatz_cache_counter++;
    }
  };
  ui.benchmarks[4].teardown = function() {
    collatz_cache = null;
  };
  ui.benchmarks[5].setup = function() {
    var collatz_cache_counter = 0;
    for (var i = 1; i < 1000000; i <<= 1) {
      collatz_cache[i] = collatz_cache_counter++;
    }
  };
  ui.benchmarks[5].teardown = function() {
    collatz_cache = null;
  };



  function collatz_count_iterative(n) {
    var count = 0;
    while (n > 1) {
      if (n % 2 == 0) {
        n = n / 2;
      } else {
        n = (n * 3) + 1;
      }
      count++;
    }
    return count;
  }

  function collatz_count_recursive(n) {
    if (n <= 1) {
      return 0;
    } else if (n % 2 == 0) {
      return (1 + collatz_count_recursive(n / 2));
    } else {
      return (1 + collatz_count_recursive(n * 3 + 1));
    }
  }

  function collatz_count_iterative_optimized(n) {
    var count = 0;
    while (n > 1) {
      if ((n & 1) == 1) {
        n += (n << 1) + 1;
        n >>= 1;
        count++;
      } else {
        n >>= 1;
      }
      count++;
    }
    return count;
  }

  function collatz_count_recursive_optimized(n) {
    if (n <= 1) {
      return 0;
    } else if ((n & 1) == 1) {
      // Odd case
      n += (n << 1) + 1;
      n >>= 1;
      return (2 + collatz_count_recursive_optimized(n));
    } else {
      // Even case
      return (1 + collatz_count_recursive_optimized(n >> 1));
    }
  }

  function collatz_count_iterative_optimized_cached(n) {
    var count = 0;
    while (n > 1) {
      if (collatz_cache[n] != null) {
        count += collatz_cache[n];
        n = 1;
      } else {
        if ((n & 1) == 1) {
          n += (n << 1) + 1;
          n >>= 1;
          count++;
        } else {
          n >>= 1;
        }
        count++;
      }
    }
    collatz_cache[n] = count;
    return collatz_cache[n];
  }

  function collatz_count_recursive_optimized_cached(n) {
    if (n <= 1) {
      return 0;
    } else if (collatz_cache[n] != null) {
      return collatz_cache[n];
    } else if ((n & 1) == 1) {
      // Odd case
      n += (n << 1) + 1;
      n >>= 1;
      collatz_cache[n] = 2 + collatz_count_recursive_optimized_cached(n);
      return collatz_cache[n];
    } else {
      // Even case
      collatz_cache[n] = 1 + collatz_count_recursive_optimized_cached(n >> 1);
      return (collatz_cache[n]);
    }
  }
</script>
<!--
<div>
 <form>
   <label for="collatz-input">
     Input:
     <input type="text" name="collatz-input" id="collatz-input" />
   </label>
   <label for="collatz-result-iterative">
     Result (Iterative):
     <input type="text" name="collatz-result-iterative" id="collatz-result-iterative" disabled="disabled"
     />
   </label>
   <label for="collatz-result-recursive">
     Result (Recursive):
     <input type="text" name="collatz-result-recursive" id="collatz-result-recursive" disabled="disabled"
     />
   </label>
   <label for="collatz-result-iterative-optimized">
     Result (Iterative Optimized):
     <input type="text" name="collatz-result-iterative-optimized" id="collatz-result-iterative-optimized" disabled="disabled"
     />
   </label>
   <label for="collatz-recursive-optimized">
     Result (Recursive Optimized):
     <input type="text" name="collatz-recursive-optimized" id="collatz-recursive-optimized" disabled="disabled"
     />
   </label>
   <label for="collatz-result-iterative-optimized-cached">
     Result (Iterative Optimized Cached):
     <input type="text" name="collatz-result-iterative-optimized-cached" id="collatz-result-iterative-optimized-cached" disabled="disabled"
     />
   </label>
   <label for="collatz-result-recursive-optimized-cached">
     Result (Recursive Optimized Cached):
     <input type="text" name="collatz-result-recursive-optimized-cached" id="collatz-result-recursive-optimized-cached" disabled="disabled"
     />
   </label>
 </form>
</div>
-->

Preparation code output

Test runner

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

Java applet disabled.

Testing in unknown unknown
Test Ops/sec
Iterative
//for (input in testcases) {
var result = collatz_count_iterative(
  //$("#collatz-input").val()
  input
);
//$("#collatz-result-iterative").val(result);
//}
pending…
Recursive
//for (input in testcases) {
var result = collatz_count_recursive(
  //$("#collatz-input").val()
  input
);
//$("#collatz-result-recursive").val(result);
//}
pending…
Optimized Math (Iterative)
//for (input in testcases) {
var result = collatz_count_iterative_optimized(
  //$("#collatz-input").val()
  input
);
//$("#collatz-result-iterative-optimized").val(result);
//}
pending…
Optimized Math (Recursive)
//for (input in testcases) {
var result = collatz_count_recursive_optimized(
  //$("#collatz-input").val()
  input
);
//$("#collatz-recursive-optimized").val(result);
//}
pending…
Cached Results (Optimized Iterative)
//for (input in testcases) {
var result = collatz_count_iterative_optimized_cached(
  //$("#collatz-input").val()
  input
);
//$("#collatz-result-iterative-optimized-cached").val(result);
//}
pending…
Cached Results (Optimized Recursive)
//for (input in testcases) {
var result = collatz_count_recursive_optimized_cached(
  //$("#collatz-input").val()
  input
);
//$("#collatz-result-recursive-optimized-cached").val(result);
//}
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:

1 comment

Ian Cervantez (revision owner) commented :

I just gave this a try in IE8 and got a lot of alerts warning that a script was taking too long to execute and it asked me if I wanted them to continue. This only occurred on the iterative tests, though. My guess is that Microsoft included this warning in loops with abnormally large termination conditions in loops to prevent a crash in IE.

Add a comment