我知道使用 << 运算符可以实现2的幂。那么10的幂呢？例如10^5？在C++中是否有比pow(10,5)更快的方法？手动计算这是一个相当简单的过程。但是由于数字的二进制表示，对于计算机来说并不容易... 假设我只关心整数幂，即10^n，其中n为整数。
13个回答
36
像这样：
int quick_pow10(int n)
{
static int pow10[10] = {
1, 10, 100, 1000, 10000,
100000, 1000000, 10000000, 100000000, 1000000000
};
return pow10[n];
}
显然，对于long long也可以做同样的事情。
相比竞争对手的任何方法，这应该快几倍。但是，如果你有很多基数（尽管随着基数变大，值的数量会急剧下降），那么它就相当受限了，所以如果组合数不是非常大，仍然可以完成。
作为比较：
#include <iostream>
#include <cstdlib>
#include <cmath>
static int quick_pow10(int n)
{
static int pow10[10] = {
1, 10, 100, 1000, 10000,
100000, 1000000, 10000000, 100000000, 1000000000
};
return pow10[n];
}
static int integer_pow(int x, int n)
{
int r = 1;
while (n--)
r *= x;
return r;
}
static int opt_int_pow(int n)
{
int r = 1;
const int x = 10;
while (n)
{
if (n & 1)
{
r *= x;
n--;
}
else
{
r *= x * x;
n -= 2;
}
}
return r;
}
int main(int argc, char **argv)
{
long long sum = 0;
int n = strtol(argv[1], 0, 0);
const long outer_loops = 1000000000;
if (argv[2][0] == 'a')
{
for(long i = 0; i < outer_loops / n; i++)
{
for(int j = 1; j < n+1; j++)
{
sum += quick_pow10(n);
}
}
}
if (argv[2][0] == 'b')
{
for(long i = 0; i < outer_loops / n; i++)
{
for(int j = 1; j < n+1; j++)
{
sum += integer_pow(10,n);
}
}
}
if (argv[2][0] == 'c')
{
for(long i = 0; i < outer_loops / n; i++)
{
for(int j = 1; j < n+1; j++)
{
sum += opt_int_pow(n);
}
}
}
std::cout << "sum=" << sum << std::endl;
return 0;
}
使用g++ 4.6.3编译，并使用-Wall -O2 -std=c++0x参数，得到以下结果：
$ g++ -Wall -O2 -std=c++0x pow.cpp
$ time ./a.out 8 a
sum=100000000000000000
real 0m0.124s
user 0m0.119s
sys 0m0.004s
$ time ./a.out 8 b
sum=100000000000000000
real 0m7.502s
user 0m7.482s
sys 0m0.003s
$ time ./a.out 8 c
sum=100000000000000000
real 0m6.098s
user 0m6.077s
sys 0m0.002s
我本来也有使用pow的选项，但当我第一次尝试时它花费了1m22.56s，所以当我决定使用优化的循环变体时，我将其移除了。
- Mats Petersson
9
不要与咖啡泡混淆。 - brian beuning
你可以尝试使用循环来初始化数据。编译器可能会在运行时之前计算这些值，从而进行优化。 - FreelanceConsultant
@EdwardBird：为此，
static 比循环更快，因为它很可能在编译时初始化，或者至少只初始化一次。而循环将每次都进行初始化。 - Mats Petersson@MatsPetersson，最近我读到了一些关于编译器优化的内容，其中会在编译时计算某些值……例如，如果你有
x = x * 10 * 5，某些编译器会将其改为 x = x * 50。那么，编译器不会检测循环初始化某些值并且在编译时进行计算，这样可执行程序就不必要了吗？ - FreelanceConsultant1不错，最优解，但我认为你真的应该在
n 上添加边界检查。 - cmaster - reinstate monica显示剩余4条评论
12
- Dietmar Kühl
11
对于一些bigint类型，可能是这样。不过我认为问题不在于此。对于固定大小的整数类型，查找表使其成为O(1)操作。(编辑：不过这并不公平。对于固定大小的整数类型，n有一个上限，如果n有一个上限，即使像O(2^n)这样的东西也等价于O(1)。)对于浮点类型，pow通常已经实现为O(1)操作。 - user743382
1@hvd “O（1）”并不一定比“O（n）”更快。” - user529758
@Mehrdad：当使用固定大小的整数时，您甚至不需要并行版本，因为可以使用查找表。但是，一旦您的整数大小不受限制（除了总可用内存的大小），硬件可以使用的并行算法将无法帮助您在O(log n)以下。 - Dietmar Kühl
7我们不是要求 pow(n,10) 而是 pow(10,n) 吗？ - dmjalund
5（x<<3）（x<<1）= 8x2x = 16x^2，这个答案存在问题。可能意思是通过重复平方实现指数运算，比如 x^(1<<3)*x^(1<<1)，但显然这种错误是不可接受的。 - Gregory Morse
显示剩余6条评论
10
使用模板元编程来解决任何进制问题：
template<int E, int N>
struct pow {
enum { value = E * pow<E, N - 1>::value };
};
template <int E>
struct pow<E, 0> {
enum { value = 1 };
};
那么它可以用来生成一个查找表，该表可以在运行时使用：
template<int E>
long long quick_pow(unsigned int n) {
static long long lookupTable[] = {
pow<E, 0>::value, pow<E, 1>::value, pow<E, 2>::value,
pow<E, 3>::value, pow<E, 4>::value, pow<E, 5>::value,
pow<E, 6>::value, pow<E, 7>::value, pow<E, 8>::value,
pow<E, 9>::value
};
return lookupTable[n];
}
为了检测可能的溢出，必须正确使用编译器标志。
用法示例：
for(unsigned int n = 0; n < 10; ++n) {
std::cout << quick_pow<10>(n) << std::endl;
}
- Vincent
1
@cmaster 好的。我尝试改进我的回答... 如果它仍然没有用或不正确，我会删除我的回答。 - Vincent
6
一个不涉及浮点转换和计算的整数幂函数可能比pow()更快：
int integer_pow(int x, int n)
{
int r = 1;
while (n--)
r *= x;
return r;
}
编辑：进行基准测试后发现，朴素的整数指数幂方法似乎比浮点数方法快大约两倍：
h2co3-macbook:~ h2co3$ cat quirk.c
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <errno.h>
#include <string.h>
#include <math.h>
int integer_pow(int x, int n)
{
int r = 1;
while (n--)
r *= x;
return r;
}
int main(int argc, char *argv[])
{
int x = 0;
for (int i = 0; i < 100000000; i++) {
x += powerfunc(i, 5);
}
printf("x = %d\n", x);
return 0;
}
h2co3-macbook:~ h2co3$ clang -Wall -o quirk quirk.c -Dpowerfunc=integer_pow
h2co3-macbook:~ h2co3$ time ./quirk
x = -1945812992
real 0m1.169s
user 0m1.164s
sys 0m0.003s
h2co3-macbook:~ h2co3$ clang -Wall -o quirk quirk.c -Dpowerfunc=pow
h2co3-macbook:~ h2co3$ time ./quirk
x = -2147483648
real 0m2.898s
user 0m2.891s
sys 0m0.004s
h2co3-macbook:~ h2co3$
- user529758
30
4
无乘法和无表格版本：
//Nx10^n
int Npow10(int N, int n){
N <<= n;
while(n--) N += N << 2;
return N;
}
- acegs
1
这很整洁，但仅适用于无符号数 - 函数签名应该传达这一点。 - Pete
2
以下是我的尝试：
上面所述的是几件事情。
首先，为了使BigNum支持成本更低，它被模板化了。默认情况下，它支持任何支持 *= own_type 的基础类型，并且可以隐式转换为 int，或者 int 可以隐式转换为它（如果两者都成立，将会出现问题），并且您需要专门指定某些模板，以表示涉及的指数类型既是无符号的又类似于整数。
在这种情况下，类似于整数和无符号意味着它支持 &1 返回 bool 并且 >>1 返回它可以构造的东西，最终（经过反复 >>1）达到一个在 bool 上下文中评估为 false 的点。我使用特征类来表达限制，因为像 -1 这样的值的朴素使用将编译并（在某些平台上）循环，而（在其他平台上）则不会。
假设乘法是 O(1) 的，那么此算法的执行时间为 O(lg(exponent))，其中 lg(exponent) 是需要 <<1 exponent 几次才能在布尔上下文中评估为 false 的次数。对于传统的整数类型，这将是 exponent 值的二进制对数：因此不超过 32。
我还消除了循环内的所有分支（或者，更准确地说，让现有编译器明显知道没有分支是必要的），只有控制分支（在它第一次变为 false 之前都为 true）。对于高基数和低指数，甚至消除那个分支可能也值得考虑…
这是一个尝试：
// specialize if you have a bignum integer like type you want to work with:
template<typename T> struct is_integer_like:std::is_integral<T> {};
template<typename T> struct make_unsigned_like:std::make_unsigned<T> {};
template<typename T, typename U>
T powT( T base, U exponent ) {
static_assert( is_integer_like<U>::value, "exponent must be integer-like" );
static_assert( std::is_same< U, typename make_unsigned_like<U>::type >::value, "exponent must be unsigned" );
T retval = 1;
T& multiplicand = base;
if (exponent) {
while (true) {
// branch prediction will be awful here, you may have to micro-optimize:
retval *= (exponent&1)?multiplicand:1;
// or /2, whatever -- `>>1` is probably faster, esp for bignums:
exponent = exponent>>1;
if (!exponent)
break;
multiplicand *= multiplicand;
}
}
return retval;
}
上面所述的是几件事情。
首先，为了使BigNum支持成本更低，它被模板化了。默认情况下，它支持任何支持 *= own_type 的基础类型，并且可以隐式转换为 int，或者 int 可以隐式转换为它（如果两者都成立，将会出现问题），并且您需要专门指定某些模板，以表示涉及的指数类型既是无符号的又类似于整数。
在这种情况下，类似于整数和无符号意味着它支持 &1 返回 bool 并且 >>1 返回它可以构造的东西，最终（经过反复 >>1）达到一个在 bool 上下文中评估为 false 的点。我使用特征类来表达限制，因为像 -1 这样的值的朴素使用将编译并（在某些平台上）循环，而（在其他平台上）则不会。
假设乘法是 O(1) 的，那么此算法的执行时间为 O(lg(exponent))，其中 lg(exponent) 是需要 <<1 exponent 几次才能在布尔上下文中评估为 false 的次数。对于传统的整数类型，这将是 exponent 值的二进制对数：因此不超过 32。
我还消除了循环内的所有分支（或者，更准确地说，让现有编译器明显知道没有分支是必要的），只有控制分支（在它第一次变为 false 之前都为 true）。对于高基数和低指数，甚至消除那个分支可能也值得考虑…
- Yakk - Adam Nevraumont
2
为什么你要在代码中无端地添加这些丑陋的模板？！？它很让人难受。我差点因此给你投反对票... - cmaster - reinstate monica
@cmaster因为只有在使用bignum或其他不是简单整数的类型时，执行此代码才有意义。如果你的基数是大于1的整数，则使用64位整数的朴素“自乘指数次”将会是一个长度不超过64的循环，然后就会溢出，这将比上面我的代码更快。上述代码处理浮点、bignum、有理数或任何其他情况下的基数，并且在这些情况之外，上述代码运行起来是没有价值的。在整数基数情况下，在最坏的情况下它不会慢得多，并且在常见情况下可能会更快。 - Yakk - Adam Nevraumont
2
现在，通过使用
constexpr，可以这样做：constexpr int pow10(int n) {
int result = 1;
for (int i = 1; i<=n; ++i)
result *= 10;
return result;
}
int main () {
int i = pow10(5);
}
i将在编译时计算。针对x86-64 gcc 9.2生成的ASM：
main:
push rbp
mov rbp, rsp
mov DWORD PTR [rbp-4], 100000
mov eax, 0
pop rbp
ret
- João Paulo
2
整型变量 i 可以在编译时计算，但也可能不会，因为 i 没有声明为 constexpr。你给出了一个没有保证编译时计算的例子。 - Vladislav Kogan
int i 可能在编译时计算，但也可能不会，因为 i 没有声明为 constexpr。你给出了一个没有保证编译时计算的例子。 - undefined
1
基于constexpr函数的通用表格构建器。浮点数部分需要C++20和GCC，但非浮点数部分适用于C++17。如果将“auto”类型参数更改为“long”，则可以使用C++14。未经充分测试。
#include <cstdio>
#include <cassert>
#include <cmath>
// Precomputes x^N
// Inspired by https://dev59.com/mmMk5IYBdhLWcg3wvARo#34465458
template<auto x, unsigned char N, typename AccumulatorType>
struct PowTable {
constexpr PowTable() : mTable() {
AccumulatorType p{ 1 };
for (unsigned char i = 0; i < N; ++i) {
p *= x;
mTable[i] = p;
}
}
AccumulatorType operator[](unsigned char n) const {
assert(n < N);
return mTable[n];
}
AccumulatorType mTable[N];
};
long pow10(unsigned char n) {
static constexpr PowTable<10l, 10, long> powTable;
return powTable[n-1];
}
double powe(unsigned char n) {
static constexpr PowTable<2.71828182845904523536, 10, double> powTable;
return powTable[n-1];
}
int main() {
printf("10^3=%ld\n", pow10(3));
printf("e^2=%f", powe(2));
assert(pow10(3) == 1000);
assert(powe(2) - 7.389056 < 0.001);
}
- Alexander Torstling
1
这个函数可以更快地计算整数值 x 的 y 次方，比 pow 函数更快。
int pot(int x, int y){
int solution = 1;
while(y){
if(y&1)
solution*= x;
x *= x;
y >>= 1;
}
return solution;
}
- Marko Gregurovic
1
你可以使用查找表，这是目前最快的方法。
你也可以考虑使用this：-
你也可以考虑使用this：-
template <typename T>
T expt(T p, unsigned q)
{
T r(1);
while (q != 0) {
if (q % 2 == 1) { // q is odd
r *= p;
q--;
}
p *= p;
q /= 2;
}
return r;
}
- Rahul Tripathi
3
1@OliCharlesworth：最多不是20个条目吗？log(2^64) < 20 - user541686
@Mehrdad：啊，是的，看起来OP可能只对整数幂感兴趣。(我考虑的是一般情况，在这种情况下，大表格会影响缓存性能...) - Oliver Charlesworth
@OliCharlesworth：二次幂算法也是一个不错的选择。如果我错了，请纠正我！！！ - Rahul Tripathi
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
pow或等效库。 - paddy<<就不会出现。 - Mad Physicist