There are many reasons why numbers larger than 64 bits must be computed. For example, cryptographic algorithms usually have to perform operations on numbers that are 256 bits or even larger in some cases. However, the programming languages that I use can only handle at maximum, 64 bit integers, so how do computers perform operations on numbers that are larger than 64 bits in size and which programming languages support computation of these larger numbers?
-
9$\begingroup$ en.wikipedia.org/wiki/Arbitrary-precision_arithmetic $\endgroup$– D.W. ♦Commented May 31, 2021 at 5:13
-
73$\begingroup$ How do you humans perform operations on numbers that are larger than one digit? $\endgroup$– Jörg W MittagCommented May 31, 2021 at 8:22
-
5$\begingroup$ GMP is an open source library which implements such computations. $\endgroup$– Yuval FilmusCommented May 31, 2021 at 9:44
-
5$\begingroup$ I wrote an answer to pretty much this question on our sister site for Cryptography a few years ago. $\endgroup$– Ilmari KaronenCommented May 31, 2021 at 20:44
-
1$\begingroup$ They don't. 64 bits are enough for everyone. $\endgroup$– Peter - Reinstate MonicaCommented Jun 1, 2021 at 12:49
5 Answers
Larger precision numbers are simulated in software using arrays of fixed-width integers. The elements of these arrays are effectively super-sized digits, and are called limbs.
The size of a limb is chosen based on considerations such as what are the available types; what, if any, special operations does the target processor have for going beyond the widest type; and what is actually available in the implementation language.
Let's consider multiplication. If our 64 bit processor does not provide a 64 × 64 → 128 multiplication, we may have to choose a 32 bit limb for our integers, or at least treat our numbers that way for the purposes of multiplication. The basic idea is that we are restricted to inputs which are half the size of the widest type that can be the result of a multiplication. We then implement long multiplication.
The following diagram represents 64 × 64 → 128 bit unsigned multiplication of an operand A
and B
. The U:V
notation shows a 64 bit value made up of an upper 32 bit half U
and a lower 32 bit half V
. The notation AH
denotes the upper 32 bits of 64 bit operand A
, and AL
denotes the lower 32 bits. x
is just the multiplication operator:
AH : AL
x BH : BL
-----------------
P0: AL x BL
P1: AH x BL
P2: AL x BH <-- 64 bit inner products
P3: AH x BH
------------------
[ 128 bit product ] <--- sum of inner products
This is just long multiplication in which four 32-bit limbs play the role of digits. All combinations of limbs from both operands are multiplied together, and then added together. Each inner product is shifted into the correct power position.
I have given the inner products names, so we can rewrite the addition like this, where 000 indicates 32 all-zero bits.
P0H:P0L
P1H:P1L:000
P2H:P2L:000
P3H:P3L:000:000
---------------
...........:P0L
If only 64 bit addition is available, adding the inner products together is tricky. The addition of two 64 bit numbers produces a 65 bit result. If we work in machine language, the processor may give us the 65th bit in the form of a carry flag, which can then be included in the next round of addition.
If we don't have access to the carry flag, we can infer it anyway. We simply add together the operands. Then if the result is smaller than either operand, we know that carry occurred: we must carry a 1 into the next addition. In C notation:
uint64_t A = get_operand_a();
uint64_t B = get_operand_b();
uint64_t SUM = A + B;
int carry = (SUM < A); // 1 if SUM < A, else 0.
In any case, we begin by working on the rightmost 64 bit column:
[P0H:P0L]
P1H[P1L:000]
P2H[P2L:000]
P3H:P3L[000:000]
-------[-------]
.......[XXX:P0L]
We begin by adding P0H:P0L
and P1L:000
. This could produce a carry which we call C0
. We then add P2L:000
to this partial result. It could carry again, so we call that C1
. Then we deal with the left column:
[C0 + C1]P0H:P0L
[ P1H]P1L:000
[ P2H]P2L:000
[P3H:P3L]000:000
[-------]-------
[ZZZ:YYY]XXX:P0L
We add together the carry C0 + C1, which can be 0, 1 or 2, with P1H
, P2H
and P3H:P3L
. This addition will not overflow, because 64 × 64 multiplication cannot overflow 128 bits.
Now 64 bit processors, like the x86-64 ones from Intel, often provide a way in the instruction set to to do 64 × 64 → 128 multiplication, right in the hardware. A special instruction might be provided whose output is a pair of registers. In that case, the problem is solved; we don't have to implement any of the above. We choose 64 bit limbs for our wider-precision numbers and take advantage of that multiplication instruction.
Some compilers for languages like C may provide access to a 128 bit type. If we are working with the GNU C compiler, we have an __uint128_t
type. Using this may be advantageous since the compiler can map that to the available hardware support, so that when two 64 bit values that are cast to this type are multiplied together, the special instruction is used. A code example of this is attached below.
Suppose no 64 × 64 → 128 multiplication is available. And suppose we are implementing general purpose multi-precision integers that can go to "arbitrary" widths, limited only by memory: so-called bignums.
In that case, we will probably skip implementing the above 64 × 64 → 128 multiplication entirely. Our bignum integers will use 32 bit limbs, and multiplication will be implemented as a more general long multiplication of two multi-precision integers using a pair of nested loops. The 64 × 64 → 128 occurs as a special case in that algorithm, when both inputs have two limbs.
The naive long multiplication is not the only choice of algoirthm for bignum integers. There is the Karatsuba algorithm which becomes advantageous when the numbers go beyond a certain size, because it has better asymptotic performance than the $O(n^2)$ of the naive long-multiplication's nested loop. In fact it achieves $O(n^{1.58})$. After Karatsuba, there are several other algorithms which get the asymptotic performance down, but require even larger numbers in order to yield an payoff).
Here is an example of using GCC on a 64 bit Intel platform to gain access to 64 × 64 → 128 multiplication:
#include <stdint.h> // for uint64_t, standard type from ISO C.
// __uint128_t is a GCC extension:
// Not found in all targets and configurations!
__uint128_t mul(uint64_t a, uint64_t b)
{
return (__uint128_t) a * b;
}
Now, when we compile this with gcc -O2 -S
(optimize at level 2, produce assembly code) we get:
mul:
movq %rsi, %rax
mulq %rdi
ret
Just three instructions, including the RET
! The quad-word multiplication instruction requires that one of the operands is in the RAX
register, and so a mov
is required to move it from RSI
to RAX
, since under the calling conventions being used, RSI is used for passing the first argument of a function. If RAX were used for passing the first argument, the move would not be required.
Thus mulq %rdi
is multiplying %rax
by %rdi
; the %rax
is implicit and understood and so doesn't appear in the assembly notation.
The output is produced in the register pair RDX:RAX. The calling convention is such that this is exactly how a 128 bit result is returned, and so there is nothing left to do but to return from the function.
If we are implementing bignum integers on 64 bit Intel, working in C, using the GNU C compiler, or any other one which provides such an extension, it behooves us to take advantage of this: we can choose 64 bit limbs for our numbers, and use the compiler-specific 128 bit type to handle the multiplication inner products.
-
$\begingroup$ intel.com/content/dam/www/public/us/en/documents/white-papers/… has similar diagrams of adding partial products. Is there a 128 bit integer in gcc? shows how to detect
unsigned __int128
support in GCC, and has the same test function you used. Getting the high part of 64 bit integer multiplication shows an MSVC intrinsic (MSVC lacks an __int128), and AArch64 output for a similar test function. $\endgroup$ Commented Jun 2, 2021 at 20:04
in school you (probably) memorized the common operations (addition, subtraction, multiplication and division) for decimal 1 digit numbers.
Then you learned how to do operations on larger numbers using those memorized operations by doing the computation part by part for example long multiplication and long division.
A computer can do the same algorithms using "digits" of whatever word size they can use carrying over the overflow into the next digit.
More advanced algorithms exist that operate a bit faster but still operate on the same principle of the large numbers being sequences of 32-bit or 64-bit digits.
-
2$\begingroup$ Getting the high part of 64 bit integer multiplication has an example of using pure C to construct a 64x64 => 128-bit multiply using only
uint64_t
. (And my answer on the same question shows how compilers do a bad job with that in practice, and you get much more efficient asm if you useunsigned __int128
in the source, or an intrinsic function.) $\endgroup$ Commented Jun 1, 2021 at 9:19 -
$\begingroup$ or if the compiler can see that you need the high part and use the instruction that emits both the high and low part of the result. $\endgroup$ Commented Jun 1, 2021 at 11:11
-
$\begingroup$ Yes, that's exactly the point of my answer; writing source such that the compiler can see that your inputs are 64-bit, and you want the high half of a full multiply.
(a * (unsigned __int128)b) >> 64
does compile tomul
on x86-64,umulh
on AArch64, etc. with GCC, while MSVC needs an intrinsic to be able to see that. Unlike if you write extended-precision stuff using 32x32=>64-bit chunks; then even GCC / clang can't see through that. $\endgroup$ Commented Jun 1, 2021 at 19:33 -
$\begingroup$ @PeterCordes Re, "...compilers do a bad job...," True enough, but the OP doesn't appear to be asking how to do a good job at it. The OP seems to want to know how it is even possible to implement multiple-precision arithmetic. The simplest answer probably is the most useful in this case. $\endgroup$ Commented Jun 2, 2021 at 19:03
-
$\begingroup$ @SolomonSlow: Yes, that's why I commented with an example that shows the basic algorithm for doing a wide multiply in smaller chunks, only mentioning efficiency as a note. intel.com/content/dam/www/public/us/en/documents/white-papers/… is also a good example, showing some nice diagrams to illustrate adding the partial products of 512 x 512-bit multiplication (and then showing how to do the add-with-carry more efficiently with new instructions like mulx that doesn't disturb the carry flag.) $\endgroup$ Commented Jun 2, 2021 at 19:59
The x86 ISA, along with many (most?) other microprocessor architectures includes the instruction ADC (add with carry), among others, to support arbitrary-precision arithmetic. The basic idea is that instead of thinking of a number as a fixed 2, 4, 8-byte integer, you instead treat it as a variable-length "string" of 2, 4, or 8-byte integers (depending on the word size of the architecture) and combine multiple operations along this string using elementary school arithmetic.
However, note that the instruction merely provides a hardware boost to an operation which can easily be implemented in software using fixed-width arithmetic instructions. To see such a software implementation, take a look at the Java BigInteger
source, which uses an array of int
to hold the "string" of [32-bit] "digits".
-
1$\begingroup$ Your link for ADC seems incorrect; could you double-check it? $\endgroup$ Commented Jun 1, 2021 at 1:15
-
$\begingroup$ Use this: felixcloutier.com/x86/adc $\endgroup$– NayukiCommented Jun 1, 2021 at 2:29
-
1$\begingroup$ Wow, I really screwed that up...thanks for the catch! $\endgroup$ Commented Jun 1, 2021 at 3:06
-
1$\begingroup$ @leftaroundabout: No, there's no single add instruction that propagates carry through the whole register, only across elements up to 64-bit qwords (
[v]paddq
). There isn't even any support for generating carry-out from each element. (And for doing it manually withcarry = sum < one_input
; only AVX-512 introduced unsigned integer compares. But even then probably not worth it to iterate add/shuffle until there's no more carry between elements.) $\endgroup$ Commented Jun 1, 2021 at 8:59 -
1$\begingroup$ Commented x86-64 asm example of adding a 128-bit integer, from un-optimized Rust compiler ouput: How does Rust's 128-bit integer `i128` work on a 64-bit system?, using
add
/adc
(add-with -carry). Might make a good link for this answer. $\endgroup$ Commented Jun 1, 2021 at 9:16
The computer hardware provides facility of storing integers and doing basic arithmetic over them; generally this is limited to integers in a range (e.g. up to $2^{64}-1$). But larger integers can be supported via programs; below is one such method.
Using Positional Numeral System (e.g. the popular base-10 numeral system), any arbitrarily large integer can be represented as a sequence of digits in base $B$. So, such integers can be stored as an array of 32-bit integers, where each array-element is a digit in base $B=2^{32}$.
We already know how to represent integers using numeral-system with base $B=10$, and also how to perform basic arithmetic (add, subtract, multiply, divide etc) within this system. The algorithms for doing these operations are sometimes known as Schoolbook algorithms. We can apply (with some adjustments) these Schoolbook algorithms to any base $B$, and so can implement the same operations for our large integers in base $B$.
To apply these algorithms for any base $B$, we will need to understand them further and handle concerns like:
what is the range of various intermediate values produced during these algorithms.
what is the maximum carry produced by the iterative addition and multiplication.
how to estimate the next quotient-digit in long-division.
(Of course, there can be alternate algorithms for doing these operations).
Some algorithm/implementation details can be found here (initial chapters), here (written by me) and here.
Decimal positional representation of numbers, called Indo-Arabic numeral system, was discovered about 20 centuries ago. It was sucessful because there is no limitation on the size of number that can be represented, and it allows fairly simple manipulations of number representations (i.e. algorithms) to realize elementary arithmetic operations.
It represents numbers as sequences of the ten distinct digits (numerical symbols) represented today as 0, 1, ... 9. Modern understanding shows that there is nothing essential about the number of distinct digits, which is called the base of the system, which is ten in this case. A similar system can be built with any number base, any number of distinct digits, as long as it is two or more. With two digits, i.e. base 2, you get the binary system commonly used in computers hardware (binary digits are called bits).
However, size limitations in computer hardware limit the size of bit sequences it can represent and manipulate simply to represent numbers and realize arithmetic operations. This is basically what this question is about.
The simple answer to this question is to come back to basics :
- chose a numeration base N
- define a set of N symbols that will be the digits. Any computer representation of the digits is ok, as long as you can identify and manipulate them.
- define a way to represent and manipulate sequences of symbols, that will be your representation of numbers.
Then you must also write routines that perform the fundamental arithmetic operations on your number thus represent$ed in base N (and possibly a few other utilities, such as I/O routine in some human readable representation). Then you can use your new numbering system.
Note that N can be arbitrary (but at leaen.wikipedia.org/wiki/Arabic_numeralsst two), such as $2^{64}$, $3$, $16$ or $3^{72}-276$.
There rest is a matter of implementation choice, depending on what you want to do with your numbering system, and on what you want to optimize, such as speed of computation or size of number representation.