fixed point - Исходники

Собственно шаблон класса для предсталения чисел с фиксированной точкой. Определены все основные арифметические операции, преобразование к типам double / float. Доступны методы: integer(), fractional(), float(), ceil(), round(). Интерестно узнать ваше мнение.

template< typename Type, uint t_shift >
class fixed_T
{
public:
    typedef Type value_type;

    static const value_type shift = t_shift;    // количество бит для хранения дробной части
    static const value_type scale = 1 << shift; // множитель для получения дробной части
    static const value_type f_max = scale - 1;  // максимальное значение дробной части
    static const value_type mask = scale - 1;   // маска для получения дробной части

private:
    value_type m_data;

    inline static int l_div( value_type a, value_type b )
    {
        return (a * scale) / b;
    }

    // Раскладывает число "v" на целую и дробные части
    static void analize( double v, value_type& integer, value_type& fractional )
    {
        integer = value_type(v);
        fractional = value_type( ( v - double(integer) ) * scale );
    }

    // Раскладывает число "v" на целую и дробные части
    static void analize( float v, value_type& integer, value_type& fractional )
    {
        integer = value_type(v);
        fractional = value_type( ( v - double(integer) ) * scale );
    }

public:
    fixed_T(){}

    explicit fixed_T(value_type v) : m_data( v * scale )
    {
    }

    explicit fixed_T(value_type integer, value_type fractional) : m_data(integer*scale + fractional)
    {
    }

    explicit fixed_T(double v)
    {
        value_type integer;
        value_type fractional;

        analize( v, integer, fractional );

        m_data = integer * scale + fractional;
    }

    explicit fixed_T(float v)
    {
        value_type integer;
        value_type fractional;

        analize( v, integer, fractional );

        m_data = integer * scale + fractional;
    }


    value_type value() const { return m_data; }
    value_type integer() const { return m_data/scale; }
    value_type fractional() const { return m_data%scale; }

    value_type sign() const { return value() > 0 ? 1 : -1; }
    bool isNegative() const { return value() < 0; }

    value_type round() const
    {
        return isNegative() ? (value() - scale/2) / scale 
                            : (value() + scale/2) / scale;
    }
    
    value_type ceil() const
    {
        return isNegative() ? value() / scale : ( value() + f_max ) / scale;
    }

    value_type floor() const
    {
        return isNegative() ? ( value() - f_max ) / scale : value() / scale;
    }

    //////////////////////////////////////////////////////////////////////////
    // Операторы
    //////////////////////////////////////////////////////////////////////////
    
    /// (+ и -) Сложение / вычитание

    fixed_T operator+(value_type a) const { return fixed_T( a, m_data ); }
    fixed_T operator-(value_type a) const { return fixed_T( 0, m_data - a*scale ); }
    fixed_T operator+(fixed_T f) const { return fixed_T( 0, m_data + f.m_data ); }
    fixed_T operator-(fixed_T f) const { return fixed_T( 0, m_data - f.m_data ); }
    fixed_T operator+(double a) const
    {
        value_type v_i, v_f;
        analize( a, v_i, v_f );
        return fixed_T( 0, m_data + v_i*scale + v_f );
    }
    fixed_T operator-(double a) const
    {
        value_type v_i, v_f;
        analize( a, v_i, v_f );
        return fixed_T( 0, m_data - v_i*scale - v_f );
    }
    fixed_T operator+(float a) const
    {
        value_type v_i, v_f;
        analize( a, v_i, v_f );
        return fixed_T( 0, m_data + v_i*scale + v_f );
    }
    fixed_T operator-(float a) const
    {
        value_type v_i, v_f;
        analize( a, v_i, v_f );
        return fixed_T( 0, m_data - v_i*scale - v_f );
    }

    /// (*) Умножение

    fixed_T operator*(value_type a) const { return fixed_T( 0, m_data*a ); }
    fixed_T operator*(fixed_T f) const
    {
        return fixed_T( 0, m_data*f.integer() + (m_data*f.fractional())/scale );
    }

    fixed_T operator*(double a) const
    {
        value_type v_i, v_f;
        analize( a, v_i, v_f );
        return fixed_T( 0, m_data*v_i + (m_data*v_f)/scale );
    }
    fixed_T operator*(float a) const
    {
        value_type v_i, v_f;
        analize( a, v_i, v_f );
        return fixed_T( 0, m_data*v_i + (m_data*v_f)/scale );
    }

    /// (/) Деление

