返回主页<-

先从简单一些的整数乘幂开始, 因为实数乘幂的计算可归结为正整数次方, 开正整数次方和求倒数. 见 指数&对数

计算 2¹⁶ .我们可以通过代数式的变形来减少计算步骤:

  2¹⁶ = 4⁸ = 16⁴ = 256² = 65536

类似地计算 2²⁰.

  2²⁰ = 4¹⁰ = 16⁵ = 16⁴*16 = 256²*16 = 65536*16 = 1048576

可见, 我们把问题转化为多次求两大数的积. 如果求积时仍用经典乘法, 并不能使计算时间显著减少, 因为时间复杂度仍是O(n²). 由于我们有快速乘法, 使得这么做可以使乘幂计算快许多:

////求 x^y ////

result=x;

While y mod 2=0 

{

y=y div 2;

result=result*result;

}

tmp=1;

While y<>1

{

If y mod 2<>0 then { tmp=tmp*result; y=y-1;};

While y mod 2=0

{

y=y div 2;

result=result*result;

}

}

result=result*tmp

result就是所求结果.

 对以上代码进行优化:

////求 x^y ////

tmp=x;

result=1;

While y<>1

{

While (y and 1)<>1

{

y=y shr 1;

tmp=tmp*tmp;

}

result=result*tmp;

y=y-1;

}

result=tmp*result;

还有一种基于二进制的乘方算法, 例:

a¹⁵=a^{2^3+2^2+2+1}=(((a²)·a)²·a)²·a

由以上,设 e=(e_n-1,e_n-2,...,e₁,e₀) 为指数的二进制表示;

1. p←a^e(n-1); i←n-2;

2. p=p²;

3. 若 e_i=1，p=pa;

4. i--; 若 i>=0 转到2;

5. 输出 p.

     正如开头所说的"可归结为正整数次方, 开正整数次方和求倒数". 但是对于类似

 14^(100000000π) 的大实数乘幂就无能为力了.

关于这个问题站长也没什么好办法.只好按下列步骤处理 x^y:

将指数y分为整数a, 小数部分b .

由 x^y=x^(a+b)=x^a*x^b

按整数指数乘幂计算 x^a.

利用 x^b=e^(b*ln(x)) 计算第二部分.

两部分相乘得 x^y.

其中计算又要涉及到乘幂 e^() 的计算, 似乎又回到开头的问题.

不过, 幸好有 e^y=1+y+y²/2!+y³/3!+...+yⁿ/n!+... 同样可把把 y 分为整数,小数部分,整数部分同样是按整数指数乘幂计算( e 的值预先用 e^1 求出), 小数部分按上式算.