10

据我了解，BigInts 通常在大多数编程语言中实现为包含数字的数组，其中，例如：当添加其中两个时，每个数字都会像我们在学校所知道的那样一个接一个地添加，例如：

 246
 816
 * *
----
1062

其中 * 表示存在溢出。我在学校就是这样学的，我实现的所有 BigInt 添加功能都与上面的示例类似。

所以我们都知道我们的处理器只能本地管理从 0 到2^32/的整数2^64。

这意味着大多数脚本语言为了成为高级语言并提供具有大整数的算术，必须实现/使用将整数作为上述数组工作的 BigInt 库。但这当然意味着它们会比处理器慢得多。

所以我问自己的是：

  • 为什么我的处理器没有内置 BigInt 函数？

它可以像任何其他 BigInt 库一样工作，只是（很多）速度更快且级别更低：处理器从缓存/RAM 中获取一个数字，添加它，然后再次写回结果。

对我来说似乎是个好主意，那为什么没有类似的东西呢？

4

8 回答 8

9

有太多的问题需要处理器处理大量不是它的工作的东西。

假设处理器 DID 具有该功能。我们可以制定一个系统，我们知道给定 BigInt 使用了多少字节 - 只需使用与大多数字符串库相同的原理并记录长度即可。

但是如果 BigInt 操作的结果超过了保留的空间量会发生什么？

有两种选择：

  1. 它会环绕在它所拥有的空间内，或者
  2. 它会使用更多的内存。

问题是，如果它做到了 1)，那么它就没用了——你必须事先知道需要多少空间，这就是你想要使用 BigInt 的部分原因——所以你不受那些限制事物。

如果它做到了 2)，那么它将不得不以某种方式分配该内存。跨操作系统的内存分配方式不同，但即使是这样，它仍然必须更新所有指向旧值的指针。它如何知道什么是指向该值的指针，以及什么是包含与所讨论的内存地址相同的值的简单整数值？

于 2010-04-12T20:07:16.053 回答
8

二进制编码十进制是字符串数学的一种形式。Intel x86 处理器具有用于直接 BCD 算术运算的操作码。

于 2010-04-12T20:06:59.057 回答
3

假设乘法的结果需要 3 倍的空间（内存）来存储——处理器会将结果存储在哪里？该结果的用户（包括指向它的所有指针）如何知道它的大小突然改变了 - 并且改变大小可能需要它在内存中重新定位它，因为扩展当前位置会与另一个变量发生冲突。

这将在处理器、操作系统内存管理和编译器之间产生大量交互，这将难以实现通用和高效。

管理应用程序类型的内存不是处理器应该做的事情。

于 2010-04-12T20:15:27.720 回答
3

它可以像任何其他 BigInt 库一样工作，只是（很多）速度更快且级别更低：处理器从缓存/RAM 中获取一个数字，添加它，然后再次写回结果。

几乎所有的 CPU都内置了这个。您必须围绕相关指令使用软件循环，但如果循环有效，则不会使其变慢。（由于部分标志停顿，这在 x86 上很重要，见下文）

例如，如果 x86 提供rep adcsrc += dst，以 2 个指针和一个长度作为输入（就像rep movsdmemcpy 一样），它仍然会在微码中实现为循环。

32 位 x86 CPU 有可能在内部实现rep adc使用 64 位加法器，因为 32 位 CPU 可能仍然有一个 64 位加法器。但是，64 位 CPU 可能没有单周期延迟 128b 加法器。所以我不希望为此有一个特殊的指令会加速你可以用软件做的事情，至少在 64 位 CPU 上。

也许特殊的宽加法指令在低功耗低时钟速度 CPU 上会很有用，在这种 CPU 中，具有单周期延迟的真正宽加法器是可能的。

您正在寻找的 x86 指令是：

