3n + 1 problem optimization

The problem can be viewed here, since it's styled. I don't think I should just copy and paste.

I implemented recessive function and dynamic programming to solve it. It can successfully passed UVa Judge with a score of 612ms, but it's not fast enough for this site. Which test my code against 200000 lines of input, and giving only 2s.

#include 
#include 

int cycleLength(long long int);

int cycleLengthResult[1000001];

int main(int argc, char *argv[])
{
    int i = 0, j = 0, cur = 0, max = 0, k = 0, s = 0;
    for (i = 1 ; i  j )
        {
            s = i;
            i = j;
            j = s;
        }
        max = 0;
        for ( k = i ; k  max) max = cur;
        }
        printf("%d\n", max);
    }

    return 0;
}

int cycleLength(long long int arg)
{
    if ( arg > 1000000 )
    {
        if (!(arg & 1))
            return 1 + cycleLength(arg/2);
        else
            return 1 + cycleLength(arg*3+1);
    }
    if (!cycleLengthResult[arg])
    {
        int valueForArg = 0;
        if (arg == 1)
            valueForArg = 1;
        else if (!(arg & 1))
            valueForArg = 1 + cycleLength(arg/2);
        else
            valueForArg = 1 + cycleLength(arg*3+1);

        cycleLengthResult[arg] = valueForArg;
    }
    return cycleLengthResult[arg];
}

I took an elective last semester in which we had to do UVa questions. Just dug up my old UVa 100 submission, and I have a few suggestions for speed (mine was accepted in 200 ms, though I suspect it could be optimized a ton more).

The main thing I see is that you shouldn't use recursion. Due to the setup cost of calling functions, iteration is going to be way faster (in some situations the same stack frame can be reused, but I doubt that optimization is being done in your code).

Though that is my main suggestion, there are a few very minor algorithmic optimizations that can be noted mathematically.

t(n) = 1      if n is 1
     = 3n + 1 if n is odd
     = n / 2  if n is even

c(n) = number of times t(n) will happen
(terrible math syntax here, but erm... go with it)

Now, the approach I took was to build a table bottom up. Basically an array like int m[1000001].

Then a loop like:

for (int i = 1; i <= 1000000; ++i) {
    if (i % 2 == 0) {
        //We know that i / 2 must already be set, so we can just do a constant time look up
        //(your code already does this implicitly through the recursion)
        m[i] = 1 + m[i / 2];
    } else {
        m[i] = cycleLength(i);
    }
}

Nothing special about this loop; it's just the iterative form of your code.

There is an odd little optimization you can make though:

if (i % 2 == 0) {
    m[i] = 1 + m[i/2];
} else if (i % 8 == 5) {
    m[i] = 4 + m[3 * ((i - 5) / 8) + 2];
} else {
    m[i] = cycleLength(i);
}

The theory here is that for any j < i, you know that m[j] is populated. Thus, if you can do some manipulation to get m[i] = c + m[f(i)] such that f(i) < i you can do a constant time look up rather than the potentially enormously expensive cycleLength call.

It's the same concept in the 1 + m[i / 2] situation, just weirder.

If i mod 8 = 5, then by definition, i = 8j + 5 for some integer j.

i = 8j + 5 = 2k + 1 with k = 4j + 2 thus i is odd.

So we follow the pattern:

8j + 5 -> 24j + 16 -> 12j + 8 -> 6j + 4 -> 3j + 2

Note the crucial part here: 3j + 2 < 8j + 5. This means that we can define m[i] in terms of 4 + m[3 * ((i - 5) / 8) + 2].

I'm too lazy to get out a pad of paper, but I suspect that more arithmetic trickery like this is possible (the weird situation of i mod 8 = 5 is something that the professor pointed out). Even without it, an iterative approach is easily fast enough to be accepted by UVa's online judge, but it does make a surprising 48 ms difference with my program.

StackExchange Code Review Q#20020, answer score: 10