Better Fibonacci sequence calculation

Question

I attempted to make better Fibonacci sequence calculation algorithm in C++. This was the best I could:

constexpr unsigned fibonacci(unsigned n) {
 unsigned result[2] = {1, 0};
 for (unsigned i = 1; i < n; ++i)
 result[i%2] = result[0] + result[1];
 return result[1 - n%2];
}

...which runs at O(n) time complexity and O(1) space complexity.
Is there any better?

• vnp: Yes. Check out mathworld.wolfram.com/FibonacciQ-Matrix.html. Combined with exponentiation by squaring it yields \$O(\log{n})\$ time complexity, while still \$O(1)\$ space.
• Dannyu NDos: @vnp That involves multiplication. Doesn't multiplication have worse complexity than addition?
• vnp: Everything else equal, an individual multiplication is (usually) slower than an individual addition. However the suggested approach performs so much less operations that individual complexity doesn't count. There is a rigorous proof of this intuition.
• Toby Speight: O(1) time and space if you're willing to go via floating-point for the closed-form expression - there's probably a crossover value of n for which that's better.
• Toby Speight: @greybeard, I don't consider solving a popular programming exercise to be reinventing the wheel. If there existed std::fibonacci (or similar in Boost etc), I think you'd be right.

Answer 1

(Uh-oh: better - better define a quality measure!)

• Your code doesn't tell what it's about.
• constexpr looks good - "my" environment complains with C++11.

• "The array&index manipulation" where "simultaneous assignment" is wanted is hard to read (could be worse: the elements of result[] could be non-interchangeable).
  Alas, what I found for "modern C++" is ghastly compared to python's a, b = b, a + b. I appreciate the attempt to avoid avoidable assignments; I'm mildly curious if it makes any difference in the code generated by an optimising compiler.

• Is there any better? Well, with output size limited by a constant, there's a tighter limit:
  the runtime of your code is in O(1), just as any other.
  In a comment, you express concern about the complexity of multiplication. If you accept ("bit-wise") "shift" as a (very) cheap operation, you can take three steps in the Fibonacci sequence at once without an increase in "logic gate complexity":

#include <cstdlib>
#include <tuple>
#include <iostream>
/// Iterates an a,b = b,a+b sequence in steps of three.
//constexpr
static unsigned long tri(int previous, int current, const unsigned int n) {
 if (n < 2)
 return n ? current : previous;
 std::div_t split = std::div(n-2, 3);
 while (0 <= --split.rem)
 std::tie(previous, current)
 = std::make_tuple(current, current+previous);
 unsigned long
 a = current - previous,
 b = current + previous; 
 while (0 <= --split.quot)
 std::tie(a, b) = std::make_tuple(b, (b<<2)+a);
 return b;
}
/// Iterates the Fibonacci sequence in steps of three.
unsigned long fibonacci(const unsigned int n) {
 return tri(0, 1, n);
}
/// Iterates the Lucas numbers in steps of three.
unsigned long lucas(const unsigned int n) {
 return tri(2, 1, n);
}

(For variants using arrays of precomputed elements in stead of "the setup-loop" (and a main()), consult the edit history.)
(b*Phi3 coincidentally can be computed with just two summands (and no other power up to 232 can).)

• greybeard: (Disclaimer: I haven't used C++ in earnest for over a decade, I never was up to speed with "modern C++", even C++03. Feel invited to improve (especially) the code above.)
• Toby Speight: I think I would move fib and luc into the scope of triFib() and triLuc() respectively (as static constants) - no need for them to be globally visible.
• Dannyu NDos: Woah... Never expected this old question to be answered! Thank you very much.
• greybeard: (For the curious: multipliers and step sizes for three summands: 3/2, (7/4((x<<3)-x, shift&mask instead of divmod)), 18/6; four summands: (7/4, shift&mask), 11/5, (47/8((x<<5)+(x<<4)-x, s&m)), 76/9, 322/12, 521/13)