C++ 如何自己编写幂函数？

How can I write a power function myself?

提问by

I was always wondering how I can make a function which calculates the power (e.g. 2³) myself. In most languages these are included in the standard library, mostly as pow(double x, double y), but how can I write it myself?

我一直想知道如何制作一个自己计算功率（例如 2 ³）的函数。在大多数语言中，这些都包含在标准库中，主要是作为pow(double x, double y)，但我如何自己编写它？

I was thinking about for loops, but it think my brain got in a loop (when I wanted to do a power with a non-integer exponent, like 5^4.5or negatives 2^-21) and I went crazy ;)

我在想for loops，但它认为我的大脑陷入了一个循环（当我想用非整数指数做幂时，比如 5 ^4.5或负数 2 ^-21），我发疯了；）

So, how can I write a function which calculates the power of a real number? Thanks

那么，如何编写一个计算实数幂的函数呢？谢谢

---

---

Oh, maybe important to note: I cannot use functions which use powers (e.g. exp), which would make this ultimately useless.

哦，也许重要的是要注意：我不能使用使用权力的函数（例如exp），这会使这最终毫无用处。

采纳答案by fortran

Negative powers are not a problem, they're just the inverse (1/x) of the positive power.

负幂不是问题，它们只是1/x正幂的倒数 ( )。

Floating point powers are just a little bit more complicated; as you know a fractional power is equivalent to a root (e.g. x^(1/2) == sqrt(x)) and you also know that multiplying powers with the same base is equivalent to add their exponents.

浮点运算稍微复杂一点；如您所知，分数幂等价于根（例如x^(1/2) == sqrt(x)），并且您还知道，乘以相同底数的幂等于将它们的指数相加。

With all the above, you can:

有了以上所有内容，您可以：

• Decompose the exponent in a integer part and a rational part.
• Calculate the integer power with a loop (you can optimise it decomposing in factors and reusing partial calculations).
• Calculate the root with any algorithm you like (any iterative approximation like bisection or Newton method could work).
• Multiply the result.
• If the exponent was negative, apply the inverse.

• 将指数分解为整数部分和有理部分。
• 使用循环计算整数幂（您可以优化它分解因子并重用部分计算）。
• 使用您喜欢的任何算法计算根（任何迭代近似，如二分法或牛顿法都可以工作）。
• 乘以结果。
• 如果指数为负，则应用倒数。

Example:

例子：

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

回答by Jerry Coffin

A^B= Log^-1(Log(A)*B)

A ^B= Log ^-1(Log(A)*B)

Edit: yes, this definition really does provide something useful. For example, on an x86, it translates almost directly to FYL2X(Y * Log₂(X)) and F2XM1(2^x-1):

编辑：是的，这个定义确实提供了一些有用的东西。例如，在 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) 

The code ends up a little longer than you might expect, primarily because F2XM1only works with numbers in the range -1.0..1.0. The fld st(0)/frndint/fsubr st(1),stpiece subtracts off the integer part, so we're left with only the fraction. We apply F2XM1to that, add the 1 back on, then use FSCALEto handle the integer part of the exponentiation.

代码最终比您预期的要长一点，主要是因为F2XM1仅适用于 -1.0..1.0 范围内的数字。该fld st(0)/frndint/fsubr st(1),st部分减去整数部分，所以我们只剩下分数。我们F2XM1对此进行应用，重新加 1，然后使用它FSCALE来处理求幂的整数部分。

回答by Stephen Canon

Typically the implementation of the pow(double, double)function in math libraries is based on the identity:

通常pow(double, double)，数学库中函数的实现基于身份：

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

Using this identity, you only need to know how to raise a single number ato an arbitrary exponent, and how to take a logarithm base a. You have effectively turned a complicated multi-variable function into a two functions of a single variable, and a multiplication, which is pretty easy to implement. The most commonly chosen values of aare eor 2-- ebecause the e^xand log_e(1+x)have some very nice mathematical properties, and 2because it has some nice properties for implementation in floating-point arithmetic.

使用这个恒等式，您只需要知道如何将单个数字提高a到任意指数，以及如何取对数底a。你已经有效地将一个复杂的多变量函数变成了一个单变量和一个乘法的两个函数，这很容易实现。最常选择的值a是eor 2--e因为e^xandlog_e(1+x)有一些非常好的数学属性，并且2因为它有一些很好的属性可以在浮点算术中实现。

