Factorial of a big number

[FREEZX]

Hello all!
I have a task to code a program that would find the last non-zero digit of the factorial of a given number n where 1<n<10000
so far i got this:

#include <iostream>
#include <string>
#include <sstream>
using namespace std;

int main()
{
    int a, xxx;
    unsigned long long b=1;
    string x;
    stringstream buf;
    cin>>a;
    for(int i=2; i<=a; i++) 
    {
            b=b*i;
    while(b%10==0){
                   b=b/10;
    }
}
    buf<<b;
    buf>>x;cout<<x[x.length()-1];
    system("pause");
    return 0;
}

The problem is that i cannot store the factorials of bigger numbers, and i find using arrays a little too complicated. Any help is greatly appreciated.
Regards, FREEZX

[tux4life]

It could be that you've to write your own function (which can handle strings) to multiply two numbers, in that case you can calculate factorials of very big numbers ...

[FREEZX]

the problem is in handling the big numbers

[tux4life]

the problem is in handling the big numbers

If I'm not wrong you mean: The factorials are becoming too big to store in a standard C++ datatype ?

Is that right?

[tux4life]

Maybe you should try to implement the following algorithm:

E.g: 6! = 1*2*3*4*5*6
But: 6! = (1/10) * (2/10) * (3/10) * (4/10) * (5/10) * (6/10) *(10^6)

In that case you can already calculate factorials of very high numbers as you can simply do the following:
> 6! = 0.1*0.2*0.3*0.4*0.5*0.6 = 0.00072
> Now you convert this number to a string
> Now you shift your result (in the string) by 6 times (= the number where you're calculating the factorial of) e.g:

0.00072 (before you started shifting)
0.0072 (first shift)
0.072
0.72
7.2
72
[U]720[/U] (sixth shift) ==> Now you've found the factorial of 6 !

> Now you've your factorial (in a string)

REMARK: If you're working with C-strings you shouldn't forget to reserve enough memory ...

[FREEZX]

thats what i meant when i said arrays as a string is an array of chars :)..

[tux4life]

thats what i meant when i said arrays as a string is an array of chars :)..

A c-string is an array of chars, but this algorithm is also working for C++-strings ...

[tux4life]

You could use Bignums, but you would need an extra library for that purpose:
> http://mattmccutchen.net/bigint/
> http://sourceforge.net/projects/cpp-bigint/

But as you have to implement it yourself, I think this isn't the solution ...

[tux4life]

Actually you only have to find the last non-zero digit of a factorial ...
So you even don't have to calculate the whole factorial ...

As you saw in my previous post you simply could do the following:
6! = 0.1*0.2*0.3*0.4*0.5*0.6*(10^6)
To calculate the factorial of 6 ...

Now you put this into a c-string ... (use the atof -command)
If you've don this, you only have to read out the last character of that c-string/char-array, that's the last non-zero digit of the factorial ...

So if you want to find the last non-zero digit of the factorial of 6 you calculate: 0.1*0.2*0.3*0.4*0.5*0.6 = 0.00072

> You use the atof -function to convert 0.00072 to a c-string ...
> You read out the last character of the c-string (the subscript of the last character is always returned by strlen )

[tux4life]

You can also just read out the (n+1) character of the c-string ...
If you have 6! as a string: "0.00072", you notice that the last character is always the number where you took the factorial of plus one (for the decimal point), so you don't need strlen ...

[tux4life]

Oh, sorry: I was wrong about the use of atof as it is to convert a string to a double ...
So you'll have to use for e.g: string streams to convert a number to a string ...

[tux4life]

I've found a better algorithm !
Forget about what I said and just write a function which calculates the last digit of a multiplication of two numbers ...

[FREEZX]

xD i never realised it could be this easy... wow the last non-zero digit of a factorial is most significant in finding the factorial of the next factorial.. Thank you! rep for you!

[FREEZX]

I tried to solve it but somehow my code is not working correctly. the buffer is not doing input and output correctly. here's the code:

#include <iostream>
#include <string>
#include <sstream>
using namespace std;

int main()
{
    int a, xxx;
    unsigned long long b=1;
    string x;
    stringstream buf, buff;
    cin>>a;
    for(int i=2; i<=a; i++) 
    {
            b=b*i;
    while(b%10==0){
                   b=b/10;
    }
    buff.str(string());
    buff<<b;
    cout<<buff.str()<<endl;
    buff>>x;
    b=x[x.length()-1]-48;
}
    buf<<b;
    buf>>x;
    cout<<x[x.length()-1];
    system("pause");
    return 0;
}

[tux4life]

I've found a better algorithm !
Forget about what I said and just write a function which calculates the last digit of a multiplication of two numbers ...

Actually you've to do this ...

[FREEZX]

Thats what im trying to do. i have some problems with the buff stringstream not getting the new value of b

[tux4life]

This code will calculate the last digit of a multiplication of two numbers:

#include <iostream>
#include <string>
#include <sstream>

using namespace std;

int str2int(string s);
string int2str(int i);

int main()
{
	int n1, n2, digit;
	string s1_dig, s2_dig, s3_dig;
	
	n1 = 25;
	n2 = 6;
	
	s1_dig = int2str(n1);
	s1_dig = s1_dig[s1_dig.length()-1];
	
	s2_dig = int2str(n2);
	s2_dig = s2_dig[s2_dig.length()-1];
	
	s3_dig = int2str(str2int(s1_dig)*str2int(s2_dig));
	s3_dig = s3_dig[s3_dig.length()-1];
	
	cout << s3_dig << endl;
	
	return 0;
}

int str2int(string s)
{
	stringstream ss;
	int i;
	ss << s;
	ss >> i;
	return i;
}

string int2str(int i)
{
	stringstream ss;
	string s;
	ss << i;
	ss >> s;
	return s;
}

NOTE: It might be useful to put the code in the main into an apart function (e.g: f_lastdigit(int n1, int n2) )

[tux4life]

Try one of the following links:
http://mathcentral.uregina.ca/QQ/database/QQ.09.07/s/mukesh1.html
http://www.mathpages.com/home/kmath489.htm
http://www.newdream.net/~sage/old/numbers/fact.htm
http://www.mathlinks.ro/Forum/viewtopic.php?p=577096#577096 (here's described a formula)

[iamthwee]

http://www.daniweb.com/code/snippet233.html, oops missed the purpose of calculating last non-zero digit which makes the algorithm simpler. :)

[FREEZX]

cool! i now know how it's done