<< 演算子を使用して 2 のべき乗を実装できることを知っています。10の累乗はどうですか？10^5のように？C++ で pow(10,5) よりも速い方法はありますか? これは、手による非常に単純な計算です。しかし、数値が 2 進数で表現されているため、コンピューターにとっては簡単ではないようです... n が整数である 10^n の整数乗のみに関心があると仮定しましょう。
47308 次
12 に答える
35
このようなもの：
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もありましたが、最初に試したときは 1 分 22.56 秒かかったので、ループ バリアントを最適化することにしたときに削除しました)
于 2013-09-02T22:42:37.567 に答える
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;
}
于 2013-09-03T15:30:10.163 に答える
6
整数べき乗関数 (浮動小数点の変換と計算を含まない) は、 よりもはるかに高速である可能性がありますpow()。
int integer_pow(int x, int n)
{
int r = 1;
while (n--)
r *= x;
return r;
}
編集:ベンチマーク - 単純な整数累乗法は、浮動小数点法よりも約 2 倍優れているようです。
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$
于 2013-09-02T22:29:52.377 に答える
2
ここに刺し傷があります：
// 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 サポートが安いので、それを化しtemplateます。そのままで、 をサポートする任意の基本型をサポートし*= own_type、 に暗黙的に変換するかint、暗黙的に変換intすることができます (両方が true の場合、問題が発生します)。template指数が関連する型は、符号なしと整数型の両方です。
この場合、整数のような符号なしとは、それを構築できるものを&1返すことをサポートし、最終的に ( を繰り返した後)コンテキストでそれを評価すると が返されるポイントに到達することを意味します。特性クラスを使用して制限を表現しました。これは、のような値による単純な使用はコンパイルされ、(一部のプラットフォームでは) 永遠にループし、(他のプラットフォームでは) ループしないためです。bool>>1>>1boolfalse-1
このアルゴリズムの実行時間は、乗算が O(1) であると仮定すると、O(lg(exponent)) になります。ここで、lg(exponent) は、ean コンテキストで評価されるまで<<1にかかる回数です。従来の整数型の場合、これはs 値のバイナリ ログになるため、32 以下になります。exponentfalseboolexponent
また、ループ内のすべての分岐を排除し (または、より正確には分岐が不要であることを既存のコンパイラーに明らかにしました)、制御分岐のみを使用しました (これは、一度 false になるまで一様に true です)。おそらく、そのブランチでさえ排除することは、高いベースと低い指数にとって価値があるかもしれません...
于 2013-09-02T23:27:13.627 に答える
1
はるかに高速なルックアップテーブルを使用できます
これを使用することも検討できます:-
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;
}
于 2013-09-02T22:29:37.337 に答える
0
Mats Peterssonのアプローチに基づいていますが、コンパイル時にキャッシュを生成します。
#include <iostream>
#include <limits>
#include <array>
// digits
template <typename T>
constexpr T digits(T number) {
return number == 0 ? 0
: 1 + digits<T>(number / 10);
}
// pow
// https://stackoverflow.com/questions/24656212/why-does-gcc-complain-error-type-intt-of-template-argument-0-depends-on-a
// unfortunatly we can't write `template <typename T, T N>` because of partial specialization `PowerOfTen<T, 1>`
template <typename T, uintmax_t N>
struct PowerOfTen {
enum { value = 10 * PowerOfTen<T, N - 1>::value };
};
template <typename T>
struct PowerOfTen<T, 1> {
enum { value = 1 };
};
// sequence
template<typename T, T...>
struct pow10_sequence { };
template<typename T, T From, T N, T... Is>
struct make_pow10_sequence_from
: make_pow10_sequence_from<T, From, N - 1, N - 1, Is...> {
//
};
template<typename T, T From, T... Is>
struct make_pow10_sequence_from<T, From, From, Is...>
: pow10_sequence<T, Is...> {
//
};
// base10list
template <typename T, T N, T... Is>
constexpr std::array<T, N> base10list(pow10_sequence<T, Is...>) {
return {{ PowerOfTen<T, Is>::value... }};
}
template <typename T, T N>
constexpr std::array<T, N> base10list() {
return base10list<T, N>(make_pow10_sequence_from<T, 1, N+1>());
}
template <typename T>
constexpr std::array<T, digits(std::numeric_limits<T>::max())> base10list() {
return base10list<T, digits(std::numeric_limits<T>::max())>();
};
// main pow function
template <typename T>
static T template_quick_pow10(T n) {
static auto values = base10list<T>();
return values[n];
}
// client code
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] == 't') {
for(long i = 0; i < outer_loops / n; i++) {
for(int j = 1; j < n+1; j++) {
sum += template_quick_pow10(n);
}
}
}
std::cout << "sum=" << sum << std::endl;
return 0;
}
コードには、読みやすくするために quick_pow10、integer_pow、opt_int_pow は含まれていませんが、コード内でそれらを使用してテストが行われています。
-Wall -O2 -std=c++0x を使用して、gcc バージョン 4.6.3 (Ubuntu/Linaro 4.6.3-1ubuntu5) でコンパイルすると、次の結果が得られます。
$ g++ -Wall -O2 -std=c++0x main.cpp
$ time ./a.out 8 a
sum=100000000000000000
real 0m0.438s
user 0m0.432s
sys 0m0.008s
$ time ./a.out 8 b
sum=100000000000000000
real 0m8.783s
user 0m8.777s
sys 0m0.004s
$ time ./a.out 8 c
sum=100000000000000000
real 0m6.708s
user 0m6.700s
sys 0m0.004s
$ time ./a.out 8 t
sum=100000000000000000
real 0m0.439s
user 0m0.436s
sys 0m0.000s
于 2016-12-21T16:18:50.113 に答える