The catch of doing it this way is that (if you want to get full accuracy) you need to compute the log_a(x)term (and its product with y) to higher accuracy than the floating-point representation of xand y. For example, if xand yare doubles, and you want to get a high accuracy result, you'll need to come up with some way to store intermediate results (and do arithmetic) in a higher-precision format. The Intel x87 format is a common choice, as are 64-bit integers (though if you really want a top-quality implementation, you'll need to do a couple of 96-bit integer computations, which are a little bit painful in some languages). It's much easier to deal with this if you implement powf(float,float), because then you can just use doublefor intermediate computations. I would recommend starting with that if you want to use this approach.

做这种方式的缺点是，（如果你想获得完全精确），你需要计算的log_a(x)项（以及它与产品y）比的浮点表示更高的精度x和y。例如，如果x和y是双精度数，并且您想要获得高精度结果，则需要想出某种方法以更高精度的格式存储中间结果（并进行算术运算）。Intel x87 格式是一个常见的选择，64 位整数也是如此（尽管如果你真的想要一个高质量的实现，你需要做几个 96 位整数计算，这在某些情况下有点痛苦语言）。如果你实现了powf(float,float)，处理这个会容易得多，因为那样你就可以使用double用于中间计算。如果您想使用这种方法，我建议您从它开始。

---

---

The algorithm that I outlined is not the only possible way to compute pow. It is merely the most suitable for delivering a high-speed result that satisfies a fixed a prioriaccuracy bound. It is less suitable in some other contexts, and is certainly much harder to implement than the repeated-square[root]-ing algorithm that some others have suggested.

我概述的算法并不是计算 的唯一可能方法pow。它只是最适合提供满足固定先验精度界限的高速结果。它不太适合其他一些上下文，并且肯定比其他一些人建议的重复平方[根]算法更难实现。

If you want to try the repeated square[root] algorithm, begin by writing an unsigned integer power function that uses repeated squaring only. Once you have a good grasp on the algorithm for that reduced case, you will find it fairly straightforward to extend it to handle fractional exponents.

如果您想尝试重复平方 [root] 算法，请首先编写一个仅使用重复平方的无符号整数幂函数。一旦您很好地掌握了该简化案例的算法，您会发现将其扩展为处理分数指数是相当简单的。

回答by dan04

There are two distinct cases to deal with: Integer exponents and fractional exponents.

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

For integer exponents, you can use exponentiation by squaring.

对于整数指数，您可以使用平方取幂。

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)

The second "elif" is what distinguishes this from the na?ve pow function. It allows the function to make O(log n) recursive calls instead of O(n).

第二个“elif”是区别于na?ve pow 函数的地方。它允许函数进行 O(log n) 递归调用而不是 O(n)。

For fractional exponents, you can use the identity a^b = C^(b*log_C(a)). It's convenient to take C=2, so a^b = 2^(b * log2(a)). This reduces the problem to writing functions for 2^x and log2(x).

对于分数指数，您可以使用恒等式 a^b = C^(b*log_C(a))。取C=2方便，所以a^b = 2^(b * log2(a))。这减少了为 2^x 和 log2(x) 编写函数的问题。

The reason it's convenient to take C=2 is that floating-point numbers are stored in base-2 floating point. log2(a * 2^b) = log2(a) + b. This makes it easier to write your log2 function: You don't need to have it be accurate for every positive number, just on the interval [1, 2). Similarly, to calculate 2^x, you can multiply 2^(integer part of x) * 2^(fractional part of x). The first part is trivial to store in a floating point number, for the second part, you just need a 2^x function over the interval [0, 1).

取 C=2 方便的原因是浮点数存储在 base-2 浮点中。log2(a * 2^b) = log2(a) + b。这样可以更轻松地编写 log2 函数：您不需要对每个正数都准确，只需在区间 [1, 2) 上即可。同样，要计算 2^x，您可以乘以 2^(x 的整数部分) * 2^(x 的小数部分)。第一部分很容易存储在浮点数中，对于第二部分，您只需要在区间 [0, 1) 上使用 2^x 函数。

The hard part is finding a good approximation of 2^x and log2(x). A simple approach is to use Taylor series.

困难的部分是找到 2^x 和 log2(x) 的一个很好的近似值。一个简单的方法是使用泰勒级数。

回答by Andreas Rejbrand

Per definition:

根据定义：

a^b = exp(b ln(a))

a^b = exp(b ln(a))

where 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! + ...

