5 ms·
So far as I can tell, they typically "parallelize" it by not memoizing it. It looks like they actually calculate the whole thing recursively, twice. That said
by wccrawford 6y ago
So far as I can tell, they typically "parallelize" it by not memoizing it. It looks like they actually calculate the whole thing recursively, twice.
That said, I found a parallel solution that was interesting and should provide a speedup, but with a large increase in complexity of the code.
https://stackoverflow.com/a/16464865/388173 https://stackoverflow.com/a/16464865/388173
- nonameiguess 6y agoGreat link and I like the mention of the fact there is actually an analytical formula for the Fibonacci number as well that allows computing it in constant time. Unfortunately, machine precision issues make it nearly impossible to accurately calculate anything large enough to be worth the speedup you get as there is no practical way to store enough of the digits in square root of 5, so you need a symbolic algebra implementation that can compute an exact answer and reduce it to a natural number.
- vlovich123 6y agoWhy symbolic algebra vs infinite precision floating point which is comparatively much cheaper computationally (& memory wise too?)?