7
\$\begingroup\$

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?

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

(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).)

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.