Skip to content

Instantly share code, notes, and snippets.

@sp4ce
Created October 25, 2018 22:07
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save sp4ce/464d749745f5dcc1029765c99950f209 to your computer and use it in GitHub Desktop.
Save sp4ce/464d749745f5dcc1029765c99950f209 to your computer and use it in GitHub Desktop.
Java utility to compute n-step fibonacci suite
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