# Speeding up 3n+1 challenge

I have been trying to make this code go faster by trying to write it more efficiently and I don't know what else to do. I got it to 30 seconds but I have seen 23 and 24 and I have no idea on how to do it.

public class Main {

public static void main(String[] args) {
long startTime = System.currentTimeMillis();

for(long n = 1; n <= 100000000; n+=2){
long value = cycleLength(n);
if(value > (n*n)){
System.out.println(n + " " + value);
}
}

long endTime = System.currentTimeMillis();

System.out.println("Runtime = " + (endTime - startTime) + " milliseconds");

}//main

public static long cycleLength(long n) {
long hi = n;

while (n > 1) {
if((n&1)==0)  // bitwise AND
n = n >> 1;  // n even
else {
n = 3*n+1; // n odd

if(hi < n)
hi = n;
n = n >> 1;
}
}

return hi;
}

}


## migrated from stackoverflow.comJun 18 '12 at 21:03

This question came from our site for professional and enthusiast programmers.

• Where have you seen the other timings? On your computer? You just might want to buy a faster computer! – Albin Sunnanbo Jun 18 '12 at 20:17
• Reducing the number of method calls to System.out.println will probably help... maybe use a StringBuilder to create the output and then print the entire thing at the very end? (idk, I've never done it before) – Alex Lockwood Jun 18 '12 at 20:36
• Most of the optimizations are through caching values in an array/hashmap. You can search SO to find similar questions. – user845279 Jun 18 '12 at 20:47
• Is cycleLength supposed to return the cycle length, or the maximum value within in the resulting sequence? – hatchet Jun 18 '12 at 20:49
• Are we talking about UVA The 3n + 1 problem? – cat_baxter Jun 19 '12 at 14:23

This code runs in 2 secs vs the original 24 secs in my box, with no additional memory needed, or 0.5 secs if you don't mind using more than 1 CPU.

Going to explain how it works with an example:

Let say that "n" is 97. At this point maxSoFar is 9232 (which is the value of cycleLength for 27, 31, 41, ...), which is the maximun value of cycleLength found for all "n" < 97. 97 * 97 is 9409 which is bigger than 9232, which means that if inside the loop of the cycleLength, "j" becomes smaller than 97, then cycleLength will be at most 9232, which is smaller than 9409 so it is not necessary to continue doing any calculations as cycleLenght will be never bigger than n * n.

So with "n" 97, n_square is 9409. We do the first loop, which means that "j" is 292. As "j" > "n", we still have hope that it can become bigger than 9409. Two cycles latter, "j" becomes 73 (292 / 2 / 2). Now we know that 73 is never going to be bigger than 9232, which means that there is no point of searching anymore and we can exit cycleLength.

Note that with this implementation cycleLength for 97 actually return 73 (instead of 9232 of your implementation) but the results are still correct.

The code is basically the same as yours but adding a condition in the cycleLength loop.

public class Main {

private static long maxSoFar = -1;

public static void main(String[] args) {
long startTime = System.currentTimeMillis();

for (long n = 1; n <= 100000000; n += 2) {
long value = cycleLength(n);
if (value > (n * n)) {
System.out.println(n + " " + value);
maxSoFar = Math.max(value, maxSoFar);
}
}

long endTime = System.currentTimeMillis();

System.out.println("Runtime = " + (endTime - startTime) + " milliseconds");
}//main

public static long cycleLength(long j) {
long hi = j;
long original = j;
long n_square = j * j;
while (j > 1) {
if (j < original && maxSoFar < n_square) {
return hi;
}
if ((j & 1) == 0)  // bitwise AND
{
j = j >> 1;  // n even
} else {
j = 3 * j + 1; // n odd
if (hi < j) {
hi = j;
}
j = j >> 1;
}
}

return hi;
}

}


The multithreaded version creates a bunch of threads each one calculating a different serie of n. So for 2 threads: Thread 1 will do 1, 5, 9, 13 ... Thread 2 will do 3, 7, 11, 15 ...

In my box (4 cores) the optimal value for n = 10^8 is 32 threads.

import java.util.concurrent.ConcurrentHashMap;

public class Main implements Runnable {

private long maxSoFar = -1;
private int start;
private int step;
static ConcurrentHashMap results = new ConcurrentHashMap();

public Main(final int start, final int step) {
this.start = start;
this.step = step;
}

public static void main(String[] args) throws InterruptedException {
long startTime = System.currentTimeMillis();

for (int i = 0; i < threads.length; i++) {
threads[i] = new Thread(new Main((i * 2) + 1, threads.length * 2));
}

}

}

System.out.println("results = " + results);

long endTime = System.currentTimeMillis();

System.out.println("Runtime = " + (endTime - startTime) + " milliseconds");

}

public void run() {
long startTime = System.currentTimeMillis();

for (long n = start; n <= 100000000; n += step) {
long value = cycleLength(n);
if (value > (n * n)) {
System.out.println(Thread.currentThread().getName() + " " + n + " " + value);
results.put(n, value);
maxSoFar = Math.max(value, maxSoFar);
}
}

long endTime = System.currentTimeMillis();

System.out.println("Runtime = " + Thread.currentThread().getName() + " " + (endTime - startTime) + " milliseconds");
}//main

