Java Variations on Fibonacci

fibonacci.java

import java.util.function.LongFunction;

// fibR, fibRM and fibT are the Java equivalents of
// https://youtu.be/oBt53YbR9Kk (10.12.2020)

try {
    assert false;
} catch (AssertionError e) {
    System.out.println("Cool, assertions are enabled!");
}

long[] data = {0, 1, 1, 2, 3, 5, 8, 13, 21, 34};

// fib recursion: O(2^n) time, O(n) space
long fibR(int n) {
    if (n <= 1) return n;
    return fibR(n - 1) + fibR(n - 2);
}

assert IntStream.range(0, data.length).noneMatch(n -> fibR(n) != data[n]) : "fibR";
System.out.println("fibR(40) = " + fibR(40));
// fibR(40) causes a noticeable delay
// fibR(50) doesn't return in a reasonable amount of time

// fib memoization with an array: O(n) time, O(n) space
long fibA(int n, long[] hashMap) {
    if (n <= 1) return n;
    if (hashMap[n] != 0) return hashMap[n];
    hashMap[n] = fibA(n - 1, hashMap) + fibA(n - 2, hashMap);
    return hashMap[n];
}

long fibAcall(int n) {
    return fibA(n, new long[n + 1]);
}

assert IntStream.range(0, data.length).noneMatch(n -> fibAcall(n) != data[n]) : "fibAcall";
System.out.println("fibA(40) = " + fibAcall(40));


// fib memoization: O(n) time, O(n) space
long fibM(int n, Map<Integer,Long> memo) {
    return memo.computeIfAbsent(n,
        num -> num <= 1 ? num : fibM(num - 1, memo) + fibM(num - 2, memo));
}

long fibMcall(int n) {
    return fibM(n, new ConcurrentSkipListMap<Integer,Long>());
}

assert IntStream.range(0, data.length).noneMatch(n -> fibMcall(n) != data[n]) : "fibMcall";
System.out.println("fibM(40) = " + fibMcall(40));
// - recursion requires a concurrent hashmap
// - ConcurrentMap is not scaleable, that's why ConcurrentSkipListMap is used
// - fib(50) is no big deal

// fib tabulation: O(n) time, O(n) space (the array is the space)
long fibT(int n) {
    long[] table = new long[n + 2];
    table[1] = 1L;
    for (int i = 0; i < n; i++) {
        table[i + 1] += table[i];
        table[i + 2] += table[i];
    }
    return table[n];
}

assert IntStream.range(0, data.length).noneMatch(n -> fibT(n) != data[n]) : "fibT";
System.out.println("fibT(40) = " + fibT(40));

// fib on steroids: O(n) time, O(2) space
long fibS(int n) {
    int j = 0, i = n == 0 ? 0 : 1;
    while (n-- >= 2) i = j + (j = i);
    return i;
}

assert IntStream.range(0, data.length).noneMatch(n -> fibS(n) != data[n]) : "fibS";
System.out.println("fibS(40) = " + fibS(40));

class Fib implements Iterator<Long> {
    long i = 1, j = 0;
    public boolean hasNext() { return true; }
    public Long next() { return i = j + (j = i); }
}

Supplier<LongStream> fibSupplier = () -> 
    LongStream.concat(LongStream.of(0, 1),
                      LongStream.generate(new Fib()::next));

LongFunction fibLambda = n -> fibSupplier.get().skip(n).findFirst().getAsLong();

assert IntStream.range(0, data.length).noneMatch(n -> !fibLambda.apply(n).equals(data[n])) : "fibLambda";
System.out.println("fibLambda(40) = " + fibLambda.apply(40));

Dies ist eine weitere Variante (hier mit BigInteger), die eine gute Ergänzung zu den Variationen ist.

Stream<BigInteger> fib() {
    return Stream.iterate(List.of(BigInteger.ZERO, BigInteger.ONE),
                          l -> List.of(l.get(1), l.get(0).add(l.get(1))))
                .map(l -> l.get(0));
}