如何用C存储10^20的值？

Question

我想把10^10的两个数字乘以，结果是10^20，也就是2^66。

我希望将该数字存储在C中的标准数据类型中。我宁愿不使用"GNU MP Bignum库“。

为什么下面的C程序不能正确地保存这个数字？

#include<stdio.h>
typedef long long int ull;
int main(){

    ull n1 = 10000000000LL;
    ull n2 = 10000000000LL;

    printf("%llu",n1*n2);
    return 0;
}

什么是最好的方式来保持这个数字并与它合作？

Answer 1

将其存储为两个long long值。下面是一个解决方案的草图：

#include <stdio.h>

typedef unsigned long long ull;

void multiply( ull a, ull b, ull * lo, ull * hi )
{
  ull ah = a >> 32;
  ull bh = b >> 32;
  ull al = a & 0xFFFFFFFF;
  ull bl = b & 0xFFFFFFFF;

  ull mid = ah * bl + al * bh;
  ull albl = al * bl;

  ull imm = mid + ( albl >> 32 );

  *lo = ( mid << 32 ) + albl;
  *hi = ah * bh + ( imm >> 32 );
}

int main()
{
  ull n1 = 10000000000LL;
  ull n2 = 10000000000LL;

  ull lo, hi;

  multiply( n1, n2, &lo, &hi );

  printf( "result in hex is %llx%016llx\n", hi, lo );
  return 0;
}

产出：

result in hex is 56bc75e2d63100000

Answer 2

您可以使用各种策略实现任意大的数值。

我个人喜欢使用链接列表。这样做的目的是将每个数字存储在一个节点中。您需要分别实现加法、减法、乘法和除法函数。

Answer 3

在64位架构上，long long最多只能容纳2^63-1。最多32位：2^32 -1。如果你需要更大的数字，那么如果有更好的方法解决问题，你应该重新评估你正在做的事情。

如果您需要更大的数字，您必须创建自己的库或使用其他人的库：

以下是处理任意精确数字的两个库。您可以使用多大的数字的限制取决于磁盘空间、内存和处理能力的大小，您必须持有和计算它们。

GMP和MAPM

如果必须滚动自己的，则可以将其存储在整数数组中。64位整数只是两个32位整数.一个1024位整数也可以看作是32位整数.创建一个包含整数数组的类，将它们拼接成任意大小。最困难的部分是编写函数，这些函数可以对整数数组进行加、减、乘和除法。