Created
October 25, 2018 22:07
-
-
Save sp4ce/464d749745f5dcc1029765c99950f209 to your computer and use it in GitHub Desktop.
Java utility to compute n-step fibonacci suite
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
package com.croutard; | |
import java.math.BigDecimal; | |
import java.math.BigInteger; | |
import java.util.ArrayList; | |
import java.util.Arrays; | |
import java.util.Collection; | |
import java.util.HashMap; | |
import java.util.LinkedList; | |
import java.util.List; | |
import java.util.Map; | |
import java.util.Queue; | |
public class Fibo | |
{ | |
private static final BigDecimal ZERO = new BigDecimal("0"); | |
private static final BigDecimal ONE = new BigDecimal("1"); | |
private static final BigDecimal TWO = new BigDecimal("2"); | |
private static final List<BigDecimal> SEED = Arrays.asList(ZERO, ONE); | |
private static final Map<Integer, List<BigDecimal>> SEED_CACHE = new HashMap<>(); | |
private static final Integer ORDER_2 = 2; | |
private static Queue<BigDecimal> fibo(Queue<BigDecimal> values, int n) | |
{ | |
for (int i = 0; i < n; i++) { | |
BigDecimal next_value = sum(values); | |
values.poll(); | |
values.add(next_value); | |
} | |
return values; | |
} | |
private static List<BigDecimal> fibo(List<BigDecimal> values, int n, int k) | |
{ | |
for (int i = 0; i < n; i++) { | |
values.add(sum(values.subList(values.size() - k, values.size()))); | |
} | |
return values; | |
} | |
private static List<BigDecimal> seed(int k) | |
{ | |
List<BigDecimal> seed = new ArrayList<>(); | |
for (int i = 0; i < k; i++) { | |
seed.add(fibo(k - 1, i)); | |
} | |
return seed; | |
} | |
private static BigDecimal fibo(int k, int n) | |
{ | |
if (k == ORDER_2) { | |
//System.out.println("n: " + n); | |
List<BigDecimal> values = fibo(new ArrayList<>(SEED), n, ORDER_2); | |
return values.get(values.size() - 1); | |
} | |
List<BigDecimal> seed; | |
if (!SEED_CACHE.containsKey(k)) { | |
SEED_CACHE.put(k, seed(k)); | |
} | |
seed = SEED_CACHE.get(k); | |
return fibo(new LinkedList<>(seed), n).peek(); | |
} | |
private static BigDecimal sum(Collection<BigDecimal> values) | |
{ | |
return values.parallelStream().reduce(BigDecimal::add).get(); | |
} | |
public static void main(String[] args) | |
{ | |
int n = 10; | |
int k = 3; | |
System.out.println("fibo_k(n+2):" + fibo(k, n + 2)); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment