8

假设我写，

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

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

4

5 回答 5

11

编译这个函数：

int f(int a, int b) {
    return a * b;
}

Withgcc -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 和架构具有非恒定时间乘法。这对于使用乘法的算法可能容易受到这些平台上的定时攻击的密码学尤其重要。

于 2013-07-28T14:45:10.733 回答
2

大多数常见架构上的乘法本身将是恒定的。加载寄存器的时间可能会根据变量（L1、L2、RAM 等）的位置而有所不同，但操作所需的周期数将是恒定的。这与sqrt可能需要额外周期才能达到一定精度的操作形成对比。

您可以在这里获得 AMD、Intel、VIA 的指令成本：http ://www.agner.org/optimize/instruction_tables.pdf

于 2013-07-28T14:53:00.193 回答
1

通过时间复杂度，我认为您的意思是它是否取决于 a 和 b 中的位数？因此，CPU 时钟周期数是否会根据您乘以 2*3 还是 111*509 而有所不同。我认为是的，它们会有所不同，这取决于该架构如何实现乘法运算以及如何存储中间结果。尽管有很多方法可以做到这一点，但一种简单/原始的方法是使用二进制加法器/减法器电路实现乘法。a*b 的乘法是使用 n 位二进制加法器将 a 添加到自身 b 次。类似地，除法 a/b 是从 a 中减去 b，直到它达到 0，尽管这将占用更多空间来存储商和余数。

于 2013-07-28T14:53:21.690 回答
0

在您的示例中，编译器会进行乘法运算，您的代码看起来像

int c = 56499;

如果您将示例更改为

int c = a * 509;

然后编译器可能决定重写你的代码

int c = a * ( 512 - 2 - 1 );
int c = (a << 9) - (a << 1) - a;

我说可能是因为编译器会将使用 shirt 的成本与乘法指令的成本进行比较并选择最佳选项。给定一个快速的多指令，这通常意味着只有 1 次或 2 次移位会更快。

如果您的数字太大而无法放入整数（32 位），则在 O(n^2) 和 O(n log n) 时间之间使用任意精度数学例程，其中 n 是所需的 32 位部分的数量保持数字。

于 2013-07-28T15:03:52.247 回答
0 
void myfun()
{
int a = 111;
int b = 509;
int c = a * b;
}

拆装部分：

movl    $111, -4(%ebp)
movl    $509, -8(%ebp)
movl    -4(%ebp), %eax
imull   -8(%ebp), %eax

如您所见，这一切都取决于imull指令，特别是 CPU 的获取、解码和执行周期。

于 2013-07-28T14:53:05.613 回答