Calculating Large Factorials in C++

Calculating large factorials in C++

Skimmed this question, not sure if I really got it right but here's a deductive guess:

First question - how do you get a zero on the end of the number? By multiplying by 10.

How do you multiply by 10? either by multiplying by either a 10 or by 2 x 5...

So, for X! how many 10s and 2x5s do you have...?

(luckily 2 & 5 are prime numbers)

edit: Here's another hint - I don't think you need to do any multiplication. Let me know if you need another hint.

Calculate the factorial of an arbitrarily large number, showing all the digits

GNU Multiprecision library is a good one! But since you say using of external libraries are not allowed, only way I believe its possible is by taking an array of int and then multiplying numbers as you do with pen on paper!

Here is the code I wrote some time back..

#include<iostream>
#include<cstring>

int max = 5000;

void display(int arr[]){
    int ctr = 0;
    for (int i=0; i<max; i++){
        if (!ctr && arr[i])         ctr = 1;
        if(ctr)
            std::cout<<arr[i];
    }
}

void factorial(int arr[], int n){
    if (!n) return;
    int carry = 0;
    for (int i=max-1; i>=0; --i){
        arr[i] = (arr[i] * n) + carry;
        carry = arr[i]/10;
        arr[i] %= 10;
    }
    factorial(arr,n-1);
}

int main(){
    int *arr = new int[max];
    std::memset(arr,0,max*sizeof(int));
    arr[max-1] = 1;
    int num;
    std::cout<<"Enter the number: ";
    std::cin>>num;
    std::cout<<"factorial of "<<num<<"is :\n";
    factorial(arr,num);
    display(arr);
    delete[] arr;
    return 0;
}

'arr' is just an integer array, and factorial is a simple function that multiplies the given number to the 'large number'.

Hope this solves your query..

Calculation of factorial of large numbers in c using arrays

The problem is probably because of this loop:

for(i=1;i<n;i++)//initialize array

In the loop you clear the n - 1 entries of the allocated memory, but you allocate memory for d entries. If n - 1 is larger than d then you write outside the allocated memory, which causes undefined behavior. If n - 1 is smaller than d then you leave some memory uninitialized which also is undefined behavior when you access it.

You should clear all of the memory, either by using your loop, by using memset or by using calloc when allocating.

find count of specific digits in a large factorial

Finally i found my answer, which could be helpful for others.

The Idea is using big numbers multiplication:

#include<stdio.h>

int main()
{
    int n , p;
    scanf("%d %d" , &n , &p);
    int digits[1000] = {1};
    for(int i = 2 ; i <= n ; i++)
    {
        for(int k = 0 ; k < 1000 ; k++) digits[k] *= i;
        for(int k = 0 ; k < 1000 ; k++) if(digits[k] > 9)
            {
                digits[k+1] += digits[k]/10;
                digits[k] %= 10;
            }
    }
    int a , count = 0;
    for(a = 999 ; !digits[a] ; a--);
    a++;
    for (int j = 0;j<a;j++) if(digits[j] == p) count++;
    printf("%d" , count);
}

Cannot calculate factorials bigger than 20! ! How to do so?

The limit on an unsigned long long is 18446744073709551615, or about 1.8e+19. 20! is about 2.4e+18, so within range, however 21! is about 5.1e+19, exceeding the maximum size of an unsigned long long.

You may find this helpful: Are there types bigger than long long int in C++?

---

Related Topics