    fixed_T operator/(value_type a) const { return fixed_T( 0, m_data/a ); }
    fixed_T operator/(fixed_T f) const { return fixed_T( 0, q_div( m_data, f.m_data ) ); }
    fixed_T operator/(double v) const { return fixed_T( 0, q_div( m_data, fixed_T(v).m_data ) ); }
    fixed_T operator/(float v) const { return fixed_T( 0, q_div( m_data, fixed_T(v).m_data ) ); }

    /// (+= и -=)

    fixed_T& operator+=(value_type a) { m_data += a*scale; return *this; }
    fixed_T& operator-=(value_type a) { m_data -= a*scale; return *this; }

    fixed_T& operator+=(fixed_T f) { m_data += f.m_data; return *this; }
    fixed_T& operator-=(fixed_T f) { m_data -= f.m_data; return *this; }

    fixed_T& operator+=(double a)
    {
        value_type v_i, v_f;
        analize( a, v_i, v_f );

        m_data += v_i*scale + v_f;
        return *this;
    }

    fixed_T& operator-=(double a)
    {
        value_type v_i, v_f;
        analize( a, v_i, v_f );

        m_data -= v_i*scale + v_f;
        return *this;
    }

    fixed_T& operator+=(float a)
    {
        value_type v_i, v_f;
        analize( a, v_i, v_f );

        m_data += v_i*scale + v_f;
        return *this;
    }

    fixed_T& operator-=(float a)
    {
        value_type v_i, v_f;
        analize( a, v_i, v_f );

        m_data -= v_i*scale + v_f;
        return *this;
    }

    // (/=)

    fixed_T& operator/=(value_type a) { m_data /= a; return *this; }
    
    fixed_T& operator/=(fixed_T f)
    {
        value_type quot = m_data / f.m_data;
        value_type rem = m_data % f.m_data;

        m_data = quot*scale + (rem*scale) / f.m_data;

        return *this;
    }

    fixed_T& operator/=(double a)
    {
        fixed f(a);
        
        value_type quot = m_data / f.m_data;
        value_type rem = m_data % f.m_data;

        m_data = quot*scale + (rem*scale) / f.m_data;
        
        return *this;
    }

    fixed_T& operator/=(float a)
    {
        fixed f(a);

        value_type quot = m_data / f.m_data;
        value_type rem = m_data % f.m_data;

        m_data = quot*scale + (rem*scale) / f.m_data;

        return *this;
    }

    // (*=)

    fixed_T& operator*=(value_type a) { m_data *= a; return *this; }

    fixed_T& operator*=(fixed_T f)
    {
        m_data = m_data*f.integer() + (m_data*f.fractional())/scale;
        return *this;
    }

    fixed_T& operator*=(double a)
    {
        value_type v_i, v_f;
        analize( a, v_i, v_f );

        m_data = m_data*v_i + (m_data*v_f)/scale;
        return *this;
    }

    fixed_T& operator*=(float a)
    {
        value_type v_i, v_f;
        analize( a, v_i, v_f );

        m_data = m_data*v_i + (m_data*v_f)/scale;
        return *this;
    }

    /// (++ и --)    
    
    fixed_T& operator++() { m_data += scale; return *this; }
    fixed_T& operator++(int) { m_data += scale; return *this; }
    fixed_T& operator--() { m_data -= scale; return *this; }
    fixed_T& operator--(int) { m_data -= scale; return *this; }
    
    /*
    friend fixed operator+(value_type a, fixed f) { return fixed( a, f.m_data ); }
    friend fixed operator-(value_type a, fixed f) { return fixed( 0, a*scale-f.m_data ); }
    friend fixed operator*(value_type a, fixed f) { return fixed( 0, f.m_data*a ); }
    friend fixed operator/(value_type a, fixed f)
    {
        value_type quot = m_data / f.m_data;
        value_type rem = m_data % f.m_data;

        return fixed( quot, (rem*scale) / f.m_data );
    }
    */

    /// Приведение к типу

    operator value_type() const { return (m_data+scale/2)/scale; }
    operator double() const { return double(m_data)/double(scale); }
    operator float() const { return float(m_data)/float(scale); }
    
    /// Присваивание

    fixed_T& operator = (value_type a) { m_data = a*scale; return *this; }
    fixed_T& operator = (fixed_T& f) { m_data = f.m_data; return *this; }
    fixed_T& operator = (double a) { m_data = fixed_T(a).m_data; return *this; }
    fixed_T& operator = (float a) { m_data = fixed_T(a).m_data; return *this; }

    /// Сравнение

