Powers of 10

Question

的表查找我正在研究計算速度極其重要的C++項目。任何時候我都可以削減，應該削減。可執行文件的最終大小和內存使用量不是，因爲很重要。

這就是說，創建一個10的冪的預先計算的查找表是否有好處？舉例來說，如果我有這樣的簡化功能：

double powTen(int exponent) { 
    return pow(10, exponent); 
} 

難道有性能上的（小）增加，如果我取代了pow()用查表？它甚至值得嗎？看起來好像pow()函數必須相當複雜。另外，GCC對此有特殊的優化嗎？

Answer 1

表查找幾乎總是很好的表現。所以假設你已經認識到這是一個瓶頸，我會花時間來實現一個生成表的模板。不過，要衡量一下。性能是現代計算機上的一種奇怪的野獸。它可以走向一個永遠不會相信的方向。

我預計編譯時間表生成的時間確實很短。但事實證明，至少在舊版本2中，Visual C++ 2015並不滿意，因爲一個類中的constexpr std::array。然而，最後，一個原始數組工作。

代碼，使用MinGW克++ 6.3.0和Visual C++ 2015更新2編譯：

#include <stddef.h>  // size_t, ptrdiff_t 
#include <utility>  // std::(make_index_sequence,) 

namespace my { 
    using std::make_index_sequence; 
    using std::index_sequence; 

    using Size = ptrdiff_t; 

    template< Size n, class Item > 
    using raw_array_of_ = Item[n]; 

    template< class Item, size_t n > 
    constexpr 
    auto n_items_of(raw_array_of_<n, Item>&) 
     -> Size 
    { return n; } 

    namespace impl { 
     constexpr 
     auto compile_time_pow_of_10(int const n) 
      -> double 
     { return (n == 0? 1.0 : 10.0*compile_time_pow_of_10(n - 1)); } 

     template< size_t... indices > 
     struct Powers_of_10_ 
     { 
      static constexpr size_t      n  = sizeof...(indices); 
      static constexpr raw_array_of_<n, double> table = 
      { 
       compile_time_pow_of_10(indices)... 
      }; 

      constexpr 
      Powers_of_10_() {} 
     }; 

     template< size_t... indices > 
     constexpr 
     raw_array_of_<Powers_of_10_<indices...>::n, double> 
      Powers_of_10_<indices...>::table; 

     template< size_t... indices, int n = sizeof...(indices) > 
     constexpr 
     auto power_of_10_table_helper(index_sequence<indices...>) 
      -> const raw_array_of_<n, double>& 
     { return Powers_of_10_<indices...>::table; } 
    } // namespace impl 

    template< int n > 
    constexpr 
    auto power_of_10_table() 
     -> const raw_array_of_<n, double>& 
    { return impl::power_of_10_table_helper(make_index_sequence<n>()); } 

} // namespace my 

#include <iostream> 
using namespace std; 
auto main() 
    -> int 
{ 
    int const n = 7; 
    constexpr auto& pow_10 = my::power_of_10_table<n>(); 

    cout << n << " powers of 10:\n"; 
    cout << fixed; cout.precision(0); 
    for(int i = 0; i < n; ++i) 
    { 
     cout << pow_10[i] << "\n"; 
    } 
} 

---

模板代碼可能難以端口。即：Visual C++ 2015在上面的代碼中拒絕接受std::array，因此需要重寫才能使用原始數組。由於通常過於冗長和神祕的編譯診斷，因此也難以維護。

甲相當快的積分功率函數可以通過表達功率作爲形式X^{（2 Ñ）}的冪的乘積來定義。例如，X = X ⋅X ⋅X ，和X，即2,8這些更基本的權力，和32可以，通過重複平方計算x。這將指數中的線性乘法的次數減少到指數中的對數。

代碼：

#include <stddef.h>  // size_t, ptrdiff_t 

namespace my { 
    using Size = ptrdiff_t; 

    template< Size n, class Item > 
    using raw_array_of_ = Item[n]; 

    namespace impl { 
     auto positive_integral_power_of(const double x, const int n) 
     { 
      double result = 1.0; 
      double power = x; 
      for(unsigned exp = n; ;) 
      { 
       if((exp & 1) != 0) 
       { 
        result *= power; 
       } 
       exp >>= 1; 
       if(exp == 0) 
       { 
        break; 
       } 
       power *= power; 
      } 
      return result; 
     } 
    } // namespace impl 

    auto integral_power_of(const double x, const int n) 
     -> double 
    { 
     return 
      n > 0? 
       impl::positive_integral_power_of(x, n) : 
      n < 0? 
       1.0/impl::positive_integral_power_of(x, -n) : 
      1.0; 
    } 
} // namespace my 

#include <iostream> 
using namespace std; 
auto main() 
    -> int 
{ 
    int const n = 7; 
    cout << n << " powers of 10:\n"; 
    cout << fixed; cout.precision(0); 
    for(int i = 0; i < n; ++i) 
    { 
     cout << my::integral_power_of(10, i) << "\n"; 
    } 
} 

Answer 2

你這麼稱呼這個功能嗎？如果是這樣，預期值的預先計算會更好。

你也可以使用部分建立的表格，並建立使用，即。第一次10^5叫做計算它，然後保存在表中，所以下次它將從表中獲得。

使用表總是比調用一個函數更好，但事情是它必須首先，通過多次調用，或多次發送相同的參數，以便您不要最終調用函數大的時間，然後根本不使用，這將破壞你的第一個最小的優化的意圖。

Answer 3

你可以做的功能多一點點高效利用的循環：

double powerTen(int exponent) 
{ 
    double result = 1.0; 
    for (int i = 0; i < exponent; ++i) 
    { 
    result = result * 10.0; 
    } 
    return result; 
} 

循環的一個好處是，你要刪除的函數調用開銷pow功能。 IMO沒有多少節省。

另一種方法是查表：

double powerTen(int exponent) 
{ 
    static const double values[] = {1.0, 10.0, 100.0, 1000.0}; 
    return values[exponent]; 
} 

您的交易存儲空間，執行時間。
此外，您可能想要添加一些數組溢出檢查以及處理負指數。