19
$\begingroup$

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?

$\endgroup$
6
9
$\begingroup$

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.

$\endgroup$
1
52
$\begingroup$

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.

$\endgroup$
5
  • 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 use unsigned __int128 in the source, or an intrinsic function.) $\endgroup$ Jun 1 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$ Jun 1 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 to mul 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$ Jun 1 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$ Jun 2 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$ Jun 2 at 19:59
11
$\begingroup$

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".

$\endgroup$
8
  • 1
    $\begingroup$ Your link for ADC seems incorrect; could you double-check it? $\endgroup$
    – Sam Estep
    Jun 1 at 1:15
  • $\begingroup$ Use this: felixcloutier.com/x86/adc $\endgroup$
    – Nayuki
    Jun 1 at 2:29
  • 1
    $\begingroup$ Wow, I really screwed that up...thanks for the catch! $\endgroup$ Jun 1 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 with carry = 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$ Jun 1 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$ Jun 1 at 9:16
0
$\begingroup$

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 and here.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.