Я знаю, что мощность 2 может быть реализована с использованием < оператор. Как насчет мощности 10? Как 10 ^ 5? Есть ли способ быстрее, чем pow (10,5) в С++? Это довольно прямолинейное вычисление вручную. Но, кажется, не так просто для компьютеров из-за двоичного представления чисел... Предположим, меня интересуют только целые степени, 10 ^ n, где n - целое число.
В любом случае быстрее, чем pow(), чтобы вычислить целую мощность 10 в С++?
Ответ 1
Примерно так:
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 с, когда я впервые попробовал, поэтому я удалил его, когда решил оптимизировать вариант с циклом)
Ответ 2
Конечно, есть способы вычислить целые степени в 10 быстрее, чем использовать std::pow()! Первая реализация заключается в том, что pow(x, n) может быть реализовано за O (log n) времени. Следующее понимание состоит в том, что pow(x, 10) совпадает с (x << 3) * (x << 1). Конечно, компилятор знает последнее, то есть, когда вы умножаете целое число на целочисленную константу 10, компилятор будет делать все, что умножит быстрее всего на 10. На основе этих двух правил легко создавать быстрые вычисления, даже если x - это большой целочисленный тип.
Если вас интересуют такие игры, как эта:
- Типовая версия O (log n) обсуждается в Элементы программирования.
- Множество интересных "трюков" с целыми числами обсуждается в Hacker Delight.
Ответ 3
Решение для любой базы с использованием метапрограмм шаблонов:
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;
}
Ответ 4
Функция целочисленной мощности (которая не включает преобразования и вычисления с плавающей запятой) может быть намного быстрее, чем 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$
Ответ 5
Вот удар по нему:
// 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 может быть неявно преобразован в него (если оба они истинны, проблемы будут возникать), и вам нужно чтобы специализировать некоторый template, чтобы указать, что задействованный тип экспоненты является как неподписанным, так и целочисленным.
В этом случае целочисленный и unsigned означает, что он поддерживает &1 возвращает bool и >>1 возвращает то, с чего он может быть построен, и в конечном итоге (после повторения >>1 s) достигает точки, где его оценивают в контексте bool возвращает false. Я использовал классы признаков, чтобы выразить ограничение, потому что наивное использование значением, подобным -1, скомпилировалось бы и (на некоторых платформах) навсегда, тогда как (на других) не было бы.
Время выполнения для этого алгоритма, предполагая, что умножение равно O (1), равно O (lg (показатель степени)), где lg (показатель степени) - это количество раз, которое требуется для <<1 exponent, прежде чем оно будет оцениваться как false в контексте bool ean. Для традиционных целых типов это будет двоичный журнал значения exponent: поэтому не более 32.
Я также удалил все ветки в цикле (или сделал очевидным для существующих компиляторов, что не требуется ветки, точнее), только с ветвью управления (которая равномерно равномерно до тех пор, пока она не станет ложной). Вероятно, устранение даже этой ветки могло бы стоить того, что было бы на высоких основаниях и низких показателях...
Ответ 6
Вы можете использовать таблицу поиска, которая будет на сегодняшний день самой быстрой
Вы также можете использовать 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;
}
Ответ 7
Нет умножения и нет версии таблицы:
//Nx10^n
int Npow10(int N, int n){
N <<= n;
while(n--) N += N << 2;
return N;
}
Ответ 8
Эта функция будет вычислять 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;
}
Ответ 9
Основываясь на матах 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 для лучшей читаемости, но тесты, выполненные с ними в коде.
Скомпилированный с gcc версии 4.6.3 (Ubuntu/Linaro 4.6.3-1ubuntu5), используя -Wall -O2 -std = С++ 0x, дает следующие результаты:
$ 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
Ответ 10
Теперь, с 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 будет рассчитан во время компиляции. ASM, сгенерированный для x86-64 gcc 9.2:
main:
push rbp
mov rbp, rsp
mov DWORD PTR [rbp-4], 100000
mov eax, 0
pop rbp
ret