500!

  • Thread starter Thread starter barhoooooom
  • Start date Start date
B

barhoooooom

hello, hows life? mine is good ;)

as I was surfing the net, I found a little question, it wants a progra
that gets the factorial of any number only less than 1000....you kno
what is 30! ...? it is simply 2.6525285981219105863630848e+32

so if I am going to get 500! or maybe 1000! then you can imagine ho
big the number is.

I thought of using an array whose elements are the digits of my bi
number, then write a function that adds two big numbers, then agai
write another function that multiplies two big numbers using th
addition function.

then just use this function in the famous factorial recursiv
solution.

it is a very stupid solution, very stupid and illogical, because...
wrote the addition and multiplication functions, and as I tried t
multiply 1000*1000, it took about 2 full long seconds, then again fo
10000*10000 it took about 20 seconds.

this is stupid, because I am not even yet using a big number, usin
long int I can get the answer of this in less than a second. s
imagine what happens when I get 500! wow, dont want to think.

any ways, here is my code,

* if you have any optimizations to the additiona and multiplicatio
functions, then please point them out, I thought of passing the resul
as a reference instead of returning it every time, but I can't think o
more performance optimizations.

* if you have a better way for manipulating huge numbers then pleas
point it out (in C++ only ofcourse not java)

* if you have a solution for this 500! problem then please, I'd like t
know it.

I am not sure if any one will bother read my long email and help me ge
1000! ....!! I'll just throw the question in this forum. hope some on
does



copy and paste it please into your compiler before reading it.





#include <iostream>
#include <deque>
#include <string>
using namespace std;
/**********************************************************************************/

/* functions to be used in the program */
void getBigNum(deque<int> &);
void outBigNum(deque<int> &);
deque<int> addBigNum(deque<int> &, deque<int> &);
deque<int> multiplyBigNum(deque<int> &, deque<int> &);


/**********************************************************************************/

int main()
{
//the big numbers are stored as deques of intacters
deque<int> BigNum1;
deque<int> BigNum2;
deque<int> answer;


// get the big numbers from the user
getBigNum(BigNum1);
getBigNum(BigNum2);

outBigNum(BigNum1);
cout << "*";
outBigNum(BigNum2);
cout << " = ";

//multiply the two big numbers and output the result
answer = multiplyBigNum(BigNum1, BigNum2);
outBigNum(answer);
cout<<endl;


return 0;
}
/**********************************************************************************/




/**********************************************************************************/
//get the big integer from the user
void getBigNum(deque<int> & num)
{
string temp;
cin >> temp;

for(int i=0; i<temp.size(); i++)
num.push_back(temp-48);
}
/**********************************************************************************/





/**********************************************************************************/
// output the big number
void outBigNum(deque<int> & num)
{
for(int i=0; i<num.size(); i++)
cout << num;
}
/**********************************************************************************/






/**********************************************************************************/
//add two big numbers and return the result
deque<int> addBigNum(deque<int> & n1, deque<int> & n2)
{
int MAX;

//give MAX the size of the larger number
if(n1>n2 && n1.size()>=n2.size())
MAX=n1.size();
else
MAX=n2.size();

deque<int> result(MAX+1), carry(MAX+1), num1(MAX+1), num2(MAX+1);

//initialize the new deques to 0;
for(int i=0; i<=MAX; i++)
{ carry=0; num1=0; num2=0;}

//copy n1 into num1 with leading zeroes if it is the smaller in size
for(i=0; i<n1.size(); i++)
num1[MAX-i] = n1[n1.size()-i-1];

//copy n2 into num2 with leading zeroes if it is the smaller in size
for(i=0; i<n2.size(); i++)
num2[MAX-i] = n2[n2.size()-i-1];

int sum;

/*********** here goes the addition ***********/
for(i=0; i<=MAX; i++)
{
sum = num1[MAX-i] + num2[MAX-i] + carry[MAX-i];

if( sum < 10)
result[MAX-i] = sum;
else
{
result[MAX-i] = (sum) - 10;
carry[MAX-i-1]=1;
}
}

//remove the unnecessary 0 if it exists
if(result[0]==0)
result.pop_front();

return result;
}
/*********************************************************************************/









/**********************************************************************************/
//multiply two big numbers and return the result
deque<int> multiplyBigNum(deque<int> &n1, deque<int> &n2)
{
deque<int> counter(1), result, one(1);
counter[0]=1;
result=n2;
one[0]=1;

while(counter.size()!=n1.size() || counter<n1)
{
result = addBigNum(n2, result);
counter = addBigNum(counter,one);
}
return result;
}
/**********************************************************************************/
 
barhoooooom said:
it is a very stupid solution, very stupid and illogical, because... I
wrote the addition and multiplication functions, and as I tried to
multiply 1000*1000, it took about 2 full long seconds, then again for
10000*10000 it took about 20 seconds.
Click to expand...

Someone may help solve the problem you posed.

If no one does, you may want to search the net for one of the "big integer"
libraries on the net. As the numbers used in strong cryptography often have
thousands of bits, you can use a library to keep from reinventing the wheel.

Regards,
Will
 
barhoooooom said:
hello, hows life? mine is good ;)

as I was surfing the net, I found a little question, it wants a
program
that gets the factorial of any number only less than 1000....you know
what is 30! ...? it is simply 2.6525285981219105863630848e+32
Click to expand...

How do you want the answer expressed? In particular, do you want a decimal
representation, or would a binary representation be sufficient?

If you want decimal, then you're probably best off doing the entire
calculation in decimal, otherwise you can do the calculation in binary.
Converting a very large binary number to decimal involves implementing
large-number division, which is rather slow and tricky compared to
multiplication.
I thought of using an array whose elements are the digits of my big
number, then write a function that adds two big numbers, then again
write another function that multiplies two big numbers using the
addition function.
Click to expand...

That's O(N*M) complexity so it's going to tend to be slow alright!
then just use this function in the famous factorial recursive
solution.

it is a very stupid solution, very stupid and illogical, because... I
wrote the addition and multiplication functions, and as I tried to
multiply 1000*1000, it took about 2 full long seconds, then again for
10000*10000 it took about 20 seconds.
Click to expand...

You must have missed some optimizations - after all, when you learned in
school how to multiply 1000*1000, you didn't add 1000 to an accumulator 1000
times...

A key observation for this particular problem is that for any pair of
numbers you're trying to multiply, one of the numbers will be "small" (<=
1000) and one of the numbers will be "large" - possibly quite large.
Presumably since you went to the trouble you did, you're looking for an
exact result of n!, not a floating point approximation.

-cd
 
hello, hows life? mine is good ;)

it's my birthday :)
as I was surfing the net, I found a little question, it wants a program
that gets the factorial of any number only less than 1000....you know
what is 30! ...? it is simply 2.6525285981219105863630848e+32 [...]
then just use this function in the famous factorial recursive
solution.
Click to expand...

perfwise this is not the best solution. have a look at

http://www.luschny.de/math/factorial/FastFactorialFunctions.htm

also gives code examples (in c# and java)

hth
ben
 
Back
Top