从Python访问大数字的最高位数

Question

我正在使用python中数万个数字的数字.long类型在对这些数字进行数学运算时效果很好,但是我无法以足够快的速度访问这些数字的最高位数.请注意,我不确切知道该数字包含多少位数."最高位"是指最重要位置的数字,可以使用模数快速访问最低位.

我可以想到在python中访问这些数字的两种方法,但它们对我的目的来说都太慢了.我已尝试转换为字符串并通过数组方法访问数字,但是当您有10,000+位数时类型转换很慢.或者,我可以简单地屏蔽掉比特并截断,但这需要我知道长度中有多少位数.找到long中的位数需要在计数器上进行循环和掩码测试,这肯定会比字符串转换慢.

从这里的描述看来,long类型确实包含一个bignum数组.有什么方法可以访问存储long的基础数据结构,或者可能检查long与基类型有多少位数？

如果人们感兴趣,我可以提供一个基准测试的例子.

Answer 1

一种简单的方法,无需挖掘long类型的低级实现:

>>> n = 17**987273 # 1.2 million digits number

>>> digits = int(math.log10(n))

>>> k = digits - 24 # i.e. first 24 digits

>>> n / (10 ** k)
9953043281569299242668853L

在我的机器上运行速度非常快.我试图得到这个数字的字符串表示,这需要很长的时间.

对于Python 3.x,请使用 n // (10 ** k)

这个大数字的一些时间(它快140倍):

%timeit s = str(n)[:24]
1 loops, best of 3: 57.7 s per loop

%timeit n/10**(int(math.log10(n))-24)
1 loops, best of 3: 412 ms per loop


# With a 200K digits number (51x faster)

%timeit s = str(n)[:24]
1 loops, best of 3: 532 ms per loop

%timeit n/10**(int(math.log10(n))-24)
100 loops, best of 3: 10.4 ms per loop


# With a 20K digits number (19x faster)

%timeit s = str(n)[:24]
100 loops, best of 3: 5.4 ms per loop

%timeit n/10**(int(math.log10(n))-24)
1000 loops, best of 3: 272 us per loop