unpredictable answer output of factorial

This is a discussion on unpredictable answer output of factorial within the C Programming forums, part of the General Programming Boards category; I use precision multiplication method to implement it. But when I input > 11, the answer is strange! I don't ...

  1. #1
    Registered User
    Join Date
    Apr 2005
    Posts
    77

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

  2. #2
    Registered User
    Join Date
    Nov 2006
    Posts
    176
    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

  3. #3
    Registered User
    Join Date
    Nov 2006
    Posts
    65
    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++;
    	}

  4. #4
    Registered User
    Join Date
    Nov 2006
    Posts
    176
    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.

  5. #5
    Registered User
    Join Date
    Nov 2006
    Posts
    65
    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.

  6. #6
    Registered User
    Join Date
    Apr 2005
    Posts
    77
    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;
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 4
    Last Post: 11-30-2005, 03:44 PM
  2. Formatting output into even columns?
    By Uncle Rico in forum C Programming
    Replies: 2
    Last Post: 08-16-2005, 05:10 PM
  3. Recursion
    By Lionmane in forum C Programming
    Replies: 11
    Last Post: 06-04-2005, 12:00 AM
  4. Control different DA output value!
    By Hunterhunter in forum A Brief History of Cprogramming.com
    Replies: 1
    Last Post: 03-13-2003, 11:11 AM
  5. code help :)
    By Unregistered in forum C Programming
    Replies: 4
    Last Post: 02-28-2002, 12:12 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21