长期从Python访问大数的最高位数 [英] Accessing the highest digits of large numbers from Python long

问题描述

我正在使用python中具有数万个数字的数字.长型在对这些数字进行数学运算时表现出色，但是我无法以足够快的方式访问这些数字的最高位数.请注意，我不完全知道该数字包含多少位数. 最高位数"是指最高位的位数，可以使用模数快速访问最低位数.

I'm working with numbers with tens of thousands of digits in python. The long type works beautifully in performing math on these numbers, however I'm unable to access the highest digits of these numbers in a sufficiently fast way. Note that I don't know exactly how many digits the number contains. The "highest digits" refers to the digits in the most significant place, the lowest digits can be accessed quickly using modulus.

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

I can think of two ways to access these digits in python but they're both too slow for my purposes. I have tried converting to a string and accessing digits through array methods, however type conversions are slow when you have 10,000+ digits. Alternatively I could simply mask out bits and truncate, but this requires that I know how many digits are in the long. Finding the number of digits in the long would require a loop over a counter and a mask test, this will surely be slower than string conversion.

从此处的描述看来，长型实际上确实可以包含一个bignum数组.有什么方法可以访问存储长整数的基础数据结构，或者可以检查基本类型中长整数的位数?

From the description here it seems that the long type does in fact contain a bignum array. Is there some way I can access the underlying data structure that stores the long, or possibly check how many digits the long has from the base type?

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

If people are interested I can provide an example with benchmarks.

推荐答案

一种简单的方法，无需深入研究long类型的低级实现:

A simple approach without digging on low level implementation of the long type:

>>> 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

在我的机器上运行非常快.我试图获取此数字的字符串表示形式，这需要花费大量时间.

Runs quite fast on my machine. I tried to get the string representation of this number and it takes a huge time.

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

For Python 3.x, use n // (10 ** k)

一些时间如此庞大(快140倍):

Some timings with this big number (It is 140 times faster):

%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

这篇关于长期从Python访问大数的最高位数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！