Java Fibonacci examples
Fibonacci number – Every number after the first two is the sum of the two preceding.
Few Java examples to find the Fibonacci numbers.
1. Java 8 stream
1.1 In Java 8, we can use Stream.iterate
to generate Fibonacci numbers like this :
Stream.iterate(new int[]{0, 1}, t -> new int[]{t[1], t[0] + t[1]})
.limit(10)
.forEach(x -> System.out.println("{" + x[0] + "," + x[1] + "}"));
Output
{0,1}
{1,1}
{1,2}
{2,3}
{3,5}
{5,8}
{8,13}
{13,21}
{21,34}
{34,55}
P.S Review the above output, the first value is what we wanted.
1.2 Final version.
Stream.iterate(new int[]{0, 1}, t -> new int[]{t[1], t[0] + t[1]})
.limit(10)
.map(t -> t[0])
.forEach(x -> System.out.println(x));
Output
0
1
1
2
3
5
8
13
21
34
1.3 Sum all the Fibonacci numbers
int sum = Stream.iterate(new int[]{0, 1}, t -> new int[]{t[1], t[0] + t[1]})
.limit(10)
.map(t -> t[0])
.mapToInt(Integer::intValue)
.sum();
System.out.println("Total : " + sum);
Output
Total : 88
1.4 Join with commas.
String collect = Stream.iterate(new int[]{0, 1}, t -> new int[]{t[1], t[0] + t[1]})
.limit(10)
.map(t -> t[0])
.map(String::valueOf) // convert to string
.collect(Collectors.joining(", "));
System.out.println("Result : " + collect);
Output
Result : 0, 1, 1, 2, 3, 5, 8, 13, 21, 34
1.5 A function to create a List of Fibonacci numbers.
package com.mkyong.concurrency;
import java.util.List;
import java.util.stream.Stream;
import static java.util.stream.Collectors.toList;
public class Fibonacci {
public static List<Integer> getFibonacci(int series) {
return Stream.iterate(new int[]{0, 1}, t -> new int[]{t[1], t[0] + t[1]})
.limit(series)
.map(n -> n[0])
.collect(toList());
}
public static void main(String[] args) {
List<Integer> fibonacci = getFibonacci(10);
fibonacci.forEach(x -> System.out.println(x));
}
}
Output
0
1
1
2
3
5
8
13
21
34
1.6 The type int
and long
are not enough to store larger Fibonacci numbers. Below is the BigInteger
example to find the first million Fibonacci numbers.
package com.mkyong.concurrency;
import java.math.BigInteger;
import java.util.stream.Stream;
public class Fibonacci {
public static BigInteger getFibonacci(int series) {
return Stream.iterate(new BigInteger[]{
BigInteger.ZERO, BigInteger.ONE}, t -> new BigInteger[]{t[1], t[0].add(t[1])})
.limit(series)
.map(n -> n[1]) // find, we need n[1]
.reduce((a, b) -> b).orElse(BigInteger.ZERO);
}
public static void main(String[] args) {
System.out.println(Fibonacci.getFibonacci(1_000_000));
}
}
Output
1953282128707757731632014947596256332443... // 208,988 digits!!!, too long to display here
2. Recursive Loop
2.1 Java recursive loop example to create a list of Fibonacci numbers. Good to demo only, this recursive loop is slow.
package com.mkyong.concurrency;
public class Fibonacci {
public static int fib(int n) {
if (n <= 1) return n;
else return fib(n - 1) + fib(n - 2);
}
public static void main(String[] args) {
for (int i = 0; i < 10; i++) {
System.out.println(fib(i));
}
}
}
Output
0
1
1
2
3
5
8
13
21
34
2.2 How it works?
fib(n) = fib(n - 1) + fib(n - 2);
fib(5) = fib(4) + fib(3);
fib(4) = fib(3) + fib(2);
fib(3) = fib(2) + fib(1);
fib(2) = fib(1) + fib(0);
fib(1) = 1
fib(0) = 1
3. Normal Loop
3.1 Java normal loop to find the Fibonacci numbers, simple and easy.
package com.mkyong.concurrency;
import java.math.BigInteger;
public class Fibonacci {
public static int fib(int n) {
if (n <= 1) return n;
int previous = 0, next = 1, sum;
for (int i = 2; i <= n; i++) {
sum = previous;
previous = next;
next = sum + previous;
}
return next;
}
public static BigInteger fib2(int n) {
if (n <= 1) return BigInteger.valueOf(n);
BigInteger previous = BigInteger.ZERO, next = BigInteger.ONE, sum;
for (int i = 2; i <= n; i++) {
sum = previous;
previous = next;
next = sum.add(previous);
}
return next;
}
public static void main(String[] args) {
for (int i = 0; i < 10; i++) {
System.out.println(fib(i));
}
System.out.println("---");
for (int i = 0; i < 10; i++) {
System.out.println(fib2(i));
}
System.out.println("---");
System.out.println(fib(100)); //overflow
System.out.println(fib2(100));
}
}
Output
0
1
1
2
3
5
8
13
21
34
---
0
1
1
2
3
5
8
13
21
34
---
-980107325
354224848179261915075
Please use
BigInteger
to store the Fibonacci numbers to avoid an overflow issue.
int num = 8;
int[] fib = new int[num];
Stream.iterate(0, n->n+1)
.limit(num)
.forEach(x-> {
fib[x] = x<2? x: fib[x-2] + fib[x-1];
System.out.println(fib[x]);
})
Is there a way to update the stream example to find if a number that is passed in is a fibonacci number? So instead of defining a limit value on the stream, you pass in an integer to test (e.g. 53 or 55, where 53 is not a fibonacci number & 55 is a fibonacci number).
int givenNumber=55;
System.out.println(” Given number is Present in Fibonacci series –> “+Stream.iterate( new int[]{0,1} , t -> new int[]{t[1],t[0]+t[1]}).limit(100).map(j -> j[0])
.filter( j -> Arrays.asList(j).contains(givenNumber)).findFirst());
This produces the output if the given number is present in the fibonacci series else empty .