faster than division on IA-32 processors, and in some cases it is possible to
avoid the use of division instructions by using multiplication instructions. The
idea is to multiply the dividend by a fraction that is the reciprocal of the divisor.
For example, if you wanted to divide 30 by 3, you would simply compute the
reciprocal for 3, which is 1 ÷ 3.The result of such an operation is approximately
0.3333333, so if you multiply 30 by 0.3333333, you end up with the correct
result, which is 10.
Implementing reciprocal multiplication in integer arithmetic is slightly
more complicated because the data type you’re using can only represent inte-
gers. To overcome this problem, the compiler uses fixed-point arithmetic.
Fixed-point arithmetic enables the representation of fractions and real num-
bers without using a “floating” movable decimal point. With fixed-point arith-
metic, the exponent component (which is the position of the decimal dot in
floating-point data types) is not used, and the position of the decimal dot
remains fixed. This is in contrast to hardware floating-point mechanisms in
which the hardware is responsible for allocating the available bits between the
integral value and the fractional value. Because of this mechanism floating-
point data types can represent a huge range of values, from extremely small
(between 0 and 1) to extremely large (with dozens of zeros before the decimal
point).
To represent an approximation of a real number in an integer, you define an
imaginary dot within our integer that defines which portion of it represents
the number’s integral value and which portion represents the fractional value.
The integral value is represented as a regular integer, using the number of bits
available to it based on our division. The fractional value represents an
approximation of the number’s distance from the current integral value (for
example, 1) to the next one up (to follow this example, 2), as accurately as pos-
sible with the available number of bits. Needless to say, this is always an
approximation—many real numbers can never be accurately represented. For
example, in order to represent .5, the fractional value would contain
0x80000000(assuming a 32-bit fractional value). To represent .1, the frac-
tional value would contain 0x20000000.
To go back to the original problem, in order to multiply a 32-bit dividend by
an integer reciprocal the compiler multiplies the dividend by a 32-bit recipro-
cal. This produces a 64-bit result. The lower 32 bits contain the remainder (also
represented as a fractional value) and the upper 32 bits actually contain the
desired result.
Table B.1 presents several examples of 32-bit reciprocals used by compilers.
Every reciprocal is used together with a divisor which is always a powers of
two (essentially a right shift, we’re trying to avoid actual division here). Com-
pilers combine right shifts with the reciprocals in order to achieve greater
accuracy because reciprocals are not accurate enough when working with
large dividends.Understanding Compiled Arithmetic 52522_574817 appb.qxd 3/16/05 8:45 PM Page 525