public long cycleLength(long j) {
long hi = j;
long original = j;
long n_square = j * j;
while (j > 1) {
if (j < original && maxSoFar < n_square) {
return hi;
}
if ((j & 1) == 0)  // bitwise AND
{
j = j >> 1;  // n even
} else {
j = 3 * j + 1; // n odd
if (hi < j) {
hi = j;
}
j = j >> 1;
}
}

return hi;
}

}


A little bit of loop unrolling plus a time memory tradeoff yields this, which on my machine runs in just over 6s. Your original code took about 32s, so that's a speedup of over 500%. You will need to launch it manually, eclipse cannot run it at the default settings, it takes too much RAM (over 800MB)

It's also worth noting that it will take a fraction of a second longer if you move the long[] solutionarray = new long[max]; declaration inside the timing zone.

Apologies for the ugly indentation, eclipse sort of mixed yours and mine.

public class Main {

public static void main(String[] args) {
int max = 100000000;
long[] solutionarray = new long[max];
solutionarray = 1;
long startTime = System.currentTimeMillis();
long n = 1;
long value = 0;
while (n < max)
{
value = cycleLength(n, solutionarray);
fillArray(n, value, solutionarray);
if(value > (n*n))
System.out.println(n + " " + value);
n += 2;
}

long endTime = System.currentTimeMillis();

System.out.println("Runtime = " + (endTime - startTime) + " milliseconds");

}//main

public static long cycleLength(long n, long[] array) {
long orig = n;
long hi = n;
while (n > 64) {
if (n < array.length)
{
long m = array[(int)n];
if (m != 0)
{
hi = (m < hi) ? hi : m;
return hi;
}
}
if((n&1)==0)  // bitwise AND
n >>= 1;  // n even
else{
n = n+n+n+1; // n odd

if(hi < n)
hi = n;
n >>= 1;
}
if (n < array.length)
{
long m = array[(int)n];
if (m != 0)
{
hi = (m < hi) ? hi : m;
return hi;
}
}
if((n&1)==0)  // bitwise AND
n >>= 1;  // n even
else{
n = n+n+n+1; // n odd

if(hi < n)
hi = n;
n >>= 1;
}
if (n < array.length)
{
long m = array[(int)n];
if (m != 0)
{
hi = (m < hi) ? hi : m;
return hi;
}
}
if((n&1)==0)  // bitwise AND
n >>= 1;  // n even
else{
n = n+n+n+1; // n odd

if(hi < n)
hi = n;
n >>= 1;
}
if (n < array.length)
{
long m = array[(int)n];
if (m != 0)
{
hi = (m < hi) ? hi : m;
return hi;
}
}
if((n&1)==0)  // bitwise AND
n >>= 1;  // n even
else{
n = n+n+n+1; // n odd

if(hi < n)
hi = n;
n >>= 1;
}
if (n < array.length)
{
long m = array[(int)n];
if (m != 0)
{
hi = (m < hi) ? hi : m;
return hi;
}
}
if((n&1)==0)  // bitwise AND
n >>= 1;  // n even
else{
n = n+n+n+1; // n odd

if(hi < n)
hi = n;
n >>= 1;
}
}
while (n > 1) {
if (n < array.length)
{
long m = array[(int)n];
if (m != 0)
{
hi = (m < hi) ? hi : m;
return hi;
}
}
if((n&1)==0)  // bitwise AND
n >>= 1;  // n even
else{
n = n+n+n+1; // n odd

if(hi < n)
hi = n;
n >>= 1;
}
}
return hi;
}

static void fillArray(long n, long hi, long[] array)
{
while (true)
{
if((n&1)==0)  // bitwise AND
n >>= 1;  // n even
else{
n = n+n+n+1; // n odd
}
if (n < array.length)
{
if (array[(int) n] != 0) break;
array[(int) n] = hi;
}
if((n&1)==0)  // bitwise AND
n >>= 1;  // n even
else{
n = n+n+n+1; // n odd
}
if (n < array.length)
{
if (array[(int) n] != 0) break;
array[(int) n] = hi;
}
if((n&1)==0)  // bitwise AND
n >>= 1;  // n even
else{
n = n+n+n+1; // n odd
}
if (n < array.length)
{
if (array[(int) n] != 0) break;
array[(int) n] = hi;
}
if((n&1)==0)  // bitwise AND
n >>= 1;  // n even
else{
n = n+n+n+1; // n odd
}
if (n < array.length)
{
if (array[(int) n] != 0) break;
array[(int) n] = hi;
}
if((n&1)==0)  // bitwise AND
n >>= 1;  // n even
else{
n = n+n+n+1; // n odd
}
if (n < array.length)
{
if (array[(int) n] != 0) break;
array[(int) n] = hi;
}
}
}
}

• This response is not correct, as it return 61 and 81, which don't show in the original code – DanLebrero Jun 18 '12 at 23:55
• So it does. Fixing it makes it run much longer unfortunately (the fix simply limits fillArray to filling only until max is reached) – Wug Jun 19 '12 at 13:53