4

我在 python 中处理数万位数的数字。long 类型在对这些数字执行数学运算时效果很好，但是我无法以足够快的方式访问这些数字的最高位。请注意，我不确切知道该数字包含多少位数。“最高位”是指最高位的数字，最低位可以使用模数快速访问。

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

从这里的描述看来，long 类型实际上确实包含一个 bignum 数组。有什么方法可以访问存储 long 的底层数据结构，或者可能检查 long 从基本类型中有多少位？

如果人们有兴趣，我可以提供一个带有基准的示例。

4

3 回答 3

7

一种简单的方法，无需深入研究 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
于 2012-11-25T01:16:24.710 回答
3

Python 2.7 有bit_length()整数方法。

于 2012-11-25T01:19:00.790 回答
1

这是一个非常丑陋的衬线，它将提取前几位小数：

(x >> (x.bit_length()-50))*(10**(math.fmod((x.bit_length()-50)*math.log(2)/math.log(10), 1)))

如果您的 x 值约为 10,000 位十进制数字，您应该得到一个精确到 12 位左右的答案。随着 x 变大，您的准确性会降低。

如果您愿意使用外部模块，我会看gmpy2。gmpy2 库提供对多精度整数和小数运算的 GMP（或 MPIR）库、多精度浮点运算的 MPFR 库和多精度复数运算的 MPC 库的访问。gmpy2 整数比 Python 的原生 long 更快，您可以将 long 整数转换为浮点数以仅提取前导数字。上面的一个衬里就变成了：

gmpy2.mpfr(x).digits()[0]

即使数字变大，gmpy2 方法也会保持准确性。

免责声明：我维护 gmpy2。

于 2012-11-25T02:44:00.933 回答