C - 大数相乘后的错误输出

Question

我正在为一个ⁿ 实现我自己的减少和征服方法。

程序如下:

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

double dncpow(int a, int n)
{
    double p = 1.0;
    if(n != 0)
    {
        p = dncpow(a, n / 2);
        p = p * p;
        if(n % 2)
        {
            p = p * (double)a;
        }
    }
    return p;
}

int main()
{
    int a;
    int n;
    int a_upper = 10;
    int n_upper = 50;
    int times = 5;
    time_t t;
    srand(time(&t));
    for(int i = 0; i < times; ++i)
    {
        a = rand() % a_upper;
        n = rand() % n_upper;
        printf("a = %d, n = %d\n", a, n);
        printf("pow = %.0f\ndnc = %.0f\n\n", pow(a, n), dncpow(a, n));
    }
    return 0;
}

我的代码适用于较小的 a 和 n 值，但观察到 pow() 和 dncpow() 的输出不匹配，例如输入:

一个 = 7，n = 39

战俘= 909543680129861204865300750663680

dnc = 909543680129861348980488826519552

我很确定算法是正确的，但 dncpow() 给出了错误的答案。有人可以帮我纠正这个吗？提前致谢!

Answer 1

就这么简单，这些数字对于您的计算机可以用单个变量精确表示的来说太大了。对于浮点类型，有一个单独存储的指数，因此它仍然可以表示一个接近实数的数字，丢弃尾数的最低位。

关于 this comment :

I'm getting similar outputs upon replacing 'double' with 'long long'. The latter is supposed to be stored exactly, isn't it?

• 如果您调用一个采用double 的函数，它不会神奇地 而是对long long 进行操作。您的值只需转换为 double，您将得到相同的结果。
• 即使使用处理 long long 的函数(在当今的典型平台上有 64 位)，您也无法处理如此大的数字。 64 位不足以存储它们。对于 unsigned 整数类型，它们将在溢出时“环绕”到 0。对于有符号 整数类型，溢出行为是未定义(但仍然有点可能是回绕)。所以你会得到一些与你的预期结果完全无关的数字。这可以说比浮点类型的结果更糟糕，只是不精确。

对于大数的精确计算，唯一的方法是将它们存储在一个数组中(通常是无符号整数，如uintmax_t)并自己实现所有算法。这是一个很好的练习，也是一项大量的工作，尤其是在关注性能时(“朴素”算术算法通常效率很低)。

对于一些现实生活中的程序，您不会在这里重新发明轮子，因为有处理大量数字的库。可以说最著名的是 libgmp .阅读那里的手册并使用它。