How are bignums represented internally?

Question

Python provides a "bignum" type called "long" which can represent arbitrarily large numbers. What is the internal representation of this type?

I ask in part because I am curious what operations might be particularly fast or slow on these numbers. For example, is bit shifting particularly fast compared to multiplication or division (as it is for "regular" ints)?

Answer 1

CPython's arbitrary precision integers are stored an array of binary digits. Each digit consists of either 15 or 30 bits. Addition, subtraction, and bit shifts are all O(n). Multiplication (for large enough values) uses Karatsuba multiplication which is O(n**1.585). Division still uses the classical O(n**2) algorithm.