在c中以很大的数字计算

Question

我是编程新手。我想计算范围为[0,10^24]的数字的模。例如：(12 * 10^22) % 89我知道我无法使用常见的数据类型（例如long，integer等）执行此操作。我怎样才能做到这一点？有办法吗？

提前感谢

Answer 1

显示的表达式可以通过在每次操作后减少89模来容易地计算：

#include <stdio.h>


int main(void)
{
    //  Initialize a product.
    int t = 1;

    //  Calculate 10^22 (modulo 89) by multiplying by 10 (modulo 89) 22 times.
    for (int i = 0; i < 22; ++i)
        t = t * 10 % 89;

    //  Multiply by 12 (modulo 89).
    t = t * 12 % 89;

    //  Show the result.
    printf("%d\n", t);
}

Answer 2

最大保证的C数据类型是uint64_t（请参阅stdint.h），最多可容纳2 ^ 64-1。我认为最好保持与标准C的一致性，所以我建议一种方法首先简化问题，以免使用超出此范围的数据类型。为此，让我们借鉴模块化算术证明：

xy % z == (x % z * y % z) % z

由此，我们可以得出结论，(12 * 10^22) % 89 == (12 % 89 * 10^11 % 89 * 10^11 %89) % 89这个新版本肯定不那么漂亮，但是它确实使所有因素都很好地适合了标准C数据类型。这样的计算之前的简化可以用于您范围内的所有数据。

但是，首先要存储要模取的值的问题。澄清用例的含义可能会得出更适用的答案。例如，值是否存储在字符串中，也许是通过用户输入存储的？

或者，您可以使用某些为处理非常大的数字而设计的库。我不知道哪种方式最适合您的目的（我什至都​​不知道您使用的是哪种操作系统），但是如果您想探索这些选项，可以通过简单的网络搜索“ bignum”，“任意-精度”或“无限精度”库应该可以为您提供所需的内容。