9 ms·

I appreciate it, thanks!

by exdsq 5y ago

Jtsummers 5y ago
NP. By the way, for grins I altered my program to generate only even Fibonacci numbers. I was seeing approximately 30% improvements, though I think you will see bigger improvements as you get to much larger numbers than I was testing on (on a cheap VPS box with 1 core and 4GB of RAM so I didn't really feel like stressing it too much because it was slow enough already). The changed recurrence relation is: EF(N) = Nth Even Fibonacci Numbers EF(N) = 4 * EF(N-1) + EF(N) EF(0) = 0, EF(1) = 2 This skips the generation of odd Fibonacci numbers and removes the need for the filtering step (if even then add to accumulator), but it adds in the multiplication which seems to reduce some of the potential performance gains. Once you get to the point that you're dealing with big numbers, addition becomes very expensive and, depending on how multiplication is implemented, you ought to get a larger performance boost as you get to very large numbers.
- 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 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 ago
      Gotcha! Thanks for all your informed answers.

I appreciate it, thanks!

by exdsq 5y ago

I appreciate it, thanks!

NP. By the way, for grins I altered my program to generate only even Fibonacci numbers. I was seeing approximately 30% improvements, though I think you will see bigger improvements as you get to much larger numbers than I was testing on (on a cheap VPS box with 1 core and 4GB of RAM so I didn't really feel like stressing it too much because it was slow enough already). The changed recurrence relation is: EF(N) = Nth Even Fibonacci Numbers EF(N) = 4 * EF(N-1) + EF(N) EF(0) = 0, EF(1) = 2 This skips the generation of odd Fibonacci numbers and removes the need for the filtering step (if even then add to accumulator), but it adds in the multiplication which seems to reduce some of the potential performance gains. Once you get to the point that you're dealing with big numbers, addition becomes very expensive and, depending on how multiplication is implemented, you ought to get a larger performance boost as you get to very large numbers.

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 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 ago
    Gotcha! Thanks for all your informed answers.