Fixed Point Arithmetics in C++ using templates

Question

I am trying to create a Fixed Point Arithmetics library : I call fixed point a number which has bits reserved for decimal part.
Here is the code :

#ifndef FIXEDPOINTNUMBER_HPP
#define FIXEDPOINTNUMBER_HPP

#include <type_traits>
#include <cstdint>

///////////////////////////////////////////////////////////
////////////////////    DECLARATION    ////////////////////
///////////////////////////////////////////////////////////

/**
* @brief Provides fixed-point number calculations.
* @author Julien Vernay (JDM)
* @date 01-01-2018 (dd-mm-yyyy)
* @arg @c T Underlying type, no overhead
* @arg @c N Number of bits used for decimal part
* @details Fixed-Point Number uses an int value, so we only needs int manipulation with bitshift tricks instead of floating arithmetics.
* @details The underlying value @c val can be represented by : <em>VALUE = val / (2^N)</em>
*/
template<typename T, unsigned char N>
class FixedPointNumber {
public:
FixedPointNumber();                        /**< @brief Constructs with 0 */
FixedPointNumber(T value, bool raw = 0);   /**< @brief Constructs with a @c T value */
FixedPointNumber(float value);             /**< @brief Constructs with a @c float value */

operator T() const;                        /**< @brief Casts to integer value of type @c T (eventually flooring) */
operator float() const;                    /**< @brief Casts to a float value */
T raw() const;                             /**< @brief Returns @c val without any casting */

template<unsigned char N2>
operator FixedPointNumber<T, N2>() const;  /**< @brief Casts to another FixedPointNumber with same underlying type */
template<typename T2>
operator FixedPointNumber<T2, N>() const;  /**< @brief Casts to another FixedPointNumber with same decimal part bits */
template<typename T2, unsigned char N2>
operator FixedPointNumber<T2, N2>() const; /**< @brief Casts to another FixedPointNumber */


FixedPointNumber<T, N>& operator+=(FixedPointNumber<T, N> const& rhs);
FixedPointNumber<T, N>& operator-=(FixedPointNumber<T, N> const& rhs);
FixedPointNumber<T, N>& operator*=(FixedPointNumber<T, N> const& rhs);
FixedPointNumber<T, N>& operator/=(FixedPointNumber<T, N> const& rhs);

FixedPointNumber<T, N> operator-() const;

bool operator==(FixedPointNumber<T, N> const& rhs) const;
bool operator>(FixedPointNumber<T, N> const& rhs) const;

private:
std::enable_if_t<std::is_integral_v<T>, T> val;
};

template<typename T, unsigned char N>
FixedPointNumber<T, N> operator+(FixedPointNumber<T, N> lhs, FixedPointNumber<T, N> const& rhs);
template<typename T, unsigned char N>
FixedPointNumber<T, N> operator-(FixedPointNumber<T, N> lhs, FixedPointNumber<T, N> const& rhs);
template<typename T, unsigned char N>
FixedPointNumber<T, N> operator*(FixedPointNumber<T, N> lhs, FixedPointNumber<T, N> const& rhs);
template<typename T, unsigned char N>
FixedPointNumber<T, N> operator/(FixedPointNumber<T, N> lhs, FixedPointNumber<T, N> const& rhs);


template<typename T, unsigned char N>
bool operator!=(FixedPointNumber<T, N> const& lhs, FixedPointNumber<T, N> const& rhs);
template<typename T, unsigned char N>
bool operator<(FixedPointNumber<T, N> const& lhs, FixedPointNumber<T, N> const& rhs);
template<typename T, unsigned char N>
bool operator>=(FixedPointNumber<T, N> const& lhs, FixedPointNumber<T, N> const& rhs);
template<typename T, unsigned char N>
bool operator<=(FixedPointNumber<T, N> const& lhs, FixedPointNumber<T, N> const& rhs);



///////////////////////////////////////////////////////////
////////////////////    DEFINITIONS    ////////////////////
///////////////////////////////////////////////////////////



template<typename T, unsigned char N>
FixedPointNumber<T, N>::FixedPointNumber() : val(0) {}

template<typename T, unsigned char N>
FixedPointNumber<T, N>::FixedPointNumber(T value, bool raw) : val(raw ? value : value << N) {}

