programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Jeanne Boyarsky
• Ron McLeod
• Paul Clapham
• Liutauras Vilda
Sheriffs:
• paul wheaton
• Rob Spoor
• Devaka Cooray
Saloon Keepers:
• Stephan van Hulst
• Tim Holloway
• Carey Brown
• Frits Walraven
• Tim Moores
Bartenders:
• Mikalai Zaikin

Calculating Fibonacci numbers with Map#computeIfAbsent

Marshal
Posts: 79278
377
• Number of slices to send:
Optional 'thank-you' note:
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:-So let's try a nice big number and see if we can't calculate Fibonacci numbers up to it:-

java AbsentFibonacciDemo
1000000
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

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.

Rancher
Posts: 379
22
• Number of slices to send:
Optional 'thank-you' note:
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.

Author
Posts: 161
31
• Number of slices to send:
Optional 'thank-you' note:
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:

Campbell Ritchie
Marshal
Posts: 79278
377
• Number of slices to send:
Optional 'thank-you' note:
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
Author
Posts: 161
31
• Number of slices to send:
Optional 'thank-you' note:
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
Author
Posts: 161
31
• Number of slices to send:
Optional 'thank-you' note:
By the way, I fixed a bug in my code. (I was not using the map!)

Bartender
Posts: 5466
212
• Number of slices to send:
Optional 'thank-you' note:
With Campbells code, you can get the fib for much larger values if you build up the cache slowly.
For instance:

Campbell Ritchie
Marshal
Posts: 79278
377
• Number of slices to send:
Optional 'thank-you' note:
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
Author
Posts: 161
31
• Number of slices to send:
Optional 'thank-you' note:
@Piet Yes, this effect may be observed with some recursive calls. But it will not work for really high values.

Pierre-Yves Saumont
Author
Posts: 161
31
• Number of slices to send:
Optional 'thank-you' note:
@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
Author
Posts: 161
31
• Number of slices to send:
Optional 'thank-you' note:
@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:

Piet Souris
Bartender
Posts: 5466
212
• Number of slices to send:
Optional 'thank-you' note:
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
Bartender
Posts: 5466
212
• Number of slices to send:
Optional 'thank-you' note:
@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
Rancher
Posts: 379
22
• Number of slices to send:
Optional 'thank-you' note:
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
Author
Posts: 161
31
• Number of slices to send:
Optional 'thank-you' note:
@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
Author
Posts: 161
31
• 1
• Number of slices to send:
Optional 'thank-you' note:
@Sean Fibonacci in Kotlin:

Pierre-Yves Saumont
Author
Posts: 161
31
• Number of slices to send:
Optional 'thank-you' note:
@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:

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
Author
Posts: 161
31
• Number of slices to send:
Optional 'thank-you' note:
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.

Piet Souris
Bartender
Posts: 5466
212
• Number of slices to send:
Optional 'thank-you' note:
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
Author
Posts: 161
31
• Number of slices to send:
Optional 'thank-you' note:
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
Marshal
Posts: 79278
377
• Number of slices to send:
Optional 'thank-you' note:
Thank you for the cow whoever it was.

 My favorite is a chocolate cupcake with white frosting and tiny ad sprinkles. a bit of art, as a gift, the permaculture playing cards https://gardener-gift.com