collatz sequence - optimising code

Question

As an additional question to an assignment, we were asked to find the 10 starting numbers (n) that produce the longest collatz sequence. (Where 0 < n < 10,000,000,000) I wrote code that would hopefully accomplish this, but I estimate that it would take a full 11 hours to compute an answer.

I have noticed a couple of small optimisations like starting from biggest to smallest so adding to the array is done less, and only computing between 10,000,000,000/2^10 (=9765625) and 10,000,000,000 because there has to be 10 sequences of longer length, but I can't see anything more I could do. Can anyone help?

Relevant Code The Sequence Searching Alg

long[][] longest = new long[2][10]; //terms/starting number
long max = 10000000000l; //10 billion

for(long i = max; i >= 9765625; i--) {
    long n = i;
    long count = 1; //terms in the sequence

    while(n > 1) {
        if((n & 1) == 0) n /= 2; //checks if the last bit is a 0
        else {
            n = (3*n + 1)/2;
            count++;
        }
        count++;
    }
    if(count > longest[0][9]) {
        longest = addToArray(count, i, longest);
        currentBest(longest); //prints the currently stored top 10
    }
}

The storage alg

public static long[][] addToArray(long count, long i, long[][] longest) {
    int pos = 0;
    while(count < longest[0][pos]) {
        pos++;
    }
    long TEMP = count; //terms
    long TEMPb = i; //starting number
    for(int a = pos; a < longest[0].length; a++) {
        long TEMP2 = longest[0][a];
        longest[0][a] = TEMP;
        TEMP = TEMP2;

        long TEMP2b = longest[1][a];
        longest[1][a] = TEMPb;
        TEMPb = TEMP2b;
    }
    return longest;
}

One micro optimization would be replacing `/ 2` by `>>> 1`. But that would not do a lot. — Martijn Courteaux, Oct 19 '14 at 20:20
I'm not being the big hero here, but Wikipedia has a nice section about it. You can do some pre-computations that allow you to make `k` iterations at once. https://en.wikipedia.org/wiki/Collatz_conjecture#Optimizations — Martijn Courteaux, Oct 19 '14 at 20:30
I'm only learning about the less common (aka non arimethic) operators, so its interesting and probably useful to know, but the wiki article is well beyond my current scope of programming. I'll definitely try and research it though — spyr03, Oct 19 '14 at 22:36

score 1 · Accepted Answer · edited Apr 13 '17 at 12:19

1

You can do something like

while (true) {
    int ntz = Long.numberOfTrailingZeros(n);
    count += ntz;
    n >>>= ntz; // Using unsigned shift allows to work with bigger numbers.
    if (n==1) break;
    n = 3*n + 1;
    count++;
}

which should be faster as it does multiple steps at once and avoids unpredictable branches. numberOfTrailingZeros is JVM intrinsic taking just one cycle on modern desktop CPUs. However, it's not very efficient as the average number of zeros is only 2.

The Wikipedia explains how to do multiple steps at once. This is based on the observation that knowing k least significant bits is sufficient to determine the future steps up to the point when the k-th halving happens. My best result based on this (with k=17) and filtering out some non-promising values is 57 seconds for the determination of the maximum in range 1 .. 1e10.

edited Apr 13 '17 at 12:19

Community

1
1

answered Oct 19 '14 at 21:03

maaartinus

44,714
32
161
320

So if I understood that, it essential divides by the highest power of two it can, and adds an appropriate amount to count? That would help a lot actually, thanks – spyr03 Oct 19 '14 at 22:33
@spyr03 Exactly. I forgot to state that `numberOfTrailingZeros` is in the class `Integer`. – maaartinus Oct 19 '14 at 22:43
@spyr03 I see, you need `long` rather than `int`, but this is no problem as `Long.numberOfTrailingZeros` exists, too. – maaartinus Oct 19 '14 at 22:53
I'm adding it now, the original program finished running after just over an hour and 40 mins, so I'll see if it starts off much faster. – spyr03 Oct 19 '14 at 22:59
@spyr03 It's good, but not as good as the optimization in Wikipedia. With it using a 2**16 table I could compute the result till `1e10` in 211 seconds. Some more improvements are still possible. – maaartinus Oct 20 '14 at 01:36
I have no idea how to go about starting that, could you point me in the right direction? – spyr03 Oct 25 '14 at 20:21
@spyr03 I have currently no access to the code I wrote and explaining is hard as I have no idea what you're missing. I'm gonna post it on [CR](http://codereview.stackexchange.com) in a few days when I come back. Make yourself a simple example, do a manual computation for a few numbers and look at their e.g., last two bits. The first two steps are fully determined by those two bits... that's the key idea. – maaartinus Oct 25 '14 at 20:44
Ok, I look forward to seeing the code, I'll look into that, thanks – spyr03 Oct 25 '14 at 21:09
@spyr03 I wanted to publish my code, but instead I optimized it a bit further (see my edit) and made it even more complicated. So posting to CR will take some more time, but I hope I can get it simple enough to be suitable. – maaartinus Dec 08 '14 at 22:29

collatz sequence - optimising code

1 Answers1