[Design by Committee] One True Fixed-Point Arithmetic Library

FordPerfect
Постоялец

#0
18:03, 11 фев 2016

Постановка задачи: библиотека для вычислений с фиксированной точкой, и соответствующий тип данных. Подразумеваемое использование: drop-in replacement для стандартного float. На C++. Хочется стандартных для fixed-point вещей: железобетонной повторяемости, фиксированной абсолютной точности, сносной скорости.

Собственно реализация выглядит достаточно тривиальной. Что и приводит к вопросу о архитектуре и дизайне.

Предполагается, что в этой теме лучшие умы gamedev.ru совместными силами изобретут этот дизайн.

Кто тролль? Я тролль?!

При желании тему можно воспринимать, как ~~контрольный в голову~~кирпичик в фундамент GameBoost. Или как разминку для мозгов. Или как повод для болтовни.

Соответственно, в целях плодотворной дискуссии, можно озвучить текущий список Design Decisions^TM (возможно не полный; дополнения допускаются).

1. Целевой стандарт языка (С89/С99/С++03/С++11/С++14/С++17)?

+ моя текущая версия

− Скрыть

С++03. Хотя <cstdint> хочется, так что для С++11 повод наблюдаем.

2. Параметризовать ли внутренним типом?

+ моя текущая версия

− Скрыть

Видимо вряд ли.
По-настоящему обобщённая реализация - вполне возможно больше мороки, чем пользы.
Можно явно выдать fixed32 и fixed64, которым не обязательно быть шаблонными и шарить код.

3. Параметризовать ли количеством дробных бит?

+ моя текущая версия

− Скрыть

Да.
Потому что why not?

4. Или вообще количество дробных бит сделать runtime параметром?

+ моя текущая версия

− Скрыть

Нет.
Данунафиг.

5. Название типа.

+ моя текущая версия

− Скрыть

template<unsigned int FractionBits> class fixed;

6. Поведение при переполнении (UB, как в С++ для встроенных знаковых целых / 2's complement wrap-around / насыщение / runtime ошибка / дать пользователю ~~рубль, пусть сам в столовую ходит~~параметр шаблона, задающий поведение / задавать поведение в runtime).

+ моя текущая версия

− Скрыть

Хрен его знает.

Но, наверное, всё-таки не UB.

7. Поведение при делении на 0.

+ моя текущая версия

− Скрыть

float по-умолчанию не падает, хочется такого же.
Хочется well-defined (т. е. повторяющееся) значение для всех случаев.
Либо 0 всегда, либо (вероятнее) -MAX, 0, +MAX в зависимости от числителя.

8. Округление. IEEE-754 довольно аккуратно относится к округлению, здесь стремиться ли делать то же?
- Round-To-Zero, как в C++ для целых?
- Round-To-Nearest-Ties-To-Even, как по умолчанию в IEEE 754?
- Параметр шаблона?
- Runtime состояние?

+ моя текущая версия

− Скрыть

Надо думать.

9. Infinity/NaN?

+ моя текущая версия

− Скрыть

Видимо нафиг.

10. Доступ к битам?
- Давать напрямую?
- Getter/Setter?
- Не давать вообще?

+ моя текущая версия

− Скрыть

Скорее давать напрямую.

11. Конструктор по умолчанию?

+ моя текущая версия

− Скрыть

Наверное оставляет непроинициализированным, как для встроенных.

12. Преобразование из встроенных вещественных?

+ моя текущая версия

− Скрыть

Наверное explicit конструктор от double.

13. Преобразование к встроенным вещественным?

+ моя текущая версия

− Скрыть

Наверное to_double().
Она (в IEEE 754) точная для fixed32, кстати.

Оператор приведения к вещественным типам - ещё думать.

14. Преобразование к встроенным целым?

+ моя текущая версия

− Скрыть

Ой, блин.

Можно бы и вообще нафиг, во избежание.
Но это вроде как несколько ломает drop-in replacement для стандартного float.

15. Математическая библиотека?

+ моя текущая версия

− Скрыть

Да.

Полноценная математическая библиотека, с std::exp, std::sin и вообще тем из <cmath> что имеет смысл для данного типа (включая std::nextafter).
И точностью порядка 1 ulp.

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

Что? Насчёт "собственно реализация выглядит достаточно тривиальной" - юмор такой.

16. Лицензия?

+ моя текущая версия

− Скрыть

Public domain.

17. SIMD?

+ моя текущая версия

− Скрыть

А чего мелочиться?

Ыы.

P. S. изначальная задумка темы Design by Committee была о One True n-Dimensional Vector. Но я подозреваю, что на это я получу ответ "взять glm и не плодить реализации". Стандарта de facto библиотеки чисел с фиксированной точкой как-то особо не заметно. Если C и 16:16, то есть libfixmath, впрочем.

gammaker
Постоялец

#1
18:21, 11 фев 2016

У меня fixed имеет два параметра - внутренний тип и делитель. Делитель - необязательно степень двойки. Например, если я хочу однобайтовое число в интервале [0;1], придётся сделать делитель 255, а не 256. Будет медленнее, но наверное тоже есть более простая формула. А степени двойки компилер должен сам оптимизировать и превратить в сдвиги и маски.
Я не делал никаких встроенных функций, потому что мне fixed нужен только для компактного хранения. Например, у меня в синтезаторе было много захардкоженных массивов во float, и я их перевёл на 1-байтовый нормализованный fixed<byte, 256>. Сэкономил несколько килобайт такой заменой.
Или ещё использовал fixed для более компактных форматов вершин в движке. Например всю позицию вершины я ужал в 4 байта, а было 3 float'а.
В обоих случаях операции над fixed'ами были не нужны, нужно было только редкое преобразование туда-сюда. float вроде всё равно быстрее в наше время, так что вычисления над fixed уже не актуальны.

}:+()___ [Smile]
Постоялец

