两个数字乘以恒定时间算法？
假设我写了，
int a = 111;
int b = 509;
int c = a * b;
那么计算'a * b'的时间复杂度是多少？ 乘法运算如何执行？
编译这个函数：
int f(int a, int b) {
return a * b;
}
使用gcc -O3 -march=native -m64 -fomit-frame-pointer -S给我下面的程序集：
f:
movl %ecx, %eax
imull %edx, %eax
ret
第一条指令（ movl ）加载第一个参数，第二条指令（ imull ）加载第二个参数并将其与第一个参数相乘，然后返回结果。
实际的乘法是用imull完成的，这取决于你的CPU类型，将需要一定数量的CPU周期。
如果你看看Agner Fog的指令计时表，你可以看到每条指令需要多少时间。 在大多数x86处理器上，它似乎是一个小常量，但AMD K8上的64位参数和结果的imul指令显示为4-5 CPU周期。 我不知道这是一个衡量问题还是真正可变的时间。
还要注意，除了执行时间之外还有其他因素。 整数必须通过处理器移动并进入正确的位置才能倍增。 所有这些和其他因素都会造成延迟，这在Agner Fog的表格中也有提到。 还有其他一些问题，例如缓存问题，这也会让生活变得更加困难 - 要简单地说一下运行速度而不运行它，并不容易。
x86不是唯一的体系结构，实际上并不难想象那里的CPU和体系结构具有非恒定时间倍增。 这对于使用乘法的算法可能容易受到这些平台上的定时攻击的密码学特别重要。
在大多数常见体系结构上进行乘法运算将保持不变。 加载寄存器的时间可能因变量的位置（L1，L2，RAM等）而异，但操作所需的周期数将保持不变。 这与像sqrt这样的操作形成对比，可能需要额外的周期才能达到一定的精度。
您可以在这里获得AMD，Intel，VIA的指令成本：http://www.agner.org/optimize/instruction_tables.pdf
按照时间复杂度，我认为你的意思是否取决于a和b中的位数。 因此，CPU时钟周期的数量是否会根据您乘以2 * 3还是111 * 509而变化。 我认为他们会有所不同，这取决于该架构如何实现乘法操作以及如何存储中间结果。 虽然可以有很多种方法来做到这一点，但一种简单/原始的方法是使用二进制加法器/减法器电路来实现乘法。 a * b的乘法是使用n位二进制加法器将a加到b次。 类似的划分a / b是从a减去b直到达到0，尽管这会占用更多的空间来存储商和余数。
链接地址: http://www.djcxy.com/p/85525.html上一篇: Is multiplication of two numbers a constant time algorithm?