取模运算符为什么速度较慢？

Question

从《编程珠玑》一书中改述（关于旧机器上的c语言，因为该书出自90年代末）：

整数算术运算（+、-、*）大约需要10纳秒的时间，而%运算符最多需要100纳秒的时间。

• 为什么差别这么大？
• 模运算符在内部是如何工作的？
• 它和除法（/）在时间上是否相同？

- AV94

---

作为一项练习，编写最朴素的除法和取模运算版本。在优化之前计算每个操作所需的指令数。显然，有更高效的方法来完成这些操作（甚至在CPU级别优化之前），但这将让你了解它们之间的差异。 - Ed S.

据报道，除法运算的速度与加减法相当，即使在新处理器上，除法运算的速度仍然比其他运算慢许多倍。 - SunsetQuest

什么语言？除数是多少？你要对int还是double或float类型进行取模运算？ - Alex Brown

@AlexBrown.. 语言：C，所谓模数运算符，我指的是“%”运算符。例如：23413％34。 - AV94

啊哈！我重新格式化了你的问题，这样我就能更好地理解它了。 - Alex Brown

Answer 1

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

除了一些退化情况（除数是操作基数的幂——即大多数数字格式的2的幂），这与整数除法同样昂贵！

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

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

考虑需要在笔记本上工作的行数（不包括输入）：

• 相等性：（布尔运算）基本上没有 - 在计算机的“大O”术语中，这被称为O（1）
• 加法：两个数，从左到右工作，一个用于输出，一个用于进位。这是一个O（N）操作
• 长乘法：n *（n + 1）+2：每个数字产品都有两行（一个用于总和，一个用于进位），再加上最终的总和和进位。因此是O（N ^ 2），但具有固定的N（32或64），并且可以在硅中进行流水线处理以减少时间
• 长除法：未知，取决于参数大小 - 这是一个递归下降，某些实例下降得比其他实例快（100万/ 500,000需要的行数比1,000 / 7要少）。此外，每个步骤本质上都是一系列乘法，以隔离最接近的因子。（虽然存在多种算法）。感觉像是O（N ^ 3）与可变N

简单来说，这应该让您了解为什么除法和取模较慢：计算机仍然必须以您在小学时所做的分步方式进行长除法。

如果这对你来说毫无意义；那么可能是因为你接受的学校数学比我（30+年前）更现代化。

---

The Order/Big O符号表示计算复杂度与输入规模的关系，并表达了执行时间的事实。O(1)在恒定时间内执行（但可能很长）。O(N)需要与数据大小相同的时间，因此如果数据是32位，则需要32倍于O(1)步骤的时间来计算其中一个N步骤，而O(N^2)需要N个步骤的平方（N的平方）时间（或者某些常数M的N乘以MN的时间）。等等。http://en.m.wikipedia.org/wiki/Big_O_notation

---

在上述工作中，我使用了O(N)而不是O(N^2)的加法，因为CPU可以并行计算第一个输入的32位或64位。在假设的1位机器上，32位加法操作将是O(32^2)及以上。其他操作也适用相同的顺序减少。

- Alex Brown

---

实际上，如果你想在笔记本上计算乘法，你可以考虑使用卡拉图巴方法，或者如果你有点疯狂的话，可以尝试快速傅里叶变换（FFT）。详见这里。 - einpoklum