Compute the factorial of a large number

Problem

Compute the factorial of a large number

Solution

#include <iostream>

#include <iomanip>

using namespace std;

int get_computer_bitsize()

{

unsigned int x = ~0;

unsigned cnt = 0;

while(x){

cnt ++;

x = x & (x -1);

}

return cnt;

}

void print_factorial(unsigned int a[], unsigned int b[], int len)

{

bool start_print = false;

for(int i = len; i >= 0; i--){

if(b[i] != 0 || a[i] != 0){

start_print = true;

}

if(!start_print) continue;

cout.setf(ios::right|ios::adjustfield);

cout << " ";

cout.width(4);

cout << hex <<setfill('0') << b[i];

cout << " ";

cout.width(4);

cout << hex <<setfill('0') << a[i];

}

cout << endl;

}

void calc_factorial(unsigned int a[], int len, int num)

{

unsigned int *b = new unsigned int[len + 1];

int bitsize = get_computer_bitsize();

unsigned int half_max = (1 << (bitsize / 2)) - 1;

for(int i = 0; i < len; i++){

a[i] = 0;

b[i] = 0;

}

a[0] = 1;

for(int n = 1; n <= num; n ++){

for(int i = 0; i < len - 1; i++){

a[i] = a[i] * n;

b[i] = b[i] * n;

}

for(int i = 0; i < len - 1; i ++){

if(a[i] > half_max){

b[i] += (a[i] >> (bitsize / 2));

a[i] = (a[i] & half_max);

}

if(b[i] > half_max){

a[i + 1] = a[i + 1] + (b[i] >> (bitsize / 2));

b[i] = b[i] & half_max;

}

}

}

print_factorial(a, b, len - 1);

delete[] b;

}

int main(int argc, char* argv[])

{

cout << get_computer_bitsize() << endl;

unsigned int a[100];

for(int i = 1; i < 40; i ++){

cout.width(4);

cout << i << "! -----------------------";

calc_factorial(a, 100, i);

}

return 0;

}

Output

1! ----------------------- 0000 0001

0002! ----------------------- 0000 0002

0003! ----------------------- 0000 0006

0004! ----------------------- 0000 0018

0005! ----------------------- 0000 0078

0006! ----------------------- 0000 02d0

0007! ----------------------- 0000 13b0

0008! ----------------------- 0000 9d80

0009! ----------------------- 0005 8980

000a! ----------------------- 0037 5f00

000b! ----------------------- 0261 1500

000c! ----------------------- 1c8c fc00

000d! ----------------------- 0000 0001 7328 cc00

000e! ----------------------- 0000 0014 4c3b 2800

000f! ----------------------- 0000 0130 7777 5800

0010! ----------------------- 0000 1307 7775 8000

0011! ----------------------- 0001 437e eecd 8000

0012! ----------------------- 0016 beec ca73 0000

0013! ----------------------- 01b0 2b93 0689 0000

0014! ----------------------- 21c3 677c 82b4 0000

0015! ----------------------- 0000 0002 c507 7d36 b8c4 0000

0016! ----------------------- 0000 003c eea4 c2b3 e0d8 0000

0017! ----------------------- 0000 0579 70cd 7e29 3368 0000

0018! ----------------------- 0000 8362 9343 d3dc d1c0 0000

0019! ----------------------- 000c d4a0 619f b090 7bc0 0000

001a! ----------------------- 014d 9849 ea37 eeac 9180 0000

001b! ----------------------- 232f 0fcb b3e6 2c33 5880 0000

001c! ----------------------- 0000 0003 d925 ba47 ad2c d59d ae00 0000

001d! ----------------------- 0000 006f 9946 1a1e 9e14 32dc b600 0000

001e! ----------------------- 0000 0d13 f637 0f96 865d f5dd 5400 0000

001f! ----------------------- 0001 956a d0aa e33a 4560 c5cd 2c00 0000

0020! ----------------------- 0032 ad5a 155c 6748 ac18 b9a5 8000 0000

0021! ----------------------- 0688 589c c0e9 505e 2f2f ee55 8000 0000

0022! ----------------------- de1b c4d1 9efc ac82 445d a75b 0000 0000

0023! ----------------------- 0000 001e 5dcb e8a8 bc8b 95cf 58cd e171 0000 0000

0024! ----------------------- 0000 0445 30ac b7ba 83a1 1128 7cf3 b3e4 0000 0000

0025! ----------------------- 0000 9e00 08f6 8df5 0647 7ada 0f38 fff4 0000 0000

0026! ----------------------- 0017 7401 5499 125e ee9c 3c5e 4275 fe38 0000 0000

0027! ----------------------- 0392 ac33 e351 cc76 59cd 325c 1ff9 ba88 0000 0000