我怎样才能写一个权力函数呢？

我总是想知道如何做一个function来计算功率（例如2 ³ ）。 在大多数语言中，这些都包含在标准库中，大部分是pow(double x, double y) ，但是我怎样才能自己写呢？

我正在考虑for loops ，但它认为我的大脑进入循环（当我想要做一个非整数指数的权力，如5 ^4.5或负面2 – ²¹ ），我疯了;）

那么，怎样才能写出一个计算实数的函数？ 谢谢

---

哦，也许重要的是要注意：我不能使用function（如exp ），这将使这最终无用。

Answer 1

负面权力不是问题，它们只是正面权力的倒数（ 1/x ）。

浮点权力稍微复杂一些， 正如你所知道的，一个小数的幂等于一个根（例如x^(1/2) == sqrt(x) ），并且你也知道，具有相同基的乘法幂相当于增加它们的指数。

通过以上所述，您可以：

• 将指数分解为整数部分和有理部分 。
• 用一个循环计算整数功率（可以优化它分解因子和重复使用部分计算）。
• 用你喜欢的任何algorithm计算根（任何迭代逼近，如二分法或牛顿法可以工作）。
• 乘以结果。
• 如果指数为负数，则应用反算。

例：

 2^(-3.5) = (2^3 * 2^(1/2)))^-1 = 1 / (2*2*2 * sqrt(2)) 

Answer 2

A ^B = Log ^-1 （Log（A）* B）

编辑：是的，这个定义确实提供了一些有用的东西。 例如，在x86上，它几乎直接转换为FYL2X （Y * Log ₂ （X））和F2XM1 （2 ^x -1）：

 fyl2x fld st(0) frndint fsubr st(1),st fxch st(1) fchs f2xmi fld1 faddp st(1),st fscale fstp st(1) 

代码结束时间比您预期的要长一些，主要是因为F2XM1只能使用-1.0..1.0范围内的数字。 fld st(0)/frndint/fsubr st(1),st从整数部分中减去的，所以我们只剩下部分。 我们把F2XM1应用到那个，再加1，然后用FSCALE来处理幂运算的整数部分。

Answer 3

通常，math库中的pow(double, double)函数的实现基于以下标识：

 pow(x,y) = pow(a, y * log_a(x)) 

使用这个标识，你只需要知道如何将一个数字a提高到一个任意的指数，以及如何取一个对数基数a 。 您已经将一个复杂的多variables函数有效地转化为一个单variables的两个函数和一个相当容易实现的乘法运算。 因为e^x和log_e(1+x)具有一些非常好的math属性，所以最常用的a值是e或2 – e ， 2因为它在浮点algorithm中具有一些很好的性能。

这样做的方法是（如果要获得完整的准确性），需要计算log_a(x)项（及其乘积为y ）的精度高于x和y的浮点表示。 例如，如果x和y是双精度，并且想要得到高精度的结果，那么您需要想出一些方法来以更高精度的格式存储中间结果（并进行算术运算）。 英特尔x87格式是一个常见的select，就像64位整数一样（尽pipe如果你真的想要一个高质量的实现，你需要做一些96位整数计算，在一些有些痛苦的一些语言）。 如果你实现powf(float,float) ，处理这个事情就容易多了，因为那样你可以使用double来进行中间计算。 如果你想使用这种方法，我会build议开始。

---

我列出的algorithm不是计算pow的唯一可能的方法。 它只是最适合提供满足固定的先验准确界限的高速结果。 这在其他一些情况下是不太合适的，并且肯定比其他一些人提出的重复平方根algorithm要难得多。

如果你想尝试重复的square [root]algorithm，首先写一个无符号的整数幂函数，只使用重复的平方。 一旦你很好地掌握了减less的情况下的algorithm，你会发现相当简单的扩展它来处理分数指数。

Answer 4

有两种不同的情况需要处理：整数指数和分数指数。

