8 Replies - 761 Views - Last Post: 20 December 2017 - 02:54 PM Rate Topic: -----

#1 illimite   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 2
  • Joined: 19-December 17

large numbers factorial

Posted 19 December 2017 - 07:29 PM

i saw a project somewhere asked for a program to calculate the factorial of a 20 digits number.

ive written this code already :
#include <iostream>

using namespace std;

void minus1(int m[], int );
void multi(int[] , int[] ,int ,int);
void show(int[] , int);

int main()
{
    int const a = 6;
    int const b = 9999;
    int x[a]={0,0,0,9,9,9};
    /*cout << "enter the number : "<< endl;
    for(int i=0 ; i<a ; i++)
        cin >> x[i];
    cout<<"the number u entered is :"<<endl; */
    show(x,a);
    int y[b] = {0} ;
    for (int i =0 ; i<a; i++)
    {
        y[b-1-i]=x[a-1-i];
    }
    minus1(x,a);

    while(x[0]!=0 || x[1]!=0 || x[2]!=0 || x[3]!=0 || x[4]!=0 || x[5]!=1)
    {
        multi(x,y,a,B)/>;
        minus1(x , a);
    }
    show(y,B)/>;

}

void minus1(int x[] , int size)
{
    for (int i=size-1 ; i>=0 ; i--)
    {
        if(i==0 && x[0]==0)
        {
            for(int i=0 ; i<size ; i++)
            {
                x[i]=0;
            }
            break;
        }
        if(x[i]>0)
        {
            x[i]-=1;
            break;
        }
        else
        {
            x[i]=9;
        }

    }
}

void show(int x[], int size)
{
    for(int i = 0 ; i <size ; i++ )
    {
        cout << x[i];
    }
    cout<<endl;
}

void multi(int x[],int y[] , int sx  , int sy)
{
    int c[sy]={0};
    int d[sy];
    int pre=0;

    for (int i= 0 ; i< sx ; i++)
    {
        for(int k=0 ; k<sy ; k++)
            d[k]=0;
        pre=0;
        for (int j=0 ; j< sy-sx; j++)
        {
            d[sy-1-i-j]=((x[sx-1-i]*y[sy-1-j])+pre)%10;
            pre = ((x[sx-1-i]*y[sy-1-j])+pre)/10;
        }
        for(int l=0; l<sy ; l++)
        {
            pre =0;
            c[sy-1-l]=(c[sy-1-l]+d[sy-1-l]+pre)%10;
            pre =(c[sy-1-l]+d[sy-1-l]+pre)/10;
        }
    }

    for(int m=0; m<sy;m++)
    {
        y[m]=c[m];
    }
}


but it can calculate the maximum of 9999 and its doing nothing for a number like 99999.
i wanted to know if the problem is with my code or its just impossible to calculate such thing with a laptop ????

Is This A Good Question/Topic? 0
  • +

Replies To: large numbers factorial

#2 macosxnerd101   User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12657
  • View blog
  • Posts: 45,831
  • Joined: 27-December 08

Re: large numbers factorial

Posted 19 December 2017 - 07:34 PM

Note that 99999! is probably too big to store. Generally, it's advisable to avoid such large calculations. Handling them symbolically, or doing some algebraic cancellations a priori (e.g., such as when calculating binomial coefficients) is much more efficient. Stirling's approximation is also an effective tool to get some control on large factorials.
Was This Post Helpful? 0
  • +
  • -

#3 Skydiver   User is offline

  • Code herder
  • member icon

Reputation: 7132
  • View blog
  • Posts: 24,221
  • Joined: 05-May 12

Re: large numbers factorial

Posted 20 December 2017 - 06:01 AM

Our OP doesn't look to be computing the factorial, but rather is computing the product of two factors in his multi() function. It looks like he is computing it symbolically. I'm just have a really hard time understanding/parsing the code because of the poorly named variables and lack of use of whitespace.
Was This Post Helpful? 0
  • +
  • -

#4 illimite   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 2
  • Joined: 19-December 17

