Channels ▼
RSS

C/C++

Fixed-Point Arithmetic Types for C++


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.


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 

Video