Square-and-multiply exponent processor
AssigneeIntel Corporation
InventorMichael D. Ruehle
Life of this patent
Estimating the term…
Abstract
Processing exponents with a square-and-multiply technique that uses a flexible number of bits in the multiply stages. Multiple bits of the exponent can be handled in a single multiply operation, thus reducing the total number of multiply operations required to raise a number to a specified power. By examining prior and subsequent bits in the exponent in addition to the current bit, the quantity of bits that are handled in a particular multiply operation can be adjusted to the particular pattern of 1's and 0's in the exponent.
Claims20
An apparatus, comprising:
- a bit holding circuit to hold at least a portion of multiple bits of an exponent;
- a pattern detection circuit coupled to the bit holding circuit to detect occurrences of any of a plurality of predetermined bit patterns in the bit holding circuit, the pattern detection circuit comprising a first output to assert a first signal in response to each detection of said occurrences, the pattern detection circuit further comprising a second output to provide one of a plurality of addresses to a storage device in response to said each detection of said occurrences;
- and
- a multiplexer to provide a default address through the second output upon non-detection of said occurrences.
A system, comprising:
- a CPU coupled to a main memory;
- an exponent processor coupled to the CPU to detect a plurality of predetermined bit patterns in an exponent;
- a storage device coupled to the exponent processor to hold pre-calculated values of a base number raised to a plurality of powers;
- and
- a multiplier circuit coupled to the storage device to multiply an accumulated value by a selected one of the pre-calculated values from the storage device upon detection of any of the plurality of predetermined bit patterns;
- wherein the storage device is to receive one of a plurality of addresses from the exponent processor in response to each detection of said any of the plurality of predetermined bit patterns and is to receive a default address in response to non-detection of said any of the plurality of predetermined bit patterns.
A method, comprising:
- providing a base number to be raised to a power specified by an exponent;
- setting an accumulated product equal to the base number;
- examining all bits of the exponent to detect each of multiple predetermined bit patterns;
- squaring the accumulated product for each bit in the exponent;
- and
- multiplying the accumulated product by one of multiple pre-calculated powers of the base number for each detection of any of the multiple predetermined bit patterns.
A machine-readable medium having stored thereon instructions, which when executed by at least one processor cause said at least one processor to perform operations comprising:
- providing a base number to be raised to a power specified by an exponent;
- setting an accumulated product equal to the base number;
- examining all bits of the exponent to detect each of multiple predetermined bit patterns;
- squaring the accumulated product for each bit in the exponent;
- and
- multiplying the accumulated product by one of multiple pre-calculated powers of the base number for each detection of any of the multiple predetermined bit patterns.
Dependencies are inferred from the claim text.