c++ - 一个非常非常长的数的模数 (fmod)

Question

我想使用 Cpp 计算阶乘中零的个数。问题是当我使用非常大的数字时。

#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;
}

我认为这里的问题是

fmod(事实，分母)给我 22 的阶乘和分母 10.00(即 0.000)的正确答案。但它给了我 23 的阶乘和分母为 10.00 的错误答案

Answer 1

将此视为您在数字精度方面的第一课。 float、double 和 long double 类型存储近似值，而不是精确值，这意味着它们通常不适合此类计算。即使它们有足够的精度来给出正确答案，您通常还是最好改用整数数字类型，例如 int64_t 和 uint64_t。有时您甚至可以使用 128 位整数类型。 (例如 __int128 可能适用于 Microsoft Visual Studio)

老实说，我认为你很幸运能从 18! 到 22! 得到正确答案。

如果 long double 在您的平台上确实是四倍精度，我认为您应该能够计算高达 30!。您在使用 fmod 时犯了一个错误——您打算使用 fmodl。

---

关于精度的第二个教训是，当您需要大量精度时，您的基本数据类型根本就不够好。虽然您可以编写自己的数据类型，但最好还是使用预先存在的解决方案。 Gnu Multiple Precision算术库 (GMP) 是一个可以在 C/C++ 中使用的又好又快的库。

或者，您可以切换语言——例如python 的整数数据类型是任意精度的(但不如 GMP 快)，因此您甚至不必做任何特殊的事情。 Java 具有用于执行此类计算的 BigInteger 类。

---

你的第三个教训是精确是找到避免的方法。您实际上不需要完全计算 23! 来查找尾随零的数量。您可以小心地组织计算以丢弃不需要的额外精度。或者，您可以切换到一种完全不同的方法来获取此数字，例如 Rob 在他的评论中暗示的方法。