Fixed point arithmetic based on compilation based metaprogram. Multiplication overflow?

Question

I am currently implementing a three-dimensional raster compiler, although metaprogramming a template.

After implementing algebraic foundations (2d / 3d / 4d vectors, arithmetic of 3x3 / 4x4 matrices, aabb2d / 3d for extraction purposes, etc.), I noticed that integer arithmetic is not good enough for vector transformations. So I started writing a fixed-point implementation:

The library has a basic header with declarations of common metafunctions that algebraic types will be implemented (to ensure a uniform interface). Here is the set of definitions used by a fixed-point implementation:

template<typename T> struct zero; //Gets the zero value of a type of data. For example, zero<std::integral_constant<int>> returns std::integral_constant<int,0> template<typename T> struct one; /* Algebraic operations: */ template<typename LHS , typename RHS> struct add; template<typename LHS , typename RHS> struct sub; template<typename LHS , typename RHS> struct mul; 

I decided to use the decimal point instead of binary-based, because it allows me to easily write the decimal number interface (the decimal alias is described below). The following is the implementation of the power metafile and decimal shift of digits:

 template<int base , int exponent> struct positive_pow : public std::integral_constant<long long int , base * positive_pow<base,exponent-1>::value> {}; template<int base> struct positive_pow<base,0> : public std::integral_constant<long long int,1> {}; template<int number , int shift> struct decimal_leftshift : public std::integral_constant<long long int,number * positive_pow<10, shift>::value> {}; template<int number , int shift> struct decimal_rightshift : public std::integral_constant<long long int,number / positive_pow<10, shift>::value> {}; template<bool CONDITION , int NUMBER , int SHIFT> struct decimal_shift_chooser { using shifter = decimal_leftshift<NUMBER,SHIFT>; }; template<int NUMBER , int SHIFT> struct decimal_shift_chooser<false,NUMBER,SHIFT> { using shifter = decimal_rightshift<NUMBER,-SHIFT>; }; //This metafunction shifts to one direction or other depending on the sign of the shift count passed: template<int number , int shift> struct decimal_shift { using shifter = typename decimal_shift_chooser<( shift >= 0 ) , number , shift>::shifter; static const long long int value = shifter::value; }; 

Here is a fixed point type implementation. The internal implementation uses long long to store numbers. So, I have 64 bits, i.e. 19 decimal digits approximately:

 using fpbits = long long int; using fdcount = unsigned int; //Fractional decimal digits count (Precision) const fdcount DEFAULT_FRACTIONAL_PRECISION = 8; template<fpbits BITS , fdcount PRECISION = DEFAULT_FRACTIONAL_PRECISION> struct fixed_point { operator float() { return (float)BITS * std::pow(10.0f,-(float)PRECISION); }; }; //An alias to define decimal numbers with default precision: template<int mantissa , int exponent = 0> // MANTISSA x 10^EXPONENT using decimal = fixed_point<decimal_shift<mantissa , DEFAULT_FRACTIONAL_PRECISION + exponent>::value>; /* Previously defined common metafunctions implementation */ template<fpbits BITS , fdcount PRECISION> struct zero<fixed_point<BITS,PRECISION>> : public fixed_point<0,PRECISION> {}; template<fpbits BITS , fdcount PRECISION> struct one<fixed_point<BITS,PRECISION>> : public fixed_point<decimal_leftshift<1,PRECISION>::value,PRECISION> {}; template<fpbits BITS1 , fdbits BITS2 , fbcount PRECISION> struct add<fixed_point<BITS1,PRECISION> , fixed_point<BITS2,PRECISION>> : public fixed_point<BITS1+BITS2 , PRECISION> {}; template<fpbits BITS1 , fdbits BITS2 , fbcount PRECISION> struct sub<fixed_point<BITS1,PRECISION> , fixed_point<BITS2,PRECISION>> : public fixed_point<BITS1-BITS2 , PRECISION> {}; template<fpbits BITS1 , fdbits BITS2 , fbcount PRECISION> struct mul<fixed_point<BITS1,PRECISION> , fixed_point<BITS2,PRECISION>> : public fixed_point<decimal_rightshift<BITS1*BITS2,PRECISION>::value , PRECISION> {}; 

As I said, the implementation has 19 decimal digits. Therefore, if we use 8 decimal digits of precision , and we multiply pi by two, the result can be represented, right? Like in this example:

 using pi = decimal<3141592 , -6>; //3141592 x 10^-6 (3,141592) This fits in our 8 precision implementation. using pi_2 = mul<pi,decimal<2>>; //pi*2 is 314159200 * 200000000 = 62831840000000000 >> 8. //The inmediate result of the product fits in a //long long (Has 17 decimal digits), so no problem? int main() { std::cout << "pi: " << pi() << std::endl; std::cout << "2*pi: " << pi_2() << std::endl; } 

But this prints:

pi: 3.14159
pi * 2: -1e-07

As you can see, the result is a very small negative number, so I think there is an integer overflow in the calculation.

Where is the problem? Is this an integer overflow, and if it's true, where and how can I fix it?

Here is a complete example.

Answer 1

Your decimal_rightshift has an int parameter, and you pass it BITS1*BIST2 . Replace each int in the long long int metaprogram and everything should work.

Answer 2

By the way, your one wrong. Correct implementation:

 template<fpbits BITS , fbcount PRECISION> struct one<fixed_point<BITS,PRECISION>> : public fixed_point<decimal_leftshift<1, PRECISION>::value, PRECISION> {}; 

That is, assuming that one should actually be the value of one.