Soru C ++ 'da 10'luk bir tamsayı gücü hesaplamak için pow ()' den daha hızlı mı?


Ben 2'nin gücü << operatör kullanılarak uygulanabileceğini biliyorum. 10'un gücü ne olacak? 10 ^ 5 gibi mi? C ++ 'da pow'ten (10,5) daha hızlı bir yol var mı? Elle oldukça basit bir hesaplamadır. Ama sayıların ikili temsili nedeniyle bilgisayarlar için kolay değil gibi görünüyor ... Sadece tamsayı güçleri ile ilgilendiğimi varsayalım, 10 ^ n, n bir tamsayıdır.


25
2017-09-02 22:27


Menşei


Bir arama tablosu kullanın? - Mehrdad
Olabilir 1 <<<<< 5? - Kerrek SB
Bir arama tablosu yalnızca tamsayı değerlerini veya bir tam sayıya ölçeklendirilebilen ondalık değerlerin gücünü artırıyorsanız kullanışlıdır. Eğer keyfi bir şamandıra olabilirseniz pow veya eşdeğer bir kütüphane. - paddy
Bir tarafta her zaman 10 ve diğer tarafta bir tam sayı ise, kendi tablonuzu yazabilir ve onunla yapılabilir. Bundan daha hızlı olamaz - kelimenin tam anlamıyla bir bellek okundu ve tabloya indekslemek için bir veya iki basit işlem. - Mats Petersson


Cevaplar:


Böyle bir şey:

int quick_pow10(int n)
{
    static int pow10[10] = {
        1, 10, 100, 1000, 10000, 
        100000, 1000000, 10000000, 100000000, 1000000000
    };

    return pow10[n]; 
}

Açıkçası, aynı şeyi yapabilir long long.

Bu, herhangi bir rakip yöntemden birkaç kat daha hızlı olmalıdır. Bununla birlikte, çok fazla bazınız varsa (değerlerin sayısı daha büyük bazlarla oldukça dramatik bir şekilde azalsa da), oldukça sınırlıdır, dolayısıyla çok sayıda kombinasyon yoksa, yine de yapılabilir.

Karşılaştırma olarak:

#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;
}

Kullanılarak g ++ 4.6.3 ile derlendi -Wall -O2 -std=c++0x, aşağıdaki sonuçları verir:

$ 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

