与えられた数よりも小さい10の最大の累乗を見つけるための迅速な方法はありますか？
現在、このアルゴリズムを使用していますが、それを見ると、自分の中の何かが死んでしまいます。
10**( int( math.log10(x) ) ) # python
pow( 10, (int) log10(x) ) // C
それぞれ1つのループで問題の単純な関数を実装できますlog10がpow、それでも10進数に少し魔法があるのではないかと思います。
8617 次
8 に答える
7
別のアルゴリズムは次のとおりです。
i = 1;
while((i * 10) < x)
i *= 10;
于 2010-12-22T21:11:59.900 に答える
6
ログと電力はコストのかかる操作です。高速にしたい場合は、テーブルでIEEEバイナリ指数を調べておよそ10の累乗を取得し、仮数が+1で変更を強制するかどうかを確認することをお勧めします。これは、3つまたは4つの整数のマシン命令（または、かなり小さい定数を持つO（1））である必要があります。
与えられたテーブル：
int IEEE_exponent_to_power_of_ten[2048]; // needs to be 2*max(IEEE_exponent)
double next_power_of_ten[600]; // needs to be 2*log10(pow(2,1024)]
// you can compute these tables offline if needed
for (p=-1023;p>1023;p++) // bounds are rough, see actual IEEE exponent ranges
{ IEEE_exponent_to_power_of_ten[p+1024]=log10(pow(2,p)); // you might have to worry about roundoff errors here
next_power_of_ten[log10(pow(2,p))+1024]=pow(10,IEEE_exponent_to_power_of_ten[p+1024]);
}
その場合、計算は次のようになります。
power_of_ten=IEEE_exponent_to_power_of_10[IEEE_Exponent(x)+1023];
if (x>=next_power_of_ten[power_of_ten]) power_of_ten++;
answer=next_power_of_ten[power_of_ten];
[最後のすべてのクロックを絞り出すために、これをアセンブラとして実際に記述する必要があるかもしれません。][このコードはテストされていません。]
ただし、Pythonでこれを行うことを主張する場合、インタープリターのオーバーヘッドがlog / exp時間を浪費する可能性があり、それは問題ではない可能性があります。
それで、あなたは速くしたいですか、それとも短く書きたいですか？
編集12/23：OPは、彼の「x」が整数であることを示しています。それが64（または32）ビット整数であるという仮定の下で、私の提案はまだ機能しますが、明らかに「IEEE_Exponent」はありません。ほとんどのプロセッサには、値の左側（最上位）部分の0ビット数（先行ゼロなど）を通知する「findfirstone」命令があります。おそらくこれは、本質的に64（または32）から値の2の累乗を引いたものです。指数=64-leadingzerosが与えられた場合、2の指数の累乗があり、残りのアルゴリズムのほとんどは基本的に変更されません（変更はリーダーに残されます）。
プロセッサにfind-first-one命令がない場合、おそらく最善の策は、10の累乗を決定するためのバランスの取れた識別ツリーです。64ビットの場合、このようなツリーは、指数（10 ^ 18 ~~ 2 ^ 64）を決定するために最大18回の比較を行います。
于 2010-12-22T21:09:41.550 に答える
4
10の累乗の配列を作成します。xよりも小さい最大値を検索します。
xがかなり小さい場合、一部には分岐の誤予測が少ないため、線形検索の方が二分探索よりもパフォーマンスが優れていることがわかります。
于 2010-12-23T13:11:47.180 に答える
3
私の知る限り、漸近的に最速の方法は、二乗を繰り返すことです。
func LogFloor(int value, int base) as int
//iterates values of the form (value: base^(2^i), power: 2^i)
val superPowers = iterator
var p = 1
var c = base
while c <= value
yield (c, p)
c *= c
p += p
endwhile
enditerator
//binary search for the correct power
var p = 0
var c = 1
for val ci, pi in superPowers.Reverse()
if c*ci <= value
c *= ci
p += pi
endif
endfor
return p
アルゴリズムは、Nの対数時間と空間を取ります。これは、Nの表現サイズに線形です。[楽観的に単純化したので、時間制限はおそらく少し悪いです]
単純なtimes-10-until-overアルゴリズムは、32ビット整数だけを処理する場合はおそらく十分に高速であるため、任意の大きさの整数を想定していることに注意してください（オーバーフローに注意してください！）。
于 2010-12-22T21:55:18.790 に答える
1
最速の方法はO（log（log（n））^ 2）だと思いますが、whileループはO（log（log（n））を取り、有限時間で再帰的に呼び出すことができます（O（c）と言うことができます。は一定です）、最初の再帰呼び出しはlog（log（sqrt（n）））を取り、2番目は..を取り、sqrt（sqrt（sqrt ....（n））<10のsqrtの数はlog（log（ n））マシンの制限により、一定です。
static long findPow10(long n)
{
if (n == 0)
return 0;
long i = 10;
long prevI = 10;
int count = 1;
while (i < n)
{
prevI = i;
i *= i;
count*=2;
}
if (i == n)
return count;
return count / 2 + findPow10(n / prevI);
}
于 2010-12-23T10:32:55.793 に答える
1
Pythonの場合：
10 **（len（str（int（x）））-1）
于 2016-06-22T16:25:01.110 に答える
0
これが言語に依存しないことを考えると、この数値が重要である2の累乗を取得できる場合、たとえばx * 2 ^ yのy（これは数値の格納方法ですが、私が見たことがあるかどうかはわかりませんが私が使用した任意の言語でyにアクセスする簡単な方法）
z = int(y/(ln(10)/ln(2)))
（1つの浮動小数点除算）
10 ^zまたは10^（z + 1）があなたの答えになりますが、10 ^ zはまだそれほど単純ではありません（修正を求められます）。
于 2010-12-22T22:48:58.623 に答える
0
a値が型であるために、C ++で次のバリエーションを使用してメソッドのタイミングを調整しましたsize_t（インライン化によりパフォーマンスは向上しますが、相対的な順序は変わりません）。
試してみてください1：数が見つかるまで乗算します。
size_t try1( size_t a )
{
size_t scalar = 1ul;
while( scalar * 10 < a ) scalar *= 10;
return scalar;
}
2：Multiway ifを試してください（ルックアップテーブルを使用してプログラムすることもできます）。
size_t try2( size_t a )
{
return ( a < 10ul ? 1ul :
( a < 100ul ? 10ul :
( a < 1000ul ? 100ul :
( a < 10000ul ? 1000ul :
( a < 100000ul ? 10000ul :
( a < 1000000ul ? 100000ul :
( a < 10000000ul ? 1000000ul :
( a < 100000000ul ? 10000000ul :
( a < 1000000000ul ? 100000000ul :
( a < 10000000000ul ? 1000000000ul :
( a < 100000000000ul ? 10000000000ul :
( a < 1000000000000ul ? 100000000000ul :
( a < 10000000000000ul ? 1000000000000ul :
( a < 100000000000000ul ? 10000000000000ul :
( a < 1000000000000000ul ? 100000000000000ul :
( a < 10000000000000000ul ? 1000000000000000ul :
( a < 100000000000000000ul ? 10000000000000000ul :
( a < 1000000000000000000ul ? 100000000000000000ul :
( a < 10000000000000000000ul ? 1000000000000000000ul :
10000000000000000000ul )))))))))))))))))));
}
試行3：@Saaed AmiriのfindPow10から変更されました。これは、2乗を使用して、試行1よりも非常に大きなパワーをより迅速に検出します。
size_t try3( size_t a )
{
if (a == 0)
return 0;
size_t i, j = 1;
size_t prev = 1;
while( j != 100 )
{
i = prev;
j = 10;
while (i <= a)
{
prev = i;
i *= j;
j *= j;
}
}
return prev;
}
試行4：@Ira Baxterに従って、先行ゼロのカウント命令を使用してインデックス付けされたルックアップテーブル。
static const std::array<size_t,64> ltable2{
1ul, 1ul, 1ul, 1ul, 1ul, 10ul, 10ul, 10ul,
100ul, 100ul, 100ul, 1000ul, 1000ul, 1000ul,
1000ul, 10000ul, 10000ul, 10000ul, 100000ul,
100000ul, 100000ul, 1000000ul, 1000000ul,
1000000ul, 1000000ul, 10000000ul, 10000000ul,
10000000ul, 100000000ul, 100000000ul,
100000000ul, 1000000000ul, 1000000000ul,
1000000000ul, 1000000000ul, 10000000000ul,
10000000000ul, 10000000000ul, 100000000000ul,
100000000000ul, 100000000000ul, 1000000000000ul,
1000000000000ul, 1000000000000ul, 1000000000000ul,
10000000000000ul, 10000000000000ul, 10000000000000ul,
100000000000000ul, 100000000000000ul, 100000000000000ul,
1000000000000000ul, 1000000000000000ul, 1000000000000000ul,
1000000000000000ul, 10000000000000000ul, 10000000000000000ul,
10000000000000000ul, 100000000000000000ul, 100000000000000000ul,
100000000000000000ul, 100000000000000000ul, 1000000000000000000ul,
1000000000000000000ul };
size_t try4( size_t a )
{
if( a == 0 ) return 0;
size_t scalar = ltable2[ 64 - __builtin_clzl(a) ];
return (scalar * 10 > a ? scalar : scalar * 10 );
}
タイミングは次のとおりです（gcc 4.8）
for( size_t i = 0; i != 1000000000; ++i) try1(i) 6.6
for( size_t i = 0; i != 1000000000; ++i) try2(i) 0.3
for( size_t i = 0; i != 1000000000; ++i) try3(i) 6.5
for( size_t i = 0; i != 1000000000; ++i) try4(i) 0.3
for( size_t i = 0; i != 1000000000; ++i) pow(10,size_t(log10((double)i)))
98.1
ルックアップ/マルチウェイ-ifはC++のすべてを打ち負かしますが、整数が有限サイズであることを知っている必要があります。ビートの数が多い場合、ループ終了値の値が小さい場合は、このテストtry3よりも遅くなります。Pythonでは、整数が制限されていないため、物事が難しくなります。そのため、と組み合わせて、固定された制限までの数値をすばやく処理し、場合によっては非常に大きな数値を処理します。try1try3try1try2try3
Pythonでは、リスト内包表記を使用したルックアップは、多方向の場合よりもおそらく高速だと思います。
# where we previously define lookuptable = ( 1, 10, 100, ..... )
scalar = [i for i in lookuptable if i < a][-1]
于 2017-08-20T16:33:23.157 に答える