当然，adc适用于二进制整数，而不是单个十进制数字。x86 可以adc包含 8、16、32 或 64 位块，这与 RISC CPU 不同，RISC CPU 通常只在全寄存器宽度下进行 adc。（GMP 将每个块称为“肢体”）。（x86 有一些使用 BCD 或 ASCII 的指令，但这些指令在 x86-64 中被删除了。）

imul/idiv是签名的等价物。Add 对有符号 2 的补码的工作方式与无符号的相同，因此没有单独的指令；只需查看相关标志即可检测有符号与无符号溢出。但是对于adc，请记住只有最重要的块才有符号位；其余的都是必不可少的未签名。

ADX 和 BMI/BMI2 添加了一些指令，例如mulx：全乘而不接触标志，因此它可以与adc链交错以创建更多指令级并行性，以供超标量 CPU 使用。

在 x86 中，adc甚至可以使用内存目标，因此它的执行方式与您描述的完全一样：一条指令触发 BigInteger 块的整个读取/修改/写入。请参见下面的示例。

大多数高级语言（包括 C/C++）不公开“进位”标志

通常在 C 中没有直接添加与携带的内在函数。BigInteger 库通常必须用 asm 编写才能获得良好的性能。

但是，英特尔实际上已经为(和/ )定义了内在函数。adcadcxadox

unsigned char _addcarry_u64 (unsigned char c_in, unsigned __int64 a, \
                             unsigned __int64 b, unsigned __int64 * out);

因此，进位结果unsigned char在 C 中作为 an 处理。对于_addcarryx_u64内在函数，由编译器来分析依赖链并决定哪些添加与adcx以及adox如何将它们串在一起以实现 C 源代码。

IDK当存在可以利用它的并行 dep 链时，_addcarryx内在函数的意义是什么，而不是仅仅让编译器将adcx/adox用于现有的内在函数。_addcarry_u64也许有些编译器不够聪明。

下面是一个 BigInteger 添加函数的示例，采用 NASM 语法：

;;;;;;;;;;;; UNTESTED ;;;;;;;;;;;;
; C prototype:
; void bigint_add(uint64_t *dst, uint64_t *src, size_t len);
;   len is an element-count, not byte-count

global bigint_add
bigint_add:   ; AMD64 SysV ABI: dst=rdi, src=rsi, len=rdx

                              ; set up for using dst as an index for src
    sub    rsi, rdi           ;  rsi -= dst.  So orig_src = rsi + rdi

    clc                           ;  CF=0 to set up for the first adc
           ; alternative: peel the first iteration and use add instead of adc

.loop:
    mov    rax, [rsi + rdi]   ; load from src
    adc    rax, [rdi]         ;  <================= ADC with dst
    mov    [rdi], rax         ; store back into dst.  This appears to be cheaper than  adc  [rdi], rax  since we're using a non-indexed addressing mode that can micro-fuse

    lea    rdi,  [rdi + 8]    ; pointer-increment without clobbering CF
    dec    rdx                ; preserves CF
    jnz    .loop              ; loop while(--len)

    ret

在较旧的 CPU 上，尤其是 Sandybridge 之前的 CPU，在写入其他标志 adc后读取 CF 时会导致部分标志停止。使用不同的指令循环将有助于旧 CPU 在合并部分标志写入时停止，但在 SnB-family 上不值得。dec

循环展开对于adc循环也非常重要。 adc在英特尔上解码为多个微指令，因此循环开销是一个问题，尤其是如果您有额外的循环开销来避免部分标志停顿。如果len是一个小的已知常数，则完全展开的循环通常是好的。（例如编译器只使用add/在 x86-64adc上做 auint128_t。）

adc使用内存目标似乎不是最有效的方法，因为指针差异技巧让我们对 dst 使用单寄存器寻址模式。（如果没有这个技巧，内存操作数就不会微熔）。