(Kullanmak için bir seçeneğim vardı pow Ayrıca, ilk denediğimde 1m22.56s aldı, bu yüzden optimize edilmiş döngü varyantına karar verdiğimde çıkardım.


24
2017-09-02 22:42



Kafe gazı ile karıştırılmamalıdır. - brian beuning
Verilerinizi bir döngü ile başlatabilirsiniz. Derleyici, çalışma zamanı öncesi değerleri hesaplayarak bunu optimize edebilir mi? - user3728501
@EdwardBird: Bu amaç için, static kesinlikle bir döngüden daha hızlıdır. Muhtemelen derleme zamanında ya da en az bir kez başlatıldığı için. Bir döngü her zaman başlayacaktır. - Mats Petersson
@MatsPetersson Derleme zamanında değerleri hesaplayan derleyici optimizasyonları hakkında son zamanlarda bir şeyler okudum ... Örneğin, eğer x = x * 10 * 5 bazı derleyiciler bunu değiştirecek x = x * 50. Bir derleyici, döngünün bazı değerleri başlattığını ve bu nedenle herhangi bir yürütülebilir programın gerekmediği şekilde derlerken bunları hesapladığını algılamaz mı? - user3728501
Güzel, en uygun cevap, ama bence gerçekten bir sınır kontrolü eklemelisiniz. n. - cmaster


10'dan daha güçlü integral güçleri hesaplamaktan daha kesin yollar vardır. std::pow()! İlk gerçekleşme şu ki pow(x, n) O (log n) zamanında uygulanabilir. Bir sonraki gerçekleşmesi pow(x, 10) aynıdır (x << 3) * (x << 1). Elbette, derleyici ikincisini bilir, yani, tamsayı sabiti 10 ile bir tamsayı çarptığınızda, derleyici 10 ile çarpmak için en hızlı olanı yapar. Bu iki kurala dayanarak, hızlı hesaplamalar oluşturmak bile kolaydır. x büyük bir tamsayı türüdür.

Böyle oyunlar ile ilgileniyorsanız:

  1. Gücün genel O (log n) sürümü tartışıldı Programlama Elemanları.
  2. İnteger ile ilginç "hileler" in bir sürü tartışılır Hacker's Delight.

11
2017-09-02 22:33



Muhtemelen büyük bir yazı tipi için. Bununla ilgili soru sanmıyorum, ama. Sabit boyutlu tam sayı türleri için, bir arama tablosu bunu bir O (1) işlemi yapar. (Düzenleme: Bu gerçekten adil değil. Sabit boyutlu tamsayı türleri için, n bir üst sınıra sahipse ve n bir üst sınıra sahipse, O (2 ^ n) gibi bir şey bile O (1) 'e eşittir.) Kayan nokta tipleri için, pow zaten normalde bir O (1) işlem olarak uygulanır. - hvd
@hvd O(1) kesinlikle daha hızlı değil O(n)olsa da.
@ H2CO3 Evet, haklısın. O (1), yeterince büyük n için O (n) 'den daha hızlı olacaktır, ancak n, 20'den fazla olamazsa çok fazla şey söylemez. - hvd
Evet, yazılım pow10 () değerini O (log n) olarak hesaplayabilir ardışık zaman, ama donanım doğal olarak paralel. Sıralı olarak şeyleri hesaplamak zorunda kalmaz (bunun gerçeği boşver) could istedikleri takdirde sıralı olarak yazılım gibi şeyler yapmak). Bu yüzden zaman karmaşıklığı noktası alakasız. Zaman karmaşıklığıyla ilgili cümlede elma ve portakalları karşılaştırıyorsun. - Mehrdad
@Mehrdad: Elbette, sabit boyutlu tamsayılar için bir paralel tabloya bile ihtiyacınız yoktur çünkü bir arama tablosu kullanabilirsiniz. Ancak, tamsayılarınızın boyutu sınırlandırılmadığında (toplam kullanılabilir belleğin boyutu dışında) donanımın kullanabileceği paralel algoritma, O'nun altına (log n) ulaşmanıza yardımcı olmaz. - Dietmar Kühl


Şablon meta-programlama kullanarak herhangi bir baz için bir çözüm:

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 };
};

Daha sonra çalışma zamanında kullanılabilecek bir arama tablosu oluşturmak için kullanılabilir:

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];
}

Bu olası taşmaları tespit etmek için doğru derleyici bayraklarıyla kullanılmalıdır.

Kullanım örneği:

for(unsigned int n = 0; n < 10; ++n) {
    std::cout << quick_pow<10>(n) << std::endl;
}

8
2017-09-03 15:30



@cmaster Tamam. Cevabımı geliştirmeye çalıştım ... Cevabımı hala faydalı veya yanlış değilse sileceğim. - Vincent


Bir tamsayı güç fonksiyonu (kayan noktalı dönüşümleri ve hesaplamaları içermez) çok daha hızlı olabilir pow():

int integer_pow(int x, int n)
{
    int r = 1;
    while (n--)
        r *= x;

    return r; 
}

Düzenle: kıyaslanmış - naif tamsayı üssülasyon yöntemi, kayan noktadan bir tanesini iki kat daha yüksek bir performansla daha iyi görmektedir:

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$ 

4
2017-09-02 22:29



@Mehrdad Birkaç yıl önce. Yakın zamanda değil. Kayan nokta donanımının (ve yazılımın) o zamandan beri ne gibi gelişmeler olduğunu kim bilir.
Tamsayı exponentiation yapmak için çok daha hızlı yollar vardır. Bakınız örn. Squaring ile üsleme veya Toplama zinciri üssüasyonu. - Ted Hopp
Sadece verme -1 olarak n. ;) - Mats Petersson
@ H2CO3: Şüphesiz ona biraz vermek ister misin? Ve sonuç neden farklı? - Mats Petersson
Bir sabit kullanmanın biraz haksızlık olduğunu düşünüyorum n döngüde de. - Mats Petersson


