1. ## 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;
*/

for (auto it = digits.begin() ; it != digits.end() ; ++it)
{
int tmp = (*it) * (*mulit) + addforward;
tmpdeque.push_back(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;
*/
}

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

int size = tmpvector.size();
int index=0;
while (!tmpdeque.empty())
{
int a = tmpdeque.front();
tmpdeque.pop_front();
if (index < size)
{
if (pos == 0)
tmpvector[index] = a;
else
{
tmpvector[index] %= 10;
}
++index;
}
else
{
else
{
}
}
/*
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;```

2. 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. 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. 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. 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.

6. 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.

7. Originally Posted by Cat
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. 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.

9. Originally Posted by Cat
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. O_o

You are accumulating the largest carry at the wrong time.

Soma

11. 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)
{
digits[j] %= 10;

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

12. 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.