    bool operator == (fixed_T& f) { return m_data == f.m_data; }
    bool operator != (fixed_T& f) { return m_data != f.m_data; }
    bool operator >= (fixed_T& f) { return m_data >= f.m_data; }
    bool operator <= (fixed_T& f) { return m_data <= f.m_data; }
    bool operator > (fixed_T& f) { return m_data > f.m_data; }
    bool operator < (fixed_T& f) { return m_data < f.m_data; }

    bool operator == (value_type a) { return m_data == a*scale; }
    bool operator != (value_type a) { return m_data != a*scale; }
    bool operator >= (value_type a) { return m_data >= a*scale; }
    bool operator <= (value_type a) { return m_data <= a*scale; }
    bool operator > (value_type a) { return m_data > a*scale; }
    bool operator < (value_type a) { return m_data < a*scale; }

    bool operator == (double a) { return double(*this) == a; }
    bool operator != (double a) { return double(*this) != a; }
    bool operator >= (double a) { return double(*this) >= a; }
    bool operator <= (double a) { return double(*this) <= a; }
    bool operator > (double a) { return double(*this) > a; }
    bool operator < (double a) { return double(*this) < a; }

    bool operator == (float a) { return float(*this) == a; }
    bool operator != (float a) { return float(*this) != a; }
    bool operator >= (float a) { return float(*this) >= a; }
    bool operator <= (float a) { return float(*this) <= a; }
    bool operator > (float a) { return float(*this) > a; }
    bool operator < (float a) { return float(*this) < a; }
};

typedef fixed_T<int, 8> fixed;

Здравствуйте, WinterMute, Вы писали:

WM>Собственно шаблон класса для предсталения чисел с фиксированной точкой. Определены все основные арифметические операции, преобразование к типам double / float. Доступны методы: integer(), fractional(), float(), ceil(), round(). Интерестно узнать ваше мнение.

я вот только не понял, где это может применятся?

обычно ведь вычисления ведуться для чисел с максимальной точностью, для уменьшения накапливания ошибки, а если числа обрезать, то и ошибка будет больше накапливаться.
помоему фиксировать точку необходимо только для выводе ресультата пользователю, что вполне решимо стандартными средствами.

Здравствуйте, ssm, Вы писали:

sm>я вот только не понял, где это может применятся?

ssm>обычно ведь вычисления ведуться для чисел с максимальной точностью, для уменьшения накапливания ошибки, а если числа обрезать, то и ошибка будет больше накапливаться.
ssm>помоему фиксировать точку необходимо только для выводе ресультата пользователю, что вполне решимо стандартными средствами.

Числа с фиксированной точкой бывают нужны когда очень важна скорость и не очень важна точность. Например, они могут пригодится в реализации алгоритма Брезенхема, для рисования линий с субпиксельной точностью. Еще, у floating point чисел есть одна неприятная особенность: они хранятся с точностью +/- EPS, где EPS какая-то маленькая величина. Т.е., если я правильно понял, даже если написать:

double dbl1 = 444.5555;
double dbl2 = 444.5555;

if( dbl == dbl2 )
{
    // Выполнится?
}

здесь нельзя быть уверенным что код внутри if( dbl == dbl2 ) выполнится (хотя я с таким поведением не сталкивался).

Здравствуйте, WinterMute, Вы писали:

[... skipped ...]

WM>Т.е., если я правильно понял, даже если написать:
WM>

WM>double dbl1 = 444.5555;
WM>double dbl2 = 444.5555;

WM>if( dbl == dbl2 )
WM>{
WM>    // Выполнится?
WM>}
WM>

WM>здесь нельзя быть уверенным что код внутри if( dbl == dbl2 ) выполнится (хотя я с таким поведением не сталкивался).

Ну такой-то выполнится — факт. А вот такой:

if (1.2 * 1.2 == 1.44)

— не факт

Здравствуйте, WinterMute, Вы писали:

...

Еще не смотрел детально но по названию то что нужно

еще бы развернутый пример использования...
Кстати под GBA компилить не пробовал случайно? имхо там это просто находка.
и вообще, под GCC компилится?

... << RSDN@Home 1.1.3 stable >>

Здравствуйте, yxiie, Вы писали:

Y>Здравствуйте, WinterMute, Вы писали:

Y>...

Y>Еще не смотрел детально но по названию то что нужно

Y>еще бы развернутый пример использования...
Y>Кстати под GBA компилить не пробовал случайно? имхо там это просто находка.
Y>и вообще, под GCC компилится?