İşte bir bıçak:

// 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;
}

Yukarıda neler olup bittiği birkaç şey.

İlk olarak, BigNum desteği ucuzdur, templateize. Kutunun dışında, destekleyen herhangi bir taban tipini destekler *= own_type ve ya örtülü olarak dönüştürülebilir intveya int dolaylı olarak ona dönüştürülebilir (eğer her ikisi de doğruysa problemler ortaya çıkacaktır) ve templateBuradaki katsayı türünün hem imzasız hem de tamsayı olduğunu belirtmek için s.

Bu durumda, tamsayı ve imzasız, desteklediği anlamına gelir &1 dönen bool ve >>1 bir şeyden geri dönebilir ve sonuçta (tekrarlandıktan sonra yapılabilir >>1s) bunu değerlendiren bir noktaya ulaşır. bool içerik döndürür false. Kısıtlamayı ifade etmek için özellikler sınıfları kullandım çünkü naif kullanım gibi bir değer -1 (başka platformlarda) derleme yapar ve (bazı platformlarda) sonsuza dek, başkaları üzerinde olmazdı.

Bu algoritma için yürütme süresi, çarpımın O (1) olduğu varsayılırsa, O (lg (üs)), burada lg (üs), alacağı sürenin sayısıdır. <<1  exponent önce değerlendirir false içinde boolean bağlam. Geleneksel tamsayı türleri için, bu ikili girişin exponents değeri: 32'den fazla değil.

Döngü içerisindeki tüm dalları da elimden aldım (ya da herhangi bir dalın gerekmediğine, daha kesin olarak var olan derleyicilere açık bir şekilde yaptık), sadece kontrol dalı ile (ki bu bir kez yanlış olana kadar tekdüze). Muhtemelen bu branşın ortadan kaldırılması, yüksek üsler ve düşük üsler için buna değer olabilir.


2
2017-09-02 23:27



Burada şube tahmini için +1. - ZijingWu
Neden bu iğrenç şablonlarla kodunuzu gereksiz yere kirletiyorsunuz? Yaralıyor. Neredeyse seni bunun için reddettim ... - cmaster
@cmaster Çünkü bu kodu yapmak, bignum veya basit tamsayı olmayan diğer türleri kullanıyorsanız, genellikle mantıklıdır. Eğer tablonuz bir tamsayı> 1 ise, 64 bit ints kullanarak, naif "kendi kendini üstel süreleriyle çarpın", taşmadan önce 64'den daha fazla olmayan bir döngü olacaktır, bu da yukarıdaki kodumdan daha hızlı olacaktır. Yukarıdaki kod, kayan nokta, bignum, rasyonal veya başka bir şey olan temelleri işler: yukarıdaki kodların dışında, yukarıdaki kod koşmaya değmez. Tam sayı taban durumunda, olmayacak çok En kötü durumda daha yavaştır ve yaygın durumlarda daha hızlı olabilir. - Yakk - Adam Nevraumont


En hızlı olacak arama tablosunu kullanabilirsiniz.

Kullanmayı da düşünebilirsiniz bu: -

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;
}

1
2017-09-02 22:29



Peki, tablonun ne kadar büyük olduğuna bağlı. - Oliver Charlesworth
Evet kesinlikle!!!! - Rahul Tripathi
@OliCharlesworth: En fazla 20 giriş olmaz mı? log (2 ^ 64) <20 - Mehrdad
Ama bence iyi bir seçenek! - Rahul Tripathi
@Mehrdad: ah, evet, OP sadece tamsayı güçleriyle ilgilenebilir gibi görünüyor. (Büyük bir tablonun önbellek performansını bozacağı genel davayı düşünürdüm ...) - Oliver Charlesworth


Çarpım yok ve tablo sürümü yok:

//Nx10^n
int Npow10(int N, int n){
  N <<= n;
  while(n--) N += N << 2;
  return N;
}

1
2018-05-22 01:58