Skip to content

Instantly share code, notes, and snippets.

@neojou
Last active July 22, 2017 22:52
Show Gist options
  • Save neojou/5169f550a33fb7175d2e to your computer and use it in GitHub Desktop.
Save neojou/5169f550a33fb7175d2e to your computer and use it in GitHub Desktop.
Java : calculate Fibonacci number by using Java's ForkJoinPool and RecursiveTask
/*
* 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());
}
}
}
/*
* 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));
}
}
/*
* 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));
}
}
@maxbisesi
Copy link

Can you help me understand your set_max method please ?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment