2 ms·
Well, in this case because we also eliminate several additions. For each even Fibonacci number you have to perform multiple additions in the naive approach (gen
by Jtsummers 5y ago
Well, in this case because we also eliminate several additions. For each even Fibonacci number you have to perform multiple additions in the naive approach (generate all, filter):
F(0) = 0
F(1) = 1
F(2) = 1 + 0
F(3) = 1 + 1 = 2 (2 additions to get here)
F(4) = 2 + 1 = 3
F(5) = 3 + 2 = 5
F(6) = 5 + 3 = 8 (3 more additions to get here, and 3 for each subsequent one)
With the faster version you have one multiplication and one addition (2 operations) versus 3 additions. The 3 additions naive version also has a branch that has been eliminated by just generating the even elements.
EF(0) = 0
EF(1) = 2
EF(2) = 4 * 2 + 0 = 8 (1 mul, 1 add)
EF(3) = 4 * 8 + 2 = 34 (1 mul, 1 add)
This is why I was getting about a 30% improvement in performance, it's performing one less op (the branch itself isn't too expensive in comparison so with large numbers it's a minor cost).
- exdsq 5y agoGotcha! Thanks for all your informed answers.