В этом небольшом рецепте, на который нас сподвигла статья с HabrHabr «Арифметика fixed-point на C++», мы покажем как организовать класс с базовыми операциями арифметики.
Арифметика чисел с фиксированной точкой — это способ обращения с числами, которые не могут быть представлены как целое число (т.е числа дробные или иррациональные, а также числа из других множеств с похожим поведением), и которые требуют особого набора операций. Данный способ позволяет достаточно эффективно, не привлекая чисел с плавающей запятой, добиваться сравнительно быстрых и умеренно точных результатов. Также, поскольку такая арифметика использует в своей основе целочисленный тип, то подобные операции могут быть использованы в микроконтроллерах, а также в иных устройствах, в которых нет аппаратно реализованных команд для работы с плавающей точкой.
В качестве идеи, а также основы кода, мы взяли реализацию на C++ из вышеупомянутой статьи и перевели ее на D, несколько переработав и исправив основной код. В частности, внутреннюю переменную, которая хранит в себе целочисленный тип для операций, мы сделали приватной с соответствующими методами доступа, которые носят одно и тоже имя — value, также переименовали один из методов fixed2float в toFloat, а также вынесли ряд операций в соответствующие перегрузки для операторов +,-, * и /. Помимо этого, параметр для экспоненты мы вынесли в соответствующий шаблонный параметр (DIGITS), а сопутствующий ему параметр для величины абсолютной погрешности (EPS) перенесли в шаблонный параметр для функции квадратного корня.
Сам код выглядит следующим образом:
class FixedPoint(uint DIGITS)
{
private {
uint _value;
}
this(uint value = 0)
{
_value = value;
}
public
{
static {
FixedPoint fromInt(uint value)
{
return new FixedPoint(value * DIGITS);
}
FixedPoint fromFloat(float value)
{
return new FixedPoint(
cast(uint) (value * DIGITS)
);
}
FixedPoint sqrt(uint EPS)(FixedPoint k)
{
import std.math : abs;
FixedPoint tmp = new FixedPoint(k.value / 2);
uint min = 0;
uint max = k.value;
FixedPoint quick = new FixedPoint;
do {
tmp.value((min + max) / 2);
quick = tmp * tmp;
if(abs(quick.value - k.value) < EPS)
{
return tmp;
}
if(quick.value > k.value)
{
max = tmp.value;
}
else
{
min = tmp.value;
}
} while (true);
}
}
uint value()
{
return _value;
}
void value(uint value)
{
_value = value;
}
float toFloat()
{
return (cast(float) _value) / DIGITS;
}
FixedPoint opBinary(string op)(FixedPoint rhs) if ((op == "+") || (op == "-"))
{
return mixin(`new FixedPoint(_value` ~ op ~ `rhs.value)`);
}
FixedPoint opBinary(string op : "*")(FixedPoint rhs)
{
uint c = _value * rhs.value;
if(c / rhs.value != _value)
{
// Overflow!
uint i1 = _value / DIGITS;
uint i2 = rhs.value / DIGITS;
uint f1 = (_value & (DIGITS - 1));
uint f2 = (rhs.value & (DIGITS - 1));
return new FixedPoint((i1 * i2) * DIGITS + (f1 * f2) / DIGITS + i1 * f2 + i2 * f1);
}
else
{
return new FixedPoint(c / DIGITS);
}
}
FixedPoint opBinary(string op : "/")(FixedPoint rhs)
{
enum MASK = 1 << 21;
if(_value > MASK)
{
// Overflow!
uint i = _value / DIGITS;
uint f = _value & (DIGITS-1);
return new FixedPoint(((i * DIGITS) / rhs.value) * DIGITS + (f * DIGITS) / rhs.value);
}
else
{
return new FixedPoint((_value * DIGITS) / rhs.value);
}
}
}
}А испытать можно к примеру так:
import std.stdio;
void main()
{
alias FixedP = FixedPoint!256;
auto a = FixedP.fromFloat(5);
auto b = FixedP.fromFloat(2);
a.toFloat.writeln;
(a / b).toFloat.writeln;
FixedP
.sqrt!20(b)
.toFloat
.writeln;
}Алгоритм простой, и его улучшения приветствуются, и честно говоря, нам несколько стыдно от того, что мы раньше не додумались до этого сами…