limb (thing)

By anatomical analogy, a limb is defined as a group of digits in a number. One common example of a limb is the grouping of digits in written numbers, with a separator such as a comma or period, depending on locale. In English, for example, "one million"is written as 1,000,000. Each group of three digits could be termed a limb.

The grouping of digits of a number into limbs can be considered as treating the number as if it were in a different radix or number system. In the decimal example above, the grouping is a way of considering the number in base 10³. This visualization is more common with numbers in digital computers. While the number may be stored internally as binary, it is typically more convenient for a user to view the number in octal (limbs of size 3 bits), or hexadecimal (limbs of size 4 bits, traditionally termed nibbles or nybbles). The computer's own groupings of the bits into bytes or words can also be considered as limbs.

A limb size often needs to be specified when working with arithmetic to arbitrary precision. In much the same way that humans can perform long multiplication using the familiar method, multiplying single digits at a time, a computer can perform multiple precision arithmetic as a sequence of operations on limbs of a size that suits the computer's architecture, such as 16 or 32 bits. The GMP bignum library, for instance, runs on a huge variety of systems, some with greatly differing capabilities than others. On each system, the limb size is defined to suit that particular computer. Since the limb size does nothing other than specify an effective base for calculation, the standard algorithms for addition, subtraction, multiplication and division of multiple digit numbers can be applied.

On occasion, the choice of limb size can be chosen for a particular algorithm and will affect the implementation. A suitable choice of limb size can make quite a difference to performance. For example, consider multiplying two numbers that are 832 bits in length, on a computer that can most efficiently add and multiply results up to 32 bits in length. One possible way of arranging the calculation is to divide each number into 64 limbs that are each 13 bits long. The product of two of these limbs will fit in 13+13=26 bits, and the particular multiplication algorithm may mean as many as 64 of these products will be summed for each limb in the result. The choice of limb size means an intermediate result will never overflow the 32 bits. A more obvious choice of limb size such as 16 or 32 would have meant the code would have to be written to handle carry from one limb to the next. Some authors have determined that the additional registers or instructions required to handle such carries have a significant performance impact.

Sources