Accéder aux chiffres les plus élevés de grands nombres de Python long

Question

Je travaille avec des nombres avec des dizaines de milliers de chiffres en python. Le type long fonctionne magnifiquement en effectuant des calculs sur ces nombres, mais je suis incapable d'accéder aux chiffres les plus élevés de ces nombres d'une manière suffisamment rapide. Notez que je ne sais pas exactement combien de chiffres le numéro contient. Les "chiffres les plus élevés" se réfèrent aux chiffres à l'endroit le plus significatif, les chiffres les plus bas peuvent être accédés rapidement en utilisant le module.

Je peux penser à deux façons d'accéder à ces chiffres en python, mais ils sont tous deux trop lent pour mes fins. J'ai essayé de convertir en une chaîne et d'accéder aux chiffres grâce à des méthodes de tableau, mais les conversions de type sont lentes lorsque vous avez plus de 10 000 chiffres. Sinon, je pourrais simplement masquer les bits et tronquer, mais cela nécessite que je sache combien de chiffres sont dans le long. Trouver le nombre de chiffres dans le long nécessiterait une boucle sur un compteur et un test de masque, ce sera sûrement plus lent que la conversion de chaîne.

From the description here Il semble que le type long contienne en fait un tableau bignum. Y at-il un moyen d'accéder à la structure de données sous-jacente qui stocke le long, ou peut-être vérifier combien de chiffres le long a à partir du type de base?

Si les gens sont intéressés, je peux donner un exemple avec des repères.

Answer 1

Une approche simple, sans creuser la mise en œuvre de bas niveau du type 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 

Runs assez vite sur ma machine. J'ai essayé d'obtenir la représentation sous forme de chaîne de ce nombre et cela prend énormément de temps.

Pour Python 3.x, utilisez n // (10 ** k)

Quelques timings avec ce grand nombre (Il est 140 fois plus rapide):

%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 

Answer 2

Python 2.7 a la méthode bit_length() sur des entiers.

Answer 3

Voici une doublure très laid qui va extraire les premiers chiffres décimaux:

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

Si votre valeur de x est d'environ 10 000 chiffres décimaux long, vous devriez obtenir une réponse précise à environ 12 chiffres ou alors. Au fur et à mesure que x grossit, votre précision diminuera. Si vous souhaitez utiliser des modules externes, je regarderais gmpy2. La bibliothèque gmpy2 fournit un accès à la bibliothèque GMP (ou MPIR) pour l'arithmétique entière et fractionnaire à précision multiple, la bibliothèque MPFR pour l'arithmétique à virgule flottante à précision multiple et la bibliothèque MPC pour l'arithmétique complexe à précision multiple. Les entiers gmpy2 sont plus rapides que les longs natifs de Python et vous pouvez convertir un entier long en un nombre à virgule flottante pour extraire seulement les chiffres principaux. La doublure ci-dessus devient simplement:

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

L'approche gmpy2 conservera sa précision même si les chiffres deviennent plus grands.

Désistement: Je maintiens gmpy2.