Thread: calculate 100! bug.

  1. #1
    -bleh-
    Join Date
    Aug 2010
    Location
    somewhere in this universe
    Posts
    463

    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;
    "All that we see or seem
    Is but a dream within a dream." - Poe

  2. #2
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,795
    You're most certainly having an overflow

    PS, I've done that PE problem and brute forcing it is not likely to work (even using an arbitrary precision library)

  3. #3
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,795
    I'm at home now and checked the solution I came up with. If you want hints you'd better ask, otherwise people might not respond (other than indicating the overflow issue). I'm assuming it's #20. I don't think I'm ruining anything for you by saying that with a bit of thinking you definitely don't have to, and probably don't want to, "brute force" this.

    Cheers

  4. #4
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    2,665
    Well, assuming you get to 100!, I don't think there is any standard data type that can hold that value. Or at least, not to an accurate precision. Instead, implement your answer as a character array which you can dynamically allocate and reallocate.

  5. #5
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    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.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  6. #6
    Registered User
    Join Date
    May 2003
    Posts
    1,619
    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.
    You ever try a pink golf ball, Wally? Why, the wind shear on a pink ball alone can take the head clean off a 90 pound midget at 300 yards.

  7. #7
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,795
    Quote Originally Posted by Cat View Post
    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.
    Umm..

    Code:
        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;

  8. #8
    Registered User
    Join Date
    May 2003
    Posts
    1,619
    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.
    You ever try a pink golf ball, Wally? Why, the wind shear on a pink ball alone can take the head clean off a 90 pound midget at 300 yards.

  9. #9
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,795
    Quote Originally Posted by Cat View Post
    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.
    I think you make a good point there. Hodor!

  10. #10
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    5,108
    O_o

    You are accumulating the largest carry at the wrong time.

    Soma
    “Salem Was Wrong!” -- Pedant Necromancer
    “Four isn't random!” -- Gibbering Mouther

  11. #11
    -bleh-
    Join Date
    Aug 2010
    Location
    somewhere in this universe
    Posts
    463
    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;
    }
    "All that we see or seem
    Is but a dream within a dream." - Poe

  12. #12
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    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.
    Right 98% of the time, and don't care about the other 3%.

    If I seem grumpy or unhelpful in reply to you, or tell you you need to demonstrate more effort before you can expect help, it is likely you deserve it. Suck it up, Buttercup, and read this, this, and this before posting again.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Exercice - Calculate the fee
    By khelkely in forum C++ Programming
    Replies: 9
    Last Post: 10-20-2013, 06:04 AM
  2. Calculate BMI and BMR
    By nguystep in forum C Programming
    Replies: 4
    Last Post: 10-26-2011, 02:59 AM
  3. Calculate ping
    By jverkoey in forum Networking/Device Communication
    Replies: 2
    Last Post: 07-09-2004, 11:52 PM
  4. Calculate Bandwith
    By scrapedbr in forum Networking/Device Communication
    Replies: 1
    Last Post: 05-20-2004, 10:06 AM
  5. how to calculate 8/16 bits ....
    By lonewolf in forum C Programming
    Replies: 5
    Last Post: 09-06-2001, 02:14 PM