4

问候，

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

tl; dr：我需要将值相乘，它们不适合进程内存限制（Windows）。

感谢您的时间。

4

1 回答 1

4

我不知道是否有支持此功能的库，但您可以在每个非常大的数字 (RBN) 的部分上使用 GMP/MPIR。也就是说，首先将每个 RBN 分解为可管理的、大小一致的块（例如 10M 位块，对于最重要的数字，期望一个较小的块，也见下文）。

    RBN1 --> ABCDE
    RBN2 --> FGHIJ

分块可以在基数 10 中完成，因此只需从文件中为每个片段读取 <chuck_size> 个字符。然后一次将每个数字的块相乘。

     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 的字符串，写出结果的底部 <chunk size> 部分并读取顶部返回作为携带的 GMP int。

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

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

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

于 2010-06-06T18:13:51.450 回答