[concurrency-interest] Fork/Join Examples

Dr Heinz M. Kabutz heinz at javaspecialists.eu
Thu May 24 18:33:57 EDT 2012

In my latest newsletter, I show two examples how we can solve a problem 
faster using Fork/Join.  The first is Fibonacci, but a better recursive 
algorithm than is found in the JavaDocs.  However, this sum-of-squares 
algorithm requires us to do multiplication which is particularly bad 
with BigInteger.  I thus also implemented the Karatsuba multiplication 
algorithm, including a way to do it with the Fork/Join framework.

I also implemented a FibonacciCache.  I believe that caching should 
maybe be solved in general for the recursive decomposition approach with 
RecursiveTask.  In my cache, if one thread tries to do work with which 
another thread is already busy, then he waits until the other thread has 
completed his task.  This prevents duplication of work.  I bet that this 
is a common problem with recursive decomposition algorithms.  Have any 
of you thought of writing a cache that solves this problem in general 
and then making that available in the JDK?

Also, could we *please* change the example in the RecursiveTask 
JavaDocs.  It is embarrassing having an exponential algorithm as an 
example of how you would use RecursiveTask.  So if we add 1000x the 
number of processors, we can now solve case n+10?

Here is a direct link to the newsletter for those who are interested: 


Dr Heinz M. Kabutz (PhD CompSci)
Author of "The Java(tm) Specialists' Newsletter"
Sun Java Champion
IEEE Certified Software Development Professional
Tel: +30 69 75 595 262
Skype: kabutz

More information about the Concurrency-interest mailing list