To Find factorial of large number(number of digits >20)

Question

I wrote some c++ code to find the factorial of int n. As factorial can be a very large number, so I decided to store the number in a vector. But My Code is not working as expected. Some please point out the bug and guide me. I lowkey feel like I messed with pointers. And Please suggest if there is a more optimal approach for this. Thanks Community.

The Code:

    #include <iostream>
    #include <vector>
    #include <algorithm>
    using std::cout;
    using std::endl;
    using Digits = std::vector<int>;
    
    //define the length of the array, should be the maximum number of digits in the factorial(n)
    #define MAX 20
    
    void multiply(int x,Digits res,int res_size){
      int carry=0;
      for(int i=0;i<res_size;i++){
          int prod=carry+ x*res[i];
          res[i] = prod%10;
          carry = prod/10;
      }
    
      while(carry){
          res[res_size] = carry%10;
          carry/=10;
          (res_size)++;
      }
    }
    
    Digits factorial(int n){
      Digits res(MAX);  
      res[0] = 1;
      int res_size=1;
      for(int i=2;i<=n;i++){
          multiply(i,res,res_size);
      }
      reverse(res.begin(),res.end());
      return res;
    }
    
    int main(){
      for(auto i: factorial(20)){
        cout << i;     
      }cout << endl;
      return 0;
    }

The Output:

10000000000000000000
 
[Done] exited with code=0 in 3.204 seconds

Answer 1

Fixed version:

#include <vector>
#include <iostream>
using namespace std;

//define the length of the array, should be the maximum number of digits in the factorial(n)
#define MAX 20

void multiply(int x, vector<int>& res, int* res_size) {
    int carry = 0;
    for (int i = 0; i < *res_size; i++) {
        int prod = carry + x * res[i];
        res[i] = prod % 10;
        carry = prod / 10;
    }

    while (carry) {
        res[*res_size] = carry % 10;
        carry /= 10;
        (*res_size)++;
    }
}

vector<int> factorial(int n) {
    vector<int> res(MAX);
    res[0] = 1;
    int res_size = 1;
    for (int i = 2; i <= n; i++) {
        multiply(i, res, &res_size);
    }
    return res;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    for (auto i : factorial(20)) {
        cout << i;
    }cout << endl;
    return 0;
}

To pass by reference, simply add an & after the type of a parameter. Also, see Why should I not #include <bits/stdc++.h>? and Why is "using namespace std;" considered bad practice?.

For more info on pass-by-value and pass-by-reference, you can look here: https://www.educative.io/edpresso/pass-by-value-vs-pass-by-reference.

Basically, passing by value creates a copy of the original type, wheras passing by reference passes a reference to the original copy, so modifying the reference is modifying the original value.

Also, pointers and references are very similar, although I would use references when you want to modify a variable you are passing to a function. More on this: https://www.tutorialspoint.com/pointers-vs-references-in-cplusplus#:~:text=References%20are%20used%20to%20refer,to%20store%20address%20of%20variable.&text=A%20reference%20shares%20the%20same,and%20size%20on%20the%20stack.

Answer 2

i see some errors:

#define MAX 20

    void multiply(int x,vector<int> res,int* res_size){ // should be .. void multiply(int x,vector<int> res,int &res_size)
      int carry=0;
      for(int i=0;i<*res_size;i++){
          int prod=carry+ x*res[i];
          res[i] = prod%10;
          carry = prod/10;
      }
    
      while(carry){
          res[*res_size] = carry%10;
          carry/=10;
          (*res_size)++;
      }
    }
    
    vector<int> factorial(int n){
      vector<int> res(MAX);
      res[0] = 1;
      int res_size=1;
      for(int i=2;i<=n;i++){
          multiply(i,res,&res_size); // should be ... multiply(i,res,res_size)
      }
      return res;
    }

total:

void multiply(int x,vector<int> res,int &res_size){
cout << &res_size<< endl; // print address of "res_size"
  int carry=0;
  for(int i=0;i<res_size;i++){
      int prod=carry+ x*res[i];
      res[i] = prod%10;
      carry = prod/10;
  }

  while(carry){
      res[res_size] = carry%10;
      carry/=10;
      (res_size)++;
  }
}

vector<int> factorial(int n){
  vector<int> res(MAX);
  res[0] = 1;
  int res_size=1;
  for(int i=2;i<=n;i++){
      multiply(i,res,res_size);
  }
  return res;
}




cout << &res_size<< endl; // prints out the address where the value is stored.

int* res_size // stores the reference ( adddress )

Pointers

#include <iostream>
using namespace std;

    int main ()
    {
      int firstvalue, secondvalue;
      int * mypointer;
    
      mypointer = &firstvalue;
      *mypointer = 10;
      mypointer = &secondvalue;
      *mypointer = 20;
      cout << "firstvalue is " << firstvalue << '\n';
      cout << "secondvalue is " << secondvalue << '\n';
      return 0;
    }

pointers provide a remote control to the original value where it's stored in the ram.

instead of making copies everywhere in your code.

check out this video, it's very good
Introduction to pointers in C/C++

Pointers and dynamic memory - stack vs heap

mycodeschool