对整数的乘法和除法分为几部分

| 有谁知道我可能在哪里得到关于如何对部分存储的整数进行乘法和除法（甚至是模）的说明？我正在制作一个将uint128_t存储为uint64_t UPPER, LOWER的库。

已邀请:

4 个回复

您熟悉GMP图书馆吗？为什么不使用它而不是自己实现？ GNU多精度算术库从上面的链接，您可以为基于Unix的操作系统下载ѭ3文件。对于Windows，请参见以下链接： Windows平台的GMP安装说明它具有有关MinGW，MSVC ++和CgyWin的大量信息和安装文件。下载适合您的需求。您还可以看到以下链接：如何使用MPIR在Windows上安装和运行GMP 使用Visual Studio构建GMP库？（Stackover主题）在完成安装和配置后，您想知道如何使用GMP进行编程，以浏览以下链接： GMP基础 GMP手册

蹦吃舷弦

用这种方法分割数字是唐津乘法的理想先决条件。考虑：

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

当然，问题在于如何处理溢出。

埃输林桨铃

http://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic可能是一个好的开始。已经有很多开源库

氮顺

看看各种Big Integer库。这是谷歌发现的一个https://mattmccutchen.net/bigint/

要回复问题请先登录或注册

对整数的乘法和除法分为几部分

4 个回复

发起人

c++

math

operator_overloading

uint

问题状态

对整数的乘法和除法分为几部分

与内容相关的链接

4 个回复

发起人

c++

math

operator_overloading

uint

问题状态