#2
18:40, 11 фев 2016

ИМХО, не нужен.
Полноценный продуманный fixed-point предполагает тщательную слежку за диапазонами (где-то 16:16, где-то 1:31 и т. п.).
Для тяжелой математики часто нужно приводить к правильному диапазону (по типу 0x40000000–0xFFFFFFFF для квадратного корня), т. е. явно выделять мантиссу и порядок.
Кое-где надо сохранять wraparound и работать с нестандартными масштабами (например, полный оборот для углов: 0–2³² вместо 0–2π).
В общем, как и любая оптимизация, fixed-point должен затачиваться под конкретную задачу, иначе смысла в оптимизации нет.

gammaker
> В обоих случаях операции над fixed'ами были не нужны, нужно было только редкое преобразование туда-сюда. float вроде всё равно быстрее в наше время, так что вычисления над fixed уже не актуальны.
Вообще-то, даже безотносительно к скорости, есть область, где фиксированная точка предпочтительнее плавающей.
Это хранение и работа с величинами, требующими равномерной точности, не зависящей от расстояния до 0 (трансляционная инвариантность).
В первую очередь, времена и координаты в больших мирах.

cNoNim
Постоялец

#3
18:47, 11 фев 2016

}:+()___ [Smile]
> Полноценный продуманный fixed-point предполагает тщательную слежку за
> диапазонами (где-то 16:16, где-то 1:31 и т. п.).
> Для тяжелой математики часто нужно приводить к правильному диапазону (по типу
> 0x40000000–0xFFFFFFFF для квадратного корня), т. е. явно выделять мантиссу и
> порядок.
> Кое-где надо сохранять wraparound и работать с нестандартными масштабами
> (например, полный оборот для углов: 0–232 вместо 0–2π).
> В общем, как и любая оптимизация, fixed-point должен затачиваться под
> конкретную задачу, иначе смысла в оптимизации нет.
балин... а я думал что я что то гениальное придумал :) когда хотел все это запилить

Panzerschrek[CN]
Постоялец

#4
18:57, 11 фев 2016

gammaker
> придётся сделать делитель 255
В топку сразу такое. Пока процессор деление произведёт - состаришься.

FordPerfect
> Полноценная математическая библиотека, с std::exp, std::sin
Под вопросом. Где-то для синуса хватит таблица на 32 значения на полный круг, а где-то точность нужна до усрачки.

> Преобразование к встроенным целым?
Через всякие int to_int() не нужно. Надо что-то вроде ceil_to_int/floor_to_int/round_to_int

Не помешали бы беззнаковые fixed величины, но только без явного каста между fixed/ufixed.

return [](){};
Постоялец

#5
20:06, 11 фев 2016

Я когда-то написал простой shmup полностью на фикседе: http://www.gamedev.ru/flame/forum/?id=186780
И это было довольно геморно, лишний раз не перемножишь, не напоровшись на переполнение.

slatazan
Постоялец

#6
0:57, 12 фев 2016

FordPerfect
// я мало понимаю в серьёзных кодах, поэтому ткну пальцем в небо
1. старый С++03
2. -
3. биты: я за тупую пару аля UINT + INT (4 милиарда и 9 нолей дробной части)
4. -
5. название: нечто mix32, mix64
6. не-определёность: _забито все биты, кроме бита минуса.
7. деление на ноль: перехватывать и ничего не делать.
8. округление: скользкая тема - глюков от неё очень много.
9. фаза бесконечности: ? только бит минуса ?

зачем это мне ? где буду применять ?

