# Optimizing Fast Fibonacci Computation

@H2CO3 I suppose it's possible to define our own "hashing" from n to an index on a Vector to avoid having to use HashMap. I suspect if you hash straight from n to index you'll end up with a kind of sparse Vector that's half missing at all times though. Anyway this is getting a bit side tracked since I was really just interested in figuring out why it's slower than Julia despite being mechanically almost identical (both using HashMap etc).

@gvissers I think you are doing Dijk's algorithm without memoization/caching. That's going to be an avoidable source of slow down since the recursion can actually hit the cache quite often (if you do cache). Just doing n = 100 would hit the cache 16 times, for example. I suspect the difference is on the order of O(logN^2) but that's just a hunch. It's true that at a smaller index (ie: n = 4784969) the caching might end up generating so much overhead it makes the code actually slower, however at higher n (ie: a billion) it's going to make a very big difference.

I;m afraid we are drifting further away a bit from your original question than intended, apologies for that. But:

Actually, not completely. It is possible to write recurrence relations for the pairs of consecutive Fibonacci numbers (Fk, Fk+1) that only use the values in the pair for k/2:

• (F2k, F2k+1) = (Fk[2Fk+1-Fk], Fk+1(2Fk+1-Fk] + (-1)k+1), and
• (F2k+1, F2k+2) = (Fk[2Fk+Fk+1] + (-1)k, Fk+1[2Fk+Fk+1])

So, to compute a (even k, odd k) pair use the first relation, for an (odd k, even k) pair use the second. To compute a single Fibonacci number Fn, calculate the pair (Fn/2, Fn/2+1) using the above relations, and combine them.

Note that at every step in the recursion, you only need a single recursive call to compute the pair for k/2. So every call to the function computing such a pair has a distinct (and strictly descending) value for k, and as such caching is not helpful.

I did not come up with these relations, I simply stole them from @ZiCog 's repository. I believe that it was Eric Olson who first introduced them in a FreeBASIC program to compute Fibonacci numbers, I might be mistaken though.

I did a small bit of benchmarking. Your program as written above, using `rug` took approximately 12s to compute F(109). Using the above relations, it took ~9s. I will admit though that I haven't looked if your program could be improved further.

To at least pretend to get back on track: it might be worth checking @H2CO3 's suggestion to use a `Vec` instead of a `HashMap` for caching. If that makes a significant difference, it is possible that the `HashMap` implementation in Rust is slower than in Julia (at least for `u32` keys), and that the difference can be explained by that (though perhaps, you should then also do the same in Julia for a fair comparison).

1 Like

Ooh this is very interesting (and should be even faster than my implementation). Thanks!

Also, if the Julia version with a plain dynamic array is still faster than the Rust version that uses `Vec`, then the difference might be due to JIT optimization. I have once written a microbenchmark in which prime counting in JavaScript won over the same algorithm implemented in C because of agressive JITing.

I have added an implementation of Fibonacci numbers calculation to my bigint benchmarks. In two versions: decimal and hexadecimal.

The hexadecimal one is particularly simple because it only really involves multiplications, assuming the number representation is already in binary.

I still like my "digits of e" benchmark a bit more given that it has more of a variety of operations: there are some small numbers involved, a lot of medium-sized ones, some big ones, multiplication and division and exponentiation.

I'm open to other benchmarking ideas.

A huge thank you for that. It is merged now.

I just posted the results I to a similar fibonacci thread here: Code Review + Why is this Fibonacci code so slow? - #10 by ZiCog