7
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Which c++ version are you targeting? c++03, c++11? \$\endgroup\$ – cloakedlearning Aug 28 '16 at 23:27
  • \$\begingroup\$ @cloakedlearning C++14 or whatever the newest version is. \$\endgroup\$ – Dmitry Kudriavtsev Aug 29 '16 at 0:07
12
\$\begingroup\$

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))
\$\endgroup\$
  • 1
    \$\begingroup\$ If you're going to change the generation algorithm, you may as well go all the way and use the closed form. \$\endgroup\$ – cloakedlearning Aug 29 '16 at 1:15
  • 2
    \$\begingroup\$ @cloakedlearning you may as well go all the way and use the closed form - which generates all those bits exactly how? \$\endgroup\$ – greybeard Aug 29 '16 at 6:29
  • \$\begingroup\$ rnd(phi^n / root(5)) or similar? Sure there's a similar number of operations, but they are first class cpu operations rather than full fat recursions. \$\endgroup\$ – cmh Aug 30 '16 at 8:03
  • \$\begingroup\$ Noted Binet's formula as a way to directly approximate the n-th fibonacci number. \$\endgroup\$ – Snowhawk Aug 30 '16 at 18:35
12
\$\begingroup\$

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];
}
\$\endgroup\$
  • \$\begingroup\$ Thanks! I'll be sure to follow these tips and use this implementation. \$\endgroup\$ – Dmitry Kudriavtsev Aug 29 '16 at 0:10
  • \$\begingroup\$ It actually iterates over the arguments and returns a result for each one. \$\endgroup\$ – Dmitry Kudriavtsev Aug 29 '16 at 0:49
  • \$\begingroup\$ @DmitryKudriavtsev, yup I didn't catch that, I'll edit. \$\endgroup\$ – cloakedlearning Aug 29 '16 at 3:03
  • \$\begingroup\$ (unsigned unsigned long int comes unexpected - C--? And which standard specifies std::uint128_t.) \$\endgroup\$ – greybeard Aug 29 '16 at 6:09
7
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ You can't assign arbitrary values to arbitrary positions in vectors, you have to do a push_back, and I think figuring out where and when to do this adds unnecessary logic. \$\endgroup\$ – Dmitry Kudriavtsev Aug 29 '16 at 0:22
  • \$\begingroup\$ @DmitryKudriavtsev, I don't think so. Vector is quite straightforward. You just need to be careful to not get out of bounds. \$\endgroup\$ – Incomputable Aug 29 '16 at 7:53
  • 2
    \$\begingroup\$ identifiers with leading double underscore are reserved \$\endgroup\$ – bolov Aug 29 '16 at 14:06
  • \$\begingroup\$ @bolov You should post that as an answer. \$\endgroup\$ – mdfst13 Aug 29 '16 at 15:28
  • 2
    \$\begingroup\$ @mdfst13: No you should remove it from your suggested solution. \$\endgroup\$ – Martin York Aug 29 '16 at 20:24
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ uint128_t is unsupported by gcc \$\endgroup\$ – Dmitry Kudriavtsev Sep 3 '16 at 23:22
  • \$\begingroup\$ @DmitryKudriavtsev, what does it change? I've provided the code only to provide some idea of how I would write it. uint128_t is implementation defined anyway. \$\endgroup\$ – Incomputable Sep 3 '16 at 23:36
1
\$\begingroup\$

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";
\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ This loses the dynamic programming aspect. The original version remembered what values it calculated, so if you asked for fibonacci(100) and then fibonacci(80), the second call is just an associative array (map) access. Also, the original version doesn't require any knowledge of what max should be. For 100, it returns the 100th value, not the last value less than 100. \$\endgroup\$ – mdfst13 Aug 29 '16 at 3:22
  • 1
    \$\begingroup\$ @mdfst13: It may not be perfect (but code review is not about giving the perfect answer). This is a perfectly good review. The design of the algorithm is a key contributing factor and designing a solution using a loop (and going up) is a better solution than using recursion and going down. \$\endgroup\$ – Martin York Aug 29 '16 at 20:19
  • \$\begingroup\$ @LokiAstari I never said that it wasn't. I just pointed out some of the things that likely got this answer downvoted. Along with the fact that it solves a different problem than the question (print all Fibonacci values less than a value rather than return a specified element in the sequence). \$\endgroup\$ – mdfst13 Aug 29 '16 at 21:12

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.