Игрушечная имлементация чисел с фиксированной точкой в C++
В C++ нет базового типа чисел с фиксированной точкой, в стандартной библиотеке также нет классов для них. В тоже время работа с числами с плавающей точкой (double, float) часто может быть неочевидна (например, ответьте на вопрос: ассоциативна ли операция сложения над ними?), вдобавок язык предоставляет (часто критикуемую) возможность перегрузки арифмитических операторов, подталкивая нас к созданию собственного типа данных.
Прежде чем писать код, давайте повторим мат. часть, а именно о представление чисел в типах uint8_t, int8_t и особенностях арифмитических операциях над ними. Итак, сложенение двух uint8_t происходит по модулю 256, то есть 1+2 = 3, но 1 + 255 = 0, для int8_t отрицательные значения можно ввести следущим образом: отрицательные числа соответсвуют тем безнаковым числам из uint8_t которые складываясь по модулю 256 дадут ноль, то есть -1 будем в памяти выглядить как 255 (FF). Границы типа int8_t -128…+127, для отрицательных чисел старший бит всегда равен 1. При умножении двух int8_t получаем результат типа int16_t, частное от деления int16_t на uint8_t будет иметь тип uint8_t. Все эти сведения носят аболютно тривиальный характер, но, они необходимы для дальнейшего понимания статьи.
Итак, перейдём к основной идее: что если мы мысленно возьмем значение типа int8_t и скажем, что теперь это не число единиц, а скажем, число ¼ (проговорим словами: это число показывает сколько четвертых частей в исходном числе)? После чего инкапсулируем эту перменную в поле класса и перегрузим для него основные арифмитичекие операторы и напишем свой operator string () для правильного вывода таких чисел. Ниже, можно посмотреть, что получается из этой идеи.
#include
#include
#include
#include
#include
#include
template
constexpr T ipow(T num, unsigned int pow)
{
return (pow >= sizeof(unsigned int)*8) ? 0 :
pow == 0 ? 1 : num * ipow(num, pow-1);
}
// fills and return given number of ones in the least significant bits of a byte
constexpr uint8_t mask(uint8_t num)
{
return num == 0 ? 0 : (mask(num - 1) << 1) | 1;
}
// FractionLength - how many bits are after a period
template
class FixedPoint
{
public:
explicit FixedPoint(int decimal, unsigned int fraction = 0): val(0)
{
if (decimal > max_dec || decimal < min_dec || (decimal == min_dec && fraction) || (fraction >= full_fraction))
{
throw std::invalid_argument("It won't fit our so few bits");
}
int8_t sign = decimal > 0 ? +1 : -1;
val |= fraction;
val |= (decimal << FractionLength);
val *= sign;
}
explicit FixedPoint(double v): val(0)
{
double decimal_double = 0.0;
double fraction = std::modf(v, &decimal_double);
if (decimal_double > max_dec || decimal_double < min_dec)
{
throw std::invalid_argument("It won't fit our so few bits");
}
int8_t decimal_part = static_cast(decimal_double);
int8_t sign = v > 0 ? +1 : -1;
decimal_part = std::abs(decimal_part);
uint32_t fraction_decimal = std::abs(fraction)* ipow(10, FractionLength + 1);
uint8_t count = fraction_decimal / fraction_unit_halv;
count += count & 0x01;
count >>= 1;
if (count && sign == -1 && decimal_part == min_dec_abs)
{
throw std::invalid_argument("It won't fit our so few bits");
}
if (count == full_fraction)
{
decimal_part += 1;
auto decimal_part_signed = sign * decimal_part;
if (decimal_part_signed > max_dec || decimal_part_signed < min_dec)
{
throw std::invalid_argument("It won't fit our so few bits");
}
}
else
{
val |= count;
}
val |= (decimal_part << FractionLength);
val *= sign;
}
FixedPoint operator + (const FixedPoint& r) const
{
return makeFx(val + r.val);
}
FixedPoint operator - (const FixedPoint& r) const
{
return makeFx(val - r.val);
}
FixedPoint operator - () const
{
return makeFx(-val);
}
FixedPoint operator * (const FixedPoint& r) const
{
uint16_t temp = val * r.val;
temp >>= (FractionLength - 1);
uint8_t unit = temp & 0x01;
return makeFx((temp >> 1) + unit);
}
FixedPoint operator / (const FixedPoint& r) const
{
uint16_t left = val;
left <<= (FractionLength + 1);
uint8_t temp = left / r.val;
uint8_t unit = temp & 0x01;
return makeFx((temp >> 1) + unit );
}
operator std::string() const
{
std::stringstream res;
uint8_t temp = val;
auto fraction = temp & fraction_mask;
if (sign_mask & temp)
{
res << '-';
temp = ~temp + 1;
fraction = temp & fraction_mask;
}
res << (temp >> FractionLength);
if (fraction)
{
res << '.' << std::setw(FractionLength) << fraction * fraction_unit;
}
return res.str();
}
private:
int8_t val;
static constexpr uint8_t decimal_lenght = CHAR_BIT - FractionLength;
static constexpr uint8_t max_dec = (1 << (decimal_lenght - 1)) - 1;
static constexpr int8_t min_dec_abs = (1 << (decimal_lenght - 1));
static constexpr int8_t min_dec = -min_dec_abs;
static constexpr uint32_t fraction_unit = ipow(10, FractionLength) / (1 << FractionLength);
static constexpr uint32_t fraction_unit_halv = ipow(10, FractionLength + 1) / (1 << (FractionLength + 1));
static constexpr uint8_t full_fraction = ipow(2, FractionLength);
static constexpr uint8_t sign_mask = 0x80;
static constexpr uint8_t fraction_mask = mask(FractionLength);
static constexpr uint8_t decimal_mask = 0xFF & ~FractionLength;
explicit FixedPoint(): val(0)
{
}
static FixedPoint makeFx(int8_t v)
{
FixedPoint fp;
fp.val = v;
return fp;
}
};
template
std::ostream& operator << (std::ostream& out, const FixedPoint& number)
{
out << std::string(number);
return out;
}
template
const FixedPoint operator + (const FixedPoint& l, int r)
{
return l + FixedPoint(r);
}
template
const FixedPoint operator + (int l, const FixedPoint& r)
{
return r + FixedPoint(l);
}
template
const FixedPoint operator - (const FixedPoint& l, int r)
{
return l - FixedPoint(r);
}
template
const FixedPoint operator - (int l, const FixedPoint& r)
{
return r - FixedPoint(l);
}
template
const FixedPoint operator * (const FixedPoint& l, int r)
{
return l * FixedPoint(r);
}
template
const FixedPoint operator * (int l, const FixedPoint& r)
{
return r * FixedPoint(l);
}
template
const FixedPoint operator / (const FixedPoint& l, int r)
{
return l / FixedPoint(r);
}
template
const FixedPoint operator *= (FixedPoint& l, const FixedPoint& r)
{
l = l * r;
return l;
}
template
const FixedPoint operator += (FixedPoint& l, const FixedPoint& r)
{
l = l + r;
return l;
}
using FixedPoint_2 = FixedPoint<2>;
using FixedPoint_4 = FixedPoint<4>;
Пояснения:
Самая длинная и сложная функция здесь — конструктор FixedPoint (double v), он нужен только для удобства тестирования — пропустите при первом чтении
Конструктор FixedPoint (int decimal, unsigned int fraction = 0) — гораздо проще, но, в основном, он нужен для перегруженных арифметических операторов, где один из аргументов типа int
Конструкторы контролируют переполнения поля val, но арифметические операторы — нет. Это осознанное решение: неудобно изначально работать с невалидными числами, которые обрезались и гадать почему вся программа работает неверно, в тоже время контролировать это всюду нет нужды, также как компилятор не контролирует это для встроенных типов
Арифметические операторы вне класса — тривиально опираются на операторы опредленные в классе
Сложение и вычитание — тривиально, нет разницы, что складывать, сотые части (четвертые) или целые
Приватный конструктор и функция makeFx — a workaround, что б «заливать» в поле val, в некоторых операторах
Что такое творится в operator * и operator / ? Поясняю: если вы умножите 2 числа представляющих собой количество ¼ вы получите число представляющее из себя количество 1/16 — поэтому сдвинем их вправо на 2 разряда, но, сдвига так, мы делаем грубое округление — учтём последний сдвинутый разряд, то есть получив число 0.102 до сдвига, без этого мы бы теряли его полность, а так делаем по стандартным правилам округления. С оператором деления немного другая история: при делении количесво ¼ друг на друга результат уезжает вправо 2 разряда, но в коде я зарнее уношу делимое влево на 3 разряда — 3ий разряд опять же нужен для лучшего округления.
string operator () делает 3 вещи, выделяет целую часть и выводит её как целое, выделяет дробную часть и пересчитывает её в десятичнное число (число сотых) и выводит его как целое, последняя — опредление знака, делаем это через старший бит, строка ~temp + 1 тоже самое, что унарный минс, просто унарный минус странно использовать над безнаковым типом.
Приведу небольшой примерчик, где посмотрим как наш тип работает
template
T poly(T x)
{
return (2*x +1)*x - 3;
}
double x = 0.261799;
FixedPoint_4 fx{x};
std::cout << poly(x) << ' ' << poly(fx) << std::endl; Результат работы:
-2.60112 -2.6250
По-моему, неплохо, для типа созданного «на коленке!»
Итак, что можно сделать, что б убрать слово «игрушечный» из аттрибутов класса:
использовать базовый тип побольше, лучше всего int32_t — промеуточные результаты будут в int64_t не придётся придумывать какое-то «длинное» умножение
перегрузить больше операторов
покрыть тестами