Re: large numbers factorial

Posted 20 December 2017 - 06:28 AM

Trust me it calculate the factorial i had to use arrays cuz of the limit of int and double and stuff , and about the multi() and being a poor program u are right im very new to programming and beside it suposed to be just a test. But my point was my program has too many loops inside each other i guess maybe a more efficiant program can calculate more digits or maybe we can use a double for main number and a double array to keep like 50 digits in each part . But i dont know how to write it. Beside ive read in anouther forume calculating such thing can take many years i dont know if its right or what.

This post has been edited by Skydiver: 20 December 2017 - 11:17 AM
Reason for edit:: Removed unnecessary quote. No need to quote the post above yours.

Was This Post Helpful? 0
  • +
  • -

#5 Skydiver   User is offline

  • Code herder
  • member icon

Reputation: 7132
  • View blog
  • Posts: 24,221
  • Joined: 05-May 12

Re: large numbers factorial

Posted 20 December 2017 - 11:18 AM

There is no need to quote the post above yours. Just use the big Reply button or the Fast Reply area.

Ah, I see. The multi() is used to multiply "x" and "x - 1" and you are using the loop on lines 26-30 to go through all the factors of the factorial.
Was This Post Helpful? 0
  • +
  • -

#6 Skydiver   User is offline

  • Code herder
  • member icon

Reputation: 7132
  • View blog
  • Posts: 24,221
  • Joined: 05-May 12

Re: large numbers factorial

Posted 20 December 2017 - 11:46 AM

I changed the main() to some lower limits and just to make it easier to see if your code even works for small numbers. Looks like you have a bug in your multi()...
int main()
{
    int const a = 6;
    int const b = 6;
    int x[a] = { 0,0,0,0,0,9 };
    /*cout << "enter the number : "<< endl;
    for(int i=0 ; i<a ; i++)
    cin >> x[i];
    cout<<"the number u entered is :"<<endl; */
    cout << "x: ";
    show(x, a);
    int y[b] = { 0 };
    for (int i = 0; i<a; i++)
    {
        y[b - 1 - i] = x[a - 1 - i];
    }
    cout << "y: ";
    show(y, B)/>;
    minus1(x, a);

    while (x[0] != 0 || x[1] != 0 || x[2] != 0 || x[3] != 0 || x[4] != 0 || x[5] != 1)
    {
        cout << "x: ";
        show(x, a);
        cout << "y: ";
        show(y, B)/>;
        multi(x, y, a, B)/>;
        minus1(x, a);
    }
    cout << "y: ";
    show(y, B)/>;

}



Output:
x: 000009
y: 000009
x: 000008
y: 000009
x: 000007
y: -1-1-1-1-1-1
x: 000006
y: -1-1-1-1-1-1
x: 000005
y: -1-1-1-1-1-1
x: 000004
y: -1-1-1-1-1-1
x: 000003
y: -1-1-1-1-1-1
x: 000002
y: -1-1-1-1-1-1
y: -1-1-1-1-1-1


Was This Post Helpful? 0
  • +
  • -

#7 Skydiver   User is offline

  • Code herder
  • member icon

Reputation: 7132
  • View blog
  • Posts: 24,221
  • Joined: 05-May 12

Re: large numbers factorial

Posted 20 December 2017 - 12:26 PM

A few suggestions to make your life easier:
1. Use the std::vector instead of the C style array. It'll let you grow up to the number of digits required for your "large" integer instead of having to guess ahead of time how much room you need.

2. Put the digits at the index location that corresponds to the power of 10. For example, if you have the value 932, you would store it as:
bignum[0] = 2;
bignum[1] = 3;
bignum[2] = 9;


because 932 = 9 x 102 + 3 x 101 + 2 x 100.

3. You can likely get by with just having a vector of char instead of int.

4. Although not required, encapsulate your concept of a "big number" into a class. Inside the class will be the vector. The class will expose methods for multiplication, addition, subtraction, and getting a most significant digit first string representation.

