3 ms·
Multiplication is more efficient than addition? That’s surprising! I assumed multiplication would be built at least partially from addition when you’re at the l
by exdsq 5y ago
Multiplication is more efficient than addition? That’s surprising! I assumed multiplication would be built at least partially from addition when you’re at the lowest levels of the stack
- Jtsummers 5y agoWell, 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.