Арифметика с фиксированной точкой на основе метапрограммирования во время компиляции. Умножение переполнения?

В настоящее время я реализую 3D-растр во время компиляции через шаблонное метапрограммирование.

После реализации алгебраических основ (2d / 3d / 4d векторы, арифметика матриц 3×3 / 4×4, aabb2d / 3d для отбраковки и т. Д.) Я заметил, что целочисленная арифметика недостаточно хороша для векторных преобразований. Итак, я начал писать реализацию с фиксированной запятой:

Библиотека имеет базовый заголовок с объявлениями общих метафункций, которые алгебраические
типы будут реализовывать (чтобы обеспечить единый интерфейс). Вот набор определений, используемых реализацией с фиксированной запятой:

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;

Я решил использовать основанную на десятичной запятой фиксированную точку вместо двоичной, потому что это позволяет мне написать easilly интерфейс десятичного числа ( decimal псевдоним предоставлен ниже).
Вот реализация степенной метафункции и сдвига десятичных цифр:

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;
};

Вот реализация типа с фиксированной запятой. Внутренняя реализация использует long long хранить цифры номера. Итак, у меня есть 64 бита, то есть 19 десятичных цифр приближено минимаксный:

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> {};

Как я уже говорил, реализация имеет 19 десятичных цифр. Так что, если мы используем Точность 8 десятичных цифр и мы умножаем число пи на два, результат можно представить, верно?
Как в этом примере:

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;
}

Но это печатает:

пи: 3,14159
пи * 2: -1е-07

Как вы можете видеть, результатом является очень небольшое отрицательное число, поэтому я думаю, что где-либо в вычислении происходит переполнение целого числа со знаком.

В чем проблема? Это целочисленное переполнение, и если это правда, где и как я могу это исправить?

Вот это полный бегущий пример.

4

Решение

Ваш decimal_rightshift имеет int параметр и вы передаете BITS1*BIST2 к этому. Заменить каждый int в вашей метапрограмме с long long int и все должно работать.

4

Другие решения

Кстати, ваш one это неверно. Правильная реализация:

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

То есть при условии one на самом деле должно быть значение один.

1

По вопросам рекламы [email protected]