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 103. 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
Granlund, T. The GNU Multiple Precision Arithmetic
Library, http://www.swox.com/gmp/gmp-man-4.1.4.pdf, as viewed on
July 13, 2005.