首页 > 代码库 > 普通乘法,加法等时间复杂度计算

普通乘法,加法等时间复杂度计算

Intel Pentium CPU计算加减乘除的指令周期

【加法】:

指令             指令周期

adc 寄存器, 立即数      1

adc 寄存器, 寄存器      1

adc 寄存器, 内存       2

adc 内存,   立即数      3

adc 内存,   寄存器      3

 

add 寄存器, 立即数      1

add 寄存器, 寄存器      1

add 寄存器, 内存       2

add 内存, 立即数       3

add 内存, 寄存器       3

 

inc 寄存器          1

inc 内存           3

 

【减法】:

dec 寄存器          1

dec 内存           3

 

sub 寄存器, 立即数      1

sub 寄存器, 寄存器      1

sub 寄存器, 内存       2

sub 内存, 立即数       3

sub 内存, 寄存器       3

 

sbb 寄存器, 立即数      1

sbb 寄存器, 寄存器      1

sbb 寄存器, 内存       2

sbb 内存, 立即数       3

sbb 内存, 寄存器       3

 

【乘法】:

imul 寄存器         11

imul 内存          11

imul 寄存器, 寄存器, 立即数 10

imul 寄存器, 立即数     10

imul 寄存器, 内存, 立即数  10

imul 寄存器, 寄存器     10

imul 寄存器, 内存      10

 

mul 8位寄存器        11

mul 16位寄存器        11

mul 32位寄存器        10

mul 8位内存         11

mul 16位内存         11

mul 32位内存         10

 

【除法】:

div 8位寄存器        17

div 16位寄存器        25

div 32位寄存器        41

div 8位内存         17

div 16位内存         25

div 32位内存         41

 

idiv 8位寄存器        22

idiv 16位寄存器       30

idiv 32位寄存器       46

idiv 8位内存         30

idiv 16位内存        30

idiv 32位内存        46

 

 

由此可见,CPU计算加减法的速度跟位运算(与、或、非、异或)相当,乘法的速度比加减法慢近10倍除法的速度比加减法慢近20倍——8位,近30倍——16位,40倍以上——32位)。算加减法,读取内存数据的比不读内存数据的慢,写内存的比读内存的慢。

假设10 8=1秒

for k:=1 to 7 do
for i:=1 to mi[k](10000) do
begin
sum:=0; x:=1;
for j:=0 to n(100) do
begin
sum:=(sum+x*b[j,k] mod mi[k]) mod mi[k];
x:=x*i mod mi[k];
end;
if sum<>0 then f[i,k]:=false;
end;

1秒

int64附带8的常数 

按理来说乘法(除法)的执行时间应该是大于N倍加法时间的,其中N是数据位长。

接下来是推测:几个乘法语句*几。

7*10 4 *100 *8 * 2=1.12*10 8 =1秒

普通乘法,加法等时间复杂度计算