Yet another Fibonacci number generator

Question

First attempt at dynamic programming. I want to make this run faster and better.

---

fibonacci.cpp

#include "fibonacci.h"

std::map<int, unsigned long long int> initializeMap() {
    std::map<int, unsigned long long int> m;
    m[0] = 0;
    m[1] = 1;
    return m;
}

std::map<int, unsigned long long int> __fib_result_map = initializeMap();

unsigned long long int fibonacci(int seq) {
    using namespace std;
    map<int, unsigned long long int>& m = __fib_result_map;
    if(m[seq] == 0 && seq != 0) {
        m[seq] = fibonacci(seq - 2) + fibonacci(seq - 1);
    }
    return m[seq];
}

---

fibonacci.h

#ifndef __fibonacci
#define __fibonacci

#include <iostream>
#include <map>
#include <vector>
#include <string>
#include <algorithm>

unsigned long long int fibonacci(int seq);

#endif

---

fib_cpp.cpp

#include "fibonacci.h"
#include <cstdlib>
using namespace std;

int main(int argc, char* argv[]) {

    if(argc <= 1) {
        cerr << "No arguments specified. Usage: " << argv[0] << " <values>\n";
        return 1;
    }
    for(int i = 1; i < argc; i++) {
        cout << fibonacci(atoi(argv[i])) << endl;
    }
    return 0;
}

---

Here is the repository on Github.

Answer 1

Is this a generator or a calculator? Generators are objects that behave like iterators, yielding the next value on every call.

---

std::map<int, unsigned long long int> __fib_result_map = initializeMap();

#ifndef __fibonacci
#define __fibonacci

Know the rules regarding underscore usage. From the C++ Standard:

17.6.4.3.2 Global names [global.names]

Certain sets of names and function signatures are always reserved to the implementation:

• Each name that contains a double underscore __ or begins with an underscore followed by an uppercase letter is reserved to the implementation for any use.
• Each name that begins with an underscore is reserved to the implementation for use as a name in the global namespace.

---

using namespace std;

Don't abuse using directives just to avoid typing std:: (once in this example).

---

Your header file includes more than needed. Why include <algorithm>, <iostream>, <string>, and <vector>?

---

