For a while now i have been "playing" with a little C program to

compute the factorial of large numbers. Currently it takes aboy 1

second per 1000 multiplications, that is 25000P1000 will take about a

second. It will be longer for 50000P1000 as expected, since more digits

will be in the answer. Now, on the Num Analyses forum/Group there is a

post reaporting that that person wrot java code that computed 1000000!

in about a second. That is about 10000 times faste than I would expect

my code to do it. So the two possiblilities are:

1) I am doing something terribly wrong

2) The othr person is lying

At the moment i am inclined to believe that its number 1.

I am posing my code below, I would like to hear your opinions about

why it is slow and how i can improove its speed.

I know that there are public BIGNUM libraries which are already

optimized for such calculations, but I dont want to use them, bcause i

want to approach this problem on a lower level. I am mostly interested

to find out how to get this code perform faster or what alternative

algorythms i should consider. The factorial calculation is just a test

program.

===================start paste==========================

#include<stdio.h>

#include<stdlib.h>

#include<math.h>

#define al 1024*20

#define base 1000

typedef long int IntegerArrayType;

struct AEI{

IntegerArrayType data[al];

long int digits;

};

void pack(IntegerArrayType i, struct AEI *N1);

void Amult(struct AEI * A, struct AEI * B, struct AEI * C);

void AEIprintf(struct AEI * N1);

void AEIfprintf(FILE * fp, struct AEI * N1);

int main(void)

{

struct AEI *N1, *MO, *Ans;

long i = 0, j = 0, ii, NUM, iii;

FILE *ff;

N1=malloc(sizeof(struct AEI));

MO=malloc(sizeof(struct AEI));

Ans=malloc(sizeof(struct AEI));

while (i < al){

N1->data[i] = 0;

MO->data[i] = 0;

Ans->data[i]=0;

i++;

}

printf("Enter integer to Factorialize: ");

scanf("%ld", &NUM);

pack(1, N1);

pack(1, Ans);

ff = fopen("Results.txt", "w");

printf("you entered: %ld", NUM);

i=1;

while(i < NUM ){

iii=0;

while(iii<NUM && iii<1000){

ii = 1;

while (ii < al)

{

MO->data[ii] = 0;

ii++;

}

pack((i+iii), MO);

Amult(N1, MO, N1);

iii++;

}

i+=iii;

Amult(Ans, N1, Ans);

printf("\nProgress is: %d",i);

pack(1, N1);

}

if(ff!=NULL){

fprintf(ff,"\n%d\n",i-1);

AEIfprintf(ff, Ans);

}

fclose(ff);

printf("\nProgress: 100\%");

return 0;

}

void AEIprintf(struct AEI *N1){

float fieldLength;

double temp;

char format1[8];

long j, FL0;

j = N1->digits-1;

FL0=(long)log10((float)base);

fieldLength = (float)log10((float)base);

temp = modf(fieldLength, &fieldLength);

format1[0] = '%';

format1[1] = '0';

format1[2] = fieldLength + 48;

format1[3] = 'd';

format1[4] = 0x00;

printf("%*d", FL0, N1->data[j]);

j--;

while (j >= 0)

{

printf(format1, N1->data[j]);

j--;

}

return;

}

void AEIfprintf(FILE * fp, struct AEI *N1){

long j = N1->digits-1;

double fieldLength, temp;

char format0[8], format1[8];

fieldLength = (int)log10(base);

temp = modf(fieldLength, &fieldLength);

format0[0] = '%';

format0[1] = fieldLength + 48;

format0[2] = 'd';

format0[3] = 0x00;

format1[0] = '%';

format1[1] = '0';

format1[2] = fieldLength + 48;

format1[3] = 'd';

format1[4] = 0x00;

fprintf(fp,format0, N1->data[j]);

j--;

while (j >= 0){

fprintf(fp, format1, N1->data[j]);

j--;

}

return;

}

void pack(IntegerArrayType i, struct AEI * N1)

{

long t = 1, i1, j = 0;

while (t == 1){

i1 = i % base;

N1->data[j] = i1;

i = (i - i1) / base;

j++;

if (i == 0)

t = 0;

}

N1->digits=j;

return;

}

void Amult(struct AEI * A, struct AEI * B, struct AEI * C){

/*C = A * B; */

long i, ii,d, result, carry=0, digits=0;

struct AEI *Ans;

Ans=malloc(sizeof(struct AEI));

i=0;

d= (A->digits+B->digits-1);

while(i<d){

Ans->data[i]=carry;

carry=0;

ii=0;

while(ii<=i){

if(B->data[ii]!=0){

Ans->data[i]+=A->data[i-ii]*B->data[ii];

carry+=Ans->data[i]/base;

Ans->data[i]=Ans->data[i]%base;

}

ii++;

}

carry+=Ans->data[i]/base;

Ans->data[i]=Ans->data[i]%base;

i++;

}

if(carry!=0){

d++;

Ans->data[i]=carry;

}

C->digits=d;

i=0;

while(i<d){

C->data[i]=Ans->data[i];

i++;

}

return;

}

====================end paste============================

I tried to indent the code with spaces instead of tabs, but if some

parts end up not properly indented, I hope no one will hold it against

me.

Thanks ahead