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();
Thread[] threads = new Thread[32];
for (int i = 0; i < threads.length; i++) {
threads[i] = new Thread(new Main((i * 2) + 1, threads.length * 2));
}
for (Thread thread : threads) {
thread.start();
}
for (Thread thread : threads) {
thread.join();
}
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;
}
}
System.out.printlnwill probably help... maybe use aStringBuilderto create the output and then print the entire thing at the very end? (idk, I've never done it before) \$\endgroup\$