5. Also not required, instead of storing the digits of the symbolically, you could store number in binary as bits within adjacent longs. It'll give you a major speed boost when doing the math operations, but it will likely make the code more complex.
Was This Post Helpful? 0
  • +
  • -

#8 GazinAtCode   User is offline

  • D.I.C Head

Reputation: 35
  • View blog
  • Posts: 139
  • Joined: 26-September 16

Re: large numbers factorial

Posted 20 December 2017 - 12:44 PM

Here's my brute-force approach using std::vector and naive addition and multiplication:

#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>

std::vector<char> add(const std::vector<char> &num1, const std::vector<char> &num2)
{
    int n1 = num1.size();
    int n2 = num2.size();
    int n = std::max(n1, n2);
    std::vector<char> result;
    int carry = 0;
    for (int i = 0; i < n; ++i) {
        int a = n1 - i < 1 ? 0 : num1[n1 - i - 1];
        int b = n2 - i < 1 ? 0 : num2[n2 - i - 1];
        int sum = a + b + carry;
        if (sum > 9) {
            sum %= 10;
            carry = 1;
        } else {
            carry = 0;
        }
        result.push_back(sum);
    }
    if (carry == 1) {
        result.push_back(carry);
    }
    std::reverse(result.begin(), result.end());
    return result;
}

std::vector<char> multiply(const std::vector<char> &num1, const std::vector<char> &num2)
{
    int n1 = num1.size();
    int n2 = num2.size();
    std::vector<char> result = { 0 };
    for (int i = 0; i < n2; ++i) {
        int carry = 0;
        std::vector<char> subResult;
        for (int j = 0; j < n1; ++j) {
            int prod = num2[n2 - i - 1] * num1[n1 - j - 1] + carry;
            if (prod > 9) {
                carry = prod / 10;
                prod %= 10;
            } else {
                carry = 0;
            }
            subResult.push_back(prod);
        }
        if (carry > 0) {
            subResult.push_back(carry);
        }
        std::reverse(subResult.begin(), subResult.end());
        if (i > 0) {
            std::vector<int> zeros(i, 0);
            subResult.insert(subResult.end(), zeros.begin(), zeros.end());
        }
        result = add(result, subResult);
    }
    return result;
}

std::vector<char> factorial(int n)
{
    std::vector<char> result = { 1 };
    std::vector<char> nextVal = { 1 };
    for (int i = 1; i < n; ++i) {
        nextVal = add(nextVal, std::vector<char>(1, 1));
        result = multiply(result, nextVal);
    }
    return result;
}

void display(const std::vector<char> &num)
{
    int n = num.size();
    for (int i = 0; i < n; ++i) {
        std::cout << +num[i];
    }
    std::cout << std::endl;
}

int main()
{
    display(factorial(10000));
}

It's very slow but steady. You can start from there, although I doubt that you can effectively compute the factorial of a 20-digit-long number.

This post has been edited by GazinAtCode: 20 December 2017 - 05:11 PM

Was This Post Helpful? 0
  • +
  • -

#9 GazinAtCode   User is offline

  • D.I.C Head

Reputation: 35
  • View blog
  • Posts: 139
  • Joined: 26-September 16

Re: large numbers factorial

Posted 20 December 2017 - 02:54 PM

By the way, you can use this function to find (or estimate for very large values) the number of digits in a factorial (inspired by this blog post):
double getFactorialDigitCount(double n)
{
    return floor(lgamma(n + 1) / log(10)) + 1;
}

Example:
int main()
{
    std::cout.precision(16);
    // number of digits in 99,999! (exact value)
    std::cout << getFactorialDigitCount(99999) << std::endl;
    // number of digits in 10,000,000,000,000,000,000! (approximation)
    std::cout << getFactorialDigitCount(1.0e19) << std::endl;
}

Output:
456569
1.856570551809675e+020 // approximately 185,657,055,180,967,500,000 digits

This post has been edited by GazinAtCode: 21 December 2017 - 06:54 AM

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1