根据Agner Fog 的Haswell 和 Skylake 指令表，adc r,m是 2 微指令（融合域），每 1 个时钟吞吐量一个，而adc m, r/i4 微指令（融合域），每 2 个时钟吞吐量一个。显然，Broadwell/Skylakeadc r,r/i作为单 uop 指令运行并没有帮助（利用具有 3 个输入依赖项的 uop 的能力，与 Haswell 一起为 FMA 引入）。我也不能 100% 确定 Agner 的结果是否正确，因为他没有意识到 SnB 系列 CPU 仅在解码器/uop-cache 中微熔丝索引寻址模式，而不是在乱序核心中。

无论如何，这个简单的未展开循环是 6 微指令，并且应该在 Intel SnB 系列 CPU 上以每 2 个周期运行一次迭代。即使部分标志合并需要额外的微指令，这仍然容易少于可以在 2 个周期内发出的 8 个融合域微指令。

一些小的展开可以使每个周期接近 1adc个，因为该部分只有 4 个微指令。但是，每个周期 2 次加载和 1 次存储不太可持续。

扩展精度乘法和除法也是可能的，利用扩大/缩小乘法和除法指令。当然，由于乘法的性质，它要复杂得多。

将 SSE 用于 add-with carry或 AFAIK 任何其他 BigInteger 操作并没有真正的帮助。

如果您正在设计一个新的指令集，如果您有正确的指令来有效地生成和传播进位，您可以在向量寄存器中添加 BigInteger。该线程对在硬件中支持进位标志的成本和收益进行了一些来回讨论，与让软件​​像 MIPS 那样生成进位：比较以检测无符号环绕，将结果放入另一个整数寄存器。

于 2016-06-17T20:49:42.503 回答
1

我认为，在现代处理器中不包括 bigint 支持的主要思想是希望减少 ISA 并尽可能少地保留指令，这些指令被全速获取、解码和执行。顺便说一句，在 x86 系列处理器中，有一组指令可以让编写大型 int 库成为一天的事情。我认为另一个原因是价格。在放弃冗余操作的晶圆上节省一些空间会更有效，这可以在更高级别上轻松实现。

于 2010-04-12T20:09:15.427 回答
1

似乎英特尔正在添加（或已添加为 @time of this post - 2015）对大整数算术的新指令支持。

英特尔® 架构处理器上引入了新指令，以实现大整数运算的快速实施。大整数运算广泛用于高性能技术计算的多精度库以及公钥密码术（例如 RSA）。在本文中，我们描述了大整数算术中所需的关键操作及其使用新指令的有效实现。

http://www.intel.com/content/www/us/en/intelligent-systems/intel-technology/ia-large-integer-arithmetic-paper.html

于 2015-08-25T00:06:36.297 回答
0

有太多的指令和功能在争夺 CPU 芯片上的区域，最终那些使用频率更高/被认为更有用的指令和功能最终会淘汰那些不使用的指令和功能。实现 BigInt 功能所需的指令就在那里，而且数学很简单。

于 2011-02-21T12:49:21.420 回答
-1

BigInt：所需的基本功能是：无符号整数乘法，加上之前的高位，我在英特尔 16 位汇编器中编写了一个，然后是 32 位... C 代码通常足够快.. 即对于 BigInt，您使用软件库。CPU（和 GPU）不是以无符号整数为最高优先级设计的。

如果你想编写自己的 BigInt...

除法是通过 Knuths Vol 2 完成的（它是一堆乘法和减法，带有一些棘手的加法）

带进位的加法和减法更容易。等等等等

我刚刚在英特尔发布了这个：xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx SSE4 是否有 BigInt LIbrary？

i5 2410M 处理器我想不能使用 AVX [AVX 仅在最近的英特尔 CPU 上] 但可以使用 SSE4.2

是否有适用于 SSE 的 BigInt 库？我想我正在寻找实现无符号整数的东西

PMULUDQ（带 128 位操作数） PMULUDQ __m128i _mm_mul_epu32 ( __m128i a, __m128i b)

并进行携带。

它是一台笔记本电脑，所以我不能购买 NVIDIA GTX 550，我听说这在未签名的 Ints 上并不那么出色。xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

于 2011-10-13T04:21:43.407 回答