Last active
July 22, 2017 22:52
-
-
Save neojou/5169f550a33fb7175d2e to your computer and use it in GitHub Desktop.
Java : calculate Fibonacci number by using Java's ForkJoinPool and RecursiveTask
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
* To change this license header, choose License Headers in Project Properties. | |
* To change this template file, choose Tools | Templates | |
* and open the template in the editor. | |
*/ | |
package neo.app; | |
import java.math.BigInteger; | |
import java.util.concurrent.*; | |
class Fibonacci extends RecursiveTask<BigInteger> { | |
final long n; | |
public static BigInteger[] result = new BigInteger[2]; | |
public static int max_num = 1; | |
public static final BigInteger zero = new BigInteger("0"); | |
public static void set_max(int num) { | |
result[0] = new BigInteger("0"); | |
result[1] = new BigInteger("1"); | |
if ( num > max_num ) { | |
BigInteger[] new_result = new BigInteger[num+1]; | |
for (int i=0; i<=max_num; i++) { | |
new_result[i] = result[i]; | |
} | |
result = new_result; | |
for (int i=max_num+1; i<=num; i++) { | |
result[i] = new BigInteger("-1"); | |
} | |
max_num = num; | |
} | |
} | |
Fibonacci(long n) { | |
this.n = n; | |
if ( n > 1 ) | |
set_max((int)n); | |
} | |
public BigInteger compute() { | |
BigInteger ret; | |
if ( result[(int)n].compareTo(zero) > 0 ) { | |
return result[(int)n]; | |
} | |
if (n<=10) { | |
return do_fibonacci(n); | |
} | |
ForkJoinTask<BigInteger> subTask = new Fibonacci(n-1).fork(); | |
ret = new Fibonacci(n-2).compute().add( subTask.join() ); | |
result[(int)n] = new BigInteger(ret.toString()); | |
return ret; | |
} | |
static BigInteger do_fibonacci(long n) { | |
BigInteger ret; | |
if ( result[(int)n].compareTo(zero) >= 0 ) { | |
ret = result[(int)n]; | |
} else { | |
BigInteger ret_n_1 = do_fibonacci(n-1); | |
BigInteger ret_n_2 = do_fibonacci(n-2); | |
ret = new BigInteger(ret_n_1.add(ret_n_2).toString()); | |
result[(int)n] = ret; | |
} | |
return ret; | |
} | |
} | |
/** | |
* | |
* @author neojou | |
*/ | |
public class FibonacciForkJoin { | |
/** | |
* @param args the command line arguments | |
*/ | |
public static void main(String[] args) { | |
for (int i=2; i<=300; i++) { | |
Fibonacci fibonacci = new Fibonacci(i); | |
ForkJoinPool pool = new ForkJoinPool(); | |
System.out.printf("%d : ", i); | |
System.out.println(pool.invoke(fibonacci).toString()); | |
} | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
* To change this license header, choose License Headers in Project Properties. | |
* To change this template file, choose Tools | Templates | |
* and open the template in the editor. | |
*/ | |
package neo.app; | |
import java.util.concurrent.*; | |
class Fibonacci extends RecursiveTask<Long> { | |
final long n; | |
Fibonacci(long n) { | |
this.n = n; | |
} | |
public Long compute() { | |
if (n<=10) { | |
return do_fibonacci(n); | |
} | |
ForkJoinTask<Long> subTask = new Fibonacci(n-1).fork(); | |
return new Fibonacci(n-2).compute() + subTask.join(); | |
} | |
static long do_fibonacci(long n) { | |
if ( n<=1 ) return n; | |
return do_fibonacci(n-1) + do_fibonacci(n-2); | |
} | |
} | |
/** | |
* | |
* @author neojou | |
*/ | |
public class FibonacciForkJoin { | |
/** | |
* @param args the command line arguments | |
*/ | |
public static void main(String[] args) { | |
Fibonacci fibonacci = new Fibonacci(45); | |
ForkJoinPool pool = new ForkJoinPool(); | |
System.out.println(pool.invoke(fibonacci)); | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
* To change this license header, choose License Headers in Project Properties. | |
* To change this template file, choose Tools | Templates | |
* and open the template in the editor. | |
*/ | |
package neo.app; | |
import java.util.concurrent.*; | |
class Fibonacci extends RecursiveTask<Long> { | |
final long n; | |
public static Long[] result = new Long[2]; | |
public static int max_num = 1; | |
public static void set_max(int num) { | |
result[0] = new Long(1); | |
result[1] = new Long(1); | |
if ( num > max_num ) { | |
Long[] new_result = new Long[num+1]; | |
for (int i=0; i<=max_num; i++) { | |
new_result[i] = result[i]; | |
} | |
result = new_result; | |
for (int i=max_num+1; i<=num; i++) { | |
result[i] = new Long(0); | |
} | |
max_num = num; | |
} | |
} | |
Fibonacci(long n) { | |
this.n = n; | |
if ( n > 1 ) | |
set_max((int)n); | |
} | |
public Long compute() { | |
Long ret; | |
if ( result[(int)n].longValue() != 0 ) { | |
return result[(int)n]; | |
} | |
if (n<=10) { | |
return do_fibonacci(n); | |
} | |
ForkJoinTask<Long> subTask = new Fibonacci(n-1).fork(); | |
ret = new Fibonacci(n-2).compute() + subTask.join(); | |
result[(int)n] = new Long(ret); | |
return ret; | |
} | |
static long do_fibonacci(long n) { | |
long ret; | |
if (result[(int)n].longValue() != 0) { | |
ret = result[(int)n].longValue(); | |
} else { | |
long ret_n_1 = do_fibonacci(n-1); | |
long ret_n_2 = do_fibonacci(n-2); | |
ret = ret_n_1 + ret_n_2; | |
result[(int)n] = new Long(ret); | |
} | |
return ret; | |
} | |
} | |
/** | |
* | |
* @author neojou | |
*/ | |
public class FibonacciForkJoin { | |
/** | |
* @param args the command line arguments | |
*/ | |
public static void main(String[] args) { | |
Fibonacci fibonacci = new Fibonacci(100); | |
ForkJoinPool pool = new ForkJoinPool(); | |
System.out.println(pool.invoke(fibonacci)); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Can you help me understand your set_max method please ?