[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
More information about the Concurrency-interest