template<typename T, unsigned char N>
FixedPointNumber<T, N>::FixedPointNumber(float value) {
std::uint32_t value_int = *reinterpret_cast<std::uint32_t*>(&value);
std::uint32_t mantissa = (value_int & 0x007FFFFF) | 0x00800000;
std::int8_t exponent = ((value_int >> 23) & 0x000000FF) - 150 + N;
if (exponent >= 0)
mantissa <<= exponent;
else
mantissa >>= -exponent;
val = (value_int & 0x80000000) ? -static_cast<T>(mantissa) : static_cast<T>(mantissa);
}

template<typename T, unsigned char N>
FixedPointNumber<T, N>::operator T() const {
return val >> (val >= 0) ? N : -N;
}

template<typename T, unsigned char N>
FixedPointNumber<T, N>::operator float() const {
if (val == 0) return 0.f; //trivial case, needed to prevent infinite loops for CLZ
std::uint32_t mantissa = (val >= 0) ? val : -val;
std::uint8_t fbs = 31; //first bit set : fbs = floor(log2(mantissa))
#if defined(__GNUC__)              //g++ compiler
fbs -= __builtin_clz(mantissa);
#elif defined(_MSC_VER)            //MSVC compiler
fbs -= __lzcnt(mantissa);
#else                              //unknown compiler : using naive algorithm
for (std::uint32_t copy = mantissa; copy & 0x80000000; --fbs) copy <<= 1;
#endif
if (fbs <= 23)
mantissa <<= 23 - fbs;
else
mantissa >>= fbs - 23;
mantissa &= 0x007FFFFF; //keeping mantissa
mantissa |= (val < 0) ? 0x80000000 : 0; //sign
mantissa |= static_cast<std::uint32_t>(127 + fbs - N) << 23; //exponent
return *reinterpret_cast<float*>(&mantissa);
}

template<typename T, unsigned char N>
T FixedPointNumber<T, N>::raw() const {
return val;
}

template<typename T, unsigned char N>
template<unsigned char N2>
FixedPointNumber<T, N>::operator FixedPointNumber<T, N2>() const {
if (N >= N2)
return { static_cast<T>(val >> (N - N2)), true };
else
return { static_cast<T>(val << (N2 - N)), true };
}

template<typename T, unsigned char N>
template<typename T2>
FixedPointNumber<T, N>::operator FixedPointNumber<T2, N>() const {
return { static_cast<T2>(val), true };
}

template<typename T, unsigned char N>
template<typename T2, unsigned char N2>
FixedPointNumber<T, N>::operator FixedPointNumber<T2, N2>() const {
if (N >= N2)
return { static_cast<T2>(static_cast<T2>(val) >> (N - N2)), true };
else
return { static_cast<T2>(static_cast<T2>(val) << (N2 - N)), true };
}

template<typename T, unsigned char N>
FixedPointNumber<T, N>& FixedPointNumber<T, N>::operator+=(FixedPointNumber<T, N> const& rhs) {
val += rhs.val;
return *this;
}

template<typename T, unsigned char N>
FixedPointNumber<T, N>& FixedPointNumber<T, N>::operator-=(FixedPointNumber<T, N> const& rhs) {
val -= rhs.val;
return *this;
}

template<typename T, unsigned char N>
FixedPointNumber<T, N>& FixedPointNumber<T, N>::operator*=(FixedPointNumber<T, N> const& rhs) {
val = ((+val) * (+rhs.val)) >> N;
return *this;
}

template<typename T, unsigned char N>
FixedPointNumber<T, N>& FixedPointNumber<T, N>::operator/=(FixedPointNumber<T, N> const& rhs) {
val = ((+val) << N) / rhs.val;
return *this;
}

template<typename T, unsigned char N>
FixedPointNumber<T, N> FixedPointNumber<T, N>::operator-() const {
return { static_cast<T>(-val), true };
}


template<typename T, unsigned char N>
bool FixedPointNumber<T, N>::operator==(FixedPointNumber<T, N> const& rhs) const {
return val == rhs.val;
}

