CIT 594 Assignment 10: ForkJoin

Spring 2012, David Matuszek

- Get you started with Java's
`ForkJoin`

.

Randomly generate one million (x, y) points, where 0.0 <= x < 1.0 and 0.0 <= y 1.0, and `x`

and `y`

are of type `double`

. Then find and print out the two *closest* points, along with the distance between them.

Do this as quickly as possible, and print out the time required in seconds, as a floating point number.

Use `ForkJoin`

. If you have a dual-core or quad-core computer, this should make your program about 2x or 4x faster. If you don't, using `ForkJoin`

will slow things down slightly--but use it anyway!

Since I need to be able to check if you got the right answer, I need some control over the "random" points you generate. So I would like you to generate them exactly as follows:

- Ask the user to input an integer.
- Use the integer as the seed to your random number generator. That is,
`static Random rand = new Random(seed)`

; Do this*only once*, at the beginning of the program. - Generate points as follows:
- The first random number is the
`x`

value of the first point. - The second random number is the
`y`

value of the first point. - The third random number is the
`x`

value of the second point. - The fourth random number is the
`y`

value of the second point. - The fifth random number is the
`x`

value of the third point. - Etc.

- The first random number is the

Nothing beats a good algorithm.

On my home computer (2.8 GHz quad core), using a sequential program to compare every point against every other point, I got the following numbers:

- 100,000 points took 142 seconds.
- 66,000 points took approximately 1 minute.

But obviously some pairs of points are so far apart that you don't even need to consider them. I used a simple trick to eliminate many of these pairs, and got the following timings:

- 100,000 points took approximately 0.2 seconds.
- 1,000,000 points took approximately 10 seconds.

Using `ForkJoin`

gave me approximately another 4x speedup.

How do you know you have the correct answer?

Comparing every point against every other point is really simple, and you can probably write that without error. Test it for a small number of points, say, 1000. Then see if your fancier algorithm gives the same answer.

Your program is due before **6am Tuesday, April 17.** * Zip* up the entire
directory for this project, and submit via Blackboard.

Because many of you are interviewing this semester, a limited number of 48-hour extensions will be available. To get an extension, email me before 5pm Friday, stating the reason you need the extension. No extensions will be granted after Friday. If you get an extension and fail to get the project in by the extended due date, late points will be counted from the original due date.