Компилироватся должно везде, никаких трюков не используется, только простая арифметика. Есть один возможный подводный камень: дробная и целая части, получаемые соответственно методами integer() и fractional(), всегда должны быть одного знака, Целая часть получается операцией m_value/scale, а дробная операцией m_value%scale. Мой английский не очень хорош, и я не понял, всегда-ли гарантируется что результат операции % будет того-же знака что и результат деления. Если нет, то плохо.

Реализовано следующим образом: всё чило хранится в переменной типа "Type". Для этого типа определены все основные арифметические операции, но второй операнд должен быть одним из следующих типов: Base, fixed_T, double, float. Пример использования:

typedef fixed_T<int, 8> fixed; // используем в качестве контейнера число типа int, для хранения дробной части отводим 8 бит

fixed a(1.5);
fixed b(-1.5);

int integer = a.integer(); // == 1
int fractional = a.fractional(); // == 128

integer = b.integer(); // == -1
fractional = b.fractional(); // == -128

int some = a; // == 2; преобразование к Base происходит с округлением, а не с отсечением дробной части

a++;
a *= 5.5f;

int ceil = a.ceil(); // == 2
int floor = a.floor(); // == 1
int round = a.round(); // == 2

a /= 5;
a /= UINT(5); // ошибка, компилятор не знает к чему преобразовать UINT(5) -- к Base? double? float?

a /= fixed::value_type( UINT(5) ); // ОК

Здравствуйте, ssm, Вы писали:

ssm>я вот только не понял, где это может применятся?

... << RSDN@Home 1.1.4 beta 6 rev. 431>>

Здравствуйте, Nose, Вы писали:

N>Они хороши тем, что ошибка предсказуема и управляема.
N>У меня диплом был по разработке методов шифрования — так вот числа с фиксированной точкой там незаменимы.

у меня частью диплома была балансировка движения самолета в пространстве, из всего запомнил хорошо только одно : при использовании float вместо double, тоесть при урезании точности, на первой минуте полета приходилось раздавать всем члена экипажа парашуты

Здравствуйте, ssm, Вы писали:

ssm>у меня частью диплома была балансировка движения самолета в пространстве, из всего запомнил хорошо только одно : при использовании float вместо double, тоесть при урезании точности, на первой минуте полета приходилось раздавать всем члена экипажа парашуты

Да не вопрос

Очевидно, что в твоем случае числа fixed-point неприменимы.
В моем случае были неприменимы числа с плавающей точкой.

... << RSDN@Home 1.1.4 beta 6 rev. 431>>

Здравствуйте, WinterMute, Вы писали:

только это... analyze — по-американски, analyse-по британски, а вот analize режет взгляд

... << RSDN@Home 1.1.4 beta 6 rev. 431>>

N>только это... analyze — по-американски, analyse-по британски, а вот analize режет взгляд

Хотелось чего-нибудь яркого, запоминающегося

А я видел физику реализованую на float'ах. Прикол был в том что когда система приходила в состояние близкое к покою то производительность резко проседала. Происходило это из-за того что скорости объектов становились очень маленькими, а float'ы с маленькими числами работают не просто медленно, а очень медленно. С фиксированой точкой такого бы не произошло ибо скорости бы просто обнулились.

... << RSDN@Home 1.1.4 beta 5 rev. 395>>

Будет ли выигрыш в скорости при использованиии фиксированной точки (по сравеннию с плавающей) на современных процессорах (Pentium 4) ?

... << RSDN@Home 1.1.4 beta 6a rev. 436>>

Здравствуйте, Ka3a4oK, Вы писали:

KK>Будет ли выигрыш в скорости при использованиии фиксированной точки (по сравеннию с плавающей) на современных процессорах (Pentium 4) ?

Точно не знаю, но думаю что будет и значительный.

WM>Точно не знаю, но думаю что будет и значительный.

Ну а если серьёзно, заявление совершенно голословное, сильно рекомендую проверить свои слова.
Кроме того, операция умножения "Самое большое представимое целое число * 0.9999 (т.е. самое большое дробное число < 1)" даст переполнение и как результат — неправильный результат.
Тоже самое с делением:
0111111111000000.........
делим на
0111111111100000.........

вы в rem*scale также получите переполнение и неправильный результат..

Если вы реализуете более точные вычисления то количество целочисленных операций и битовых сдвигов заставит усомниться вас в скорости fixed_point класса, для P4 (учтите что double-ы считаются одной командой на процессоре), и даже для embedded машин (имхо деление 2х float-ов всё таки реализуется гораздо проще даже программно — поделил мантиссы, вычел экспоненты, всё сложил назад).

