Calculating Fibonacci numbers with Map#computeIfAbsent

[Campbell Ritchie]

So we look in Ken Kousen's book (page 123) and it tells you about the Map#computeIfAbsent(), and there is an example for calculating Fibonacci numbers. So I tried it on the train yesterday, where I didn't have any internet connection and I thought I couldn't check the documentation:-

private Map<Long, BigInteger> cache = new HashMap<>();
    
public AbsentFibonacciDemo()
{
    cache = new HashMap<>();
}
    
private BigInteger fib(long i)
{
    if (i == 0) return BigInteger.ZERO;
    if (i == 1) return BigInteger.ONE;
        
    return cache.computeIfAbsent(i, n -> fib(n - 2).add(fib(n - 1)));
}
    
public void computeAndShowNumbers()
{
    Scanner inScan = new Scanner(System.in);
    long input;
    while ((input = inScan.nextLong()) >= 0)
    {
        System.out.printf("fib(%d) = %d%n", input, fib(input));
    }
}

So let's try a nice big number and see if we can't calculate Fibonacci numbers up to it:-

java AbsentFibonacciDemo
1000000
Exception in thread "main" java.lang.StackOverflowError
at java.base/java.lang.Long.hashCode(Long.java:1404)

Surprise, surprise. At least the stack trace wasn't 1,000,000 lines long So let's try a smaller number:-

java AbsentFibonacciDemo
2000

Exception in thread "main" java.util.ConcurrentModificationException
at java.base/java.util.HashMap.computeIfAbsent(HashMap.java:1138)
at AbsentFibonacciDemo.fib(AbsentFibonacciDemo.java:25)
at AbsentFibonacciDemo.lambda$fib$0(AbsentFibonacciDemo.java:25)
at java.base/java.util.HashMap.computeIfAbsent(HashMap.java:1137)
at AbsentFibonacciDemo.fib(AbsentFibonacciDemo.java:25)
at AbsentFibonacciDemo.lambda$fib$0(AbsentFibonacciDemo.java:25)
at java.base/java.util.HashMap.computeIfAbsent(HashMap.java:1137)
at AbsentFibonacciDemo.fib(AbsentFibonacciDemo.java:25)

java AbsentFibonacciDemo
0
fib(0) = 0
1
fib(1) = 1
2
fib(2) = 1
3
fib(3) = 2
4
fib(4) = 3
5
fib(5) = 5
6
fib(6) = 8
7
fib(7) = 13
8
fib(8) = 21
9
fib(9) = 34
10
fib(10) = 55
11
fib(11) = 89
-1

Which appears to mean you can't calculate big Fibonacci numbers like that. Only a key one larger than the preceding keys in the Map. So today I went to look in the documentation (link above) and it seems the computeIfAbsent method is intended for computing a single value to be put into the Map; since the method I was using would appear to be attempting to put multiple values into the Map, that isn't allowed and any attempt would appear to require a concurrent modification exception be thrown.
I haven't checked whether computeIfPresent also only calculates a single value: Let's look. Yes, it does:

That API link (computeIfPresent) wrote:The remapping function should not modify this map during computation. . . . Non-concurrent implementations should override this method and, on a best-effort basis, throw a ConcurrentModificationException if it is detected

Isn't that in line with the conventions of functional programming? Altering the Map anywhere else would constitute a side effect and side effects are to be avoided.

[Sean Corfield]

In Functional Programming, you wouldn’t be updating in place — your hash map would be immutable — so there wouldn’t be any concurrency issues to avoid.

[Pierre-Yves Saumont]

