有谁知道我在哪里可以获得有关如何对存储在部分中的整数进行乘法和除法(甚至可能是模数)的说明?我正在制作一个存储 a 的uint128_t
库uint64_t UPPER, LOWER
。
问问题
404 次
4 回答
2
你熟悉GMP
图书馆吗?你为什么不使用它而不是实现你自己的?
从上面的链接,您可以下载tar.bz
基于 Unix 的操作系统的文件。
对于 Windows,请参阅此链接:
它有很多关于 MinGW、MSVC++ 和 CgyWin 的信息和安装文件。下载适合您的需求。您还可以查看以下链接:
完成安装和配置后,您想知道如何使用 GMP 进行编程,请浏览以下链接:
于 2011-05-25T21:20:45.933 回答
1
以这种方式拆分您的数字是Karatsuba 乘法的理想先决条件。考虑:
x = x1 * 2^k + x2
y = y1 * 2^k + y2
使用学校乘法,您需要 4 次乘法:
x*y = (x1*y1) * 2^(2*k) + (x1*y2 + x2*y1) * 2^k + x2*y2
Karatsuba 需要更多的加法,但只有 3 次乘法:
p1 = x1 * y1
p2 = x2 * y2
x*y = p1 * 2^(2*k) + ((x1+x2)*(y1+y2) - p1 - p2) * 2^k + p2
当然问题是如何处理溢出。
于 2011-05-26T07:05:16.687 回答
0
http://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic可能是一个好的开始。已经有很多开源库
于 2011-05-25T21:18:40.600 回答
0
看看各种 Big Integer 库。这是谷歌发现的一个https://mattmccutchen.net/bigint/
于 2011-05-25T21:19:03.093 回答