WM>

WM>template< typename Type, uint t_shift >
WM>class fixed_T
WM>{
WM>    // Раскладывает число "v" на целую и дробные части
WM>    static void analize( double v, value_type& integer, value_type& fractional )
WM>    {
WM>        integer = value_type(v);
WM>        fractional = value_type( ( v - double(integer) ) * scale );
WM>    }
WM>};
WM>

Если double 64 бита и Type 64 бита (например UINT64), то в функции analize ошибка.

WH>Происходило это из-за того что скорости объектов становились очень маленькими, а float'ы с маленькими числами работают не просто медленно, а очень медленно.

Интересно!
А как зависит скорость операций с числами с плавающей точкой от значения мантиссы? Я наверное чего-то не понимаю...

... << RSDN@Home 1.1.4 stable SR1 rev. 568>>

L>Интересно!
L>А как зависит скорость операций с числами с плавающей точкой от значения мантиссы? Я наверное чего-то не понимаю...

Виноват — оговорился, конечно же имелось в виду значение порядка.

... << RSDN@Home 1.1.4 stable SR1 rev. 568>>

Здравствуйте, Ka3a4oK, Вы писали:

KK>Будет ли выигрыш в скорости при использованиии фиксированной точки (по сравеннию с плавающей) на современных процессорах (Pentium 4) ?

Скорее всего нет , на (Pentium 4) почти уверен что нет.
А вот на платформах типа ARM — запросто (до 10 раз)!

KK>>Будет ли выигрыш в скорости при использованиии фиксированной точки (по сравеннию с плавающей) на современных процессорах (Pentium 4) ?

M>Скорее всего нет , на (Pentium 4) почти уверен что нет.
Не могу разделить эту уверенность, по крайней мере не посмотрев на результаты тестов. Всё-таки даже в 4-м пне — сопроцессор хоть и быстрый, но ALU-то лупит на удвоенной частоте. Ну и целочисленных конвейеров ЕМНИП поболе чем конвейеров для плавающей точки. Да и исполнение одной команды сопроцессора за один такт — бывает только в случае "идеальной" загрузки сопроцессора (на самом деле тактов-то будет поболе, просто несколько команд будут выполянтся одновременно за счёт конвейера).

PS. Вот если бы это добро (fixed point) положить на MMX/SSE — вот где счастье-то было-бы!

... << RSDN@Home 1.1.4 stable SR1 rev. 568>>

L>PS. Вот если бы это добро (fixed point) положить на MMX/SSE — вот где счастье-то было-бы!

хотелось бы верить что современные оптимизирующие компиляторы могут сделать это и без нас

ЯЕ>хотелось бы верить что современные оптимизирующие компиляторы могут сделать это и без нас
ЯЕ>

Разве что Intel-овский. И то — очень мало шансов.

... << RSDN@Home 1.1.4 stable SR1 rev. 568>>

Здравствуйте, MShura, Вы писали:

WM>>

WM>>template< typename Type, uint t_shift >
WM>>class fixed_T
WM>>{
WM>>    // Раскладывает число "v" на целую и дробные части
WM>>    static void analize( double v, value_type& integer, value_type& fractional )
WM>>    {
WM>>        integer = value_type(v);
WM>>        fractional = value_type( ( v - double(integer) ) * scale );
WM>>    }
WM>>};
WM>>

MS>Если double 64 бита и Type 64 бита (например UINT64), то в функции analize ошибка.

Это понятно, но какой есть способ это обойти. Разве что, как в AGG -- явно задавать WideType.

От:	WinterMute	http://yarrr.ru
Дата:	22.04.05 12:31
Оценка:	28 (5)

	От:	ssm
	Дата:	22.04.05 14:09
	Оценка:

От:	WinterMute	http://yarrr.ru
Дата:	22.04.05 14:28
Оценка:

От:	Oyster	https://github.com/devoyster
Дата:	22.04.05 14:31
Оценка:

От:	yxiie	www.enkord.com
Дата:	22.04.05 15:50
Оценка:

От:	Яшин Евгений	https://www.facebook.com/TachyonWars/
Дата:	11.04.06 06:21
Оценка:

	От:	Nose
	Дата:	25.04.05 12:29
	Оценка:

	От:	Nose
	Дата:	25.04.05 12:56
	Оценка:

	От:	Nose
	Дата:	25.04.05 13:00
	Оценка:

	От:	WolfHound
	Дата:	26.04.05 12:08
	Оценка: