两个数的乘法是一个恒定时间算法吗？

Question

假设我写,

int a = 111;
int b = 509;
int c = a * b;

那么计算'a*b'的时间复杂度是多少？如何执行乘法运算？

Answer 1

编译这个函数:

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处理器上,它似乎是一个小常量,但imulAMD K8上带有64位参数和结果的指令显示为4-5CPU周期.我不知道这是一个测量问题还是真正可变的时间.

另请注意,除了执行时间之外还涉及其他因素.整数必须通过处理器移动并进入正确的位置才能成倍增加.所有这些因素和其他因素都会导致延迟,这在Agner Fog的表格中也有所体现.还有其他一些问题,例如缓存问题也会让生活变得更加困难 - 简单地说一下如果没有运行它就能运行得多快就不容易.

x86并不是唯一的体系结构,实际上并不是不可想象的,那里有CPU和体系结构具有非恒定的时间乘法.这对于使用乘法的算法可能容易受到这些平台上的定时攻击的加密技术尤为重要.