I use precision multiplication method to implement it. But when I input > 11, the answer is strange! I don't know where is the bugs... hope anyone can find it. Thanks.
Code:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define MAX_SIZE 3000
#define MAX_DIGIT 3
int charToInt(char x)
{ return (int)(x-'0'); }
char intToChar(int x)
{ return (char)(x+'0'); }
void reverse(char *x, int lenX)
{
int i;
char t;
for (i = 0; i < lenX/2; i++) {
t = x[i];
x[i] = x[lenX-i-1];
x[lenX-i-1] = t;
}
}
void precMult(char *c, char *a, char *b, int *lenC, int lenA, int lenB)
{
int i, j, lenMax, lenMin;
int *tmp;
lenMax = MAX(lenA, lenB);
lenMin = MIN(lenA, lenB);
tmp = malloc((lenA+lenB+1) * sizeof *tmp);
for (i = 0; i < lenA+lenB+1; i++)
tmp[i] = 0;
printf("a = %s, b = %s\n", a, b);
reverse(a, lenA);
reverse(b, lenB);
for (i = 0; i < lenMax; i++)
tmp[i] = 0;
for (i = 0; i < lenMin; i++)
for (j = 0; j < lenMax; j++)
tmp[i+j] += charToInt(a[j])*charToInt(b[i]);
i = 0;
do {
if (tmp[i] >= 10) {
tmp[i+1] += (int)tmp[i]/10;
tmp[i] %= 10;
}
i++;
} while (tmp[i] > 0);
*lenC = i;
printf("lenA = %d, lenB = %d, lenC = %d\n", lenA, lenB, *lenC);
for (i = *lenC-1; i >= 0; i--)
c[*lenC-i-1] = intToChar(tmp[i]);
free(tmp);
}
int main()
{
char fac[MAX_SIZE], tmp[MAX_SIZE];
char digit[MAX_DIGIT];
int i, j, n, len, tmpLen;
tmp[0] = '1';
tmp[1] = '\0';
tmpLen = 1;
scanf("%d", &n);
/*
char a[] = {"12341234124"};
char b[] = {"3456"};
precMult(fac, a, b, &len, 11, 4);
for (i = 0; i < len; i++)
printf("%c", fac[i]);
printf("\n");
*/
for (i = 2; i <= n; i++) {
sprintf(digit, "%d", i);
precMult(fac, tmp, digit, &len, tmpLen, strlen(digit));
strncpy(tmp, fac, len);
tmp[len] = '\0';
tmpLen = len;
for (j = 0; j < len; j++)
printf("%c", fac[j]);
printf("\n");
}
return 0;
}
output data
Code:
12
a = 1, b = 2
lenA = 1, lenB = 1, lenC = 1
2
a = 2, b = 3
lenA = 1, lenB = 1, lenC = 1
6
a = 6, b = 4
lenA = 1, lenB = 1, lenC = 2
24
a = 24, b = 5
lenA = 2, lenB = 1, lenC = 3
120
a = 120, b = 6
lenA = 3, lenB = 1, lenC = 3
720
a = 720, b = 7
lenA = 3, lenB = 1, lenC = 4
5040
a = 5040, b = 8
lenA = 4, lenB = 1, lenC = 5
40320
a = 40320, b = 9
lenA = 5, lenB = 1, lenC = 6
362880
a = 362880, b = 10
lenA = 6, lenB = 2, lenC = 1
0
a = 0, b = 11
lenA = 1, lenB = 2, lenC = 1
0
a = 0, b = 12
lenA = 1, lenB = 2, lenC = 1
0
I think char *digit cause the problem but I know know why...