對數整數整數

Question

的基礎，我想找到整數n的對數的向上舍入的值，以整數基本b。代碼：

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

問題是，有時值不能完全代表浮點數，高估結果。例如：

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

我該怎麼辦？減去微小的epsilon會低估其他地方。有沒有一種方法可以完全的側步浮點計算，有點像使用base 2？

我可以用一個循環來找到對數，但我不知道是否有可能做到這一點在一定的時間。

Answer 1

好了，你必須通過你的意思是恆定的時候什麼小心。如果你正在處理固定寬度的整數，那麼一個簡單的for循環是有界的（對於基數爲2的64位整數，最壞的情況將是64次乘法），並且可能仍然比鑄造成浮點數更快，稱爲log函數，並截斷回到一個整數。

如果您使用的是任意精度整數，那麼基本上不存在常量算法，因爲幾乎每個操作都至少爲O（log（n）），包括將其轉換爲浮點數。

這就是說，有一對夫婦的其他東西，你可以嘗試：

• 可以使用find first set操作找到2爲底的對數（雖然我不認爲Python提供這樣的功能） 。 x86爲此提供了bsr指令。這也是針對任意精度整數的少數操作之一，它可以是恆定的時間（儘管這取決於實現，內存存儲等）。

• 一旦你有一個基本2對數，你可以用它整數除法計算到任何電力的-2。

• 如果你只使用相同的基極b，和輸入由D ^ķ界，你可以使用的b相二進制搜索相結合的權力，這會爲O的預先計算的查找表（日誌（ k）* log（n））爲任意精度整數（log（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))