2

I’m a newcomer to c++ trying to pick up the ropes, i was trying to write a recursive and memoized fibonacci function that returns the nth fibonacci number, i want to use std::map for the memoization, i also wrote a python version that does the same thing. the problem is that at the number 94, the c++ version of the program returns the wrong value but up until that point it was working well, could anyone point me in the right direction?

#include <iostream>
#include <map>
#define Log(x) std::cout << x << std::endl;

unsigned long long int fib(const int &n)
{
    static std::map<int, unsigned long long int> memo;
    if (n < 3)
        return 1;
    if (memo.count(n) > 0)
        return memo[n];
    memo[n] = fib(n - 1) + fib(n - 2);
    return memo[n];
}

int main(int argc, const char *argv[])
{
    int number;
    std::cout << "Enter a number: ";
    std::cin >> number;
    Log(fib(number));
}

here is the python version which works fine,

import sys


def fib(n, memo={}):
    if n < 3:
        return 1
    if n in memo:
        return memo[n]
    memo[n] = fib(n - 1) + fib(n - 2)
    return memo[n]


sys.setrecursionlimit(10**7)
number = int(input("Enter a number: "))
print(fib(number))

here is the output:

$ ./executables/fib
Enter a number: 93
12200160415121876738
$ python ./fib.py
Enter a number: 93
12200160415121876738
$ ./executables/fib
Enter a number: 94
1293530146158671551
$ python ./fib.py
Enter a number: 94
19740274219868223167

Any help would be highly appreciated

poison_pwn
  • 76
  • 2
  • 6
  • 2
    That number is too large to fit in an `unsigned long long`. https://stackoverflow.com/questions/34842637/whats-the-limit-of-long-long-int – Retired Ninja Dec 29 '20 at 01:39
  • i see, it can’t be fit in 64 bits, thank you for you help!. – poison_pwn Dec 29 '20 at 01:44
  • 1
    *I’m a newcomer to c++ trying to pick up the ropes,* -- Don't use Python as a model in writing C++ code. All you will end up with is being more confused with a program that is buggy, inefficient, or just looks plain weird to a C++ programmer. – PaulMcKenzie Dec 29 '20 at 02:11
  • 2
    Welcome to C++! One thing to note is try and stay away from `#define`. In this case you should write a log function instead of leaning on that macro. If you want it to accept a generic *whatever* argument you can use templates, as that's a perfect example to test with. – tadman Dec 29 '20 at 03:16
  • 1
    Another thing worth noting is `unsigned long long int` is a clunky way of saying `uint64_t`, as defined in [``](https://en.cppreference.com/w/cpp/types/integer). The short type name makes it abundantly clear that it's a 64-bit unsigned, while the former is a lot more ambiguous. – tadman Dec 29 '20 at 03:18
  • thanks for all the advice! i shall take this into account when writing c++ – poison_pwn Dec 30 '20 at 23:03

2 Answers2

1

I fixed the fixed caused by the number being too large to be fit into a unsigned long long int (uint64_t as indicated by tadman) into by using cpp_int from the boost multiprecision library.

#include <boost/multiprecision/cpp_int.hpp>
#include <iostream>
#include <map>

using namespace boost::multiprecision;
using namespace std;
cpp_int fib(const int &n)
{
    static map<int, cpp_int> memo;
    if (n < 3)
        return 1;
    if (memo.count(n) > 0)
        return memo[n];
    memo[n] = fib(n - 1) + fib(n - 2);
    return memo[n];
}

int main()
{
    int number;
    cout << "Enter a number: ";
    cin >> number;
    cout << fib(number) << endl;
}

and it works just fine now.

$ ./executables/fib
19740274219868223167

Thanks for all the help from the comments!

poison_pwn
  • 76
  • 2
  • 6
-1

map usage

var m := map(0 → 0, 1 → 1)
function fib(n)
    if key n is not in map m 
        m[n] := fib(n − 1) + fib(n − 2)
    return m[n]

class Solution {
public:
    map<int, int> m = {
        {0, 0},
        {1, 1}
    };
    int fib(int n) {
        if (m.count(n) == 0) {
            m[n] = fib(n - 1) + fib(n - 2);
        }
        return m[n];
    }
};
xiaotian
  • 59
  • 4
  • This is not addressing the question in any way. In fact, it is wrong, since the OP asked specifically for an answer to address the overflow problem. Posting just code, and wrong code at that (overflow) isn't a high quality answer which is what SO aims at. – Carlo Wood Jan 28 '23 at 12:43
  • Thank you for pointing out, because I am a novice in C++. This answer is just a translation of the wiki content and the usage of map in C++, which is not a high-quality answer. – xiaotian Jan 29 '23 at 16:40