为什么模数运算符比较慢? [英] Why is modulus operator slow?

问题描述

"Programming Pearls"(编程珍珠)一书中的措辞(关于旧机器上的c语言，因为该书来自90年代后期):

Paraphrasing from in "Programming Pearls" book (about c language on older machines, since book is from the late 90's):

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

Integer arithmetic operations (+, -, *) can take around 10 nano seconds whereas the % operator takes up to 100 nano seconds.

• 为什么会有如此大的差异?
• 模运算符如何在内部工作?
• 在时间上与除法(/)一样吗?

• Why there is that much difference?
• How does a modulus operator work internally?
• Is it same as division (/) in terms of time?

推荐答案

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

The modulus/modulo operation is usually understood as the integer equivalent of the remainder operation - a side effect or counterpart to division.

除了某些退化的情况(除数是运算基数的幂，即，大多数数字格式为2的幂)，这和整数除法一样昂贵！

Except for some degenerate cases (where the divisor is a power of the operating base - i.e. a power of 2 for most number formats) this is just as expensive as integer division!

问题是，为什么整数除法如此昂贵?

So the question is really, why is integer division so expensive?

我没有时间或专业知识来进行数学分析，所以我将呼吁小学数学:

I don't have the time or expertise to analyze this mathematically, so I'm going to appeal to grade school maths:

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

Consider the number of lines of working out in the notebook (not including the inputs) required for:

• 相等性:(布尔运算)基本上没有-在计算机大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)

因此，简单来说，这应该让您了解为什么除法和模数较慢:计算机仍然必须像在小学时一样，以逐步的方式进行长除法.

So in simple terms, this should give you a feel for why division and hence modulo is slower: computers still have to do long division in the same stepwise fashion tha you did in grade school.

如果这对您没有意义；您可能在学习数学方面比我(30年前)要先进一些.

If this makes no sense to you; you may have been brought up on school math a little more modern than mine (30+ years ago).

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

The Order/Big O notation used above as O(something) expresses the complexity of a computation in terms of the size of its inputs, and expresses a fact about its execution time. http://en.m.wikipedia.org/wiki/Big_O_notation

O(1)以恒定(但可能很大)的时间执行. O(N)花费的时间与其数据大小一样长-因此，如果数据是32位，则它需要花费该步骤O(1)时间的32倍来计算其N个步骤之一，并且O(N ^ 2)取N步的时间的N倍N(N平方)(对于某个常数M可能取N倍MN).等等.

O(1) executes in constant (but possibly large) time. O(N) takes as much time as the size of its data-so if the data is 32 bits it takes 32 times the O(1) time of the step to calculate one of its N steps, and O(N^2) takes N times N (N squared) the time of its N steps (or possibly N times MN for some constant M). Etc.

在上面的工作中，我使用O(N)而不是O(N ^ 2)进行加法，因为第一个输入的32位或64位是由CPU并行计算的.在假设的1位计算机中，32位加法运算将为O(32 ^ 2)并发生变化.同样的降阶也适用于其他操作.

In the above working I have used O(N) rather than O(N^2) for addition since the 32 or 64 bits of the first input are calculated in parallel by the CPU. In a hypothetical 1 bit machine a 32 bit addition operation would be O(32^2) and change. The same order reduction applies to the other operations too.

这篇关于为什么模数运算符比较慢?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！