Large integer computations

Today's $32$-bit processors can efficiently calculate with integers $<2^{32}$. They add/subtract in about 1 instruction cycle, multiply in about 10 cycles, and divide in about 40 cycles. (Numbers are approximate and vary between vendors and hardware configurations.)

To beat the hardware limit, one either uses special representations tailored to the problem at hand, or simply uses a software library that implements multiprecision integers. (Such integers have in the past also been called "large integers" or "big integers".)

Here is a (partial) list of existing multiprecision integer packages with comments. Please notify me with corrections and additions. For information on writing your own multiprecision integer package, see the bottom of the list. The list was last updated June 2001.

Remark: It would be nice if there were a single top-notch publically-maintained multiprecision integer package with a standardized interface having a runtime self-configuration that adjusts parameters and selects appropriate assembly code to achieve maximum performance on the given processor. The set of hardware/parameter combinations could be reduced (possibly to a singleton) at compile time, with a runtime default, but optionally allowing the final selection to be determined at runtime. Both single and vector-based operations should be supported in the interface, and the vector operations should maximize hardware pipelining. At the lowest level there should be maximally efficient support for both fixed-size and variable-size integers, at the higher levels supporting aliasing and other stuff (perhaps signs, perhaps rational numbers or floating point, perhaps operations beyond arithmetic). Beyond that, there should be super-high-level C++ wrappers giving access to both the low-level and intermediate level. For example, C++ templates are appropriate for accessing the fixed-size lowlevel stuff. Of existing package, GNU GMP comes closest to all this, but in many ways is far away. Of course, I'm not complaining, just recording my ideas, realizing that the impetus is on me to implement this if I want to see it done!