[JAVA] Find the Fibonacci number with the Fork / Join Framework

Let's find the Fibonacci number with the Fork / Join Framework.

What is the Fibonacci number?

[Fibonacci number-Wikipedia](https://ja.wikipedia.org/wiki/Fibonacci number)

The Fibonacci number (Fibonacci number) is named after the Italian mathematician Leonardo Fibonacci (Pisa's Leonardo).

Find the Fibonacci number

If the $ n $ th Fibonacci number is represented by $ F_n $, $ F_n $ is recursive.

$ F_0 = 0 $ $ F_1 = 1 $ $ F_{n+2} = F_n + F_{n+1}\quad(n\geqq1) $

It is defined by.

FibonacciTask.java

import java.util.concurrent.RecursiveTask;

public class FibonacciTask extends RecursiveTask<Integer> {
    private final int n;

    FibonacciTask(int n) {
        this.n = n;
    }

    @Override
    protected Integer compute() {
        if (n <= 1) {
            //If n is 0 or 1, return as is
            return n;
        }

        // n-Find the Fibonacci number for 1
        FibonacciTask f1 = new FibonacciTask(n - 1);
        f1.fork();

        // n-Find the Fibonacci number for 2
        FibonacciTask f2 = new FibonacciTask(n - 2);

        //Add the processing results to get the Fibonacci number of n
        return f2.compute() + f1.join();
    }
}

Main.java

import java.util.concurrent.ForkJoinPool;

public class Main {
    public static void main(String[] args) {
        ForkJoinPool pool = new ForkJoinPool();
        for (int n = 0; n < 40; n++) {
            int result = pool.invoke(new FibonacciTask(n));
            System.out.println("F[" + n + "]:" + result);
        }
    }
}

I will do it.

$ java Main
F[0]:0
F[1]:1
F[2]:1
F[3]:2
F[4]:3
F[5]:5
F[6]:8
F[7]:13
F[8]:21
F[9]:34
F[10]:55
F[11]:89
F[12]:144
F[13]:233
F[14]:377
F[15]:610
F[16]:987
F[17]:1597
F[18]:2584
F[19]:4181
F[20]:6765
F[21]:10946
F[22]:17711
F[23]:28657
F[24]:46368
F[25]:75025
F[26]:121393
F[27]:196418
F[28]:317811
F[29]:514229
F[30]:832040
F[31]:1346269
F[32]:2178309
F[33]:3524578
F[34]:5702887
F[35]:9227465
F[36]:14930352
F[37]:24157817
F[38]:39088169
F[39]:63245986

It's slow, so make a note of it.

FibonacciTask.java

import java.util.concurrent.RecursiveTask;
import java.util.Map;
import java.util.HashMap;

public class FibonacciTask extends RecursiveTask<Integer> {
    private final int n;

    private static Map<Integer, Integer> sequence = new HashMap<>();

    static {
        sequence.put(0, 0);
        sequence.put(1, 1);
    }

    FibonacciTask(int n) {
        this.n = n;
    }

    @Override
    protected Integer compute() {
        return sequence.computeIfAbsent(this.n, x -> fibonacci(this.n));
    }

    private static Integer fibonacci(int n) {
        // n-Find the Fibonacci number for 1
        FibonacciTask f1 = new FibonacciTask(n - 1);
        f1.fork();

        // n-Find the Fibonacci number for 2
        FibonacciTask f2 = new FibonacciTask(n - 2);

        //Add the processing results to get the Fibonacci number of n
        return f2.compute() + f1.join();
    }
}