Thread: unpredictable answer output of factorial

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...

I didn't look threw everything, but I have an idea why it may not be working.

output is wrong for > 9 not 11 it looks like to me
and then you said it looks like its char *

whats the difference between 1, 2, 3, 4, 5, 6, 7, 8, 9 and 10, 11, 12, 13, 14, 15.....99
then think of how char * could be a problem

I just had a quick look at it also, the code should be able to calculate the fractorial properly if you change the while loop. Right now, you cannot multiply by 10, because your loop will terminate early (it's not really a problem related to char length, but rather than tmp[i] can well be 0 when multiplying certain numbers). Here's a rough example of how to fix it. (It will produce too many leading zeros in many cases. You may need a little more code to strip them)

Code:

int n = lenA + lenB;

i = 0;
	while(n--) {
		if (tmp[i] >= 10) {
			tmp[i+1] += (int)tmp[i]/10;
			tmp[i] %= 10;
		}
		i++;
	}

you need to add some whitespace as well, and maybe comment a bit. more informative variable naming would be a plus aswell, its farily hard to follow this.

Just to expand on what sl4nted said... you need to be careful how you use len/A/B/Max/Min. Seems your function assumes the length of a always to be bigger than b. Maybe you should use lenA/B, rather than lenMAX for the loops. Also, calloc is probably more efficient than looping over the array (twice) to set ints to 0.

I have fixed it. A few bugs here. But now it is correct.

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 5000
#define MAX_DIGIT 4

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;
	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 || i < lenA+lenB-1);
	*lenC = i;
	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, n, len, tmpLen;
	while (scanf("%d", &n) != EOF) {
		if (n == 0) printf("1\n");
		else {
			tmp[0] = '1';
			tmp[1] = '\0';
			tmpLen = 1;
			for (i = 1; 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 (i = 0; i < len; i++)
				printf("%c", fac[i]);
			printf("\n");
		}
	}
	return 0;
}