一个非常长的数的模数 (fmod) [英] Modulus of a really really long number (fmod)

问题描述

我想使用 Cpp 在阶乘中找到零的数量.问题是当我使用非常大的数字时.

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);
for(int i=2;i<=n;i++)
{
    fact=fact*i;
    printf("Looping with fact %LF
",fact);
}
printf("Fmod %lf %d
",fmod(fact,denominator),(fmod(fact,denominator)==zero));
while(fmod(fact,denominator)==zero)
{
    fact=fact/10;
    z++;
}
printf("Number of zeroes is %ld
",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
");
    zeroesInFact(x);
}
return 0;
}

我认为这里的问题是

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

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

推荐答案

请考虑这是您在数值精度方面的第一课.float、double 和 long double 类型存储近似值，而不是精确值，这意味着它们通常不适合这种计算.即使它们对正确答案有足够的精度，您通常最好还是使用整数类型来代替，例如 int64_t 和 uint64_t.有时您甚至可以使用 128 位整数类型.(例如 __int128 可能在 Microsoft Visual Studio 中可用)

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)

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

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

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

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.

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

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

或者，您可以切换语言 - 例如python 的整数数据类型是任意精度的(但不如 GMP 快)，因此您甚至不需要做任何特别的事情.Java 有 BigInteger 类来进行此类计算.

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.

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

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.

这篇关于一个非常长的数的模数 (fmod)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！