1

I want to find the number of zeroes in a factorial using Cpp. The problem is when I use really big numbers.

#include <stdio.h>
#include <math.h>

long zeroesInFact(long n)
{
long double fact=1;
long double denominator=10.00;
long double zero=0.0000;
long z=0;
printf("Strating loop with n %ld\n",n);
for(int i=2;i<=n;i++)
{
    fact=fact*i;
    printf("Looping with fact %LF\n",fact);
}
printf("Fmod %lf %d\n",fmod(fact,denominator),(fmod(fact,denominator)==zero));
while(fmod(fact,denominator)==zero)
{
    fact=fact/10;
    z++;
}
printf("Number of zeroes is %ld\n",z);
return z;
}

int main()
{
long n;
long x;
scanf("%ld",&n);
for(int i=0;i<n;i++)
{
    scanf("%ld",&x);
    printf("Calling func\n");
    zeroesInFact(x);
}
return 0;
}

I think the problem here is that

fmod(fact,denominator) gives me the correct answer for factorial of 22 and denominator as 10.00 (which is 0.000). But it gives me the wrong answer for factorial of 23 and denominator as 10.00

Shashank Singh
  • 283
  • 1
  • 5
  • 16
  • 2
    Hint: the number of zeroes in a product is related to the number of `5`s and `2`s in the list of prime factors of the multiplicands. – Robᵩ May 04 '12 at 14:50
  • 1
    Not at all. 11^5 = 161051. It is not clear if the OP is interested in the `number of zeroes` as he stated or if he really wants the `number of TRAILING zeroes`. From his code it looks like he wants the second. – fjardon May 04 '12 at 15:17
  • Maybe [this related discussion](http://stackoverflow.com/q/2847069/312172) is interesting for you. – user unknown May 04 '12 at 15:26

1 Answers1

3

Consider this your first lesson in numeric precision. The types float, double, and long double store approximations, not exact values, which means they are typically unsuitable for this sort of calculation. Even when they have enough precision for correct answers, you're still usually better off using integer numeric types instead, like int64_t and uint64_t. Sometimes you even even have a 128-bit integer type available. (e.g. __int128 might be available with Microsoft Visual Studio)

Honestly, I think you were lucky to get the right answer for 18! through 22!.

If long double truly is quadruple precision on your platform, you should be able to compute up to 30!, I think. You made a mistake when you used fmod -- you meant to use fmodl.

Your second lesson in precision is that when you need a lot of it, your basic data types simply aren't good enough. While you can write your own data types, you're probably better off using a pre-existing solution. The Gnu Multiple Precision Arithmetic Library (GMP) is a good, and fast one you can use in C/C++.

Alternatively, you could switch languages -- e.g. pythons integer data type is arbitrary precision (but not as fast as GMP), so you wouldn't even have to do anything special. Java has the BigInteger class for doing such computations.

Your third lesson is precision is to find ways to do without. You don't actually need to compute 23! in its full glory to find the number of trailing zeroes. With care, you can organize your calculation to discard extra precision you don't need. Or, you can switch to an entirely different method of obtaining this number, such as what Rob was hinting at in his comment.