Computers cannot exactly represent the value of fractions such as 8/9, where the divisor is not a multiple of 2 [1]. In fact, the value of the integer expression 8/9 is zero, even though the mathematical quantity is much closer to 1. For computations involving fractions, most developers use floating-point arithmetic, which approximates the value of 8/9 as the decimal fraction 0.88889, a more sensible and accurate choice than the unintuitive result of the integer expression.
The floating-point numeric representation is complex internally. This makes floating-point math slower than integer math, even when floating-point instructions are built into the processor. Fortunately, there are other ways to represent fractional numbers.
A fixed-point number (for instance, the number "123.456") has a radix point with a fixed number of digits to the right, representing a fractional part. We say "radix point" instead of decimal point because there are fixed-point numeric representations for both decimal and binary numbers. In a decimal fixed-point number, the digits to the right of the radix point are decimal digits. In binary fixed-point, the fractional digits are binary bits.
Fixed-point numeric types are implemented using integer arithmetic operations that execute faster than corresponding floating-point operations. The range of a fixed-point type is limited by the range of the integer that represents it internally, whereas floating-point numbers can represent extremely large numbers [2]. For a large class of everyday problems that don't need the astronomical values representable by floating-point numbers, this trade-off is quite reasonable.
I coded C++ template classes implementing three fixed-point types. They are intended as drop-in replacements for int or double. Their precision and range can be tuned to suit different applications. On my Pentium 4, compiled by Visual C++ 7.1 with optimization turned on, the fixed-point types I present here are over twice as fast as equivalent scalar floating-point code. On embedded processors and integer digital signal processors (DSPs) with no floating-point hardware, I expect them to be many times faster than floating-point function libraries.
Arithmetic Helper Template Class
The fixed-point classes directly implement four arithmetic assignment operators (+=, -=, *=, /=), and two comparison operators (==, <). A trick from the Boost numerics library [3] uses a helper class to define five more arithmetical operators (+, -, *, /, unary -) and the remaining comparison operators (!=, >=, <=, >). The fixed-point classes derive from the helper template class, which takes the fixed-point class as a template argument. At first glance, this technique looks impossibly circular. It works because the compiler doesn't check the template functions until they are instantiated, and both classes have complete definitions at this point. Listing One illustrates how the helper template implements operator+() and operator>=() in terms of the derived class's operator+=() and operator<(), respectively.
Listing One
// Listing1.h: helper base class
template <class D> class Helper
{
friend D operator+(D const& lhs, D const& rhs)
{ D tmp = lhs; tmp += rhs; return tmp; }
friend bool operator>=(D const& lhs, D const& rhs)
{ return !(lhs < rhs); }
};
class D : public Helper<D>
{
int rep_;
public:
D(int i=0) : rep_(i) {/*empty*/}
D& operator+=(D const& rhs)
{ rep_ += rhs.rep_; return *this; }
bool operator<(D const& rhs) const
{ return rep_ < rhs.rep_; }
};
Chip makers have spent much effort and silicon (perhaps 20 percent of the Pentium 4 die) to improve the performance of floating-point computations. Beating the Pentium's floating-point performance in my fixed-point types was thus a nontrivial challenge. I chose C++ template classes so the compiler would inline method calls and reduce template parameters to compile-time constants.
I benchmarked the fixed-point implementations against floating-point code, and checked the compiler-generated assembly-language output to see if unexpected artifacts were confounding my measurements.
Because different compilers implement different optimizations, users of these fixed-point classes may need to tweak them for best performance on other compilers or non-Intel processors. The Boost numerics library [3] contains an alternate implementation for compilers that don't perform the returned value optimization.
Rounding Integer Template Class
The rounding integer representation produces a more satisfying integer result by rounding the result to the nearest integer, rather than truncating it toward zero. Thus, the value of the expression 8/9 in rounding integer representation is 1, not 0. The speed penalty (on my Pentium 4 using VC7) is only 15 percent versus ordinary integer calculations involving division. Rounding integers have the same range as ordinary integers.
