C++ 在不使用 pow 或循环的情况下计算数字的幂
C++ calculate the power of a number without using pow or loop
我是 C++ 初学者,接到任务编写一个函数来计算一个数的幂,但我们不允许使用 pow 函数或循环。
函数的用户必须在命令中输入底数和指数 window。
从哪里开始比较好?
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)
这是可以在汇编代码中发现的两个幻数。
pow(x, y)
可以写成exp(y * log(x))
。据我所知,满足问题限制。
对于真正的 x
和 y
,任何替代方案都是困难的。当然,对于积分使用递归有一些愚蠢的替代方法 y
但是对于线性问题使用递归从来都不是一个特别好的方法。
这里是你将如何做的。
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));
}
如果您觉得难以消化,请告诉我。
使用递归的解决方案:
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);
}
假设整数底和指数,为什么不直接展开循环呢。假设 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 函数或循环。
函数的用户必须在命令中输入底数和指数 window。
从哪里开始比较好?
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)
这是可以在汇编代码中发现的两个幻数。
pow(x, y)
可以写成exp(y * log(x))
。据我所知,满足问题限制。
对于真正的 x
和 y
,任何替代方案都是困难的。当然,对于积分使用递归有一些愚蠢的替代方法 y
但是对于线性问题使用递归从来都不是一个特别好的方法。
这里是你将如何做的。
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));
}
如果您觉得难以消化,请告诉我。
使用递归的解决方案:
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);
}
假设整数底和指数,为什么不直接展开循环呢。假设 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 次。