3 ms·
That it's the fastest is pretty surprising to me. Both Binet and matrix multiplication require exponentiation to n, which can be done in O(log n) multiplication
by sidedishes 10y ago
That it's the fastest is pretty surprising to me. Both Binet and matrix multiplication require exponentiation to n, which can be done in O(log n) multiplications (not n-1) using a clever recursion (and indeed numpy uses it). 2x2 matrices aren't exactly the hardest to multiply either, but I figured that the floating point operations with the Binet formula would enough baggage that would make it slower than the matrix method. Edit: I just saw Someone's comment - I guess that explains it.
- Someone 10y agoNo, it doesn't, if I understand the OPs claim correctly. I agree with you that, for large enough n, using O(n) steps in the recursion will be slower than doing O(log n) matrix multiplication steps. The addition chain improves on the binary approach for some values of n, but I don't think it can go below O(log n) because the binary method is fastest for all n that are powers of two (disclaimer: I know almost nothing of addition chains besides what I learned from TAOCP). And of course, finding the fastest addition chain doesn't come cheaply, either, if P != NP. Hm, maybe I understand the OP's claim: if you want to generate the first n items in the series, the recursive formula will be hard to beat. Even then, it may not be fastest on modern CPUs. https://oeis.org/A000045 https://oeis.org/A000045 gives F(n + 12) = 18F(n + 6) - F(n) So, six completely independent threads can each compute a sixth of the sequence. Doing that may be faster than trying to paralllelize the bignum additions.