Не знаю, наверно, можно обойтись без этого.

1 frag / 2 deaths
Участник

#7
10:04, 12 фев 2016

Как конструировать?
Из собственного литерала? ++03 не может.
Из вещественного? Теряешь железность.
Из дроби? Извратненько, но за неимением альтернатив...

FordPerfect
Постоялец

#8
10:42, 12 фев 2016

gammaker
Ок, если они только формат хранения - то это, вроде, другая задача, с другим дизайном.
У неё своя ценность.

}:+()___ [Smile]
Возможно.
Поэтому я и говорил о чуть более конкретном использовании: drop-in replacement для float (строго одинаковые вычисления +равномерная точность). Думаешь всё равно не заживёт?

Panzerschrek[CN]
>В топку сразу такое. Пока процессор деление произведёт - состаришься.
Целочисленное деление на константу вроде все популярные компиляторы радостно преобразовывают в умножение и сдвиги.
Плюс если там только формат хранения, то целочисленного деления может быть и не возникает.
А вещественное. Можно предрассчитать табличку (конкретно для byte). Ну или на худой конец множить на предрассчитаный 1.0/N и что-то думать про точную представимость 1.0=N/N.

>Через всякие int to_int() не нужно. Надо что-то вроде ceil_to_int/floor_to_int/round_to_int
Выглядит здраво.

>Не помешали бы беззнаковые fixed величины, но только без явного каста между fixed/ufixed.
Вызывает смутные опасения.
Но может и можно сделать так, чтобы (пользователю) не нарваться.

Hardcode
Ок.
Data point принят к сведению.

TarasB
Ну походу, да.

Т. е. либо что-то вроде

fixed(long long numerator,long long denominator);

либо что-то вроде

fixed(int32_t integer_part,uint32_t fractional_part);

и обе одновременно предоставлять мягко говоря решение сомнительное.

И конструктор от числа с плавающей точкой, походу, выкинуть нафиг, а сделать явные from_double_floor(), from_double_to_nearest_ties_to_even() и т. д.

Ghost2
Постоялец

#9
11:01, 12 фев 2016

FordPerfect

> Преобразование к встроенным целым?
Чревато багами, проверял на собственном горьком опыте (в коде был operator int). Еще на практике оказалось, что функция from_int не нужна, достаточно явного конструктора. А конструктор типа fixed(int i, int frac) используется крайне редко, но может это специфика.

1 frag / 2 deaths
Участник

#10
11:12, 12 фев 2016

FordPerfect
> Ну походу, да.
У меня есть такие извраты:

class Fixed
{
...
  Fixed(int a, int b) : g( (int)((((long long)a << BP) + (b/2))/b) ) {}
...
};


inline Fixed DoubleToFixed (double a) { return Fixed(Fixed::RAW, int(a*double(1<<Fixed::BP))); }

inline Fixed fxd(int a) { return Fixed(a,10); }
inline Fixed fxh(int a) { return Fixed(a,100); }
inline Fixed fxt(int a) { return Fixed(a,1000); }

const Fixed 
  fx0 = 0, 
  fx1 = 1, 
  fx2 = 2, 
  fx3 = 3, 
  fx4 = 4, 
  fx5 = 5, 
  fx6 = 6, 
  fx7 = 7, 
  fx8 = 8, 
  fx9 = 9, 
  fx10 = 10, 
  fxEps(Fixed::RAW,1), 
  fxHalf(1,2);

Короче, нафиг это говно, пили под версию с пользовательскими литералами. Кстати, с какой студии они есть?

FordPerfect
Постоялец

#11
11:39, 12 фев 2016

TarasB
User-defined floating-point literal с compile-time парсингом строчки символов и внятным округлением?

Нескучно.

Или ты чисто про целочисленные?

FordPerfect
Постоялец

#12
11:46, 12 фев 2016

TarasB
Ну хотя

template<char ... Args>
int operator ""_fix()
{
    char s[sizeof...(Args)+1]={Args...,0};
    return printf("%s",s);
}

выглядит нестрашно.

И сам парсинг... тоже делается.

FordPerfect
Постоялец

#13
11:50, 12 фев 2016

TarasB
>Кстати, с какой студии они есть?
https://msdn.microsoft.com/en-us/library/hh567368.aspx

Visual Studio 2013 No  
Visual Studio 2015 Yes

1 frag / 2 deaths
Участник

#14
12:08, 12 фев 2016

FordPerfect
> User-defined floating-point literal с compile-time парсингом строчки символов и
> внятным округлением?
Да.

FordPerfect
> Нескучно.
Да ничё сложного, мне кажется. Или там ограничения на императивность?

Страницы: 1 2 3 … 7 8 Следующая »

Тема в архиве.