Author |
Topic: Unbounded Multiplication (Read 1215 times) |
|
mad
Junior Member
Posts: 118
|
 |
Unbounded Multiplication
« on: Mar 8th, 2008, 5:35pm » |
 Quote  Modify
|
Write a program to calculate factorial of nos till 300! or even 400!
Should we use normal multiplication technique storing each digit in a number as an integer and then multiplying normally or Karatsuba algorithm etc. is required?
|
|
 IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 2084
|
|
Re: Unbounded Multiplication
« Reply #1 on: Mar 10th, 2008, 6:13am » |
Quote Modify
|
Three or four hundred factorial is still under a thousand (decimal) digits -- and only around 2000 bits -- not really much of a stress for a modern computer. "Gradeschool" multiplication and a naive factorial algorithm (just multiply by each number) will work just fine.
#include <iostream>
#include <vector>
using namespace std;
class bigint {
vector<unsigned long> digits; // each element stores 9 decimal digits
public:
bigint(unsigned long x) { digits.push_back(x); }
bigint & operator *= (unsigned long x) {
unsigned long long t = 0;
for(unsigned int i = 0; i < digits.size(); i++) {
t += digits[i] * (unsigned long long)(x);
digits[i] = (unsigned long)(t % 1000000000UL);
t /= 1000000000UL;
}
if (t != 0) digits.push_back(t);
return *this;
}
friend ostream & operator << (ostream & o, const bigint & x);
};
ostream & operator << (ostream & o, const bigint & x) {
// print first digit group without leading zeros
o << x.digits.back();
// print rest of digit groups with leading zeros
int width = o.width(); char fill = o.fill('0');
for(unsigned int i = x.digits.size(); i > 1; i--) {
o.width(9); o << x.digits[i-2];
}
o.width(width); o.fill(fill);
return o;
}
int main(void) {
const unsigned long N = 400;
bigint f(1);
for(unsigned long i = 2; i <= N; i++) f *= i;
cout << f;
return 0;
}
Now, if you wanted a million factorial, that would be more challenging. The biggest improvement would be to use a better factorial algorithm; calculate the number of factors of each prime which will be present in the result (in the same way that "how many zeros in n!" is solved), then use a parallel binary powering algorithm to do the calculation. At those sizes, Karatsuba would probably help, although only for the largest few multiplications.
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
johny_cage
Full Member
Gender:
Posts: 155
|
|
Re: Unbounded Multiplication
« Reply #2 on: Mar 20th, 2008, 7:09am » |
Quote Modify
|
I already calculate 1,00,000 factorial using linked list. It took around 35 mins on my 3 Ghz 64-bit Intel PC with 512 MB RAM support. So, you can easily do with linked list (storing 9 digits in each node).
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print