# Better Fibonacci sequence calculation

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

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


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

• 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. – vnp May 12 '17 at 1:59
• @vnp That involves multiplication. Doesn't multiplication have worse complexity than addition? – Dannyu NDos May 12 '17 at 2:09
• 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. – vnp May 12 '17 at 2:16
• 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 Jan 15 '18 at 8:36
• @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. – Toby Speight Jan 15 '18 at 8:37

(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*Phi³ coincidentally can be computed with just two summands (and no other power up to 2³² can).)

• (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.) – greybeard Jan 15 '18 at 1:15
• 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. – Toby Speight Jan 15 '18 at 8:40
• Woah... Never expected this old question to be answered! Thank you very much. – Dannyu NDos Jan 16 '18 at 0:23
• (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) – greybeard Jan 17 '18 at 8:04