Editing Collatz Conjecture

This edit will create a new revision.

Your details (optional)

Name

Email (won’t be displayed; might be used for Gravatar)

URL

Test case details

Title *

Published (uncheck if you want to fiddle around before making the page public)

Description (in case you feel further explanation is needed)(Markdown syntax is allowed)

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.__

Are you a spammer? (just answer the question)

Preparation code

Preparation code HTML (this will be inserted in the <body> of a valid HTML5 document in standards mode) (useful when testing DOM operations or including libraries)

<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>

Include JavaScript libraries as follows: <script src="//cdn.ext/library.js"></script>

Define setup for all tests (variables, functions, arrays or other objects that will be used in the tests) (runs before each clocked test loop, outside of the timed code region) (e.g. define local test variables, reset global variables, clear canvas, etc.) (see FAQ)

Define teardown for all tests (runs after each clocked test loop, outside of the timed code region) (see FAQ)

Code snippets to compare

Test 1

Title

Async (check if this is an asynchronous test)

Code

//for (input in testcases) {
var result = collatz_count_iterative(
  //$("#collatz-input").val()
  input
);
//$("#collatz-result-iterative").val(result);
//}

Test 2

Title

Async (check if this is an asynchronous test)

Code

//for (input in testcases) {
var result = collatz_count_recursive(
  //$("#collatz-input").val()
  input
);
//$("#collatz-result-recursive").val(result);
//}

Test 3

Title

Async (check if this is an asynchronous test)

Code

//for (input in testcases) {
var result = collatz_count_iterative_optimized(
  //$("#collatz-input").val()
  input
);
//$("#collatz-result-iterative-optimized").val(result);
//}

Test 4

Title

Async (check if this is an asynchronous test)

Code

//for (input in testcases) {
var result = collatz_count_recursive_optimized(
  //$("#collatz-input").val()
  input
);
//$("#collatz-recursive-optimized").val(result);
//}

Test 5

Title

Async (check if this is an asynchronous test)

Code

//for (input in testcases) {
var result = collatz_count_iterative_optimized_cached(
  //$("#collatz-input").val()
  input
);
//$("#collatz-result-iterative-optimized-cached").val(result);
//}

Test 6

Title

Async (check if this is an asynchronous test)

Code

//for (input in testcases) {
var result = collatz_count_recursive_optimized_cached(
  //$("#collatz-input").val()
  input
);
//$("#collatz-result-recursive-optimized-cached").val(result);
//}