template<typename T, unsigned char N>
bool FixedPointNumber<T, N>::operator>(FixedPointNumber<T, N> const& rhs) const {
return val > rhs.val;
}

template<typename T, unsigned char N>
FixedPointNumber<T, N> operator+(FixedPointNumber<T, N> lhs, FixedPointNumber<T, N> const& rhs) {
return lhs += rhs;
}

template<typename T, unsigned char N>
FixedPointNumber<T, N> operator-(FixedPointNumber<T, N> lhs, FixedPointNumber<T, N> const& rhs) {
return lhs -= rhs;
}

template<typename T, unsigned char N>
FixedPointNumber<T, N> operator*(FixedPointNumber<T, N> lhs, FixedPointNumber<T, N> const& rhs) {
return lhs *= rhs;
}

template<typename T, unsigned char N>
FixedPointNumber<T, N> operator/(FixedPointNumber<T, N> lhs, FixedPointNumber<T, N> const& rhs) {
return lhs /= rhs;
}

template<typename T, unsigned char N>
bool operator!=(FixedPointNumber<T, N> const& lhs, FixedPointNumber<T, N> const& rhs) {
return !(lhs == rhs);
}

template<typename T, unsigned char N>
bool operator<(FixedPointNumber<T, N> const& lhs, FixedPointNumber<T, N> const& rhs) {
return rhs > lhs;
}

template<typename T, unsigned char N>
bool operator>=(FixedPointNumber<T, N> const& lhs, FixedPointNumber<T, N> const& rhs) {
return !(rhs > lhs);
}

template<typename T, unsigned char N>
bool operator<=(FixedPointNumber<T, N> const& lhs, FixedPointNumber<T, N> const& rhs) {
return !(lhs > rhs);
}

#endif

So to resume it, the class FixedPointNumber contains only one variable of integral type T, which the N least significant bits are the decimal part, and the sizeof(T) - N most significant bits are the integral part.
What was aimed first is to have non-integer value smaller than a float, and all the syntax and casting to go with it.
Operators +,-,*,/ and !=,<, >=, <= are not methods of the class in order to have better encapsulation.
Here is an example for a main.cpp file :

#include "FixedPointNumber.hpp"
#include <iostream>
using namespace std;

using Nbr8 = FixedPointNumber<uint8_t, 8>;     //domain : [0, 1[    epsilon = 1/256          8 bits
using Nbr16A = FixedPointNumber<int16_t, 11>;  //domain : [-16, 16[ epsilon = 1/2048        16 bits
using Nbr16B = FixedPointNumber<uint16_t, 15>; //domain : [-1, 1[   epsilon = 1/32768       16 bits

int main() {
    {
    Nbr8 a = 0.37f, b = 0.52f;
    float af = 0.37f, bf = 0.52f;
    cout << af << " -> " << float(a) << "\t\tError (%) : " << 100 * (af - float(a)) / af << endl;
    cout << bf << " -> " << float(b) << "\t\tError (%) : " << 100 * (bf - float(b)) / bf << endl;
    cout << af + bf << " -> " << float(a + b) << "\t\tError (%) : " << 100 * (af + bf - float(a + b)) / (af + bf) << endl;
    cout << "Nbr8 recap : 25% bits for about 0.5% error if interval correctly chosen" << endl << endl;
    }
    {
    Nbr16B a = 0.37f, b = 0.52f;
    float af = 0.37f, bf = 0.52f;
    cout << af << " -> " << float(a) << "\t\tError (%) : " << 100 * (af - float(a)) / af << endl;
    cout << bf << " -> " << float(b) << "\t\tError (%) : " << 100 * (bf - float(b)) / bf << endl;
    cout << af + bf << " -> " << float(a + b) << "\t\t\tError (%) : " << 100 * (af + bf - float(a + b)) / (af + bf) << endl;
    cout << "Nbr16 recap : 50% bits for about 0.002% error if interval correctly chosen" << endl << endl;

    Nbr16A a2 = a, b2 = b;
    cout << "switching point position, less precision but wider domain !" << endl;
    cout << "a2 = " << float(a2) << " b2 = " << float(b2) << " AGAINST a1 = " << float(a) << " b1 = " <<float(b) << endl;
    cout << "Notice that gap between two consecutive values is constant in a domain, contrary to floating point numbers." << endl << endl;
    }
    return 0;
} 

