KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > Fib


1 import EDU.oswego.cs.dl.util.concurrent.*;
2
3
4 /**
5  * Recursive task-based version of Fibonacci. Computes:
6  * <pre>
7  * Computes fibonacci(n) = fibonacci(n-1) + fibonacci(n-2); for n> 1
8  * fibonacci(0) = 0;
9  * fibonacci(1) = 1.
10  * </pre>
11  **/
12
13 public class Fib extends FJTask {
14
15   // Performance-tuning constant:
16 static int sequentialThreshold = 0;
17   
18   public static void main(String JavaDoc[] args) {
19     try {
20       int procs;
21       int num;
22       try {
23         procs = Integer.parseInt(args[0]);
24         num = Integer.parseInt(args[1]);
25         if (args.length > 2) sequentialThreshold = Integer.parseInt(args[2]);
26       }
27       catch (Exception JavaDoc e) {
28         System.out.println("Usage: java Fib <threads> <number> [<sequntialThreshold>]");
29         return;
30       }
31
32       FJTaskRunnerGroup g = new FJTaskRunnerGroup(procs);
33       Fib f = new Fib(num);
34       g.invoke(f);
35       g.stats();
36
37       long result = f.getAnswer();
38       System.out.println("Fib: Size: " + num + " Answer: " + result);
39     }
40     catch (InterruptedException JavaDoc ex) {}
41   }
42
43
44   // Initialized with argument; replaced with result
45 volatile int number;
46
47   Fib(int n) { number = n; }
48
49   int getAnswer() {
50     if (!isDone()) throw new Error JavaDoc("Not yet computed");
51     return number;
52   }
53
54
55   public void run() {
56     int n = number;
57
58     // Handle base cases:
59 if (n <= 1) {
60       // Do nothing: fib(0) = 0; fib(1) = 1
61 }
62     // Use sequential code for small problems:
63 else if (n <= sequentialThreshold) {
64       number = seqFib(n);
65     }
66     // Otherwise use recursive parallel decomposition:
67 else {
68       // Construct subtasks:
69 Fib f1 = new Fib(n - 1);
70       Fib f2 = new Fib(n - 2);
71       
72       // Run them in parallel:
73 coInvoke(f1, f2);
74       
75       // Combine results:
76 number = f1.number + f2.number;
77       // (We know numbers are ready, so directly access them.)
78 }
79   }
80
81   // Sequential version for arguments less than threshold
82 static int seqFib(int n) {
83     if (n <= 1)
84       return n;
85     else
86       return seqFib(n-1) + seqFib(n-2);
87   }
88
89 }
90
91
Popular Tags