c++ - 极大的整数乘法和加法

Question

问候，

我需要将存储在文本文件中的两个非常长的整数值相乘(通过 GMP(准确地说是 MPIR)导出，因此它们可以是任何基数中的任何一个)。现在，我通常只是通过 mpz_inp_str() 函数导入这些整数并在 RAM 中执行乘法，但是，这些值太长以至于我无法真正加载它们(每个大约 1 GB 的数据)。最快的方法是什么？也许已经有一些外部库在做这种事情了？是否有任何易于实现的方法(性能并不是非常重要，因为此操作只会执行一次或两次)？

tl;dr:我需要将值相乘得如此之大以至于不符合进程内存限制 (Windows)。

感谢您的宝贵时间。

Answer 1

我不知道是否有支持此功能的库，但您可以对每个真大数 (RBN) 的部分使用 GMP/MPIR。也就是说，首先将每个 RBN 分解为可管理的、大小统一的 block (例如 1000 万个数字 block ，预计最有效数字的 block 尺寸较小，另见下文)。

    RBN1 --> A B C D E    RBN2 --> F G H I J

分块可以以 10 为基数进行，因此只需从文件中为每个片段读取 个字符。然后一次将每个数字的 block 相乘。

     AxF BxF CxF DxF ExF    +    AxG BxG CxG DxG ExG    +        AxH BxH CxH DxH ExH    +            AxI BxI CxI DxI ExI    +                AxJ BxJ CxJ DxJ ExJ

在内存中执行最后求和的每一列。然后，将进位保留在内存中，将列写到磁盘，对下一列重复...对于进位，使用 GMP 将每列总和结果转换为字符串，写出结果的底部 部分并读取顶部作为进位的 GMP int 返回。

我建议为每个乘法动态选择 block 大小，以便将每个列加法保存在内存中；数字越大，需要添加的列就越多，需要的 block 大小就越小。

对于读取和写入，我建议使用内存映射文件，boost 有一个很好的接口(interface) this (请注意，这不会加载整个文件，它只是在虚拟内存上缓冲 IO)。为每个输入的 RBN 数打开一个映射文件，并打开一个 size = size(RBN1) + size(RBN2) + 1 的输出；对于内存映射文件，文件访问被视为原始 char*，因此您可以使用 gmp c-string io 方法直接读/写 block 。您可能需要读入一个中间缓冲区，以便为 GMP 以 NULL 结尾的字符串(除非您想临时更改内存映射文件)。

这不是很容易正确实现，但话又说回来这不是一个特别容易的问题(也许只是乏味)。这种方法的优点是它准确地反射(reflect)了 GMP 在内存中所做的事情，因此算法是众所周知的。