java - collatz sequence - optimising code -

java - collatz sequence - optimising code -

as additional question assignment, asked find 10 starting numbers (n) produce longest collatz sequence. (where 0 < n < 10,000,000,000) wrote code accomplish this, estimate take total 11 hours compute answer.

i have noticed couple of little optimisations starting biggest smallest adding array done less, , computing between 10,000,000,000/2^10 (=9765625) , 10,000,000,000 because there has 10 sequences of longer length, can't see more do. can help?

relevant code sequence searching alg

long[][] longest = new long[2][10]; //terms/starting number long max = 10000000000l; //10 billion for(long = max; >= 9765625; i--) { long n = i; long count = 1; //terms in sequence while(n > 1) { if((n & 1) == 0) n /= 2; //checks if lastly bit 0 else { n = (3*n + 1)/2; count++; } count++; } if(count > longest[0][9]) { longest = addtoarray(count, i, longest); currentbest(longest); //prints 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 = pos; < 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; } homecoming longest; }

you can like

while (true) { int ntz = long.numberoftrailingzeros(n); count += ntz; n >>>= ntz; // using unsigned shift allows work bigger numbers. if (n==1) break; n = 3*n + 1; count++; }

which should faster multiple steps @ 1 time , avoids unpredictable branches. numberoftrailingzeros jvm intrinsic taking 1 cycle on modern desktop cpus. however, it's not efficient average number of zeros 2.

the wikipedia explains how multiple steps @ once. based on observation knowing k to the lowest degree important bits sufficient determine future steps point when k-th halving happens. best result based on (with k=17) , filtering out non-promising values 57 seconds determination of maximum in range 1 .. 1e10.

java arrays optimization mathematical-optimization collatz