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 <cstdio>
#include <iostream>

int cycleLength(long long int);

int cycleLengthResult;

int main(int argc, char *argv[])
{
int i = 0, j = 0, cur = 0, max = 0, k = 0, s = 0;
for (i = 1 ; i < 1000001 ; ++ i ) cycleLength(i);

while ( scanf("%d%d", &i, &j) != EOF )
{
printf("%d %d ", i, j);
if ( i > j )
{
s = i;
i = j;
j = s;
}
max = 0;
for ( k = i ; k <= j ; ++ k )
{
cur = cycleLengthResult[k];
if (cur > 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];
}
• Why are you using the C standard library and C programming idioms in what is apparently supposed to be a C++ program? – Paul R Dec 30 '12 at 18:11
• @Paul R I was told that scanf and printf will be faster than com and cout. And on the compiler provided by zerojudge.tw, you will need cstdlib. – Shane Hsu Dec 30 '12 at 22:20
• This is also known as the Collatz Conjecture, and there's also the XKCD view on it too. – Jonathan Leffler Jan 1 '13 at 7:52

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.

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);
}
}

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.

• @Corbin I read your answer, and will try it next week. – Shane Hsu Dec 30 '12 at 14:33
• @WilliamMorris Whoops, yup. Double typed it. – Corbin Dec 30 '12 at 18:22
• Don't know why I didn't accept this more than a year ago. This did the trick then. – Shane Hsu Jan 31 '14 at 2:55

The only places I have found that improve cycleLength (by 5-10%) are

• reversing the (somewhat illogical) if (!(arg & 1)) conditions (not really sure if this had an effect though, as there seems no reason for it to)
• and removing the test for arg == 1 by initialising cycleLengthResult to 1:

int cycleLengthResult = {0, 1, 0}

It is also possible to extract the duplicated code to make the function more readable, although this does not improve the performance:

int cycleLength(long arg);

static inline int nextLength(long arg)
{
long n;
if (arg & 1) {
n = (arg * 3) + 1;
} else {
n = arg / 2;
}
return 1 + cycleLength(n);
}

int cycleLength(long arg)
{
if (arg > 10000000) {
return nextLength(arg);
}
if (cycleLengthResult[arg] != 0) {
return cycleLengthResult[arg];
}
return cycleLengthResult[arg] = nextLength(arg);
}

There might be ways to improve main but I didn't look at that.

• I've read your answer, and will try it this week. – Shane Hsu Dec 30 '12 at 14:34

I've wrote some similar code and submitted on programming challenges website. If I precompute the cache array it executes in 570ms, while if I cache as I go as needed it executes in 62ms.

I'd say then that the greatest optimisation is not to compute values that don't need to be computed. Doing a single printf instead of two shaved about 5 ms. A bit better, but not really significant.

#include <cstdio>
#include <algorithm> // std::min, std::max
using namespace std;

int cycleLength(int);
const int CACHE_LEN = 1000001;
short cache[CACHE_LEN] = {0};

int main()
{
int leftNo, rightNo, minNo, maxNo;
while ( scanf("%d%d", &leftNo, &rightNo) != EOF )
{
int maxCycles = 0;
minNo = min(leftNo, rightNo);
maxNo = max(leftNo, rightNo);
for (int curNo = minNo; curNo <= maxNo; ++curNo )
{
int curCycles = cycleLength(curNo);
if (curCycles > maxCycles) maxCycles = curCycles;
}
printf("%d %d %d\n", leftNo, rightNo, maxCycles);
}
return 0;
}

int cycleLength(int start)
{
int length = cache[start];
if (length != 0) return length;
length++;
long long int current = start;
while (current != 1)
{
if (current % 2 == 0) current /= 2;
else current = 3 * current + 1;
length++;
}
cache[start] = length;
return length;
}
• This isn't really a review of the asker's code. Posting some of your own code is okay, but you should explain how it can lead to an improvement. – Jamal Dec 12 '14 at 0:57
• thanks for pointing it out, I'm new to the site. I've said how to lead to a ten-fold improvement though: don't pre-compute everything, but only what you're asked for. – stivlo Dec 12 '14 at 10:13