modulo - 为什么模数运算符很慢？

Question

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

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

为什么会有这么大的区别？

模数运算符如何在内部工作？

就时间而言，它与除法( / )相同吗？

Answer 1

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

除了一些退化的情况(除数是运算基数的幂 - 即大多数数字格式的 2 的幂)之外，这与整数除法一样昂贵!

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

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

考虑以下所需的笔记本中的锻炼行数(不包括输入):

平等:( bool 运算)基本上没有 - 在计算机“大 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) 并且会发生变化。相同的订单减少也适用于其他操作。