Класс с фиксированной точкой
ОГЛАВЛЕНИЕ
Введение
Было решено начать работу над многократно используемым классом для математики с фиксированной точкой. Другой побуждающей причиной было желание узнать, действительно ли на C++ можно написать класс, объекты которого будут вести себя аналогично встроенным числовым типам. Были поставлены цели, что этот класс с фиксированной точкой:
- должен быть пригоден к использованию в качестве вставной замены для существующих типов с плавающей точкой,
- должен быть быстрее, чем эмуляция плавающей точки на аппаратном обеспечении, не поддерживающем плавающую точку,
- должен быть в общем пригодным к использованию во многих обстоятельствах,
- должен быть красивым по сути, безупречно написанным, и документированным для последующих ссылок.
После краткого введения в математику с фиксированной точкой в статье объясняется, как использовать класс fixed_point. Затем разъясняется реализация класса.
Краткое введение в математику с фиксированной точкой
Число с фиксированной точкой можно разделить на необязательный знаковый разряд, целое и дробную часть.
Целая часть состоит из i битов, дробная часть состоит из f битов.
Суммарное значение числа с фиксированной точкой V равняется:
Число с фиксированной точкой имеет формат i.f.
Диапазон беззнаковых чисел с фиксированной точкой - от 0 до 2^i-1. Диапазон чисел с фиксированной точкой со знаком - от -2^i до 2^i-1. Точность числа с фиксированной точкой равняется 2^(-f).
Пример: предположим, что есть число с фиксированной точкой в 16 битов, в формате 7.8, с дополнительным знаковым битом, при этом биты установлены в 0000 0110 1010 0000 (то есть, 0x06A0 в шестнадцатеричной системе). Значение этого числа с фиксированной точкой +6.625.
Если имеется такой набор битов, независимо от формата числа с фиксированной точкой, с ним можно обращаться как с целым и выполнять над ним действия целочисленной математики. Небольшие сложности возникают только при выполнении умножения или деления: необходимо убедиться, что десятичная точка находится в правильной позиции. Это приблизительно сопоставимо с тем, как вы учились умножать вручную в школе: в конце умножения вы должны были сосчитать разряды после десятичной точки и затем поставить десятичную точку в правильное место.
Следствие для компьютера в том, что быстрые целочисленные команды могут использоваться для выполнения вычислений. Недостаток в том, что диапазон и точность чисел с фиксированной точкой обычно меньше, чем у чисел с плавающей точкой.
Установка проекта
Если вы просто хотите использовать класс fixed_point в своем коде, то вам всего лишь нужно скачать проект. Вы найдете fixed_point.h в папке include/fpml.
Но проект также содержит тестовый код, включая тестирование модулей и контрольные задачи. Для их выполнения вам также потребуется CMake (версия 2.6 или выше), который можно скачать с сайта http://www.cmake.org/. Запустите CMake и укажите в нем каталог, в котором вы сохранили загруженный проект, и используйте его для создания решений и проектов Visual Studio. Затем вы можете загрузить FPMATH.sln, который будет содержать тестовые проекты.
Использование класса fixed_point
Для начала нужно включить заголовочный файл fixed_point.h:
#include <fixed_point.h>
Класс fixed_point<B, I, F> определен внутри пространства имен fmpl. Для его использования можно писать перед именем класса fpml:: везде, где он необходим, или использовать утверждение using:
using namespace fmpl;
Это два принципиально разных сценария использования класса fixed_point<B, I, F>. Вы можете использовать его в только что написанном коде, в котором требуется математика с фиксированной точкой, или в котором вы контролируете поведение, т.е., устанавливаете число целых и дробных битов. Чрезвычайно простой пример кода первого сценария использования может выглядеть так:
#include <fixed_point.h>
using namespace fpml;
main()
{
fixed_point<int, 16> a = 256;
fixed_point<int, 16> b = sqrt(a);
}
Разумеется, можно использовать все остальные операторы и функции. Класс fixed_point<B, I, F> содержит реализации для всех важных операторов и функций, которые вы можете принимать как должное при работе с числами с плавающей точкой.
Второй сценарий использования – это сценарий переноса, когда код уже существует, и был написан с использованием типов с плавающий точкой или с плавающей точкой двойной точности. Если вы тщательно проверили код на наличие проблем с диапазоном и точностью и приняли решение, что код по-прежнему будет работать, если вычисления с плавающей точкой заменить на вычисления с фиксированной точкой, то вы можете использовать #define для переноса кода с выполнением незначительных изменений в исходном коде:
#include <fixed_point.h>
#define double fpml::fixed_point<int, 16>
… original code here, unchanged …
#undef double
Однако необходимо быть очень осторожным, так как диапазон и точность чисел с фиксированной точкой будут отличаться от тех, которые имеют исходные числа с плавающей точкой, и это приведет к появлению ошибок в исходном коде. Особенно когда используются такие функции, как sqrt, log иди sin, распространение ошибок чисел с фиксированной точкой больше не является линейным, и можно столкнуться с неожиданностями.
Реализация класса fixed_point
Одна из целей заключается в том, что код должен быть как можно более обобщенным. Для достижения этого можно применять шаблоны. Были использованы три параметра шаблона:
template<typename B, unsigned char I, unsigned char F
= std::numeric_limits<B>::digits - I>
class fixed_point
{
BOOST_CONCEPT_ASSERT((boost::Integer<B>));
BOOST_STATIC_ASSERT(I + F == std::numeric_limits<B>::digits);
...
private:
B value_;
}
B – базовый тип. Это должен быть целый тип. Данный тип используется для большинства вычислений. Примеры – беззнаковый символьный тип, знаковое короткое целое, или целое. Этот тип может быть выбран в зависимости от размера, точности и требований к производительности. Если выбран беззнаковый тип, поведение класса fixed_point беззнаковое; в противном случае оно знаковое. Знаковое поведение более точно совпадает с поведением встроенных типов с плавающей точкой.
Оператор BOOST_CONCEPT_ASSERT((boost::Integer<B>)) в теле класса обеспечивает, что только целые типы могут использоваться в качестве базового типа. Обратите внимание, что базовый тип не используется здесь в смысле базового класса. Более того, класс fixed_point не является производным ни от какого базового класса, будучи самостоятельным.
I – число битой целой части, не считая знаковый бит. Оно определяет диапазон чисел, который может быть представлен.
F – число битов дробной части. Оно определяет точность чисел, которая может быть представлена. Нет необходимости устанавливать F, когда создается экземпляр шаблона, так как оно всегда может быть автоматически вычислено из базового типа B и числа целых битов I. Но если оно задано, оно должно быть правильным. Оператор BOOST_STATIC_ASSERT(I + F == std::numeric_limits<B>::digits) в теле класса обеспечивает выполнение этого условия.
Число битов базового типа должно удовлетворять следующей формуле: #(B)=S+I+F, где:
- #(B) – число битов базового типа,
- S равен 1 для знаковых типов и 0 для беззнаковых типов,
- I – число целых битов,
- F – число дробных битов.
В следующей таблице перечислены используемые типы и требования к I и F:
| B | #(B) | S | I | F |
| знаковый символьный | 8 | 1 | 7…1 | 0…6 |
| беззнаковый символьный | 8 | 0 | 8…1 | 0…7 |
| короткий целый | 16 | 1 | 15…1 | 0…14 |
| беззнаковый короткий целый | 16 | 0 | 16…1 | 0…15 |
| целый | 32 | 1 | 31…1 | 0…30 |
| беззнаковый целый | 32 | 0 | 32…1 | 0…31 |
Объекты типа fixed_point<B, I, F> имеют такой же размер, что и лежащий в их основе тип B. Класс был тщательно спроектирован так, чтобы не навязывать дополнительные требования к размеру.
Путем использования всех доступных битов для целой части достигается целочисленное поведение. Но можно вызывать определенные функции, такие как sqrt или log и т.д., для целых чисел. Далее об этих функциях рассказывается более подробно.
Типы больше 32 бит еще не поддерживаются. Одна причина этого в том, что для некоторых функций требуются в два раза большие внутренние результаты. Если разрешить 64 битовые типы, то эти внутренние результаты будут иметь размер 128 бит. Вторая причина в том, что если вы можете выделить 64 бита для типа с фиксированной точкой, то вы также сможете использовать тип с двойной точностью во многих случаях.
Создание и преобразование
Если нужно использовать объект fixed_point<B, I, F>, его сначала нужно создать. Класс предоставляет набор конструкторов. Имеется конструктор по умолчанию без параметров:
fixed_point()
{ }
Как и для встроенных типов, отсутствует инициализация. После выполнения этого конструктора значение неопределенное.
Имеется конструктор, допускающий создание из целых значений. Он реализован в виде шаблона:
template<typename T> fixed_point(T value) : value_((B)value << F)
{
BOOST_CONCEPT_ASSERT((boost::Integer<T>));
}
Этот конструктор принимает целое значение типа T и преобразует его в тип fixed_point<B, I, F>. Преобразование из целого формата в формат с фиксированной точкой выполняется путем сдвига на F разрядов влево, чтобы положение двоичной точки было правильным.
Имеется конструктор, допускающий создание из логического значения:
fixed_point(bool value) : value_((B)(value * power2<F>::value))
{ }
Объект fixed_point<B, I, F>, созданный из ложь, имеет значение 0.0, а объект fixed_point<B, I, F>, созданный из истина, имеет значение 1.0.
Имеется ряд конструкторов, допускающих создание из значений с плавающей точкой:
fixed_point(float value) : value_((B)(value * power2<F>::value))
{ }
fixed_point(double value) : value_((B)(value * power2<F>::value))
{ }
fixed_point(long double value) : value_((B)(value * power2<F>::value))
{ }
Эти конструкторы принимают значение с плавающей точкой типа float, double или long double и преобразуют его в тип(у) fixed_point<B, I, F>. Преобразование выполняется путем умножения с подходящим показателем степени 2 и приведения результата к базовому типу B. Подходящий показатель степени 2 определяется по числу битов F дробной части. Это соответствует операции сдвига, выполняемой целочисленными конструкторами.
Все описанные конструкторы с одним параметром также выполняют функцию операторов неявного преобразования и преобразуют из типа конструктора в тип fixed_point<B, I, F>. Поэтому можно инициализировать переменные fixed_point<B, I, F> числовыми значениями, как указано ниже:
fixed_point<int, 16> a(0);
fixed_point<int, 16> b = -1.5;
Наконец, реализуется конструктор копирования:
fixed_point(fixed_point<B, I, F> const& rhs) : value_(rhs.value_)
{ }
Конструктор копирования просто копирует содержимое члена класса fixed_point<B, I, F>::value_.
Собственно, этот конструктор не обязателен, так как компилятор автоматически создает похожий конструктор копирования. Но лучше задать его в явном виде.
Как сказано ранее, конструкторы с одним параметром дважды выполняют функцию преобразований из числовых значений к типу fixed_point<B, I, F>. Также нужно другое направление преобразования, которое реализуется при помощи операторов преобразования для этих же числовых типов:
template<typename T> operator T() const
{
BOOST_CONCEPT_ASSERT((boost::Integer<T>));
return value_ >> F;
}
operator float() const
{
return (float)value_ / power2<F>::value;
}
operator double() const
{
return (double)value_ / power2<F>::value;
}
operator long double() const
{
return (long double)value_ / power2<F>::value;
}
Преобразования из типа fixed_point<B, I, F> симметричны для конструкторов. Собственно, целочисленные преобразования сдвигают вправо, а преобразования с плавающей точкой делят на подходящий показатель степени 2.
Несколько замечаний.
К сожалению, C++ не задает точное поведение операторов сдвига, но оставляет его реализацию определенной. Любая реализация может выполнять арифметический сдвиг (правильная обработка знакового бита для отрицательных чисел) или логический сдвиг (отсутствие особой обработки самого левого бита). При этом есть вероятность, что код не будет работать так, как предполагалось. Но опробованные реализации (Visual Studio 2005, Visual Studio 2008) работают правильно: они выполняют арифметический сдвиг для чисел со знаком и выполняют логический сдвиг для чисел без знака.
Преобразования с плавающей точкой должны вычислять 2 в степени F. Можно было бы использовать функцию времени выполнения pow, но нет смысла откладывать на время выполнения вычисления, которые столь же успешно можно выполнить во время компиляции. К сожалению, это не так просто. Для вычисления во время компиляции был использован метод метапрограммирования шаблона:
template<int F> struct power2
{
static const long long value = 2 * power2<P-1,T>::value;
};
template <> struct power2<0>
{
static const long long value = 1;
};
Шаблон power2 работает посредством рекурсии шаблона. Например, если F == 2, выполняются следующие шаги:
- создается экземпляр power2<2>, power2<2>::value устанавливается 2 * power2<1>::value. Так как power2<1>::value еще неизвестно, компилятор должен создать экземпляр power2<1>.
- создается экземпляр power2<1>, power2<1>::value устанавливается в 2 * power2<0>::value. Так как power2<0>::value еще неизвестно, компилятор должен создать экземпляр power2<0>.
- создается экземпляр power2<0>, power2<0>::value равно 1. Теперь рекурсия может перемотать весь путь обратно, эффективно вычислив 2 * 2 * 1, являющееся 2^2, равное 4.
Операторы
Разумеется, чтобы была возможность делать что-либо полезное с объектами fixed_point<B, I, F>, необходимо несколько операторов.
Присваивание и преобразование
Имеется простой оператор присваивания, реализованный в виде конструктора копирования, и операция перестановки.
fixed_point<B, I, F> & operator =(fixed_point<B, I, F> const& rhs)
{
fixed_point<B, I, F> temp(rhs);
swap(temp);
return *this;
}
Сама операция перестановки передает полномочия перестановке из стандартной библиотеки C++.
void swap(fixed_point<B, I, F> & rhs)
{
std::swap(value_, rhs.value_);
}
Имеется также версия присваивания, способная выполнять преобразования между различными форматами с фиксированной точкой, и поэтому также нужен преобразующий конструктор копирования. Преобразование между различными форматами с фиксированной точкой может выполняться путем сдвига представления влево или вправо при необходимости.
template<unsigned char I2, unsigned char F2>
fixed_point<B, I, F> & operator =(fixed_point<B, I2, F2> const& rhs)
{
fixed_point<B, I, F> temp(rhs);
swap(temp);
return *this;
}
template<unsigned char I2, unsigned char F2>
fixed_point(fixed_point<B, I2, F2> const& rhs)
: value_(rhs.value_)
{
if (I-I2 > 0)
value_ >>= I-I2;
if (I2<I > 0)
value_ <<= I2-I;
}
Сравнение
Для сравнения реализованы операторы operator < и operator ==.
bool operator <(fixed_point<B, I, F> const& rhs) const
{
return value_ < rhs.value_;
}
bool operator ==(fixed_point<B, I, F> const& rhs) const
{
return value_ == rhs.value_;
}
Класс boost::ordered_field_operators автоматически реализует операторы operator >, operator >=, и operator <= на основе operator <, а также operator != на основе operator ==.
В форме записи псевдокода автоматическое предоставление операторов выглядит примерно так:
| boost::ordered_field_operators | |
| operator <(a, b) |
|
| operator >(a, b): | return operator <(b, a); |
| operator >=(a, b): | return ! operator <(a, b); |
| operator <=(a, b): | return ! operator <(b, a); |
| operator ==(a, b) |
|
| operator !=(a, b): | return ! operator ==(a, b); |
Преобразование в логический тип
Типы с плавающей точкой float и double поддерживают преобразование в логический тип. Значение с плавающей точкой преобразуется в истину, когда оно != 0, и в противном случае оно преобразуется в ложь. Итак, было реализовано преобразование в логический тип, и operator !, возвращающий противоположное значение.
operator bool() const
{
return (bool)value_;
}
bool operator !() const
{
return value_ == 0;
}
Одноместный оператор –
Для знаковых типов с фиксированной точкой можно применять одноместный минус-оператор для получения инверсии относительно сложения. Для беззнаковых типов с фиксированной точкой эта операция не определена. Разделенное с целочисленным базовым типом B, минимальное значение, представимое данным типом, не может быть инвертировано, так как оно может выдать положительное значение, которое выходит за пределы допустимого диапазона и не может быть представлено.
fixed_point<B, I, F> operator -() const
{
fixed_point<B, I, F> result;
result.value_ = -value_;
return result;
}
Инкремент и декремент
Типы с плавающей точкой могут быть увеличены или уменьшены на 1.
fixed_point<B, I, F> & operator ++()
{
value_ += power2<F>::value;
return *this;
}
fixed_point<B, I, F> & operator --()
{
value_ -= power2<F>::value;
return *this;
}
Класс boost::unit_steppable автоматически реализует операторы operator ++(int) (последующее увеличение) и operator -–(int) (последующее уменьшение) в виде operator ++ и operator --.
В форме записи псевдокода автоматическое предоставление операторов выглядит примерно так:
| boost::unit_steppable | |
| operator ++() |
|
| operator ++(int): | tmp(*this); ++tmp; return tmp; |
| operator --() |
|
| operator --(int): | tmp(*this); --tmp; return tmp; |
Сложение и вычитание
Сложение и вычитание реализованы для fixed_point<B, I, F> в виде операторов operator += и operator -=.
fixed_point<B, I, F> & operator +=(fixed_point<B, I, F> const& summand)
{
value_ += summand.value_;
return *this;
}
fixed_point<B, I, F> & operator -=(fixed_point<B, I, F> const& diminuend)
{
value_ -= diminuend.value_;
return *this;
}
Класс boost::ordered_field_operators автоматически реализует операторы operator + и operator – в виде operator += и operator -=.
В форме записи псевдокода автоматическое предоставление операторов выглядит примерно так:
| boost:: ordered_field_operators | |
| operator +=(s) |
|
| operator +(s): | tmp(*this); tmp += s; return tmp; |
| operator -=(d) |
|
| operator -(d): | tmp(*this); tmp -= d; return tmp; |
Со сложением и вычитанием нужно быть внимательным, так как из-за наследования ими целочисленной реализации они могут переполняться.
Умножение и деление
Умножение и деление реализованы для fixed_point<B, I, F> в виде опеаторов operator *= и operator /=.
fixed_point<B, I, F> & operator *=(fixed_point<B, I, F> const& factor)
{
value_ = (static_cast<fpml::fixed_point<B, I, F>::promote_type<B>::type>
(value_) * factor.value_) >> F;
return *this;
}
fixed_point<B, I, F> & operator /=(fixed_point<B, I, F> const& divisor)
{
value_ = (static_cast<fpml::fixed_point<B, I, F>::promote_type<B>::type>
(value_) << F) / divisor.value_;
return *this;
}
Класс boost::ordered_field_operators автоматически реализует операторы operator * и operator / в виде operator *= и operator /=.
В форме записи псевдокода автоматическое предоставление операторов выглядит примерно так:
| boost:: ordered_field_operators | |
| operator *=(s) |
|
| operator *(s): | tmp(*this); tmp *= s; return tmp; |
| operator /=(d) |
|
| operator /(d): | tmp(*this); tmp /= d; return tmp; |
Реализация умножения и деления представляет собой небольшие трудности. Вероятно, вы помните: класс fixed_point<B, I, F> имеет член value_ типа B, имеющий целочисленный тип.
Теперь рассмотрим, что происходит, когда перемножаются два целых числа, каждое из которых имеет длину 8 битов. Получится результат длиной в 16 битов. Крайний случай – возведение в квадрат наибольшего представимого значения, например:
a = 255 = 0xFF
a*a = 65025 = 0xFE01
Ясно видно, что для того, чтобы иметь возможность хранить любой возможный результат умножения, потребуется 16 битов, что в два раза превышает число битов в исходных множителях. Иными словами: два множителя при перемножении друг на друга дают результат, длина которого в два раза превышает число битов в исходных множителях.
Число битов целого числа – это свойство его типа, т.е. беззнаковый символьный тип имеет длину 8 битов, беззнаковое короткое целое имеет длину 16 битов, и т.д. К счастью, можно выполнять небольшую обработку типов при помощи шаблонов, чтобы найти правильные размеры в битах и типы для результатов умножения.
Для каждого типа, используемого в качестве базового класса B (иначе называемого малым типом) нужно найти соответствующий тип с вдвое( два раза) большим числом битов, который можно использовать для результата (иначе называемый большим типом).
| Малый тип | Большой тип |
| знаковый символьный | знаковый короткий целый |
| беззнаковый символьный | беззнаковый короткий целый |
| знаковый короткий целый | знаковый целый |
| беззнаковый короткий целый | беззнаковый целый |
| знаковый целый | знаковый длинный целый |
| беззнаковый целый | беззнаковый длинный целый |
Было создано несколько закрытых шаблонных структур, дающих необходимую информацию во время компиляции:
template<>
struct promote_type<signed char>
{
typedef signed short type;
};
template<>
struct promote_type<unsigned char>
{
typedef unsigned short type;
};
template<>
struct promote_type<signed short>
{
typedef signed int type;
};
template<>
struct promote_type<unsigned short>
{
typedef unsigned int type;
};
template<>
struct promote_type<signed int>
{
typedef signed long long type;
};
template<>
struct promote_type<unsigned int>
{
typedef unsigned long long type;
};
Больший результат используется только временно. Установка десятичной точки после умножения выполняется при помощи сдвига результата вправо точно на F битов. После сдвига результат приводится обратно к исходному типу. И здесь нужно быть внимательным, так как умножение может вызывать переполнение примерно таким же образом, что и для целочисленного умножения.
Деление аналогично в том, что делимое с битами делится при помощи делителя с битами для получения результата с битами.
Сдвиг влево и сдвиг вправо
Оператор сдвига влево << и оператор сдвига вправо >> не определены для типов с плавающей точкой. Однако fixed_point<B, I, F> определяет их, так как он может использоваться для эмуляции целочисленного типа, когда F установлен в 0. В этом случае fixed_point<B, I, F> ведет себя как целое число, но дает доступ к основным математическим функциям (то есть они полезны, если нужно вычислить квадратный корень целого числа).
fixed_point<B, I, F> & operator >>=(size_t shift)
{
value_ >>= shift;
return *this;
}
fixed_point<B, I, F> & operator <<=(size_t shift)
{
value_ <<= shift;
return *this;
}
Класс boost::shiftable автоматически реализует операторы operator >> и operator << в виде operator >>= и operator <<=.
В форме записи псевдокода автоматическое предоставление операторов выглядит примерно так:
| boost::shiftable | |
| operator >>=(n) |
|
| operator >>(n): | tmp(*this); tmp >>= n; return tmp; |
| operator <<=(n) |
|
| operator <<(n): | tmp(*this); tmp <<= n; return tmp; |
Ввод и вывод
Для удобства были реализованы операторы потокового ввода и вывода. Для реализации этих операторов было использовано преобразование в/из double.
template<typename S, typename B, unsigned char I, unsigned char F>
S & operator>>(S & s, fpml::fixed_point<B, I, F> & v)
{
double value=0.;
s >> value;
if (s)
v = value;
return s;
}
Поток ввода S – это параметр шаблона. Это позволяет использовать почти любой поток, будь то файловый или строковый поток, будь то поток символов в кодировке ANSI (Американский национальный институт стандартов) или поток символов расширенной формы.
template<typename S, typename B, unsigned char I, unsigned char F>
S & operator<<(S & s, fpml::fixed_point<B, I, F> const& v)
{
double value = v;
s << value;
return s;
}
Использование параметра шаблона S для потока вывода позволяет использовать любой поток, независимо от того, файловый это или строковый поток, или это поток символов в кодировке ANSI, или поток символов расширенной формы.
Потоковые операторы передают полномочия типу double. Нет особой выгоды в реализации этих операторов с нуля для типа fixed_point<B, I, F>. Ввод и вывод по определению медленный, поэтому допустимо применять математику с плавающей точкой в этих случаях.
Функции
При помощи этих операций можно легко выполнить множество математических вычислений с использованием класса fixed_point<B, I, F>, например, вычисления, необходимые для перемножения матриц, и т.д. Но класс был бы неполным без других функций, которые стандартная библиотека C++ предоставляет для типов с плавающей точкой, такие как sqrt, или sin, или log, и другие. Хотя можно преобразовать значение fixed_point<B, I, F> в значение с плавающей точкой и затем вызвать соответствующую функцию из стандартной библиотеки C++, это так или иначе, прежде всего, лишило бы смысла класс fixed_point<B, I, F>.
Поэтому были реализованы математические функции для класса fixed_point<B, I, F>. Эти функции достаточно трудно реализовать правильно. Было проделана немалая работа по выбору правильных алгоритмов, но вряд ли их качество реализации столь же высокое, что и у некоторых реализаций стандартной библиотеки C++.
fabs
Функция fabs вычисляет модуль ее аргумента.
friend fixed_point<B, I, F> fabs(fixed_point<B, I, F> x)
{
return x < fixed_point<B, I, F>(0) ? -x : x;
}
ceil
Функция ceil вычисляет минимальное целое значение, которое не меньше ее аргумента.
friend fixed_point<B, I, F> ceil(fixed_point<B, I, F> x)
{
fixed_point<B, I, F> result;
result.value_ = x.value_ & ~(power2<F>::value-1);
return result + fixed_point<B, I, F>(
x.value_ & (power2<F>::value-1) ? 1 : 0);
}
floor
Функция floor вычисляет максимальное целое значение, которое не больше ее аргумента.
friend fixed_point<B, I, F> floor(fixed_point<B, I, F> x)
{
fixed_point<B, I, F> result;
result.value_ = x.value_ & ~(power2<F>::value-1);
return result;
}
fmod
Функция fmod вычисляет остаток деления x/y с фиксированной точкой.
friend fixed_point<B, I, F> fmod(fixed_point<B, I, F> x, fixed_point<B, I, F> y)
{
fixed_point<B, I, F> result;
result.value_ = x.value_ % y.value_;
return result;
}
modf
Функция modf разбивает аргумент на целую и дробную части, каждая из которых имеет такой же знак, что и аргумент. Она сохраняет целую часть в объекте, на который указывает ptr, и возвращает дробную часть x/y со знаком.
friend fixed_point<B, I, F> modf(fixed_point<B, I, F> x, fixed_point<B, I, F> * ptr)
{
fixed_point<B, I, F> integer;
integer.value_ = x.value_ & ~(power2<F>::value-1);
*ptr = x < fixed_point<B, I, F>(0) ?
integer + fixed_point<B, I, F>(1) : integer;
fixed_point<B, I, F> fraction;
fraction.value_ = x.value_ & (power2<F>::value-1);
return x < fixed_point<B, I, F>(0) ? -fraction : fraction;
}
exp
Функция exp вычисляет экспоненту x.
friend fixed_point<B, I, F> exp(fixed_point<B, I, F> x)
{
fixed_point<B, I, F> a[] = {
1.64872127070012814684865078781,
…
1.00000000046566128741615947508 };
fixed_point<B, I, F> e(2.718281828459045);
fixed_point<B, I, F> y(1);
for (int i=F-1; i>=0; --i)
{
if (!(x.value_ & 1<<i))
y *= a[F-i-1];
}
int x_int = (int)(floor(x));
if (x_int<0)
{
for (int i=1; i<=-x_int; ++i)
y /= e;
}
else
{
for (int i=1; i<=x_int; ++i)
y *= e;
}
return y;
}
cos
Вычисляет косинус. Алгоритм использует разложение в ряд Маклорена.
Сначала аргумент сокращается так, чтобы он был в пределах диапазона от -Pi до Pi. Затем ряд Маклорена разворачивается. Сокращение аргумента проблематично, так как Pi нельзя представить точно. Чем больше циклов сокращения, тем менее значим аргумент (каждый цикл сокращения вносит небольшую ошибку), до той степени, когда сокращенный аргумент и, следовательно, результат не имеют смысла.
Сокращение аргумента использует одно деление. Разложение в ряд использует 3 сложения и 4 умножения.
friend fixed_point<B, I, F> cos(fixed_point<B, I, F> x)
{
fixed_point<B, I, F> x_ = fmod(x, fixed_point<B, I, F>(M_PI * 2));
if (x_ > fixed_point<B, I, F>(M_PI))
x_ -= fixed_point<B, I, F>(M_PI * 2);
fixed_point<B, I, F> xx = x_ * x_;
fixed_point<B, I, F> y = - xx *
fixed_point<B, I, F>(1. / (2 * 3 * 4 * 5 * 6));
y += fixed_point<B, I, F>(1. / (2 * 3 * 4));
y *= xx;
y -= fixed_point<B, I, F>(1. / (2));
y *= xx;
y += fixed_point<B, I, F>(1);
return y;
}
sin
Вычисляет синус.Алгоритм использует разложение в ряд Маклорена.
Сначала аргумент сокращается так, чтобы он был в пределах диапазона от -Pi до Pi. Затем ряд Маклорена разворачивается. Сокращение аргумента проблематично, так как Pi нельзя представить точно. Чем больше циклов сокращения, тем менее значим аргумент (каждый цикл сокращения вносит небольшую ошибку), до той степени, когда сокращенный аргумент и, следовательно, результат не имеют смысла.
Сокращение аргумента использует одно деление. Разложение в ряд использует 3 сложения и 5 умножения.
friend fixed_point<B, I, F> sin(fixed_point<B, I, F> x)
{
fixed_point<B, I, F> x_ = fmod(x, fixed_point<B, I, F>(M_PI * 2));
if (x_ > fixed_point<B, I, F>(M_PI))
x_ -= fixed_point<B, I, F>(M_PI * 2);
fixed_point<B, I, F> xx = x_ * x_;
fixed_point<B, I, F> y = - xx *
fixed_point<B, I, F>(1. / (2 * 3 * 4 * 5 * 6 * 7));
y += fixed_point<B, I, F>(1. / (2 * 3 * 4 * 5));
y *= xx;
y -= fixed_point<B, I, F>(1. / (2 * 3));
y *= xx;
y += fixed_point<B, I, F>(1);
y *= x_;
return y;
}
sqrt
Функция sqrt вычисляет неотрицательный квадратный корень ее аргумента.
Она вычисляет приближенный квадратный корень при помощи целочисленного алгоритма. Алгоритм описан в Википедии: http://en.wikipedia.org/wiki/Methods_of_computing_square_roots.
Алгоритм происходит из книги по программированию абаков, написанной К. Ву.
Функция возвращает квадратный корень аргумента. Если аргумент отрицательный, функция возвращает 0.
friend fixed_point<B, I, F> sqrt(fixed_point<B, I, F> x)
{
if (x < fixed_point<B, I, F>(0))
{
errno = EDOM;
return 0;
}
fixed_point<B, I, F>::promote_type<B>::type op =
static_cast<fixed_point<B, I, F>::promote_type<B>::type>(
x.value_) << (I - 1);
fixed_point<B, I, F>::promote_type<B>::type res = 0;
fixed_point<B, I, F>::promote_type<B>::type one =
(fixed_point<B, I, F>::promote_type<B>::type)1 <<
(std::numeric_limits<fixed_point<B, I, F>::promote_type<B>
::type>::digits - 1);
while (one > op)
one >>= 2;
while (one != 0)
{
if (op >= res + one)
{
op = op - (res + one);
res = res + (one << 1);
}
res >>= 1;
one >>= 2;
}
fixed_point<B, I, F> root;
root.value_ = static_cast<B>(res);
return root;
}
Свойства класса std::numeric_limits<>
Класс fixed_point<B, I, F> был бы неполным без специализации шаблона std::numeric_limits<>. Шаблон std::numeric_limits<> позволяет запрашивать информацию о любом числовом типе, такую как его минимальные и максимальные значения, и многую другую. Необходимо написать подлинно универсальный код, независимый от типа и волшебным образом работающий для разных типов.
| свойство | тип | значение |
| has_denorm | const float_denorm_style | denorm_absent |
| has_denorm_loss | const bool | false |
| has_infinity | const bool | false |
| has_quiet_NaN | const bool | false |
| has_signaling_NaN | const bool | false |
| is_bounded | const bool | true |
| is_exact | const bool | true |
| is_iec559 | const bool | false |
| is_integer | const bool | false |
| is_modulo | const bool | false |
| is_signed | const bool | numeric_limits<B> (1) |
| is_specialized | const bool | true |
| tinyness_before | const bool | false |
| traps | const bool | false |
| round_style | const float_round_style | round_toward_zero |
| digits | const int | I |
| digits10 | const int | digits |
| max_exponent | const int | 0 |
| max_exponent10 | const int | 0 |
| min_exponent | const int | 0 |
| min_exponent10 | const int | 0 |
| radix | const int | 0 |
| min() | fixed_point<B, I, F> | (2) |
| max() | fixed_point<B, I, F> | (2) |
| epsilon() | fixed_point<B, I, F> | (2) |
| round_error() | fixed_point<B, I, F> | (2) |
| denorm_min() | fixed_point<B, I, F> | (3) |
| infinity() | fixed_point<B, I, F> | (3) |
| quiet_NaN() | fixed_point<B, I, F> | (3) |
| signaling_NaN() | fixed_point<B, I, F> | (3) |
- Зависит от базового типа. Если базовый тип B знаковый, то fixed_point<B, I, F> также знаковый. Иначе он беззнаковый.
- Эти значения вычисляются на основе параметров шаблона.
- Эти значения бессмысленны для типа с фиксированной точкой, и устанавливаются в ноль.
Помощники для отладки программы
Visual Studio поддерживает визуализаторы отладчика, помогающие отладчику подробно отображать переменные. Без специальных визуализаторов отображение по умолчанию переменных типа fixed_point<B, I, F> прежде всего бесполезно, если не выполняется надлежащее преобразование в формат с плавающей точкой вручную.
Выведенное значение -49152 не говорит вам ни о чем существенном, если вы не знаете, что для получения закодированного значения нужно разделить значение -49152.
Но есть кое-что, что визуализатор отладчика может автоматически сделать для вас. При помощи этого визуализатора значение отображается правильно (он не выводит число разрядов после десятичной точки правильно, но это не большая проблема).
Visual Studio сохраняет визуализаторы отладчика в текстовом файле с названием autoexp.dat, в разделе [Визуализатор]. Этот файл можно найти в папке %VSINSTALLDIR%\Common7\Packages\Debugger. Ниже приводится определение визуализатора отладчика для типа fixed_point<B, I, F>:
;------------------------------------------------------------------------------
; fpml::fixed_point
;------------------------------------------------------------------------------
fpml::fixed_point<*,*,*>{
preview (
#if ($T3 == 32)( #( $e.value_ / 4294967296., " fixed_point ", $T2,".",$T3 ))
#elif ($T3 == 31)( #( $e.value_ / 2147483648., " fixed_point ", $T2,".",$T3 ))
#elif ($T3 == 30)( #( $e.value_ / 1073741824., " fixed_point ", $T2,".",$T3 ))
#elif ($T3 == 29)( #( $e.value_ / 536870912., " fixed_point ", $T2,".",$T3 ))
#elif ($T3 == 28)( #( $e.value_ / 268435456., " fixed_point ", $T2,".",$T3 ))
#elif ($T3 == 27)( #( $e.value_ / 134217728., " fixed_point ", $T2,".",$T3 ))
#elif ($T3 == 26)( #( $e.value_ / 67108864., " fixed_point ", $T2,".",$T3 ))
#elif ($T3 == 25)( #( $e.value_ / 33554432., " fixed_point ", $T2,".",$T3 ))
#elif ($T3 == 24)( #( $e.value_ / 16777216., " fixed_point ", $T2,".",$T3 ))
#elif ($T3 == 23)( #( $e.value_ / 8388608., " fixed_point ", $T2,".",$T3 ))
#elif ($T3 == 22)( #( $e.value_ / 4194304., " fixed_point ", $T2,".",$T3 ))
#elif ($T3 == 21)( #( $e.value_ / 2097152., " fixed_point ", $T2,".",$T3 ))
#elif ($T3 == 20)( #( $e.value_ / 1048576., " fixed_point ", $T2,".",$T3 ))
#elif ($T3 == 19)( #( $e.value_ / 524288., " fixed_point ", $T2,".",$T3 ))
#elif ($T3 == 18)( #( $e.value_ / 262144., " fixed_point ", $T2,".",$T3 ))
#elif ($T3 == 17)( #( $e.value_ / 131072., " fixed_point ", $T2,".",$T3 ))
#elif ($T3 == 16)( #( $e.value_ / 65536., " fixed_point ", $T2,".",$T3 ))
#elif ($T3 == 15)( #( $e.value_ / 32768., " fixed_point ", $T2,".",$T3 ))
#elif ($T3 == 14)( #( $e.value_ / 16384., " fixed_point ", $T2,".",$T3 ))
#elif ($T3 == 13)( #( $e.value_ / 8192., " fixed_point ", $T2,".",$T3 ))
#elif ($T3 == 12)( #( $e.value_ / 4096., " fixed_point ", $T2,".",$T3 ))
#elif ($T3 == 11)( #( $e.value_ / 2048., " fixed_point ", $T2,".",$T3 ))
#elif ($T3 == 10)( #( $e.value_ / 1024., " fixed_point ", $T2,".",$T3 ))
#elif ($T3 == 9)( #( $e.value_ / 512., " fixed_point ", $T2,".",$T3 ))
#elif ($T3 == 8)( #( $e.value_ / 256., " fixed_point ", $T2,".",$T3 ))
#elif ($T3 == 7)( #( $e.value_ / 128., " fixed_point ", $T2,".",$T3 ))
#elif ($T3 == 6)( #( $e.value_ / 64., " fixed_point ", $T2,".",$T3 ))
#elif ($T3 == 5)( #( $e.value_ / 32., " fixed_point ", $T2,".",$T3 ))
#elif ($T3 == 4)( #( $e.value_ / 16., " fixed_point ", $T2,".",$T3 ))
#elif ($T3 == 3)( #( $e.value_ / 8., " fixed_point ", $T2,".",$T3 ))
#elif ($T3 == 2)( #( $e.value_ / 4., " fixed_point ", $T2,".",$T3 ))
#elif ($T3 == 1)( #( $e.value_ / 2., " fixed_point ", $T2,".",$T3 ))
#elif ($T3 == 0)( #( $e.value_ / 1., " fixed_point ", $T2,".",$T3 ))
)
}
Если вы хотите узнать больше о визуализаторах отладчика для внутреннего кода, ознакомьтесь с подробной документацией по адресу https://svn.boost.org/trac/boost/wiki/DebuggerVisualizers.
Требования к использованию
Тип fixed_point<B, I, F> поступает в форме библиотеки только с заголовками. Не нужно ничего связывать или компоновать. Просто включите fixed_point.h там, где он нужен, и все должно заработать.
Исходный код требует последнюю версию «повышения» (http://www.boost.org/) и считает, что она установлена, и что ее можно найти в ходе (пути) включения. Нужно убедиться, что «повышение» установлено. «Повышение» используется для статических утверждений (утверждений во время компиляции) и проверки понятий, чтобы убедиться, что типы и значения используются по назначению. Кроме того, библиотека операторов повышения используется для автоматического предоставления набора операторов.
Все эти библиотеки повышения являются только заголовочными и требуют наличия файлов повышения, но они не требуют от вас проделывать длительный процесс компоновки каких-либо библиотек повышения.
Пока испытания проведены только с Visual Studio 2005 и 2008, но другие соответствующие стандартам компиляторы также должны работать.
Испытания
Вместе с кодом поставляется программа для испытаний, проверяющая класс и все функции. Не все возможные комбинации типов, размеры в битах целой и дробной частей проверяются, но достаточная подгруппа параметров испытывается.
Если ваши требования меняются, можно легко изменить программу для испытаний, чтобы обеспечить надлежащую проверку ваших требований.
Контрольные задачи
Хотя основной фокус библиотеки – ее использование во встроенных системах с аппаратным обеспечением, не поддерживающим формат с плавающей точкой, были выполнены измерения распределения интервалов времени на платформе ПК. Рассчитывались по времени различные операции, и измеренные временные интервалы сравнивались с типами float и double. Результаты представлены в виде числа периодов тактовых импульсов в расчете на операцию. Эталонная тестовая программа выполняет большое число операций в цикле и считает периоды тактовых импульсов. Общее число периодов тактовых импульсов затем делится на число повторений.
| Функция | float | double | 15.16 |
| сложение | 1.00367 | 1.00365 | 1.00373 |
| умножение | 1.00368 | 1.00371 | 1.00376 |
| деление | 1.00369 | 1.0037 | 1.0037 |
| квадратный корень | 1.00371 | 1.00371 | 473.881 |
| синус | 1.00364 | 1.00375 | 162.533 |
Можно увидеть, что основные операции, такие как сложение, умножение и деление, выполняются быстро, но над функциями все еще нужно работать.
Вывод
Разработка этого класса была довольно трудной, и поначалу невозможно было представить, насколько трудно будет писать элементарные функции для класса с фиксированной точкой. Не было мыслей о std::numeric_limits<> и о визуализаторах отладчика.