19

从“Programming Pearls”一书中转述（关于旧机器上的 c 语言，因为这本书是 90 年代后期的）：

整数算术运算 ( +, -, *) 可能需要大约 10 纳秒，而%运算符最多需要 100 纳秒。

  • 为什么会有这么大的区别？
  • 模数运算符如何在内部工作？
  • /就时间而言，它与除法（ ）相同吗？
4

1 回答 1

22

模数/模运算通常被理解为取余运算的整数等价物——除法的副作用或对应物。

除了一些退化的情况（其中除数是运算基数的幂 - 即大多数数字格式的 2 的幂），这与整数除法一样昂贵！

所以问题是，为什么整数除法如此昂贵？

我没有时间或专业知识来对此进行数学分析，所以我将求助于小学数学：

考虑以下所需的笔记本中的锻炼行数（不包括输入）：

  • 平等：（布尔运算）基本上没有 - 在计算机“大 O”术语中，这被称为 O(1)
  • 补充：二，从左到右工作，一根线输出，一根线进位。这是一个 O(N) 操作
  • 长乘法：n*(n+1) + 2：每个数字乘积两行（一个用于总计，一个用于进位）加上最终总计和进位。所以 O(N^2) 但具有固定的 N（32 或 64），并且它可以在硅中流水线化到小于
  • 长除法：未知，取决于参数大小 - 它是递归下降，某些实例下降速度比其他实例快（1,000,000 / 500,000 需要的行数少于 1,000 / 7）。此外，每个步骤本质上都是一系列乘法，以隔离最接近的因素。（尽管存在多种算法）。感觉就像一个带有变量 N 的 O(N^3)

因此，简单来说，这应该让您了解为什么除法和模数更慢：计算机仍然必须以与小学时相同的逐步方式进行长除法。

如果这对您没有意义；你可能在学校数学方面比我的更现代（30 多年前）。

上面用作 O(something) 的 Order/Big O 表示法根据其输入的大小表示计算的复杂性，并表示有关其执行时间的事实。 http://en.m.wikipedia.org/wiki/Big_O_notation

O(1) 以恒定（但可能很大）时间执行。O(N) 花费的时间与其数据的大小一样多——因此，如果数据是 32 位，则计算其 N 个步骤中的一个步骤需要 32 倍的 O(1) 时间，并且 O(N^2)需要 N 乘以 N（N 平方）其 N 步的时间（或者对于某个常数 M，可能需要 N 乘以 MN）。等等。

在上述工作中，我使用 O(N) 而不是 O(N^2) 进行加法，因为第一个输入的 32 位或 64 位是由 CPU 并行计算的。在假设的 1 位机器中，32 位加法运算将是 O(32^2) 并且会发生变化。相同的订单减少也适用于其他操作。

于 2015-01-16T09:08:05.650 回答