Decimal Fixed-Point Template Class
In the decimal fixed-point template class, a template parameter N gives the number of decimal digits to the right of the decimal point. The decimal fixed-point type precisely represents all decimal fractions (all hundredths, thousandths, and so on, depending on the template parameter). It is an excellent choice for computations involving currency, because it exactly represents every penny. Whole integer values are represented internally by multiplying the integer by a scale factor that is the Nth power of 10; 102 or 100 for dollars-and-cents calculations. Thus, if N equals 2, the value 1.23 has an exact representation as 123.
Addition and subtraction are implemented as ordinary integer operations on the scaled values.
You multiply decimal fixed-point numbers using integer multiplication to obtain an intermediate product. The intermediate product has twice as many fractional digits as the operands, so if the operands must have the full 32 bits of significance, the intermediate result requires 64 bits. An implementation can use a long long variable for the intermediate product or accept overflow over a wider range of operands. The intermediate product is divided by the scale factor to produce the proper number of fractional digits in the final result. The scaled result is rounded up if the remainder is greater than or equal to half the scale factor.
For division, you multiply the dividend by the scale factor before dividing. This leaves the quotient with the proper number of decimal digits of precision. As with multiplication, the implementation must choose between using a long long intermediate dividend, or accepting overflow on a greater range of dividends. The quotient is rounded up if the remainder is greater than or equal to half the scale factor.
Listing Three shows multiplication and division code for decimal fixed-point numbers. I implemented scaling the intermediate product in terms of rounding division to avoid duplicating the tricky rounding code.
Listing Three
// Listing3.h: scaled multiply and divide
fixed_decimal& operator*=(fixed_decimal const& that)
{// multiplication with rounding
this->rep_ = scaled_multiplication(this->rep_, that.rep_, scale_);
return *this;
}
fixed_decimal& operator/=(fixed_decimal const& that)
{// division with rounding
this->rep_ = rounded_division(this->rep_ * scale_, that.rep_);
return *this;
}
The scale factor is the Nth power of 10. I obtain this number as a compile-time constant using a recursive template with a specialization to stop the recursion. This common template idiom is reproduced in Listing Four.
Listing Four
template <int N> struct exp10
{ enum { value = 10 * exp10<N-1>::value }; };
template <> struct exp10<0>
{ enum { value = 1 }; };
Binary Fixed-Point Template Class
In the binary fixed-point template class, a template parameter N gives the number of binary bits to the right of the radix point. Whole integer values are represented internally by multiplying the integer by a scale factor that is the Nth power of 2; 27 or 128 gives about 2 decimal digits of precision. Thus, the value 1.23 is represented approximately as 1.23*128=157. Note that 157/128 is 1.2265625, which rounds to 1.23 but is not exactly 1.23. The multiplication involved in scaling integers may be efficiently implemented as a left shift, which is faster than integer multiplication on most processors.
Addition and subtraction are implemented as ordinary integer operations on the scaled values.
Multiplication and division work the same as for decimal fixed-point numbers, except the scale factor can, in principle, be more efficiently applied as a left shift. The presented implementation uses the same scaled multiplication function as for the decimal fixed-point type. This leaves it to the optimizer to discover the shortcut multiplication.
An int has 31 bits of magnitude in VC7, so a fixed_binary<7> has 31-7=24 bits of magnitude, providing an integer range of +/-16,777,215. This may not be enough to count Bill Gates's fortune, but it's plenty for many applications.
Conclusion and Further Work
The fixed-point classes presented here provide useful basic functionality, but much more could be done. I have not yet investigated whether a template specialization for unsigned integral types would improve performance. There could be a function to convert among fixed-point types of differing precision. Multiplication (and division) could be distributed into two 32-bit multiplies (divides), to increase the range over which the product (quotient) can be computed without overflow and without 64-bit arithmetic. This would come at the cost of a second multiply (divide). Overflow could be handled either by throwing an exception, or more intriguingly, by saturation—the replacement of an overflowed result by the largest representable value. I imagine a traits class to parameterize all this functionality.
I have used fixed-point arithmetic to improve the precision of computations for calibration and interpolation in analog to digital conversion, for computing latency in networks, and for collecting performance statistics in servers. Fixed-point math also has well-known uses in graphics and digital-signal processing. All these applications have common properties—a need for speed, a desire for accuracy, limited range of the computed values, and computations involving multiplication and division. For these applications, there is no need to sacrifice speed for precision because fixed-point arithmetic gives both.
Notes
[1] Rational numbers such as 8/9 can be represented exactly as a separated numerator and denominator. Doing arithmetic using this representation requires repeated computation of the greatest common divisor, which is not an operation built into processors or optimized by compilers. I didn't code this implementation because I didn't expect a performance advantage over floating point.
[2] The values exactly representable by a fixed-point type are spaced evenly through its range, and include each integer value. This isn't true for floating-point types. Fully half the exactly represented floating-point values are in the interval (-1,1). Exactly represented floating-point values become increasingly sparse as their magnitude increases.
[3] Boost operators, by Dave Abrahams and Jeremy Siek. (http://www.boost.org/libs/ utility/operators.htm).
[4] http://www.guntheroth.com/ contains an updated copy of this paper and the fixed-point templates and support functions.
Kurt Guntheroth holds an MS in computer science from the University of Washington and has been developing commercial software for 20 years. He can be contacted at http:// www.guntheroth.com/.