对于整数指数，可以通过平方来使用指数。

 def pow(base, exponent): if exponent == 0: return 1 elif exponent < 0: return 1 / pow(base, -exponent) elif exponent % 2 == 0: half_pow = pow(base, exponent // 2) return half_pow * half_pow else: return base * pow(base, exponent - 1) 

第二个“elif”是区分这与天真的powfunction。 它允许函数使O（log n）recursion调用而不是O（n）。

对于分数指数，可以使用标识a ^ b = C ^（b * log_C（a））。 取C = 2是很方便的，所以a ^ b = 2 ^（b * log2（a））。 这减less了写入2 ^ x和log2（x）函数的问题。

C = 2方便的原因是浮点数存储在基2浮点数中。 log2（a * 2 ^ b）= log2（a）+ b。 这使得编写log2函数变得更加容易：只要在区间[1,2]上，不需要为每个正数准确。 同样，要计算2 ^ x，可以乘以2 ^（x的整数部分）* 2 ^（x的小数部分）。 第一部分是浮点数，第二部分只需要2 ^ x的区间[0,1]函数。

困难的部分是find2 ^ x和log2（x）的一个很好的近似值。 一个简单的方法是使用泰勒级数 。

Answer 5

根据定义：

a ^ b = exp（b ln（a））

exp(x) = 1 + x + x^2/2 + x^3/3! + x^4/4! + x^5/5! + ... exp(x) = 1 + x + x^2/2 + x^3/3! + x^4/4! + x^5/5! + ...

哪里n! = 1 * 2 * ... * n n! = 1 * 2 * ... * n 。

在实践中，您可以存储1/n!的前10个值的数组 1/n! ，然后近似

exp(x) = 1 + x + x^2/2 + x^3/3! + ... + x^10/10!

因为10！ 是一个巨大的数字，所以1/10！ 非常小（2.7557319224⋅10^ -7）。

Answer 6

Wolfram函数给出了用于计算权力的各种公式。 其中一些将是非常直接的实施。

Answer 7

对于正整数幂， 通过平方和加法链取幂来看幂 。

Answer 8

使用三个自我实现的函数iPow(x, n) ， Ln(x)和Exp(x) ，我可以计算fPow(x, a) ，x和a是双精度 。 下面的函数都不使用库函数，而只是迭代。

关于function的一些解释：

（1） iPow(x, n) ：x是double ，n是int 。 这是一个简单的迭代，因为n是一个整数。

（2） Ln(x) ：这个函数使用泰勒级数迭代。 用于迭代的序列是Σ (from int i = 0 to n) {(1 / (2 * i + 1)) * ((x - 1) / (x + 1)) ^ (2 * n + 1)} 。 符号^表示在第一个函数中实现的幂函数Pow(x, n) ，它使用简单的迭代。

（3） Exp(x) ：这个函数再次使用泰勒级数迭代。 迭代中使用的序列是Σ (from int i = 0 to n) {x^i / i!} 。 这里， ^表示幂函数，但不是通过调用1st Pow(x, n)函数来计算的; 而是使用d *= x / i在第三个函数中实现，并与阶乘同时执行。 我觉得我不得不使用这个技巧 ，因为在这个函数中，迭代相对于其他函数需要更多的步骤，并且阶乘(i!)大部分时间溢出。 为了确保迭代没有溢出，本部分的幂函数与阶乘同时迭代。 这样，我克服了溢出。

（4） fPow(x, a) ： x和a都是双打 。 这个函数什么都不做，只是调用上面实现的其他三个函数。 这个函数的主要思想取决于一些微积分： fPow(x, a) = Exp(a * Ln(x)) 。 现在，我已经完成了iPow ， Ln和Exp所有function。

NB我用一个constant MAX_DELTA_DOUBLE为了决定在哪一步停止迭代。 我已经把它设置为1.0E-15 ，对于双打似乎是合理的。 因此，如果(delta < MAX_DELTA_DOUBLE)迭代停止，如果需要更多的精度，可以使用long double并将MAX_DELTA_DOUBLE的常量值减小到1.0E-18 （例如1.0E-18）。

这是代码，这对我很有用。

 #define MAX_DELTA_DOUBLE 1.0E-15 #define EULERS_NUMBER 2.718281828459045 double MathAbs_Double (double x) { return ((x >= 0) ? x : -x); } int MathAbs_Int (int x) { return ((x >= 0) ? x : -x); } double MathPow_Double_Int(double x, int n) { double ret; if ((x == 1.0) || (n == 1)) { ret = x; } else if (n < 0) { ret = 1.0 / MathPow_Double_Int(x, -n); } else { ret = 1.0; while (n--) { ret *= x; } } return (ret); } double MathLn_Double(double x) { double ret = 0.0, d; if (x > 0) { int n = 0; do { int a = 2 * n + 1; d = (1.0 / a) * MathPow_Double_Int((x - 1) / (x + 1), a); ret += d; n++; } while (MathAbs_Double(d) > MAX_DELTA_DOUBLE); } else { printf("\nerror: x < 0 in ln(x)\n"); exit(-1); } return (ret * 2); } double MathExp_Double(double x) { double ret; if (x == 1.0) { ret = EULERS_NUMBER; } else if (x < 0) { ret = 1.0 / MathExp_Double(-x); } else { int n = 2; double d; ret = 1.0 + x; do { d = x; for (int i = 2; i <= n; i++) { d *= x / i; } ret += d; n++; } while (d > MAX_DELTA_DOUBLE); } return (ret); } double MathPow_Double_Double(double x, double a) { double ret; if ((x == 1.0) || (a == 1.0)) { ret = x; } else if (a < 0) { ret = 1.0 / MathPow_Double_Double(x, -a); } else { ret = MathExp_Double(a * MathLn_Double(x)); } return (ret); } 

Answer 9

有效地计算正整数幂的更好的algorithm是重复地对基底进行平方，同时跟踪额外的剩余被乘数。 以下是Python中的示例解决scheme，应该比较容易理解并翻译成您的首选语言：

 def power(base, exponent): remaining_multiplicand = 1 result = base while exponent > 1: remainder = exponent % 2 if remainder > 0: remaining_multiplicand = remaining_multiplicand * result exponent = (exponent - remainder) / 2 result = result * result return result * remaining_multiplicand 

为了使它处理负指数，你所要做的就是计算正数版本，并把结果除以1，所以应该是对上述代码的简单修改。 分数指数要困难得多，因为它实质上意味着计算n = 1/abs(exponent % 1)的基数n根，然后将结果乘以整数部分的功率计算结果：

 power(base, exponent - (exponent % 1)) 

你可以使用牛顿的方法来计算根的精确度。 查看关于algorithm的维基百科文章 。

Answer 10

这是一个有趣的练习。 以下是一些build议，您应该按以下顺序尝试：

1. 使用循环。
2. 使用recursion（不是更好，但有趣的是less）
3. 通过使用分而治之的技巧，大大优化您的recursion
4. 使用对数

Answer 11

你可以像这样findpow函数：

 static double pows (double p_nombre, double p_puissance) { double nombre = p_nombre; double i=0; for(i=0; i < (p_puissance-1);i++){ nombre = nombre * p_nombre; } return (nombre); } 

你可以find这样的地板function：

 static double floors(double p_nomber) { double x = p_nomber; long partent = (long) x; if (x<0) { return (partent-1); } else { return (partent); } } 

最好的祝福

Answer 12

我正在使用固定点长algorithm，我的战略是基于log2 / exp2。 数字包括：

• int sig = { -1; +1 } int sig = { -1; +1 } signum
• DWORD a[A+B]数字
• A是数字的整数部分的DWORD的数量
• B是小数部分的DWORD的数量

我简化的解决scheme是：

 //--------------------------------------------------------------------------- longnum exp2 (const longnum &x) { int i,j; longnum c,d; c.one(); if (x.iszero()) return c; i=x.bits()-1; for(d=2,j=_longnum_bits_b;j<=i;j++,d*=d) if (x.bitget(j)) c*=d; for(i=0,j=_longnum_bits_b-1;i<_longnum_bits_b;j--,i++) if (x.bitget(j)) c*=_longnum_log2[i]; if (x.sig<0) {d.one(); c=d/c;} return c; } //--------------------------------------------------------------------------- longnum log2 (const longnum &x) { int i,j; longnum c,d,dd,e,xx; c.zero(); d.one(); e.zero(); xx=x; if (xx.iszero()) return c; //**** error: log2(0) = infinity if (xx.sig<0) return c; //**** error: log2(negative x) ... no result possible if (d.geq(x,d)==0) {xx=d/xx; xx.sig=-1;} i=xx.bits()-1; e.bitset(i); i-=_longnum_bits_b; for (;i>0;i--,e>>=1) // integer part { dd=d*e; j=dd.geq(dd,xx); if (j==1) continue; // dd> xx c+=i; d=dd; if (j==2) break; // dd==xx } for (i=0;i<_longnum_bits_b;i++) // fractional part { dd=d*_longnum_log2[i]; j=dd.geq(dd,xx); if (j==1) continue; // dd> xx c.bitset(_longnum_bits_b-i-1); d=dd; if (j==2) break; // dd==xx } c.sig=xx.sig; c.iszero(); return c; } //--------------------------------------------------------------------------- longnum pow (const longnum &x,const longnum &y) { //x^y = exp2(y*log2(x)) int ssig=+1; longnum c; c=x; if (y.iszero()) {c.one(); return c;} // ?^0=1 if (c.iszero()) return c; // 0^?=0 if (c.sig<0) { c.overflow(); c.sig=+1; if (y.isreal()) {c.zero(); return c;} //**** error: negative x ^ noninteger y if (y.bitget(_longnum_bits_b)) ssig=-1; } c=exp2(log2(c)*y); c.sig=ssig; c.iszero(); return c; } //--------------------------------------------------------------------------- 

哪里：

 _longnum_bits_a = A*32 _longnum_bits_b = B*32 _longnum_log2[i] = 2 ^ (1/(2^i)) ... precomputed sqrt table _longnum_log2[0]=sqrt(2) _longnum_log2[1]=sqrt[tab[0]) _longnum_log2[i]=sqrt(tab[i-1]) longnum::zero() sets *this=0 longnum::one() sets *this=+1 bool longnum::iszero() returns (*this==0) bool longnum::isnonzero() returns (*this!=0) bool longnum::isreal() returns (true if fractional part !=0) bool longnum::isinteger() returns (true if fractional part ==0) int longnum::bits() return num of used bits in number counted from LSB longnum::bitget()/bitset()/bitres()/bitxor() are bit access longnum.overflow() rounds number if there was a overflow X.FFFFFFFFFF...FFFFFFFFF??h -> (X+1).0000000000000...000000000h int longnum::geq(x,y) is comparition |x|,|y| returns 0,1,2 for (<,>,==) 

所有你需要了解这个代码是二进制forms的数字包括2的幂的和，当你需要计算2 ^ num，那么它可以被重写为这个

• 2^(b(-n)*2^(-n) + ... + b(+m)*2^(+m))

其中n是小数位， m是整数位。 乘以二进制forms的二分之一是简单的位移，所以如果你把它放在一起，你会得到类似于我的exp2代码。 log2基于binarusearch…将结果位从MSB更改为LSB，直到匹配search值（与快速sqrt计算非常相似的algorithm）。 希望这有助于澄清事情…

Answer 13

在其他答案中给出了很多方法。 这是我认为可能是有用的整体权力的情况下。

在n ^×的整数次幂x的情况下，直接的方法将进行x-1次乘法运算。 为了优化这个，我们可以使用dynamic编程并重新使用一个较早的乘法结果来避免所有的x乘法。 例如，在5 ⁹ ，我们可以说， 批量3 ，即计算5 ³一次，得到125，然后立方体125使用相同的逻辑，在这个过程中只有4乘法，而不是8直接的方式乘法。

问题是批次b的理想大小是多less，所以乘法的次数是最小的。 所以让我们来写这个公式。 如果f（x，b）是表示使用上述方法计算n ^x所需的乘法次数的函数，则

说明：一批p个乘积的乘积将乘以p-1。 如果我们将x次乘法分成b个批次，则每个批次内需要（x / b）-1次乘法运算，所有b批次都需要b-1次乘法运算。

现在我们可以计算这个函数关于b的一阶导数，并把它等于0，得到最小乘法次数b。

现在把这个b的值放到函数f（x，b）中以获得最小的乘法次数：

对于所有正x，这个值比直接的乘法小。