模数运算符为什么慢？

Question

从"编程珍珠"一书中解释(关于旧机器上的c语言,因为本书是从90年代后期开始的):

整数算术运算(+,-,*),而可能需要大约10纳秒%操作员最多需要100毫微秒.

Answer 1

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

除了一些退化情况(除数是操作基数的幂 - 即大多数数字格式的2的幂),这和整数除法一样昂贵!

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

我没有时间或专业知识来数学分析这个,所以我会吸引小学数学:

考虑笔记本中的工作线数(不包括输入):

平等:(布尔运算)基本上没有 - 在计算机"大O"术语中这是已知的O(1)
另外:两个,从左到右工作,一个输出线和一个输入线.这是O(N)操作
long乘法:n*(n + 1)+ 2:每个数字产品两条线(一条用于总数,一条用于进位)加上最终总数和进位数.所以O(N ^ 2)但是具有固定的N(32或64),并且它可以在硅中流水线化到小于
长划分:未知,取决于参数大小 - 它是递归下降,有些实例比其他实例下降得更快(1,000,000/500,000需要的线数少于1,000/7).此外,每个步骤基本上是一系列乘法,以隔离最接近的因素.(尽管存在多种算法).感觉像一个变量为N的O(N ^ 3)

因此,简单来说,这应该让你感觉到为什么除法和因此模数更慢:计算机仍然需要以与小学时相同的逐步方式进行长时间划分.

如果这对你没有意义; 你可能已经把学校的数学培养成比我的更现代(30多年前).

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

O(1)在恒定(但可能很大)的时间内执行.O(N)花费的时间与其数据的大小相同 - 因此,如果数据是32位,则需要32倍于步骤的O(1)时间来计算其N个步骤之一,并且O(N ^ 2) N次N(N平方)取其N步的时间(或者对于某些常数M可能是N次MN).等等.

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

实际上,如果你想在笔记本中计算乘法,你可以考虑使用Karatsuba的方法,或者如果你有点疯狂--FFT.见[here](https://en.wikipedia.org/wiki/Multiplication_algorithm). (2认同)