Not sure what the question is (I can't reproduce the ConcurrentModificationException), but it will not work anyway since Java recursion is extremely limited. Using corecursion through TCE is not possible neither, but it is possible with Stream (and of course with a simple loop!). Here is a quick and dirty working corecursive version using Stream:

import java.math.BigInteger;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
import java.util.stream.Stream;

public class AbsentFibonacciDemo2 {

  private Map<Long, Pair> cache = new HashMap<>();

  AbsentFibonacciDemo2() {
    cache.put(-1L, new Pair(1, BigInteger.ZERO, BigInteger.ONE));
  }

  private Pair fib(long i) {
    if (i == 0) return new Pair(0, BigInteger.ZERO, BigInteger.ZERO);
    if (i == 1) return new Pair(0, BigInteger.ZERO, BigInteger.ONE);

    return cache.computeIfAbsent(i, (Long n) -> {
      Pair pmax =  cache.get(-1L);
      long max = pmax.n;
      Pair result = Stream.iterate(pmax, p -> {
        Pair p2 = new Pair(p.n + 1, p.second, p.first.add(p.second));
        cache.put(p2.n, p2);
        return p2;
      }).skip(i - max).findAny().get();
      cache.put(-1L, result);
      return result;
    });
  }

  public BigInteger compute(long n)  {
    return fib(n).second;
  }

  static class Pair {
    final long n;
    final BigInteger first;
    final BigInteger second;

    Pair(long n, BigInteger first, BigInteger second) {
      this.n = n;
      this.first = first;
      this.second = second;
    }
  }

  static class Result {
    final BigInteger result;
    final  Map<Long, Pair> memoMap;

    Result(BigInteger result, Map<Long, Pair> memoMap) {
      this.result = result;
      this.memoMap = memoMap;
    }
  }

  public static void main(String... args) {
    Scanner inScan = new Scanner(System.in);
    long input;
    AbsentFibonacciDemo2 fib = new AbsentFibonacciDemo2();
    while ((input = inScan.nextLong()) >= 0) {
      System.out.printf("fib(%d) = %d%n", input, fib.compute(input));
    }
  }
}

[Campbell Ritchie]

SC: Yes, isn't that why you would only compute one value at a time. I am not sure a Java® Map would be immutable because the computeIfAbset methpd puts a new Entry into the Map.
P-YS: I was wondering about whether it was possible to calculate lots of Fibonacci numbers like that; if I start with 2 and go up one at a time, I get Fibonacci numbers printed. If I leave a gap inthe sequence however (e.g. 5→7 without using 6 first), I got that exception.
I am going to have to take some time to study your code. Thank you. I think however, you are iterating from the pairs already in the Map, in which case you would be avoiding any gaps. You get the exception if you have any gaps between the current size of the Map and the new value of input.

[Pierre-Yves Saumont]

Yes, I think I understand that, but I can't reproduce it. Whatever value I use for input, it works except for the StackOverflow problem.

[Pierre-Yves Saumont]

By the way, I fixed a bug in my code. (I was not using the map!)

[Piet Souris]

With Campbells code, you can get the fib for much larger values if you build up the cache slowly.
For instance:

public static void computeAndShowNumbers() {
    LongStream.rangeClosed(0, 40)
            .map(i -> 1000 * i)
            .forEach(i -> System.out.format("fib(%,d) = %,d%n", i, fib(i)))
    ;
}

[Campbell Ritchie]

Yes, that's what I said; if you go up one at a time you don't suffer any exceptions.

By the way: that code is copied with very few changes from Ken Kousen's book; I'm not clever enough to work it out for myself.

[Pierre-Yves Saumont]

@Piet Yes, this effect may be observed with some recursive calls. But it will not work for really high values.

[Pierre-Yves Saumont]

@Piet Sorry, I did not read the code fully. You example is no longer recursive. Using forEach is like using a loop. I was thinking of the recursive example, if you ask for values incremented by one, the StackOverflowException may occur much later.

[Pierre-Yves Saumont]

@Sean Using an immutable map, you would have to store it somewhere, which means a mutable reference to a map. Or you can pass the map along with the number, and get back a map. Then you can extract the value from the map and ask for a new value passing the map along.

This would either mean that your successive calls are chained, or that they are made from a non functional program. Here his an example where the program is functional (although it is a simulation with a mutable map, but it would work just the same with an immutable one). Only the user (here the main method) is not functional:

import java.math.BigInteger;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
import java.util.stream.Stream;

public class AbsentFibonacciDemo {


  private Map<Long, Pair> compute(long i, Map<Long, Pair> cache) {

    cache.computeIfAbsent(i, (Long n) -> {
      Pair pmax =  cache.get(-1L);
      long max = pmax.n;
      Pair result = Stream.iterate(pmax, p -> {
        Pair p2 = new Pair(p.n + 1, p.second, p.first.add(p.second));
        cache.put(p2.n, p2);
        return p2;
      }).skip(i - max).findAny().get();
      cache.put(-1L, result);
      return result;
    });
    return cache;
  }

  static class Pair {
    final long n;
    final BigInteger first;
    final BigInteger second;

    Pair(long n, BigInteger first, BigInteger second) {
      this.n = n;
      this.first = first;
      this.second = second;
    }
  }

  static class Result {
    final BigInteger result;
    final  Map<Long, Pair> memoMap;

    Result(BigInteger result, Map<Long, Pair> memoMap) {
      this.result = result;
      this.memoMap = memoMap;
    }
  }

  public static void main(String... args) {
    Scanner inScan = new Scanner(System.in);
    long input;
    AbsentFibonacciDemo fib = new AbsentFibonacciDemo();
    Map<Long, Pair> cache = new HashMap<>();
    cache.put(-1L, new Pair(1, BigInteger.ZERO, BigInteger.ONE));
    cache.put(0L, new Pair(0, BigInteger.ZERO, BigInteger.ZERO));
    cache.put(1L, new Pair(1, BigInteger.ZERO, BigInteger.ONE));
    while ((input = inScan.nextLong()) >= 0) {
      cache = fib.compute(input, cache);
      System.out.printf("fib(%d) = %d%n", input, cache.get(input).second);
    }
  }
}

[Piet Souris]

My example was only meant to show that building up the cache slowly would allow for much larger values. I got to fib(164.000) before I got an OOM error.

[Piet Souris]

@Pierre-Yves
Thanks for this code, it looks pretty impressive at first sight.

But if you compare this code with Campbells code, isn't the price for working with an immutable map not pretty high (in terms of complexity of the code)? (I wanted to ask a similar question like this on the forum about your book, but did not get to that unfortunately).

[Sean Corfield]

It’s instructive to compare those Java versions with three (very short, simple) Clojure versions in this article: http://blog.klipse.tech/clojurescript/2016/04/20/fibonacci.html

[Pierre-Yves Saumont]

@Piet  The cost is not very high but the benefit is null.  Of course, here you have to populate the map with three values. But this could be encapsulated in a FibCache class. So the only cost would be to get the initial FibCache and store it between successive calls. What are the benefits? In fact, there are none because either you share the cache, allowing other threads to benefit from the already computed values, but requiring synchronization of the cache, or you don't share the cache and you get the same result as when using a mutable map and not sharing the AbsentFibonacciDemo instance.

It is a common mistake to think that using immutable data structures makes sharing mutable state safer or easier. Immutable data structures prevent unintentional sharing of mutable state. This is fine when you don't need to share state. It makes sure you don't accidentally share mutable state. But it make sharing mutable state much more difficult. One solution, although not a functional one, is to use an actor framework which encapsulates access serialization and safe state mutation. It is not functional, but it fits nicely with functional programming. (This is chapter 14 of my book.)

[Pierre-Yves Saumont]

@Sean Fibonacci in Kotlin:

fun main(args: Array<String>) {
    (0 .. 1000).forEach { println(fibo(it)) }
    println(fibo(100_000))

}

fun fibo(n: Int) = when (n) {
    0 -> BigInteger.ZERO
    else -> generateSequence(Pair(BigInteger.ZERO, BigInteger.ONE))
            { Pair(it.second, it.first + it.second)}.take(n).last().second
}

[Pierre-Yves Saumont]

@Piet: Your solution does not really consist in building up the cache slowly, but in precomputing the cache in increments of 1000 elements, which allows using recursion inside each increment. As Java is able to handle a few thousand recursion steps with the default stack size, you could use a value higher than 1000.

Stream.foEach is actually a loop. You don't need to display the precomputed values, so you could simply write:

    public void computeAndShowNumbers() {
        LongStream.rangeClosed(0, 33)
                .map(i -> 3000 * i)
                .forEach(i -> fib(i));

        Scanner inScan = new Scanner(System.in);
        long input;
        while ((input = inScan.nextLong()) >= 0) {
            System.out.printf("fib(%d) = %d%n", input, fib(input));
        }
    }

These parameters allow for relatively fast precomputation and a function working up to n = 34 * 3000, so you can, for example, compute fib(100_000).

However, it is still limited. You can't go any further because you will be out of memory. Memoized functions should generally use some way of invalidating cache entries in order to recover memory space when necessary.

[Pierre-Yves Saumont]

Here is an example of a very simple memoized recursive Fibonacci function. It works without any loop (not counting the loop in the main method, of course) for input values up to 100_000_000, without causing stack overflow nor heap overflow. It is very easy to alter to make it work for any long value (since this will, in any case, be limited to the maximum long value in Java).

It is not the fastest way to compute Fibonacci numbers (corecursion is not fast!). Only an example of handling recursion in a stack safe manner. Note that a maximum depth of 10_000 might not work for you. In such case, just use a lower value. Using 3_000 should work in all cases and allow calling the function with values up to 9_000_000. Also note that the fib(0 ) = 1. This is consistent with the definition, as the first Fibonacci number is 1.

import java.math.BigInteger;
import java.util.Map;
import java.util.Objects;
import java.util.Scanner;
import java.util.WeakHashMap;

public class CorecursiveMemoizedFibonacci {

    private static long MAX_DEPTH = 10_000;

    private static Map<Long, Pair> cache = new WeakHashMap<>();

    private static Pair fib(long n) {
        return cache.computeIfAbsent(n, (Long i) -> {
            long q = n / MAX_DEPTH;
            long r = n % MAX_DEPTH;
            Pair p = fib1(r, new Pair(BigInteger.ZERO, BigInteger.ONE));
            return fib2(q, p);
        });
    }

    private static Pair fib2(long i, Pair p) {
        if (i == 0) return p;
        return fib2(i - 1, fib1(MAX_DEPTH, p));
    }

    private static Pair fib1(long i, Pair p) {
        if (i == 0) return p;
        return fib1(i - 1, p.successor());
    }

    public static void main(String... args) {
        Scanner inScan = new Scanner(System.in);
        long input;
        while ((input = inScan.nextLong()) >= 0) {
            System.out.println(String.format("fib(%s) = %s", input, fib(input)));
        }
    }

    private static class Pair {
        final BigInteger first;
        final BigInteger second;

        Pair(BigInteger first, BigInteger second) {
            this.first = first;
            this.second = second;
        }

        Pair successor() {
            return new Pair(second, first.add(second));
        }

        @Override
        public String toString() {
            return second.toString();
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Pair pair = (Pair) o;
            return Objects.equals(second, pair.second);
        }

        @Override
        public int hashCode() {
            return Objects.hash(second);
        }
    }
}

[Piet Souris]

hi Pierre-Yves,

thanks for this demo. It does work as you say, 5.000.000 is no problem, and you showed us (well, me at least) some totally new things. I just ordered your book, since I think there are quite some interesting new things to learn.

To get some practice, I took the liberty of adjusting your code slightly, even though it is just a demo. The fact that a Fib is recalculated from the ground up when it is not present in the cache is a pity. I changed the HashMap to a TreeMap, and only stored a Fib if its index is a multiple of 1000. If an index is absent, then I start from the closest available index in the cache, and calculating from there, either going forward of going backward. I added for this reason also a 'predecessor' to the Pair class.
Well, it was just to keep me busy for a while.

Thanks Campbell, for starting this interesting topic.

[Pierre-Yves Saumont]

Very good idea. In a previous example, I had implemented a system consisting of starting from the highest value present in the cache in case the needed value was not found, but it  would not work with a WeakHashMap. (Or should we implement a WeakTreeMap?   )

[Campbell Ritchie]

Thank you for the cow whoever it was.