patternjavaMinor
Speeding up 3n+1 challenge
Viewed 0 times
speedingchallengestackoverflow
Problem
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 (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 > 1;
}
}
return hi;
}
}
Solution
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" "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.
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.
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" "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 (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 > 1; // n even
} else {
j = 3 * j + 1; // n odd
if (hi > 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 (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 > 1; // n even
} else {
j = 3 * j + 1; // n odd
if (hi > 1;
}
}
return hi;
}
}Code Snippets
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;
}
}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;
}
}Context
StackExchange Code Review Q#12715, answer score: 4
Revisions (0)
No revisions yet.