0

I've implemented Fibonacci Series with memoization using dictionary in Python.

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

print(fib(50))

I've tried to create an equivalent in C++ it's working fine till 46 but giving strange output after 46. I've provided the code below.

#include<iostream>
#include<unordered_map>

using std::unordered_map;
using std::cout;


int fib(int num, unordered_map <int, int> &Dict)
{

  if (Dict.find(num) != Dict.end())
  {
    return Dict[num];
  }

  if (num <= 2)
  {
    return 1;
  }

  Dict[num] = fib(num-1, Dict) + fib(num-2, Dict);

  return Dict[num];

}

int main()
{
  int n;
  cout<<"Enter the number: ";
  std::cin>>n;
  unordered_map <int, int> Dict;
  cout<<fib(n, Dict);
  return 0;
}
nobody
  • 19,814
  • 17
  • 56
  • 77
Srijan Singh
  • 41
  • 7
  • 4
    Looks like you're overflowing `int`. Try using a bigger integer type, such as `long`. – Fred Larson Oct 11 '21 at 13:40
  • 2
    Python uses complex object to represent integers so memory limits size of integer types. In C++ `int` type represents what hardware supports for integer types so limit is much smaller. You need some none standard library to have big_intergers in C++ – Marek R Oct 11 '21 at 13:43
  • In the nitpicking department, since `(num <= 2)` is likely to be a lot faster than `Dict.find()` you should probably do the two in opposite order. – 500 - Internal Server Error Oct 11 '21 at 13:47
  • 1
    Python has GNU GMP built in, i.e., arbitrary length integers. In C++ you have to use GNU GMP manually to achieve that effect. Or postpone the problem by using a longer type than `int`, such as `uint64_t`, or go for a 128-bit version if the compiler supports it. Reaching the Fibonacci number `2971215073` yields undefined behavior, because it is larger than 2³¹ – 1. An `unsigned int` would be guaranteed to overflow (which would not help either). With a signed `int` things are undefined. Fibonacci numbers grow exponentially — that’s the reason why they exceed 32-bit integer range quite quickly. – Andrej Podzimek Oct 11 '21 at 13:47
  • I've used long and it works fine in Code Chef Online IDE but in my machine the issue remains same even after using long. I'm using G++ compiler in my machine. Could you help me to resolve the issue? – Srijan Singh Oct 11 '21 at 13:52
  • Thanks @AndrejPodzimek unsigned long has resolve the issue. – Srijan Singh Oct 11 '21 at 13:54
  • Yes, it does. Thanks @pptaszni – Srijan Singh Oct 11 '21 at 13:56
  • 1
    It is safer to use `uint64_t` and other types with explicit length. `long` is usually 32-bit, rarely 64-bit. `unsigned long`, if it is 32-bit, will make the number `2971215073` work by just a tiny margin and the following Fibonacci number will already overflow. So it is not really a solution; no finite integer is. GNU GMP provides the (much needed) “infinite” integers. – Andrej Podzimek Oct 11 '21 at 17:15

0 Answers0