How to store long integer in python
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
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 store long integers in python?Python supports a "bignum" integer type which can work with arbitrarily large numbers. In Python 2.5+, this type is called long and is separate from the int type, but the interpreter will automatically use whichever is more appropriate.
How do you store large integers?Below are the steps: Take the large number as input and store it in a string. Create an integer array arr[] of length same as the string size. Iterate over all characters (digits) of string str one by one and store that digits in the corresponding index of the array arr.
How long big can integers numbers be in python?These represent numbers in the range -2147483648 through 2147483647.
How large can an integer be in python 3?In Python3, int has no max limit. Python2 has two integer types, int and long , but Python3 has only int . int in Python3 is equivalent to long in Python2, and there is no max limit. You can handle as large value as memory is available.
|