C++ 在不使用 pow 或循环的情况下计算数字的幂

Question

我是 C++ 初学者，接到任务编写一个函数来计算一个数的幂，但我们不允许使用 pow 函数或循环。

函数的用户必须在命令中输入底数和指数 window。

从哪里开始比较好？

Answer 1

void start_here(unsigned int n) {
    if (n > 0)
        start_here(n - 1);
}

start_here(2019);

然后你写：

double pow(double x, unsigned int exp) {
    if (exp > 0)
        return x * pow(x, exp - 1);
    else
        return 1;
}

那你进步：

double pow(double x, unsigned int exp) {
    if (exp > 0) {
        const auto p2 = pow(x, exp / 2);        
        return p2 * p2 * ((exp & 1) ? x : 1);
    }
    else
        return 1;
}

最后一种算法称为二进制求幂。

最后你学习了模板：

template<unsigned int exp>
constexpr double pow(double x) {
    if constexpr (exp > 0) {
        const auto p2 = pow<exp / 2>(x);        
        return p2 * p2 * ((exp & 1) ? x : 1);
    }
    else
        return 1;
}

编辑。尾递归优化。我们来看看第一版生成的汇编代码 pow() 没有优化 (-O0)：

pow(double, unsigned int):
        push    rbp
        mov     rbp, rsp
        sub     rsp, 16
        movsd   QWORD PTR [rbp-8], xmm0
        mov     DWORD PTR [rbp-12], edi
        cmp     DWORD PTR [rbp-12], 0
        je      .L2
        mov     eax, DWORD PTR [rbp-12]
        lea     edx, [rax-1]
        mov     rax, QWORD PTR [rbp-8]
        mov     edi, edx
        movq    xmm0, rax
        call    pow(double, unsigned int)
        mulsd   xmm0, QWORD PTR [rbp-8]
        jmp     .L3
.L2:
        movsd   xmm0, QWORD PTR .LC0[rip]
.L3:
        leave
        ret
.LC0:
        .long   0
        .long   1072693248

我们看到递归 call pow(double, unsigned int).

现在让我们添加一些优化(-O2 -ffast-math):

pow(double, unsigned int):
        movapd  xmm1, xmm0
        movsd   xmm0, QWORD PTR .LC0[rip]
        test    edi, edi
        je      .L4
.L3:
        mulsd   xmm0, xmm1
        sub     edi, 1
        jne     .L3
        ret
.L4:
        ret
.LC0:
        .long   0
        .long   1072693248

递归调用在哪里？它消失了！编译器使用 tail call optimization 并将递归调用转换为简单循环。此汇编代码等同于此 C++ 代码：

double pow(double x, unsigned int exp) {
    double p = 1;
    if (exp == 0)
        return p;
  loop:
    p *= x;
    if (--exp > 0)
       goto loop;
    return p;     
}

由于浮点乘法的非关联性，没有 -ffast-math option 就无法进行此优化。

最后，1.d's 在内存中用 8 个字节表示：

3F F0 00 00 | 00 00 00 00  (base 16)

转换成两个long数后，变成：

1072693248  | 0            (base 10)

这是可以在汇编代码中发现的两个幻数。

Answer 2

pow(x, y)可以写成exp(y * log(x))。据我所知，满足问题限制。

对于真正的 x 和 y，任何替代方案都是困难的。当然，对于积分使用递归有一些愚蠢的替代方法 y 但是对于线性问题使用递归从来都不是一个特别好的方法。

Answer 3

这里是你将如何做的。

int exponent(int , int );

int main()
{
    cout<<exponent(3,8);
    return 0;
}
int exponent(int x , int y )
{
    if(y==0)
        return 1;
    return (x*exponent(x,y-1));
}

如果您觉得难以消化，请告诉我。

Answer 4

使用递归的解决方案：

double power(double x, double n, double product = 1) {
    if (n <= 0) return product;
    product *= x;
    return power(x, n - 1, product);
}

int main()
{
    cout << power(10, 2);
}

Answer 5

假设整数底和指数，为什么不直接展开循环呢。假设 sizeof(int) = 4 字节 = 32 位。

long long power (int base, int exponent)
 {
  long long result = 1;
  long long powOf2 = base;

  if (exponent%2)
    result *= powOf2;
  exponent >>= 1;
  powOf2 *= powOf2;

  if (exponent%2)
    result *= powOf2;
  exponent >>= 1;
  powOf2 *= powOf2;

  (copy paste 30 more times)

  return result;
 }

如果 sizeof(int) = 8，复制粘贴 62 次而不是 30 次。

C++ 在不使用 pow 或循环的情况下计算数字的幂

C++ calculate the power of a number without using pow or loop

c++

loops

function

exponent