Complete and updated code can be found here.

Answer 1

Looks really good!

A few improvements:

Confusing construction.

Construction from raw is making your constructors more complicated than they need to be.

Your class would be easier to work with if constructing from a value ALWAYS constructs by actual value.

Also consider that boolean arguments are often hard to understand at the call site. Can someone not familiar with your library tell what the following line does without having to sift through your header? No, and it's a problem here since raw construction is clearly going to be an unfamiliar edge case.

FixedPointNumber<char, 4> val(12, true);

To fix these issues, I would instead add a static member function, and get rid of the (T,bool) constructor entirely:

static FixedPointNumber<T, N> from_raw(T data);

My example becomes proper self-documenting code at the call site:

auto val = FixedPointNumber<char, 4>::from_raw(12);

No conversion to/from double

A bit of a no-brainer, but that would definitely be nice.

In fact... it would be nice to support arbitrary floating point formats through a traits type.

Concerns about overflow behavior of multiply/division operation

val = ((+val) * (+rhs.val)) >> N;

I don't really like how inconsistent you are being with the overflow behavior. char and short get promoted, but not int or long? I would rather see everything get promoted, or nothing.

Edit: followup:

I'm not sure to understand what you meant by "through a traits type"

Imagine that you had a type that looks very roughly like this, and your conversion functions used these values to build the resulting float value.

template<typename T>
struct float_traits;

template<>
struct float_traits<float> {
  static constexpr int mantissa_offset = 0;
  static constexpr int mantissa_bits = 23;

  static constexpr int exponent_offset = 23;
  static constexpr int exponent_bits = 8;

  static constexpr int sign_bit_offset = 31;
};

Adding support for double or half-precision floats would just be a matter of adding the proper specialization to float_traits, which a user can even do within their own codebase.

Answer 2

I recently had my interest in fixed point math piqued as part of a side project I was doing, so this is great to see! Having a C++ class for fixed point numbers would make things so easy!

I'm guessing that the weird formatting is due to copy/paste issues and that your actual code uses indentation. If not, it definitely should.

Description

I notice throughout your comments you say "decimal part". However, you don't use any decimal representation. I was thinking that maybe you were working in BCD or something like that. I would change all references to "decimal" to be "fractional" to be more precise.

Don't Use using namespace std

You've written:

using namespace std;

in your header main.cpp file. That means that every file which includes your header now has all of the std namespace defined, too. If I have my own max() function that's not in std and I include your header, I will now get conflicts on my max() function. See here for more details on why this isn't a good idea.

Usage

Seeing the examples of how to use this type in your example main.cpp file left me very confused, even with a comment describing the range. The way you have it now, I have to know how many bits are in a given type's representation, then subtract from that the number of bits I want for the fractional part in order to figure out the range I'll end up with. I also have to make sure that the type I supply has enough bits for the representation. (What happens if I do using Nbr32 = FixedPointNumber<uint8_t, 17>;?)

Furthermore, the type I supply may be unsigned, but the range of the resulting type can still cover negative values. Does it make sense to have an unsigned fixed point type and a signed fixed point type? I'm not sure. But it is odd to supply an unsigned type and have it end up being signed.

I'm not an expert at templates, so I'm not entirely sure what's possible. I think it would be better to have the template take the number of bits for the integral part and the number of bits for the fractional part and choose the type it uses internally based on that and not require a caller to figure it out.

In other words, I'd like to use it like this:

using Fixed16_16 = FixedPointNumber<16, 16>;
using Fixed8_4 = FixedPointNumber<8, 4>;

As I say, I don't know whether it's possible to make that work, but it sure would be nice. If you can get closer to that, it would be great.

Naming

I'm all for long descriptive names. However, I do feel like FixedPointNumber is too long. We don't call float a floatingPointNumber or int an intNumber. I think it would be fine as FixedPoint or even Fixed (though be aware that Apple has used that type name in the past for 16.16 fixed point numbers).

Future Directions

I'd love to see a whole math library for this type. Things like trigonometric and transcendental functions would be helpful. (You might look into cordics if you plan to pursue something like that.)