числовой — В любом случае быстрее, чем pow (), чтобы вычислить целую степень 10 в C ++?
Я знаю, что сила 2 может быть реализована с помощью << оператор.
Как насчет мощности 10? Как 10 ^ 5? Есть ли способ быстрее, чем pow (10,5) в C ++? Это довольно простое вычисление вручную. Но кажется, что для компьютеров это непросто из-за двоичного представления чисел … Допустим, меня интересуют только целочисленные степени, 10 ^ n, где n — целое число.
Решение
Что-то вроде этого:
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, когда я впервые попробовал это, таким образом я удалил это, когда я решил оптимизировать вариант петли)
Другие решения
Конечно, есть способы вычислить целые степени в 10 быстрее, чем при использовании std::pow()! Первая реализация заключается в том, что pow(x, n) может быть реализовано за O (log n). Следующее осознание того, что pow(x, 10) такой же как (x << 3) * (x << 1), Конечно, компилятор знает последнее, то есть, когда вы умножаете целое число на целочисленную константу 10, компилятор будет делать все, что умножит быстрее всего на 10. На основе этих двух правил легко создавать быстрые вычисления, даже если x большой целочисленный тип
В случае, если вы заинтересованы в таких играх:
- Общая версия мощности O (log n) обсуждается в Элементы программирования.
- Много интересных «трюков» с целыми числами обсуждаются в Восторг Хакера.
Решение для любой базы с использованием шаблонного метапрограммирования:
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;
}
Целочисленная степенная функция (не требующая преобразования и вычисления с плавающей запятой) вполне может быть быстрее, чем 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$
Вот удар в этом:
// 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, возникнут проблемы), и вам необходимо специализировать некоторые templates, чтобы указать, что тип экспоненты является как беззнаковым, так и целочисленным.
В этом случае целочисленный и беззнаковый означает, что он поддерживает &1 возврате bool а также >>1 возвращая что-то, из чего можно построить >>1s) достигает точки, где оценка его в bool возвращение контекста false, Я использовал классы черт, чтобы выразить ограничение, потому что наивное использование таким значением, как -1 будет компилироваться и (на некоторых платформах) зацикливаться вечно, в то время как (на других) не будет.
Время выполнения для этого алгоритма, при условии, что умножение равно O (1), равно O (lg (экспонента)), где lg (экспонента) — это количество раз, которое требуется для <<1 exponent прежде чем он оценивается как false в boolВ любом контексте. Для традиционных целочисленных типов это будет двоичный журнал exponentзначение s: так не более 32.
Я также исключил все ветви в цикле (или сделал для существующих компиляторов очевидным, что ветвь не нужна, точнее), только с управляющей ветвью (которая верна единообразно, пока не станет ложной один раз). Возможно, устранение даже этой ветви могло бы стоить высоких баз и низких показателей …
Вы можете использовать справочную таблицу, которая будет самой быстрой
Вы также можете рассмотреть возможность использования этот: —
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;
}
Нет умножения и нет версии таблицы:
//Nx10^n
int Npow10(int N, int n){
N <<= n;
while(n--) N += N << 2;
return N;
}
Эта функция будет вычислять 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;
}