从十进制中快速查找大正整数位长度的方法

Question

给定一个大正整数的十进制字符串表示形式，如何快速找到该整数的位长度?先用int()，再用bit_length()，速度很慢。这个100万数字的例子花了5秒钟告诉我它有3321926位:

s = '1234567890' * 10**5
print(int(s).bit_length())

结果应该是精确的，至少对于内存中可以存储的所有字符串(所以我们说多达1000亿个十进制数字)。

Answer 1

如果存储空间不是问题，并且您不介意预先花费时间(并且您宁愿有一个不依赖于浮点精度的解决方案，即使它在其他方面不切实际)，您可以使用更多内存来解决几乎任何速度问题。建立2**n的字符串表示的查找表。建立一个字典，将字符串长度键设为(该长度的字符串，对应n个值)对的列表。要测试一个输入，请查找适当的列表，然后使用普通的字符串比较来确定它属于哪个位长度类别。

Answer 2

这应该是准确的数十亿数字，我认为。计算100000的确切结果…00000的简单位数，然后加上前10位的对数。

import math
s = '1234567890' * 10**5
dper = math.log(10)/math.log(2)
base= (len(s)-10)*dper
extra = math.log(int(s[:10]))/math.log(2)
print(int(base+extra+0.99))

Answer 3

这个示例大约需要0.15秒，'1234567890' * 10**6大约需要2秒，'1234567890' * 10**7大约需要20秒。首先，我用对数近似比特长度(类似于蒂姆的方法)，然后我使用decimal.Decimal进行调整，直到精确。该类使用10进制，因此不需要进行代价高昂的进制转换。

位长b覆盖区间[2**(b-1)， 2**b)。所以我们要求(指数)2的最小次幂大于这个数

上网试试!

from time import time
from math import log2
from decimal import *
setcontext(Context(prec=MAX_PREC, Emax=MAX_EMAX, Emin=MIN_EMIN))
def bit_length(s):
if len(s) <= 20:
return int(s).bit_length()
head_bits = log2(int(s[:20]))
tail_bits = (len(s) - 20) * log2(10)
b = int(head_bits + tail_bits)
n = Decimal(s)
power = Decimal(2) ** b
while power > n:
b -= 1
power //= 2
while power <= n:
b += 1
power *= 2
return b
s = '1234567890' * 10**5
start = time()
print(bit_length(s))
print(time() - start, 'seconds')