2

刚刚突然出现在我脑海中的问题，我想我在这里没有看到答案。二进制加法算法所花费的时间是否与操作数的大小成正比？

显然，添加1101011010101010101101010and10110100101010010101将花费比 更长的时间1 + 1，但我的问题更多地涉及较小的值。是否存在可忽略不计的差异，没有差异，理论上的差异？

在什么时候，有了这些基本的计算，我们应该开始寻找更有效的计算方法？即：通过与大指数平方来计算大幂的幂。

4

3 回答 3

5

我们如何看待二进制模式......

1101011010101010101101010 (大)
10110100101010010101 (中)
1 (小)

32位计算机如何看到二进制模式......

00000001101011010101010101101010 32位，
00000000000010110100101010010101 32位，
00000000000000000000000000000001 我喜欢它

在 32 位系统上，上述所有数字都需要相同的时间（CPU 指令数）才能相加。因为它们都适合基本计算块，即 32 位 CPU 寄存器。

16位计算机如何看到二进制模式......

 1
+1 = ?

0000000000000001 我喜欢它
0000000000000001 我喜欢它

 00000001101011010101010101101010
+00000000000010110100101010010101 = ?

00000001101011010101010101101010 对我来说太大了！
00000000000010110100101010010101 对我来说太大了！

在 16 位系统上，由于较大的数字不适合 16 位寄存器，因此需要一个额外的通道（添加前 16 个 LSB 后剩余的有效位）。

Step1：添加最低有效位
0101010101101010
0100101010010101

Step2：添加其余部分（记住之前操作中的进位）
000000000000000C
0000000110101101
0000000000001011

一旦数字不再适合系统的基本计算单元即 CPU 寄存器，我们就可以开始考虑优化数字的数学运算。

开发现代硬件架构时牢记这一点并支持SIMD指令。当编译器看到这样的情况时，通常会使用它们（x86上的SSE ，ARM 上的NEON），即在 32 位系统上运行 128 位解密逻辑。

此外，不仅检查操作数的大小，结果的大小还决定了系统是否可以在一步内完成数学运算。不仅涉及到的操作数，还需要考虑正在执行的操作。

例如，在 32 位系统上，将两个 30 位数字相加肯定可以使用常规操作进行，因为结果保证不会超过 32 位寄存器。但是将相同的两个 30 位数字相乘可能会导致一个数字不适合 32 位。

在没有能够将结果存储在单个计算单元中的保证的情况下，为确保所有可能值的结果的有效性，架构（和编译器）必须：

  • 走很长的路，即多步数学运算
    或
  • 采用 SIMD 优化
    或
  • 定义和实现自定义机制
    （如寄存器对EDX:EAX以在 x86 上保存结果）
于 2013-07-29T08:56:53.933 回答
2

实际上，添加适合处理器字的不同整数之间没有（或完全可以忽略不计）差异，因为这应该始终是固定时间操作。

理论上，两个无符号整数相加的复杂度应该是 O(log(n))，其中 n 是两者中的较大者。因此，在仅仅添加成为问题之前，您需要达到相当高的水平。

至于在计算数字的简单算法和复杂算法之间究竟在哪里划清界限，我没有确切的答案。然而，GMP库浮现在脑海中。据我了解，他们已经仔细选择了他们的算法以及在什么情况下在性能方面使用它们。你可能想看看他们做了什么。

于 2013-07-29T08:50:27.627 回答
0

我有点不同意上面的答案。这在很大程度上取决于上下文。

对于简单的整数运算（用于循环计数器等），然后在 64 位机器上，将使用 64 位通用寄存器（RSI/RCX/等）完成计算。在这些情况下，8 位或 64 位加法之间的速度没有差异。

但是，如果您正在处理整数数组，并假设编译器已经能够很好地优化代码，那么是的，越小越快（但不是因为您认为的原因）。

在 AVX2 指令集中，您可以访问 4 个整数加法指令：

__m256i _mm256_add_epi8 (__m256i a, __m256i b); // 32 x 8bit
__m256i _mm256_add_epi16(__m256i a, __m256i b); // 16 x 16bit
__m256i _mm256_add_epi32(__m256i a, __m256i b); // 8 x 32bit
__m256i _mm256_add_epi64(__m256i a, __m256i b); // 4 x 64bit

您会注意到它们一次都在 256 位上运行，这意味着如果您使用 64 位，您可以处理 4 个整数加法，而如果您使用 8 位整数，则可以处理 32 次加法。（如上所述，您需要确保您有足够的精度）。它们都需要相同数量的时钟周期来计算 - 1clk。

使用较小的数据类型还有其他效果，主要是更好的 CPU 缓存使用率，以及减少的内存读取/写入次数。

但是，回到您关于逐位计算的原始问题。在新的 AVX-512 指令集之前，它可能看起来并不傻。但是，新指令集包含一个三元逻辑指令。使用这条指令，可以相当容易地计算任意位长度的数字的 512 次加法。

inline __m512i add(__m512i x, __m512i x, __m512i carry_in)
{
  return _mm512_ternarylogic_epi32(carry_in, y, x, 0x96);
}
inline __m512i adc(__m512i x, __m512i x, __m512i carry_in)
{
  return _mm512_ternarylogic_epi32(carry_in, y, x, 0xE8);
}

__m512i A[NUM_BITS];
__m512i B[NUM_BITS];
__m512i RESULT[NUM_BITS];
__m512i CARRY = _mm512_setzero_ps();

for(int i = 0; i < NUM_BITS; ++i)
{
  RESULT[i] = add(A[i], B[i], CARRY);
  CARRY = adc(A[i], B[i], CARRY);
}

在这个特定的例子中（老实说，它在现实世界中的使用可能非常有限！），执行 512 次加法所需的时间确实与 NUM_BITS 成正比。

于 2017-06-20T09:04:59.033 回答