Omnimaga
General Discussion => Technology and Development => Computer Programming => Topic started by: Munchor on June 16, 2011, 05:38:03 pm
-
I was trying to make a C Program that returns the factorial of a given number without using any libraries (besides stdio.h).
#include <stdio.h>
int main();
int factorial(int n);
int main() {
int n;
scanf("%d",&n);
int i;
for (i=0;i<n;i++)
{
int x;
scanf("%d",&x);
printf("%i\n",factorial(x));
}
return 0;
}
int factorial(int n)
{
if (n==0)
{
return 1;
}
int sum = 1;
int i;
for (i=n;i>0;i--)
{
sum = sum*i;
}
return sum;
}
That's my code, the first line of input is supposed to be the number of inputs. Then for each input I output its factorial.
It works fine for me. However, this (https://www.spoj.pl/problems/FCTRL2/) won't accept it. Any ideas?
-
You should replace
printf("%i",factorial(x));with
printf("%i\n",factorial(x));
You forgot the newlines.
EDIT: Ninja'd?
-
The numbers are getting way too big. You'd have to use some sort of arbitrary-precision math or something (considering it can go up to 100!)
-
Try using doubles. Integers will definitely not go up to the factorial of 100, which has 157 digits. You'll lose precision in the lower digits, but that may not be not important.
-
Doubles will definitively do the job. 32-bit integers will only hold up to 12!, while 64-bit will hold up to 20!. Doubles will hold up to 170!.
Note that 100! = 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000.
-
Ah, doubles will hold numbers as large as 170! but will you get all of the decimal precision? I think not, if I remember correctly the double in C only allows for around 16 decimal digits
-
52 bits of precision's not enough indeed. You might want to try binary-coded decimal (BCD) and figure out how to multiply stuff in BCD.
I did some BCD in Axe today to hold up to a lot of digits.
-
Or it might be even easier to just store individual digits in an array (even though that wastes a little bit of space).
-
Yeah, same principle as BCD. You have to store each digit separately and figure out multiplication with that.
-
That may or may not be faster depending on CPU design, memory bandwidth, caching, integer size, et cetera. If you have high-latency memory, BCD may well make things much faster, as the code for screwing with the individual nibbles could be faster than the penalty for a cache miss.
The Z80 has instructions for helping with BCD a little, namely the DAA instruction. You might consider making an Axiom of a generic open source BCD library.
-
That may or may not be faster depending on CPU design, memory bandwidth, caching, integer size, et cetera. If you have high-latency memory, BCD may well make things much faster, as the code for screwing with the individual nibbles could be faster than the penalty for a cache miss.
The Z80 has instructions for helping with BCD a little, namely the DAA instruction. You might consider making an Axiom of a generic open source BCD library.
I'm talking about Scout's C program ;)
-
Yeah, I first addressed, that, and the I addressed the BCD in Axe. I'm assuming that Scout is coding for a PC, and I thought that it might be worth pointing out that there are performance considerations in which you choose.
-
Ah, doubles will hold numbers as large as 170! but will you get all of the decimal precision? I think not, if I remember correctly the double in C only allows for around 16 decimal digits
If it's an integer data type, then yes. A double floating point number will not have the precision, though. As for BCD...
Anyone who uses BCD for any reason other than ease of use should be shot :P
You get all the precision of a floating point number with a little more than half the space efficiency.
If you need to operate on large numbers without math.h, then I recommend using arrays to store your numbers. 100! takes up 66 bytes in integer format, so a custom routine that malloc's an array and then applies the operations to that array will be able to represent massive numbers with no loss of precision. You'll also likely want to improve that algorithm with numbers like 100! :P
-
Ah, doubles will hold numbers as large as 170! but will you get all of the decimal precision? I think not, if I remember correctly the double in C only allows for around 16 decimal digits
If it's an integer data type, then yes. A double floating point number will not have the precision, though. As for BCD...
Anyone who uses BCD for any reason other than ease of use should be shot :P
You get all the precision of a floating point number with a little more than half the space efficiency.
If you need to operate on large numbers without math.h, then I recommend using arrays to store your numbers. 100! takes up 66 bytes in integer format, so a custom routine that malloc's an array and then applies the operations to that array will be able to represent massive numbers with no loss of precision. You'll also likely want to improve that algorithm with numbers like 100! :P
I recommend storing in decimal because he's going to have to output the values in human-readable format. I assume he won't want to make a routine to extract decimal digits from a large binary number.
-
Well yeah. You have to store each decimal digit separately and allow for a seemingly infinite number of digits. That's how BCD works, kinda.
-
I recommend storing in decimal because he's going to have to output the values in human-readable format. I assume he won't want to make a routine to extract decimal digits from a large binary number.
It's not terribly difficult to convert to decimal, but yeah.
Example psuedo-code for Hex array->Dec:
int arraysize;
char *array;
char *output;
int j = 0;
For(i,i<arraysize,i++) {
stream = *array[i];
if stream>0x0A {
*array[j] = 0x31;
j = j+1;
stream = stream % 10;
}
*array[j] = stream + 0x30;
j = j+1;
}
-
I recommend storing in decimal because he's going to have to output the values in human-readable format. I assume he won't want to make a routine to extract decimal digits from a large binary number.
It's not terribly difficult to convert to decimal, but yeah.
Example psuedo-code for Hex array->Dec:
int arraysize;
char *array;
char *output;
int j = 0;
For(i,i<arraysize,i++) {
stream = *array[i];
if stream>0x0A {
*array[j] = 0x31;
j = j+1;
stream = stream % 10;
}
*array[j] = stream + 0x30;
j = j+1;
}
That's assuming each byte holds a value from 0-99 (or 0x00 to 0x63 if you prefer). Binary numbers are in base 2, not base 100.
-
Actually, it assumes a value from 0x0 to 0xF, which just proves that BCD is better :P
-
Oh yeah, cause when you display 0xFFFF, it turns out as 15151515! Nice to know :D
-
I see everyone, I tried this:
#include <stdio.h>
int main();
double factorial(int n);
int main() {
int n;
scanf("%d",&n);
int i;
for (i=0;i<n;i++)
{
int x;
scanf("%d",&x);
printf("%f\n",factorial(x));
}
return 0;
}
double factorial(int n)
{
if (n==0)
{
return 1;
}
double sum = 1;
int i;
for (i=n;i>0;i--)
{
sum = sum*i;
}
return sum;
}
But it returns "inf" for all numbers :/
-
Well, you're not declaring x to be anything but null, so..
-
Well, you're not declaring x to be anything but null, so..
Oh I see, but I also tried this and get the same output:
#include <stdio.h>
int main();
double factorial(double n);
int main() {
int n;
scanf("%d",&n);
int i;
for (i=0;i<n;i++)
{
double x;
scanf("%lf",&x);
printf("%lf\n",factorial(x));
}
return 0;
}
double factorial(double n)
{
if (n==0)
{
return 1;
}
double sum = 1;
int i;
for (i=n;i>0;i--)
{
sum = sum*i;
}
return sum;
}
-
He means you are not initializing X with a value, you are just going int X or double X, which creates the variable, but it holds no value.
-
And both of you seem to be missing the scanf() with argument of &x.
-
He means you are not initializing X with a value, you are just going int X or double X, which creates the variable, but it holds no value.
double x;
scanf("%lf",&x);
I get it through input.
-
Bump anybody?
-
Try this? It's just a different method of calculating the factorial.
#include <stdio.h>
int main();
double factorial(double n);
int main() {
int n;
scanf("%d",&n);
int i;
for (i=0;i<n;i++)
{
double x;
scanf("%lf",&x);
printf("%lf\n",factorial(x));
}
return 0;
}
double factorial(double n)
{
if ((n == 1) || (n == 0))
{
return(1);
}
else
{
return(n * factorial(n - 1));
}
}