unsigned long long int fibonacci(int seq) {
    // ...
    m[seq] = fibonacci(seq - 2) + fibonacci(seq - 1);

Thoroughly test your code. unsigned long long can only have values of fibonacci upto fibonacci(93).

---

Avoid non-const global variables. They can be modified from anywhere. Consider using a universal memoization function.

---

Research the topic. Calculating the 16th fibonacci using

$$ fib(0) = 0\\ fib(1) = 1\\ fib(n) = fib(n-1) + fib(n-2), n > 1 $$

requires us to look up all 15 values before it. This is slow.

If we are just calculating \$fib(n)\$ via looping, Dijkstra showed in EWD654 "In Honor of Fibonacci" that we don't have to calculate every fibonacci upto \$n\$.

$$ fib(0) = 0\\ fib(1) = 1\\ fib(2n-1) = fib(n-1)^2 + fib(n)^2\\ fib(2n) = fib(n) \times (2 \times fib(n-1) + fib(n)) $$

Calculating \$fib(16)\$ requires \$fib([8, 7, 4, 3, 2, 1])\$. \$fib(1000)\$ only takes a maximum of 22 fibonacci calculations while the naive approach requires a maximum of 999 calculations. As noted in the comments, you can approximate the n-th fibonacci number using Binet's Formula.

$$ fib(n) = \left[\frac{\phi^n}{\sqrt{5}}\right],\ n > 0 $$

If we are implementing a generator, calculating the next fibonacci number is done in constant time.

$$ fib(n+1) = round( fib(n) \times Phi ),\ n > 1 $$

---

if (m[seq] == 0 && seq != 0)

If you want to check if a std::map contains an element, use std::map::count()

if (!m.count(seq))

Answer 2

Assuming you're using the current c++ standard, since you don't specify in your question.

• Prefer stoi to atoi. atoi has issues.
• Prefer standard int types: std::uint128_t instead of unsigned long long int
• Create a type alias for your map type since you use it a lot.
• Don't include unnecessary headers in the fibbonacci.h file. Include them in the implementation.
• It would make more sense to implement your memoizing map statically in the function.
• You should use the map count method rather than relying on [] returning zero for a missing key

Putting these together

using fibmap = std::map<int, std::uint128_t>;

std::uint128_t fibonacci(int seq) {

    static fibmap m = {{0,0}, {0,1}};
    if (!m.count(seq)){
        m[seq] = fibonacci(seq - 2) + fibonacci(seq - 1);
    }
    return m[seq];
}

Answer 3

using namespace std

    using namespace std;

Count the number of characters you use with this (twenty) and compare to the number of characters you save by having it (five). Wouldn't it be better to just say std::map instead?

Even in fib_cpp.cpp, you only save fifteen characters for a net increase of five.

std::vector vs. std::map

    map<int, unsigned long long int>& m = __fib_result_map;

You want a type indexed by integers starting with 0 and increasing to an arbitrarily large amount in sequence, as what Fibonacci is is a sequence. So why use a std::map, which allows for sparse, out of sequence results? Just use

    std::vector<std::uint128_t>& m = __fib_results;

Changing the name to __fib_results won't affect performance, but it saves having to rename the variable if you change types.

It will use less memory because a map has to leave room to add new elements between other elements in an arbitrary order. Which you don't need. And a map has to store the keys as well as the values. A vector uses position to do that, so the fourth is always index 3.

It will be faster, because integer indexes are more efficient than hash indexes.

The only way that the map might be as fast as a vector is if optimization turns it into a vector.

    if(m[seq] == 0 && seq != 0) {

Then this becomes

    if (m.size() <= seq) {

You don't even need a hash calculation for this.

Headers

#include <iostream>
#include <map>
#include <vector>
#include <string>
#include <algorithm>

The only one of these that fibonacci.cpp actually uses that I can see is map (although I think that you should use vector instead). You use iostream in fib_cpp.cpp, but not in fibonacci.cpp.

There's an argument that you should only do includes like this in header files if needed in the header file itself. That's not true in this case, as the header file only uses primitives. So you could include vector or map in fibonacci.cpp directly. The header file only needs to include the function prototype.

Working example

#include <vector>
#include <stdint.h>

std::vector<std::uint64_t> initializeFibonacci() {
    std::vector<std::uint64_t> m;

    m.push_back(0);
    m.push_back(1);

    return m;
}

std::vector<std::uint64_t> __fib_results = initializeFibonacci();

std::uint64_t fibonacci(int seq) {
    std::vector<std::uint64_t>& m = __fib_results;

    while (m.size() <= seq) {
        auto i = m.size();
        m.push_back(m[i-1] + m[i-2]);
    }

    return m[seq];
}

The compiler that I used for testing did not seem to have uint128_t, so I substituted uint64_t. I don't see any reason why uint128_t wouldn't work if available, but this is what I actually tested.

Instead of recursively working down to the last known value, this works up from it. This saves doing any recursive calls, so it doesn't have to worry about overloading the stack. Also, this makes it work more easily with push_back.

Answer 4

Your program is ill-formed because you have double underscores. They are reserved by the implementation.

Despite review of @cloackedlearning was nice, I didn't see any reason to not use std::vector<std::uint128_t> instead of map. On top of that, if the algorithm is not the only function running during execution of the program, having static map is a bad idea. Having static objects inside of a free standing functions is almost perfect case to encapsulate it in a class.

I propose a stateful templates fib_numbers class, so that users of it can supply their own type, since Fibonacci numbers grow really fast. It will emulate container with immutable elements, and will support functions to search until the number inclusively, searching for N more numbers, resizing, and checking if the number is Fibonacci number.

#include <vector>
#include <cstddef>
#include <algorithm>

template <typename NumberType>
class fib_numbers
{
    std::vector<NumberType> fibs;
public:
    fib_numbers():
        fibs{0, 1, 1, 2, 3}
    {}

    const NumberType& back() const
    {
        return fibs.back();
    }

    const NumberType& front() const
    {
        return fibs.front();
    }

    const NumberType& operator[](std::size_t index) const
    {
        return primes[index];
    }

    const NumberType& at(std::size_t index)
    {
        if (fibs.size() < index)
        {
            find_n(index - fibs.size() + 1);
        }
    }

    auto begin() const
    {
        return fibs.begin();
    }

    auto end() const
    {
        return fibs.end();
    }

    auto rbegin() const
    {
        return fibs.rbegin();
    }

    auto rend() const
    {
        return fibs.rend();
    }

    void find_until(const NumberType& number)
    {
        if (fibs.size() < 2)
        {
            fibs.clear();
            fibs.push_back(0);
            fibs.push_back(1);
        }

        while (fibs.back() < number)
        {
            fibs.push_back(fibs.back() + fibs[fibs.size() - 2]);
        }
    }

    void find_n(std::size_t count = 1)
    {
        if (fibs.size() < 2)
        {
            fibs.clear();
            fibs.push_back(0);
            fibs.push_back(1);
        }

        fibs.reserve(fibs.size() + count);
        for (std::size_t i = fibs.size(); i < fibs.capacity(); ++i)
        {
            fibs.push_back(fibs[i - 1] + fibs[i - 2]);
        }
    }

    void resize(std::size_t size)
    {
        if (fibs.size() > size)
        {
            fibs.resize(size);
        } 
        else
        {
            find_n(size - fibs.size() + 1);
        }
    }

    bool is_fib(const NumberType& number)
    {
        if (number > fibs.back())
        {
            find_until(number);
        }

        return std::binary_search(fibs.begin(), fibs.end(), number);
    }

    std::vector<NumberType>&& release()
    {
        return fibs;
    }
};

It uses idea "fill once, traverse many times", thus input on operator[] is unchecked, to give better performance.

Now, if you want to output them, you can range for loop, since it provides begin and end.

fib_numbers<unsigned long long> nums;
nums.find_until(12);
for (auto number : nums)
{
    std::cout << number << '\n';
}

You can make a default argument for template parameter as std::uint128_t, I haven't written it because it is not supported in VC++14.

If you are searching for the fastest way to find only nth Fibonacci number, then there are plenty of formulas on wikipedia page. I recommend you to make them templated free standing functions, since they don't need a state.

Answer 5

I want to make this run faster and better.

Use unsigned rather than unsigned long long for speed. If range is of concern use the widest range uintmax_t instead of unsigned long long.

unsigned long long may be a happy compromise, but it is neither fastest nor necessarily the widest range.

---

Should seq take on a negative value, fibonacci() will certainly attempt m[some_negative_value]. Suggest using unsigned seq or test for sign-ness.

if (seq < 0) Handle_Error();

---

Pedantic: Do not use argv[0] unless argc >= 1 or argv[0] is not 0. "The value of argc shall be non-negative." C++11 § 3.6.1 2. argc could be 0.

if(argc <= 1) {
    cerr << "No arguments specified. Usage: " << argv[0] ? argv[0] : "" << " <values>\n";

Answer 6

I'm sorry if posting this as an answer is a violation, since this is not really an answer rather than a suggestion.

You asked for ways to make this run faster and better, and I have an idea, but I have to say in advance I'm not a C++ developer so excuse me if I sound ridiculous but I have a feeling this can be simplified drastically.

I'm going to use some pseudo-c++ code to represent my idea, which is extremely simple, just use a for loop and avoid recursion.

int a = 0;
int b = 0;

for(int i = 1; i < max; i = a + b) {
    a = b;
    b = i;
    cout << i << "\n";
}

where max is the highest you want to go.

EDIT: Just ran this in cpp.sh, it seems to work.