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
– Martijn Courteaux, Commented Oct 19, 2014 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. en.wikipedia.org/wiki/Collatz_conjecture#Optimizations — Martijn Courteaux
– Martijn Courteaux, Commented Oct 19, 2014 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
– spyr03, Commented Oct 19, 2014 at 22:36

Community · Accepted Answer · 2017-04-13 12:19:16Z

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, 2017 at 12:19

CommunityBot

11 silver badge

answered Oct 19, 2014 at 21:03

maaartinus

46.8k40 gold badges176 silver badges343 bronze badges

Sign up to request clarification or add additional context in comments.

9 Comments

spyr03 Over a year ago

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

maaartinus Over a year ago

@spyr03 Exactly. I forgot to state that numberOfTrailingZeros is in the class Integer.

maaartinus Over a year ago

@spyr03 I see, you need long rather than int, but this is no problem as Long.numberOfTrailingZeros exists, too.

spyr03 Over a year ago

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.

maaartinus Over a year ago

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

|

Collectives™ on Stack Overflow

collatz sequence - optimising code

1 Answer 1

9 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

9 Comments

Your Answer

Sign up or log in

Post as a guest

Related