Can't do factorial for numbers greater than 12

[Crushyerbones]

Hello again :) This time I'm back with a stranger question. The following program is meant to factorialize (spelling?) a number from the command line while printing out the number of calls it made to the function "factorial".

#include <stdio.h>
#include <stdlib.h>

unsigned long long factorial(int num,int *count_ptr){
	printf("Call %u\n",*count_ptr);
	*count_ptr=(*count_ptr)+(1);
	if (num==0)
	return (1);
	num=num * (factorial(num-1,count_ptr));
	return (num);
	}

int main(int arg_num, char *argv[]){
	int num=atoi(argv[1]);

	unsigned long long output;
	
	int count=0;
	int *count_ptr;
	count_ptr=&count;
	
	output=num*factorial(num-1,count_ptr);
	printf("%llu \n",output);
	
	return 0;
}

This code is very similar to a friend of mine's but for some reason it doesn't seem to be correct for anything greater than 13. Everything works fine, including the number of calls it makes. Except for the result... I thought there was an overflow somewhere but unsigned long long didn't fix it :(

[jephthah]

compile the following program, run it, and print the results back here

#include <stdio.h>
int main()
{
  printf("sizeof(char) == %d\n", sizeof(char));
  printf("sizeof(short) == %d\n", sizeof(short));
  printf("sizeof(int) == %d\n", sizeof(int));
  printf("sizeof(long) == %d\n", sizeof(long));
  printf("sizeof(long long) == %d\n", sizeof(long long));

  return 0;
}

this will show you that 12! is good for longs, but you do indeed need a long long for 13! and greater.

meanwhile the real problem is in your type casting.

.

[jephthah]

never mind about posting the 'sizeof' vars back here. it's definitely your code that is causing the problem, not the compiler. i just wrote a program similar to yours that works. i could just post it i suppose, but that wouldn't help you out much.

the main problem is that your 'num' is declared (in both cases) as an int, yet you're trying to return one instance of it back through through the factorial function as an unsigned long long.

redeclare num as a 64-bit long. you might want to give one of the 'num's a different name just for clarity... it gets confusing when you have different variables in different functions that use the same name. confusing for the reader (and programmer!)... compiler doesnt care.

interesting though, how yours turned out, it actually gives the correct answer for 13! = 6227020800, which is clearly greater than a 32-bit number. it definitely does break down after that.

FYI, you dont really need to do "unsigned long long"... "long long" will suffice -- both of them happen to cross the 64-bit boundary at 21!, so neither of them work past 20!

[mitrmkar]

You should also handle factorial of zero i.e. 0!

[Crushyerbones]

the main problem is that your 'num' is declared (in both cases) as an int, yet you're trying to return one instance of it back through through the factorial function as an unsigned long long.

I figured it was something like that :P I thought of changing the function from int to unsigned long long but I never thought that num would eventually surpass the size I gave it. Thanks a lot :)

You should also handle factorial of zero i.e. 0!

Thanks, that will be my next step :) I decided to leave "protecting" until after if worked :P

[Crushyerbones]

FYI, you don't really need to do "unsigned long long"... "long long" will suffice -- both of them happen to cross the 64-bit boundary at 21!, so neither of them work past 20!

I've been thinking... Shouldn't unsigned double the amount of numbers I can use?

For example: Long makes me able to represent numbers between -2^63 and (2^63)-1. Since unsigned means I no longer need to represent negatives, shouldn't we be able to represent about 2^128 numbers? Is there a "real" 64 bit limit somewhere?

[jephthah]

yes... sort of. using "unsigned" increases the range of positive integers by a power of 2, because it removes the need to handle negatives.

so, for "unsigned long long", you'd have the range from (0) to (2^64) - 1 ... instead of the range -(2^63) to (2^63)-1 that you'd have for just "long long" ... but it would not give you 2^128 numbers... you'll still only have 2^64 unique numbers available, whether you use "unsigned" or not.

what i was saying is that the difference between 20! and 21! is too great for the additional range supplied by "unsigned" to be of any help, in this case.

[Crushyerbones]

yes... sort of. using "unsigned" increases the range of positive integers by a power of 2, because it removes the need to handle negatives.

so, for "unsigned long long", you'd have the range from (0) to (2^64) - 1 ... instead of the range -(2^63) to (2^63)-1 that you'd have for just "long long" ... but it would not give you 2^128 numbers... you'll still only have 2^64 unique numbers available, whether you use "unsigned" or not.

what i was saying is that the difference between 20! and 21! is too great for the additional range supplied by "unsigned" to be of any help, in this case.

Oh, I thought C worked in complements of 2 for some reason... as in 00000 = 0 and 11111 = -1, etc...

By the way, is there a way to increase the limit so we can use it for number larger than 20! ? Besides using a large array and printing the numbers out one at a time or something similar.

[jephthah]

it does work in 2's complement. i hope i didn't say something to indicate it doesn't.

consider a 4 bit number. if it's signed the range is from -(2^3) to (2^3)-1, that is, from -8 to +7 including 0. that is a total of 16 (2^4) unique numbers. if it's UNsigned, the range is from (0) to (2^4)-1, that is, from 0 to 15. that is still a total of 16 (2^4) unique numbers. apply this concept to any 'n'-bit number. so for the 64-bit number (long long) you'll still only have 2^64 unique numbers regardless if it's unsigned or signed.

as for larger factorials, i suppose you could use "double". it will give you positive range up to about 1x10E+37, with 10 digits of precision. that will give you the (approximate) value of up to 33! ... if you wanted to get fancy, you could test the input and use "long long" for values < 21 and "double" for values above that.

integers larger than 2^64 will require the use of large number caches and advanced programming beyond what your class (or myself!) should attempt to get into :P

[mitrmkar]

Anyone interested in various ways of calculating factorials should look into
http://www.luschny.de/math/factorial/FastFactorialFunctions.htm

[hammerhead]

Factorial of any number greater than 5 ends with a zero. For a larger number, the number of zeroes at the end constitute a large part of the number. If you can eliminate those zeroes it will help.

If you can simple check at the end of the factorial that if it ends with 0 then you can reduce that number by dividing it by 10. In this case

For example

6!= 720
7!=5040

7!=7*6!
now 6! is reduced to 72
7!=7*72=504
append a 0 at the end and we get 5040

you will have to maintain a counter for the number of zeroes you will be required to add at the end.

[jephthah]

well, i guess that's a trick to squeeze a couple more out.

but if you're going to try and do a "real" factorial program (not just this intro to functions), you'll need to use one of the known prime number factorization programs.

no point in reinventing the wheel.

[Crushyerbones]

Thanks for everything guys! It turns out my friend's program was also faulty, it just escaped both him and the teacher :P This exercise turned out to be way more interesting than expected :)