On the 3x+1 Problem: Basic algorithm speedups

The last time I talked about the 3x+1 Problem, I gave a basic overview of what it is. Today, I will talk about some (basic) ways to speed up the search for a counterexample, and next time I will introduce the Structure Theorem for the 3x+1 Problem.

• Part I: An introduction to 3x+1
• Part II: Basic algorithm speedups (this one)
• Part III: The Structure Theorem

I suggest reading from the beginning if you do not know what the 3x+1 (Collatz) Problem is.

To get starting on thinking of some simple reasoning can do in speeding it up, here is some pseudocode of a naïve implementation of an algorithm that forever checks numbers. After it checks that a number goes to 1, it moves on to the next.

 repeat with x from 1 to forever
     set testMe to x
     while testMe is not 1 do
         if testMe is odd then
             set testMe to 3*testMe + 1
         else -- It must be even
             set testMe to testMe divided by 2
         end if
     end while
 end repeat

Somewhat ironically, we will have found a counterexample to the conjecture if we stay in the while loop forever on some value of x. Otherwise, we will keep increasing x and checking that. As I said before, this will run up to at least 2^60, as that is what has been checked so far.

Now, when I talk about algorithmic speedups, I mean in a more mathematical sense. A common implementation trick people like to use is that multiplying x by 3 is the same as multiplying x by 2 and adding x again. Why? Well, due to the way almost every processor in existence handles integers, multiplying by two (or any power of two, really) is exceptionally fast, so fast that doing that and doing an addition operation is faster than doing a single multiplication. These kind of tricks are fine, but to me mathematical speedups more interesting.

Let’s take a look at the actual 3x+1 algorithm. What happens when x is even? Well, obviously we divide by two. But if you think about it, the number we get from that is half of what we started with. So we must have already checked it. So our new algorithm is as follows. Oh, and from now on, let’s call the 3x+1 part a new function T(). It will make more sense next time.

 repeat with odd x from 1 to forever
     set testMe to x
     while testMe is not 1 do
         set testMe to T(testMe)
     end while
 end repeat

Notice something about our reasoning. We ruled out bothering to check even numbers, because we would have already checked the number it went to. We are increasing x on each step, and have checked every number less than it. Once we drop below x in our checking, we know it eventually stops (we have already checked it!) So now…

 repeat with odd x from 3 to forever
     set testMe to x
     while testMe is greater than or equal to x do
         set testMe to T(testMe)
     end while
 end repeat

Let’s take a look at how we are doing. I went and wrote a C++ program that (mostly) does what we just talked about. People complain about doing timings, so instead I am going to measure something else people can complain about (we can just agree there is no truly good measure. How about that?) Let’s measure the number of times we apply T(), i.e., how many times the “if testMe is odd…else…” gets called. Also, we will have to stop somewhere, so I chose our bound to be 2^20, or roughly 1,000,000.

In the very first implementation, T() is called 138,300,296 times, which is a lot. We tested every number from 1 to 1,048,576 and T() is called on average 132 times each.

In our second implementation, T() is called 72,389,565 times. This step is really just clearing out the chafe, and probably does not act as much of a speedup. Note that we are now testing just the odd numbers, but T() is called on average 138 times each. This can most likely be explained by the fact that even numbers automatically go to a much smaller number, which probably take fewer iterations to go to 1.

So how about our third change? In that case T() is called 5,478,130 times, so on average about 10½ times each. Now this is a major speedup.

It turns out there is one relatively easy change we can make, but I will have to leave it for the Structure Theorem. It does turn out, though, that we do not need to check all the odd numbers. In fact, it is unnecessary to check those numbers that, when divided by 6, have a remainder of 3 (so we now have ruled out another ⅓ of the numbers we are looking at. I will explain that next, and also explain how the Structure Theorem can actually do us one better.

Technorati Tags: Collatz+Conjecture, math