limb

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

Limb (?), n. [OE. lim, AS. lim; akin to Icel. limr limb, lim branch of a tree, Sw. & Dan. lem limb; cf. also AS. li, OHG. lid, gilid, G. glied, Goth. lipus. Cf. Lith, Limber.]

1.

A part of a tree which extends from the trunk and separates into branches and twigs; a large branch.

2.

An arm or a leg of a human being; a leg, arm, or wing of an animal.

A second Hector for his grim aspect, And large proportion of his strong-knit limbs. Shak.

3.

A thing or person regarded as a part or member of, or attachment to, something else.

Shak.

That little limb of the devil has cheated the gallows. Sir W. Scott.

4.

An elementary piece of the mechanism of a lock.

Limb of the law, a lawyer or an officer of the law. [Colloq.]

Landor.

© Webster 1913.

Limb, v. t.

1.

To supply with limbs.

Milton.

2.

To dismember; to tear off the limbs of.

© Webster 1913.

Limb, n. [L. limbus border. Cf. Limbo, Limbus.]

A border or edge, in certain special uses.

The border or upper spreading part of a monopetalous corolla, or of a petal, or sepal; blade.

The border or edge of the disk of a heavenly body, especially of the sun and moon.

The graduated margin of an arc or circle, in an instrument for measuring angles.

© Webster 1913.