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