where n! = 1 * 2 * ... * n.

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

In practice, you could store an arrayof the first 10 values of 1/n!, and then approximate

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

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

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

because 10! is a huge number, so 1/10! is very small (2.7557319224?10^-7).

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

回答by Richie Cotton

For positive integer powers, look at exponentiation by squaringand addition-chain exponentiation.

对于正整数幂，请查看平方和加法链求幂。

回答by High Performance Mark

Wolfram functionsgives a wide variety of formulae for calculating powers. Some of them would be very straightforward to implement.

Wolfram 函数提供了多种计算幂的公式。其中一些实施起来非常简单。

回答by ssd

Using three self implemented functions iPow(x, n), Ln(x)and Exp(x), I'm able to compute fPow(x, a), x and a being doubles. Neither of the functions below use library functions, but just iteration.

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

Some explanation about functions implemented:

关于实现的功能的一些解释：

(1) iPow(x, n): x is double, n is int. This is a simple iteration, as n is an integer.

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

(2) Ln(x): This function uses the Taylor Series iteration. The series used in iteration is Σ (from int i = 0 to n) {(1 / (2 * i + 1)) * ((x - 1) / (x + 1)) ^ (2 * n + 1)}. The symbol ^denotes the power function Pow(x, n)implemented in the 1st function, which uses simple iteration.

(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): This function, again, uses the Taylor Series iteration. The series used in iteration is Σ (from int i = 0 to n) {x^i / i!}. Here, the ^denotes the power function, but it is notcomputed by calling the 1st Pow(x, n)function; instead it is implemented within the 3rd function, concurrently with the factorial, using d *= x / i. I felt I had to use this trick, because in this function, iteration takes some more steps relative to the other functions and the factorial (i!)overflows most of the time. In order to make sure the iteration does not overflow, the power function in this part is iterated concurrently with the factorial. This way, I overcame the overflow.

(3) Exp(x)：该函数再次使用泰勒级数迭代。迭代中使用的系列是Σ (from int i = 0 to n) {x^i / i!}。这里，^表示幂函数，但不是通过调用第一个Pow(x, n)函数来计算的；相反，它是在第三个函数中与阶乘同时实现的，使用d *= x / i. 我觉得我必须使用这个技巧，因为在这个函数中，迭代相对于其他函数需要更多的步骤，并且(i!)大部分时间阶乘溢出。为了保证迭代不会溢出，这部分的幂函数与阶乘同时迭代。这样，我克服了溢出。

(4) fPow(x, a): x and a are both doubles. This function does nothing but just call the other three functions implemented above. The main idea in this function depends on some calculus: fPow(x, a) = Exp(a * Ln(x)). And now, I have all the functions iPow, Lnand Expwith iteration already.

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

n.b.I used a constant MAX_DELTA_DOUBLEin order to decide in which step to stop the iteration. I've set it to 1.0E-15, which seems reasonable for doubles. So, the iteration stops if (delta < MAX_DELTA_DOUBLE)If you need some more precision, you can use long doubleand decrease the constant value for MAX_DELTA_DOUBLE, to 1.0E-18for example (1.0E-18 would be the minimum).

nb我使用 aconstant MAX_DELTA_DOUBLE来决定停止迭代的步骤。我已将其设置为1.0E-15，这对于双打似乎是合理的。因此，(delta < MAX_DELTA_DOUBLE)如果您需要更高的精度，则迭代停止，您可以使用long double并减小 的常数值MAX_DELTA_DOUBLE，1.0E-18例如（1.0E-18 将是最小值）。

Here is the code, which works for me.

这是代码，对我有用。

#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);
}

回答by che.moor

You can found the powfunction like this:

你可以找到这样的pow函数：

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);
}

You can found the floorfunction like this:

你可以找到这样的floor函数：

static double floors(double p_nomber)
{
    double x =  p_nomber;
    long partent = (long) x; 

    if (x<0)
    {
        return (partent-1);
    }
    else
    {
        return (partent);
    }
}

Best regards

此致

回答by Wouter Lievens

It's an interesting exercise. Here's some suggestions, which you should try in this order:

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

1. Use a loop.
2. Use recursion (not better, but interesting none the less)
3. Optimize your recursion vastly by using divide-and-conquer techniques
4. Use logarithms

1. 使用循环。
2. 使用递归（不是更好，但仍然有趣）
3. 使用分而治之的技术极大地优化你的递归
4. 使用对数