Thread: calculate 100! bug.

Hi,
i'm trying to calculate 100! for a project Euler problem. However, i ran into an issue while testing. The program does a correct calculation of 14! when i check the answer against google calculator. However, 15! and above doesn't give a correct answer. I've been at it for a while, so i appreciate any input:

Code:

int main()
{
    vector<int> digits(1,1);
    int power;
    cout << " enter factorial base:";
    cin >> power;
    for (int i=1 ; i <= power ; ++i)
    {
        vector<int> multiplier;
        auto tmpi = i;
        while( tmpi != 0 )
        {
            multiplier.push_back(tmpi % 10);
            tmpi /= 10;
        }

        auto mulit = multiplier.begin();
        int pos = 0;
        vector<int> tmpvector(digits);
        while (mulit != multiplier.end())
        {
            deque<int> tmpdeque;
            for (int j = 0 ; j < pos ; ++j)
                tmpdeque.push_back(0);

            /*
            cout << "tmpdeque init " << pos << "multi=" << (*mulit) << " |";
            copy(tmpdeque.begin(),tmpdeque.end(),ostream_iterator<int>(cout,""));
            cout << endl;
            */

            int addforward = 0;
            for (auto it = digits.begin() ; it != digits.end() ; ++it)
            {
                int tmp = (*it) * (*mulit) + addforward;
                tmpdeque.push_back(tmp % 10);
                addforward = tmp / 10;

                /*
                cout << "in tmpdeque tmp="<< tmp << " it-> " << (*it) << " multi->"<< (*mulit);
                cout << "\n";
                copy(tmpdeque.rbegin(),tmpdeque.rend(),ostream_iterator<int>(cout,""));
                cout << "\n";
                copy(digits.rbegin(),digits.rend(),ostream_iterator<int>(cout,""));
                cout << endl;
                */
            }
            if (addforward != 0)
                tmpdeque.push_back(addforward);

            /*
            cout << "tmpdeque:";
            copy(tmpdeque.rbegin(),tmpdeque.rend(),ostream_iterator<int>(cout,""));
            cout << endl;
            */

            int size = tmpvector.size();
            int index=0;
            addforward=0;
            while (!tmpdeque.empty())
            {
                int a = tmpdeque.front();
                tmpdeque.pop_front();
                if (index < size)
                {
                    if (pos == 0)
                        tmpvector[index] = a;
                    else
                    {
                        addforward += a;
                        tmpvector[index] += addforward;
                        addforward = tmpvector[index] / 10;
                        tmpvector[index] %= 10;
                    }
                    ++index;
                }
                else
                {
                    addforward += a;
                    if (addforward<10)
                        tmpvector.push_back(addforward);
                    else
                    {
                        tmpvector.push_back(addforward/10);
                        tmpvector.push_back(addforward%10);
                    }
                }
                /*
                cout << "tmpvector:" << a << "|";
                copy(tmpvector.rbegin(),tmpvector.rend(),ostream_iterator<int>(cout,""));
                cout << endl;
                */
            }
            /*
            tmpvector.clear();
            */
            cout << endl;
            ++pos;
            ++mulit;
        }
        digits.swap(tmpvector);
        cout << "digits "<< i << "!:";
        copy(digits.rbegin(),digits.rend(),ostream_iterator<int>(cout,""));
        cout << endl;
    }
    int sum = 0;
    cout << power <<"! = ";
    for (vector<int>::reverse_iterator rit = digits.rbegin() ; rit != digits.rend() ; ++rit)
    {
        cout << *(rit);
        sum += *rit;
    }
    cout << "\n sum of digits  " << sum << endl;

Log2[100!] ~= 525, i.e. it would take at least 525 bits to represent such a number. There is no such standard data type, hence it's an overflow. Ints are 32 to 64 bits, depending on system and operating system. There's no way it can represents a number that large.

I don't see an overflow problem here. The poster is storing the result as a vector of individual decimal digits, so none of the numbers anywhere should be larger than 100.

That shouldn't overflow either. 100! is on the order of 10^157th so the digital sum must be less than 1,413 (which would be the sum of 157 '9' digits).

And the poster implied his problem was with the calculation of 15!, not the digital sum of 15!, and there I don't see where it could overflow.

O_o

You are accumulating the largest carry at the wrong time.

Soma

I couldn't figure out head or tail with that mess. I just rewrote the whole thing with an array. at least it worked.

thank you everyone for your input.

Code:

#include <iostream>


using namespace std;

int main()
{
    const int size = 200;
    int digits[size];
    for (auto i=0 ; i < size ; ++i)
        digits[i]=0;
    digits[0] = 2;
    for (auto i = 3 ; i <= 100 ; ++i)
    {
        for (auto j = 0 ; j < size ; ++j)
        {
            int tmp = i;
            if ((i%10) == 0)
                tmp = i / 10;
            digits[j] *= tmp;
        }

        for (auto j = 0; j < size ; ++j)
        {
            int addforward = digits[j]/10;
            digits[j] %= 10;

            auto k = j+1;
            while(addforward != 0)
            {
                digits[k] += (addforward % 10);
                addforward /= 10;
                ++k;
            }
        }
    }
    int count=0;
    for (auto i = (size-1) ; i>=0 ; --i)
    {
        cout << digits[i];
        count += digits[i];
    }
    cout << "\n" << endl;
    cout << count << endl;
}

Part of the original problem in the original code was related to addforward. There was no guarantee that addforward would be in the range 0-9, but some code acted as if it was.