2016-09-04 18:17:30 +00:00
|
|
|
// Ben Harris
|
2016-09-08 05:16:56 +00:00
|
|
|
// CS426 Collatz Assignment
|
2016-09-08 01:23:26 +00:00
|
|
|
|
2016-09-08 05:16:56 +00:00
|
|
|
class Collatz {
|
2016-09-08 17:46:05 +00:00
|
|
|
static final int one_mil = 1000000;
|
|
|
|
|
2016-09-08 01:23:26 +00:00
|
|
|
public static void main (String[] args) {
|
2016-09-08 05:16:56 +00:00
|
|
|
Curr curr = new Curr(1);
|
2016-09-08 22:07:59 +00:00
|
|
|
Prev prev = new Prev(new int[one_mil]);
|
|
|
|
Max max = new Max(0, 0);
|
|
|
|
CollatzCalc ccalc = new CollatzCalc(curr, prev, max);
|
|
|
|
|
|
|
|
int num_threads = args.length > 0 ? Integer.parseInt(args[0]) : 4;
|
|
|
|
Thread threads[] = new Thread[num_threads];
|
|
|
|
System.out.println("Starting " + num_threads + " thread(s)...");
|
|
|
|
|
|
|
|
for (int t = 0; t < num_threads; t++){
|
|
|
|
threads[t] = new Thread(ccalc);
|
|
|
|
threads[t].start();
|
2016-09-08 17:46:05 +00:00
|
|
|
}
|
2016-09-08 22:07:59 +00:00
|
|
|
try{
|
|
|
|
for (int t = 0; t < num_threads; t++)
|
|
|
|
threads[t].join();
|
|
|
|
} catch (InterruptedException ie) {}
|
2016-09-04 18:17:30 +00:00
|
|
|
|
2016-09-08 22:07:59 +00:00
|
|
|
System.out.println("Longest path was " + max.maxsteps + " steps for i=" + max.maxpos);
|
|
|
|
}
|
2016-09-08 05:16:56 +00:00
|
|
|
}
|
2016-09-04 18:17:30 +00:00
|
|
|
|
2016-09-08 17:46:05 +00:00
|
|
|
class CollatzCalc implements Runnable {
|
2016-09-09 16:36:28 +00:00
|
|
|
Curr curr; Prev prev; Max max; long tmp; int start, cnt; boolean keep_going;
|
2016-09-08 22:07:59 +00:00
|
|
|
|
|
|
|
public CollatzCalc (Curr curr, Prev prev, Max max) {
|
|
|
|
this.curr = curr;
|
|
|
|
this.prev = prev;
|
|
|
|
this.max = max;
|
2016-09-04 18:17:30 +00:00
|
|
|
}
|
|
|
|
|
2016-09-08 23:33:21 +00:00
|
|
|
public synchronized void run () {
|
2016-09-09 16:36:28 +00:00
|
|
|
while (true) {
|
2016-09-08 22:07:59 +00:00
|
|
|
synchronized (curr) {
|
2016-09-09 16:36:28 +00:00
|
|
|
keep_going = curr.curr <= Collatz.one_mil;
|
2016-09-08 22:07:59 +00:00
|
|
|
tmp = curr.curr;
|
|
|
|
start = curr.curr;
|
|
|
|
curr.curr++;
|
|
|
|
}
|
2016-09-09 16:36:28 +00:00
|
|
|
if (!keep_going) break;
|
2016-09-08 22:07:59 +00:00
|
|
|
|
|
|
|
cnt = 0;
|
2016-09-08 17:46:05 +00:00
|
|
|
while (tmp != 1) {
|
|
|
|
if (tmp < start){
|
2016-09-08 22:07:59 +00:00
|
|
|
synchronized (prev) {
|
|
|
|
cnt += prev.prev[(int)tmp];
|
|
|
|
}
|
2016-09-08 23:33:21 +00:00
|
|
|
break;
|
2016-09-08 17:46:05 +00:00
|
|
|
}
|
2016-09-08 23:33:21 +00:00
|
|
|
tmp = tmp%2 == 0 ? tmp/2 : 3*tmp + 1;
|
2016-09-08 17:46:05 +00:00
|
|
|
cnt++;
|
2016-09-08 05:16:56 +00:00
|
|
|
}
|
2016-09-08 23:33:21 +00:00
|
|
|
|
2016-09-08 22:07:59 +00:00
|
|
|
if (start < Collatz.one_mil) {
|
|
|
|
synchronized (prev) {
|
|
|
|
prev.prev[start] = cnt;
|
|
|
|
}
|
2016-09-04 18:17:30 +00:00
|
|
|
}
|
2016-09-08 22:07:59 +00:00
|
|
|
|
|
|
|
synchronized (max) {
|
|
|
|
if (cnt > max.maxsteps) {
|
|
|
|
max.maxpos = start;
|
2016-09-09 16:07:05 +00:00
|
|
|
max.maxsteps = cnt;
|
2016-09-08 22:07:59 +00:00
|
|
|
}
|
|
|
|
}
|
|
|
|
|
|
|
|
}
|
2016-09-04 18:17:30 +00:00
|
|
|
}
|
2016-09-08 05:16:56 +00:00
|
|
|
}
|
|
|
|
|
2016-09-08 22:07:59 +00:00
|
|
|
// current int that we're calculating
|
|
|
|
class Curr {
|
|
|
|
int curr;
|
2016-09-08 23:44:11 +00:00
|
|
|
Curr (int curr) { this.curr = curr; }
|
2016-09-08 22:07:59 +00:00
|
|
|
}
|
|
|
|
|
|
|
|
// cache of previous answers
|
|
|
|
class Prev {
|
|
|
|
int prev[];
|
2016-09-08 23:44:11 +00:00
|
|
|
Prev (int[] prev) { this.prev = prev; }
|
2016-09-08 22:07:59 +00:00
|
|
|
}
|
|
|
|
|
|
|
|
// max value and position
|
|
|
|
class Max {
|
|
|
|
int maxpos, maxsteps;
|
2016-09-08 23:44:11 +00:00
|
|
|
Max (int pos, int steps) { maxpos = pos; maxsteps = steps; }
|
2016-09-08 22:07:59 +00:00
|
|
|
}
|
|
|
|
|