整数の整数の整数への対数

Question

整数の対数の上に丸められた値nを整数の基底bにしたいと思います。コード内：

result = int(ceil(log(n, b))) 

問題は、値が浮動小数点で正確に表現できず、結果を過大評価することがあります。例：

log(125, 5) == int(ceil(3.0000000000000004)) == 4 

これについてはどうすればよいですか？小さなイプシロンを引くことはそれを他の場所で過小評価することになる。 base 2を使用するときのように、浮動小数点計算を完全に一歩進める方法がありますか？

私は対数を見つけるためにループを使うことができましたが、一定の時間内にこれを行うことが可能かどうかは疑問でした。

Answer 1

まあ、あなたは一定の時間を意味するものに注意する必要があります。固定幅の整数を扱う場合、単純なforループが束縛されます（基底2の64ビット整数の最悪の場合は64回の乗算になります）。log関数に変換し、整数に切り捨てます。

任意精度の整数を使用している場合、floatへのキャストを含むほとんどすべての操作が少なくともO（log（n））以上であるため、基本的に定数時間アルゴリズムはありません。

• （私はPythonがこのような機能を提供していないと思いますが）あなたは2を底とする対数を見つけるためにfind first set操作を使用することができます。あなたが試すことができ、他の物事のカップルがある、と述べた

  。 x86では、この目的のためのbsr命令が提供されています。これはまた、任意の精度の整数に対する少数の演算のうちの1つで、これは一定時間である可能性があります（実装、メモリの格納などに依存します）。

• 基本2の対数をとったら、それを使って2のべき乗2を整数除算で計算できます。

• だけ同じベースBを使用している場合、および入力は、あなたが（Oだろうバイナリ検索と組み合わせるBの力、の事前に計算されたルックアップテーブル（ログを使用することができ、B ^Kで囲まれています任意の精度整数（検索の場合はlog（k）、各不等式比較の場合はlog（n））に対して、k（* k）* log（n）

• これが当てはまらない場合でも、ある種のバイナリ検索を試みることができます：大きすぎるまで二乗して指数を二倍にし続け、そこから二分探索します。

• オリジナルのアイデアと少しのエラー解析を組み合わせることで、いくつかのケースをすばやく計算し、不正確なものを後から取り除くことができます。 Pythonは2つの引数logのエラー境界を提供していません（しかし、あなたが提供する例は正確でなければならないのですばらしい）が、今日では最も適切な数学ライブラリは1つの引数logを1 ulpあなたの基底が浮動小数点として正確に表現可能であると仮定して（つまり、最後の場所で）、浮動小数点型にキャストして1/2 ulp以内に分割し、3 ulpsの合計相対誤差を与えます（これらはすべて乗法型です）。 1e30）。

Pythonでは、これは次のようになります整数次に精度が固定されている場合

import math, sys 
def clog(n,b): 
    a = math.log(n)/math.log(b) 
    r = round(a) 
    i = int(r) 
    if abs(a-r) <= a*3*sys.float_info.epsilon: 
     # slow 
     if n > b**i: 
      return i+1 
     else: 
      return i 
    else: 
     return int(math.ceil(a))