Hướng dẫn python format long numbers
I've been considering fast poker hand evaluation in Python. It occurred to me that one way to speed the process up would be to represent all the card faces and suits as prime numbers and multiply them together to represent the hands. To whit: Show
Nội dung chính
AND
This would give each hand a numeric value that, through modulo could tell me how many kings are in the hand or how many hearts. For example, any hand with five or more clubs in it would divide evenly by 2^5; any hand with four kings would divide evenly by 59^4, etc. The problem is that a seven-card hand like AcAdAhAsKdKhKs has a hash value of approximately 62.7 quadrillion, which would take considerably more than 32 bits to represent internally. Is there a way to store such large numbers in Python that will allow me to perform arithmetic operations on it? Backend @Unacademy • Data @Amazon • Platform @Practo | Writes about Language internals and Math in Computer Science When you code in a low-level language like C, you worry
about picking the right data type and qualifiers for your integers; at every step, you need to think if In C, when you try to compute 2²⁰⁰⁰⁰ using builtin
But for python, it is a piece of cake 🎂
Python must be doing something beautiful internally to support integers of arbitrary sizes and today we find out what's under the hood! Representation and definitionAn integer in Python is a C struct defined as following
Other types that has
This indicates that an
integer, just like a
Decoding ob_digit
Generally, In low-level languages like C, the precision of integers is limited to 64-bit, but Python implements Arbitrary-precision integers. Since Python 3 all integers are represented as a bignum and these are limited only by the available memory of the host system. Decoding ob_size
StorageA naive way to store an integer digit-wise is by actually storing a decimal digit in one item of the array and then operations like addition and subtraction could be performed just like grade school mathematics. With this approach, a number This approach is inefficient as we will be using up 32 bits of digit ( So, can we do better? for sure, otherwise, this article should hold no place on the internet. Let's dive into how python stores a super long integer. The pythonic wayInstead of storing just one decimal digit in each item of the array
In the hexadecimal number system, the base is 16 ~ 2⁴ this means each "digit" of a hexadecimal number ranges from 0 to 15 of the decimal system. Similarly for python, "digit" is in base 2³⁰ which means it will range from 0 to 2³⁰ - 1 = 1073741823 of the decimal system. This way python efficiently uses almost all of the allocated space of 32 bits per digit and keeps itself resourceful and still performs operations such as addition and subtraction like grade school mathematics.
Example: 1152921504606846976As
mentioned, for Python a "digit" is base 2³⁰ hence if you convert 1152921504606846976 = 0 * (2³⁰)⁰ + 0 * (2³⁰)¹ + 1 * (2³⁰)² The
I have created a demo REPL that will output the way python is storing integers internally and also has reference to struct members like Operations on super long integersNow that we have a fair idea on how python supports and implements arbitrary precision integers its time to understand how various mathematical operations happen on them. AdditionIntegers are persisted "digit-wise", this means the addition is as simple as what we learned in the grade school and python's source code shows us that this is exactly how it is implemented as well. The function named x_add in file longobject.c performs the addition of two numbers.
The code snippet above is taken from
SubtractionSimilar to how addition is implemented, subtraction also happens digit-wise. The function named x_sub in file longobject.c performs subtraction of two numbers.
The code snippet above is taken from MultiplicationAgain a naive way to implement multiplication will be what we learned in grade school math but it won't be very efficient. Python, in order to keep things efficient implements the Karatsuba algorithm that multiplies two n-digit numbers in O ( nˡᵒᵍ³ ) elementary steps. The algorithm is slightly complicated is out of the scope of this article but you can find its implementation in k_mul and Division and other operationsAll operations on integers are defined in the file longobject.c and it is very simple to locate and trace each one. Warning: it will take some time to understand each one in detail so grab some popcorn before you start skimming. Optimization of commonly-used integersPython preallocates small integers in a range of -5 to 256. This allocation happens during initialization and since we cannot update integers (immutability) these preallocated integers are singletons and are directly referenced instead of reallocating. This means every time we use/creates a small integer, python instead of reallocating just returns the reference of preallocated one. This optimization can be traced in the macro This is the second article in the Python Internals series. The first article was How I changed my Python and made it dubious and it helps you take your first steps in Python's source code and paves the way for you to become a Python Core Developer. This article was originally published on my blog - How python implements super long integers?. If you want to read more articles like this, subscribe to my newsletter and get the post delivered directly to your inbox. I write about Engineering, System Design and a bit of programming, every Friday. Give me a shout-out @arpit_bhayani. You can find my previous articles @arpitbhayani.me/blogs. How do you take long values in Python?Type int(x) to convert x to a plain integer. Type long(x) to convert x to a long integer. Type float(x) to convert x to a floating-point number. What's the largest number Python can handle?It's usually 2^31 - 1 on a 32-bit platform and 2^63 - 1 on a 64-bit platform. How does Python store long integers?Python, however, doesn't use a fixed number of bit to store integers. Instead, Python uses a variable number of bits to store integers. For example, 8 bits, 16 bits, 32 bits, 64 bits, 128 bits, and so on. The maximum integer number that Python can represent depends on the memory available. What is long number in Python?Long: Integer type with unlimited length. In python 2.2 and later, Ints are automatically turned into long ints when they overflow. Dropped since Python 3.0, use int type instead. Float: This is a binary floating point number. |