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)?

Bonnette

This is interesting. You should test it: perform a hundred thousand operations of each kind on both int and long, and see which are faster! – Polychromatic

This is just a guess, but this should depend on the implementation and against which arbitrary precision library it links. – Estop

see e.g. https://mcmap.net/q/1626163/-how-do-languages-such-as-python-overcome-c-39-s-integral-data-limits – Selena

@Estop You're not wrong, but FYI: At least CPython and PyPy roll their own implementation (they don't link to a third party library), and the two implementations are very similar aside from being written in rather different languages. – Tireless

Aside from a curiosity (I agree with @uʍopǝpısdn: you should just benchmark it and move on), I'd be wary of prematurely optimizing for something that isn't going to have significant performance implications. – Propitiatory

What version of Python are we talking about? In Python2, there is int and long, but in Python3, there is only long (renamed to int). This is how Python2 int is implemented. – Stripe

@Two-BitAlchemist Does the version matter? AFAIK the implementation has remained mostly unchanged for a long time. In any case we're talking about the arbitrary precision one, so not Python 2 int. – Tireless

you could read longintrepr.h – Stephine

legacy.python.org/dev/peps/pep-0237 – Blowtube

@delnan It matters because what are you comparing it to? Are operations particularly fast or slow compared to what? In Python 2, a comparison is available. In Python 3, we're just talking about how Python handles numbers mostly in general (unless we want to talk about the decimal library, I guess). – Stripe

@Two-BitAlchemist The comparison considered in the question is bit shifting these numbers vs. multiplying/dividing these numbers. No need for another number type to compare to. – Tireless

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.

Triclinic

Answer 2

Well, I wrote this. I'm not sure how good this is, but you can use it as a starting point for a more refined and complete benchmark.

import timeit

def timef(f, *args):
    return timeit.timeit(lambda: f(*args), number = 1000000) # repetitions


tests = {
    'addition'      : lambda x: x + 17,
    'substraction'  : lambda x: x - 17,
    'multiplication': lambda x: x * 17,
    'division'      : lambda x: x / 17,
    'float division': lambda x: x / 17.0
}


for name, f in tests.items():
    print  'int {0}'.format(name).ljust(20), timef(f, 0)
    print 'long {0}'.format(name).ljust(20), timef(f, 10 ** 50)
    print

What I'm seeing is that int() operations are indeed faster, but not a lot faster.

Polychromatic