所以，我想用代码写一个函数，使用某种算法来计算任何数字的任何幂，包括小数。我使用JavaScript，它已经有一个内置的pow函数:
Math.pow(2, 0.413) // 2^0.413 = 1.331451613236371, took under 1 second.
现在我想写我自己的:
function pow(x, y) {
// Algorithm
}
这是一个计算任何数字(x^0.5)的平方根的函数，它非常精确，只有10个循环:
function sqrt(x, p) { // p = precision (accuracy)
var a = 1;
var b = x;
while (p--) {
a = (a + b) / 2
b = x / a
}
return a
}
是否有简单的公式来计算任何指数?
如果没有简单的，还有难的吗?
如果解决方案是缓慢的，JavaScript的功率如何在一秒钟内估计?
这里有一个很好的正整数幂算法，它首先处理一些简单的情况，然后使用循环测试指数的二进制位。例如，在二进制中查找3^11 11是1011，因此循环中的阶段为
- bitMask = 1011, evenPower = 3, result = 3
- bitMask = 101, evenPower = 3*3 = 9, result = 3*9 = 27
- bitMask = 10, evenPower = 9*9 = 81, result = 27
- bitMask = 1, evenPower = 81*81 = 6561, result = 27*6561 = 177147
这是每个循环的偶数幂平方，如果底部位为1，则结果乘以偶数幂。这个密码是从帕特丽夏·沙纳汉的方法中提取出来的http://mindprod.com/jgloss/power.html，而这种方法又起源于昆斯，可以追溯到公元前200年的印度。
/**
* A fast routine for computing integer powers.
* Code adapted from {@link <a href="http://mindprod.com/jgloss/power.html">efficient power</a>} by Patricia Shanahan pats@acm.org
* Almost identical to the method Knuth gives on page 462 of The Art of Computer Programming Volume 2 Seminumerical Algorithms.
* @param l number to be taken to a power.
* @param n power to take x to. 0 <= n <= Integer.MAX_VALUE
* Negative numbers will be treated as unsigned positives.
* @return x to the power n
*
*/
public static final double power(double l,int n)
{
assert n>=0;
double x=l;
switch(n){
case 0: x = 1.0; break;
case 1: break;
case 2: x *= x; break;
case 3: x *= x*x; break;
case 4: x *= x; x *= x; break;
case 5: { double y = x*x; x *= y*y; } break;
case 6: { double y = x*x; x = y*y*y; } break;
case 7: { double y = x*x; x *= y*y*y; } break;
case 8: x *= x; x *= x; x *= x; break;
default:
{
int bitMask = n;
double evenPower = x;
double result;
if ( (bitMask & 1) != 0 )
result = x;
else
result = 1;
bitMask >>>= 1;
while ( bitMask != 0 ) {
evenPower *= evenPower;
if ( (bitMask & 1) != 0 )
result *= evenPower;
bitMask >>>= 1;
} // end while
x = result;
}
}
return x;
}
对于一个实数指数，你基本上需要找到exp和log的方法。你可以用最简单的泰勒级数但也有更好的方法。我们有
exp(x) = 1 + x + x^2/2 + x^3/6 + x^4/24 + x^5/120 + x^6/6! + ...
ln(1+x) = x - x^2 /2 + x^3 /3 - x^4 / 4 + x^5 / 5 - x^6/6 + ... |x|<1
要找到x^y，请注意ln(x^y) = y*ln(x)。现在我们需要让实参在正确的范围内这样我们就可以用幂级数了。设x = m * 2^ex，尾数和指数选择1/根号(2)<= m <sqrt(2)和ln(m*2^ex) = ln(m) + ex*ln(2)。令h>
使用java和浮点数，因为有一个简单的方法来找到IEEE表示的内部(我使用浮点数，因为有更少的位要处理)
int b = Float.floatToIntBits(x);
int sign = (b & 0x80000000) == 0 ? 1 : -1;
int mattissa = b & 0x007fffff;
int ex = ((b & 0x7f800000) >> 23 ) - 127;
在javascript中可能是最容易的。toExponential和解析结果。
在期望的范围内构造一个数字z 1/sqrt(2)
int bits = mattissa | 0x3f800000;
float z = Float.intBitsToFloat(bits);
if(z>root2) {
z = z/2;
++ex;
}
用泰勒级数求log (1+x)
static float ln1px(float x) {
float x_2 = x*x; // powers of x
float x_3 = x_2 * x;
float x_4 = x_3 * x;
float x_5 = x_4 * x;
float x_6 = x_5 * x;
float res = x - x_2 /2 + x_3 /3 - x_4 / 4 + x_5 / 5 - x_6/6;
return res;
}
这似乎适用于三个有效数字，当x接近于0时通常更好。
可以找到x的对数
float w = z - 1;
float ln_z = ln1px(w);
float ln_x = ln_z + ln2 * ex;
System.out.println("ln "+ln_x+"t"+Math.log(x));
如果我们写y = n + a其中n是整数，a是分数。所以x^y=x^(n+a) = x^n * x^a。使用这个答案中的第一个算法来找到x^n。写x=m*2^ex然后ln((m*2^ex)^a) = yln(m) + yex*ln(2)和
x^a=exp(ln((m*2^ex)^a)) = exp(a * ln(m)) * exp(a * ln(2))^ex
两个指数项有相当小的值，所以泰勒级数应该是好的。
我们需要一个函数来表示指数函数
的泰勒级数static float exp(float x) {
float x_2 = x*x; // powers of x
float x_3 = x_2 * x;
float x_4 = x_3 * x;
float x_5 = x_4 * x;
float x_6 = x_5 * x;
float res = 1+ x + x_2 /2 + x_3 /6 + x_4 / 24 + x_5 / 120 + x_6/ 720;
return res;
}
最后我们可以把碎片拼在一起
// Get integer and fractional parts of y
int n = (int) Math.floor(y);
float a = y-n;
float x_n = power(x,n); // x^n
float a_ln_m = a * ln_z; // ln(m^a) = a ln(m)
float a_ln_2 = a * ln2; // ln(2^a) = a ln(2)
float m_a = exp(a_ln_m); // m^a = exp(a ln(m))
float _2_a = exp(a_ln_2); // 2^a = exp(a ln(2))
float _2_a_ex = power(_2_a,ex); // (2^ex)^a = 2^(a*ex) = (2^a)^ex
float x_a = m_a * _2_a_ex; // x^a = m^a * 2^(a*ex)
float x_y = x_n * x_a; // x^y = x^n * x^a
System.out.println("x^y "+x_y+"t"+Math.pow(x,y));
这应该是完整的程序，你需要一些聪明来处理负面参数等。
注意，这不是特别准确，因为我只使用了泰勒级数的几个项。其他SO问题有更详细的答案我如何写一个幂函数自己?
这些都是很好的例子，这里也有一个更简单的例子。
function exponential(a,b){
var c = 1;
for(var i=1; i<=b; i++){
c = c * a;
}
return c;
}
现在调用函数:
exponential(2,4);
编辑:它只适用于整数，但它是简单和快速。
我检查了这篇文章，但它只适用于整数(1,2,3…不是0.1,0.3…)
递归幂函数:如果没有初始返回值，为什么它可以工作?
,
我从这里得到了这个:算法为pow(float, float)
function power(x,n) {
if(n === 0) return 1;
if(n === -1) return 1/x;
if(n === 1) return x;
return Math.exp(n*Math.log(x))
}
console.log(power(2,3.5));
我添加了一些基本检查(n===0)…把东西系牢，以防万一。
柔印总结:
http://mathworld.wolfram.com/NewtonsMethod.html http://mathworld.wolfram.com/TaylorSeries.html一般算法倾向于将浮点幂作为整数次幂和余数根的组合。整数Power相当简单，根可以使用任何一种方法来计算牛顿-拉夫森方法或者泰勒级数。IIRC数值配方有一些关于这个的文字。还有其他(可能更好的)方法但这是一个合理的起点这是一个非常复杂的问题。还请注意一些实现使用查找表和一些技巧来减少所需的计算。
https://en.wikipedia.org/wiki/Logarithm Power_series
https://rads.stackoverflow.com/amzn/click/0521431085