How are bignums represented internally?
bignum, python, python-2.7
Solution
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.
Problem
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)?