Собственные реализации плавающей запятой - примеры есть?

Общие вопросы программирования, алгоритмы и т.п.

Модератор: Модераторы

Собственные реализации плавающей запятой - примеры есть?

Сообщение Cheb » 23.04.2015 10:28:11

Код: Выделить всё
type float = bitpacked record
    sign: 0..1;
    exponent: 1..$fe;
    fraction: 0..$7fffff;
  end;
  operator * (a, b: float) z: float;
  operator / (a, b: float) z: float;
  operator + (a, b: float) z: float;
[...]


Вопрос: есть ли примеры реализации работы с подобным?
Сам я велосипед изобрести могу и готов, но если можно избежать этой мутоты...

Зачем:
Гарантированный, крос-платформенный детерминизм.
Стандартная реализация плавающей запятой не позволяет надеяться на побитовую идентичность вычислений. В основном из-за: реализаций SSE, потенциально различных ключей компиляции под разные платформы и прочая. Слишком много факторов чтобы быть уверенным.
Я готов заплатить 10-кратным (или сколько там) падением производительности за гарантированную воспроизводимость.

Зачем:
Для продвинутого, ММО-способного движка. Передача по сети только инпутов игроков, синхронизированный мир с тысячами активных объектов.

Ранее я планировал использовать fixed point, и даже большинство операторов реализовал. Но потом понял, что с этим будет слишком много геморроя. :x Лучше просто свой флоат с блэкджеком и шлюхами. :roll:
Аватара пользователя
Cheb
энтузиаст
 
Сообщения: 994
Зарегистрирован: 06.06.2005 15:54:34

Re: Собственные реализации плавающей запятой - примеры есть?

Сообщение Mikhail » 23.04.2015 10:33:33

Cheb писал(а):Зачем:
Для продвинутого, ММО-способного движка. Передача по сети только инпутов игроков, синхронизированный мир с тысячами активных объектов.


Все равно не понятно зачем. Зачем нужна арифметика?
Mikhail
энтузиаст
 
Сообщения: 565
Зарегистрирован: 24.10.2013 16:06:47

Re: Собственные реализации плавающей запятой - примеры есть?

Сообщение Vapaamies » 23.04.2015 12:09:51

А Real48 в FPC нет? Если целевая платформа -- только Windows, можно на Delphi написать DLL с Real48 и использовать из FPC.
Аватара пользователя
Vapaamies
постоялец
 
Сообщения: 292
Зарегистрирован: 24.07.2012 22:37:59
Откуда: Санкт-Петербург

Re: Собственные реализации плавающей запятой - примеры есть?

Сообщение Дож » 23.04.2015 13:21:35

Мне кажется IEEE 754 настолько распространённым и поддерживаемым, что лучше использовать его на большинстве платформ, а в особых случаях эмулировать арифметику на процессоре.

Либо написать свою надстройку над стандартными single/double, исправляющую все различия.
Аватара пользователя
Дож
энтузиаст
 
Сообщения: 899
Зарегистрирован: 12.10.2008 16:14:47

Re: Собственные реализации плавающей запятой - примеры есть?

Сообщение Cheb » 23.04.2015 14:18:03

А Real48 в FPC нет?

Есть как *затычка*, чтобы позволить читать древние файлы данных. Но для вычислений он преобразуется в double. Математики в нём нет.
Целевая платформа - в перспективе Линукс 64 и Виндовс 64 и 32.

Зачем нужна арифметика?

Побитовая синхронность мира.
Образно говоря, мир размером 100 Мб выращивается из 16-байтного seed. Потом в нём происходит изменений на 50 Мб, но по сети передаётся, скажем, лишь 50 Кб описания шевелений мышью. Мир у всех игроков одинаковый потому что изменения происходят абсолютно одинаково.

IEEE 754 настолько распространённым и поддерживаемым,

Но идентичность вычислений не гарантируется. Если бы я ограничился одной платформой (скажем, win32) и следил, чтобы не использовать SSE - то тогда *может быть*. Да и то были случаи, когда у людей варкрафт рассинхронизировался из за *крохотной* подлянки в процессорах AMD при арифметике с очень большими числами.
То есть, производители процессоров ещё пытаются держать совместимость, но всё упирается в компилятор который может, например для виндовс и для линукс чуточку по разному соптимизировать. И опять же, для SSE все на побитную предсказуемость забили. А ещё есть тригонометрическиф функции, для которых никто никогда не гарантировал.


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

Не катит. Один бит не совпал - всей птичке пропасть.

Физика и логика должны обладать полным детерминизмом.

P.S. Если кто ещё не заметил, формат этой штуки абсолютно идентичен типу single:
Код: Выделить всё
type float = bitpacked record
    sign: 0..1;
    exponent: 1..$fe;
    fraction: 0..$7fffff;
  end;

т.е. 32-битное IEEE 754 число с плавающей запятой.
Нужно лишь написать для него собственные математические функции с гарантированным детерминизмом
Аватара пользователя
Cheb
энтузиаст
 
Сообщения: 994
Зарегистрирован: 06.06.2005 15:54:34

Re: Собственные реализации плавающей запятой - примеры есть?

Сообщение Vapaamies » 23.04.2015 19:08:21

Cheb писал(а):То есть, производители процессоров ещё пытаются держать совместимость, но всё упирается в компилятор который может, например для виндовс и для линукс чуточку по разному соптимизировать.

Угу, мы обсуждали проблему плавающей арифметики на OSDev.ru, но тема теоретическая, за реализацию никто не брался.
Аватара пользователя
Vapaamies
постоялец
 
Сообщения: 292
Зарегистрирован: 24.07.2012 22:37:59
Откуда: Санкт-Петербург

Re: Собственные реализации плавающей запятой - примеры есть?

Сообщение kazalex » 23.04.2015 20:41:34

Cheb писал(а):Сам я велосипед изобрести могу и готов, но если можно избежать этой мутоты...

Не знаю поможет ли, но можешь посмотреть в softfpu.pp
kazalex
постоялец
 
Сообщения: 296
Зарегистрирован: 01.06.2012 14:54:10

Re: Собственные реализации плавающей запятой - примеры есть?

Сообщение pda » 23.04.2015 23:34:58

Библиотека, тесты, лицензия BSD.
Аватара пользователя
pda
постоялец
 
Сообщения: 303
Зарегистрирован: 27.05.2005 19:59:53

Re: Собственные реализации плавающей запятой - примеры есть?

Сообщение Cheb » 24.04.2015 17:17:02

softfpu.pp

:D Выглядит обещающе :D


P.S. Только ф-ю countLeadingZeros32 переделать на asm bsf + cmovz :x

*страшно* раздражает отсутствие в языке операторов bsr / bsf , из за чего приходится городить циклы там, где у процессора для этого есть машинная команда :evil:

Потому что ассемблерные вставки - это не есть гуд. Они не портируемые, и как кость в горле у оптимизатора.
Аватара пользователя
Cheb
энтузиаст
 
Сообщения: 994
Зарегистрирован: 06.06.2005 15:54:34

Re: Собственные реализации плавающей запятой - примеры есть?

Сообщение скалогрыз » 24.04.2015 19:22:32

Cheb писал(а): :D Выглядит обещающе :D

имхо fixed-point таки надёжнее, ибо soft-float это тот же геморрой.

Cheb писал(а):P.S. Только ф-ю countLeadingZeros32 переделать на asm bsf + cmovz :x

*страшно* раздражает отсутствие в языке операторов bsr / bsf , из за чего приходится городить циклы там, где у процессора для этого есть машинная команда :evil:

bsfdword? (в секции See Also ссылки на все поддерживаемые bsfXXX типы) ну и их BSR аналоги :)

Ситуация схожа с тем, что win32 не поддерживает адресацию больше 2 гигов? ;)
скалогрыз
долгожитель
 
Сообщения: 1803
Зарегистрирован: 03.09.2008 02:36:48

Re: Собственные реализации плавающей запятой - примеры есть?

Сообщение Cheb » 25.04.2015 14:19:53

bsfdword?

Изображение

Ещё раз убеждаюсь, как страшно Фри Паскаль страдает от нехватки чего-то хотя бы на уровне http://php.net/

Сколько замечательных фич разработчиками - и никто не пользуется, потому что никто не знает (поиск по исходникам RTL дал ноль использований этой функции). Очень обидно. :(

имхо fixed-point таки надёжнее, ибо soft-float это тот же геморрой.

Мммм... Наверно, так и сделаю. Действительно геморрой.

Во первых, 32 бита - это таки дохрена много. Если правильно разместить точку - это таки 65535 километров с разрешением 15 мм. Этого *уже* хватило бы, т.к. я планирую *хитрую* систему представления медленных движений снижением частоты просчётов физики для объекта. Например, вектор скорости - это три 16-битных целых плюс экспонента, общая на всех. Весь вектор - 64 бита.

Потом, можно объявить один и тот же фиксированный тип несколько раз для разных диапазонов, состыковав их через операторы присваивания младшего старшему, включающие умножение на константу (< 1.0), а присваивание старшего младшему - недопустимая операция.
Заодно дисциплинирует при написании ИИ, оперирующего этими понятиями.

Хммм... Тогда, 1.0 будет
ближняя детализованная зона: один метр. Предел - 32 километра, погрешность 0.01 мм.
планета: один километр. Предел 32767 километров, погрешность 15мм.
система: одна А.Е. Предел и погрешность - настраиваемые в рантайме, в зависимости от масштаба мира.
Изначально планирую полу-игрушечную вселенную, где радиус Земли - 60 км. Тогда одна А.Е. будет 1.5 млн.км., погрешность 22км. Сравнимо с радиусом планеты :evil: Так. Стоп. Не катит. На кой мне межзвёздные расстояния? Жёстко ограничить размер системы 32.768 А.Е, воткнуть один-два Юпитера на 5..6 А.Е., до которых лететь месяц реального времени - и на этом всё, никакого пояса Койпера. Это скучно и для геймплея нафиг не нужно. Тогда 1.0 - это 0.001 А.Е, погрешность 22 метра. Катит. А если корабли сойдутся в космосе - выделять им локальные системы координат масштабов планета и локальная. Пусть относительно неё крутятся.

увгнор [сгоняет голубя с клавиатуры] В принципе, дальше можно не идти, т.к. межзвёздные перелёты не планируются, их роль исполнят порталы в параллельные миры (как вариант - гиперджамп, жёско привязанный к звёздам), и звёзды - не более, чем серебряные гвозди на чёрном скайбоксе.

Для полного использования диапазона нужно везде, где используется возведение в квадрат (типа расчёта расстояния), разработать функции с внутреней точность 64 бита, чтобы без переполнения высирали обратно 32-битное фиксированное, приведённое обратно к диапазону.

Опять же, пичалька: где взять fast inverse square root для фиксированных чисел? Я слишком валенок в математике чтобы портировать этот метод самому. :x
Аватара пользователя
Cheb
энтузиаст
 
Сообщения: 994
Зарегистрирован: 06.06.2005 15:54:34

Re: Собственные реализации плавающей запятой - примеры есть?

Сообщение pda » 26.04.2015 00:13:59

Cheb писал(а):Ещё раз убеждаюсь, как страшно Фри Паскаль страдает от нехватки чего-то хотя бы на уровне http://php.net/

Не поможет. Читать документацию для большинства - моветон. :)
Аватара пользователя
pda
постоялец
 
Сообщения: 303
Зарегистрирован: 27.05.2005 19:59:53

Re: Собственные реализации плавающей запятой - примеры есть?

Сообщение скалогрыз » 26.04.2015 04:31:00

Cheb писал(а):Опять же, пичалька: где взять fast inverse square root для фиксированных чисел? Я слишком валенок в математике чтобы портировать этот метод самому.

алгоритм основан на особенностях представления float-point числа в битах.
Так что способ портирования прост:
Код: Выделить всё
  FixedToSingle();
  InvSqrt()
  Result:= SingleToFixed();


Добавлено спустя 31 секунду:
pda писал(а):Не поможет. Читать документацию для большинства - моветон.

+1
скалогрыз
долгожитель
 
Сообщения: 1803
Зарегистрирован: 03.09.2008 02:36:48

Re: Собственные реализации плавающей запятой - примеры есть?

Сообщение daesher » 26.04.2015 09:20:46

Куда полезнее "набросать" десятибайтный soft-extended для 64-ричного кода (хотя бы его преобразование в double с потерей точности).
daesher
постоялец
 
Сообщения: 221
Зарегистрирован: 09.03.2010 22:17:14

Re: Собственные реализации плавающей запятой - примеры есть?

Сообщение PapaNT » 29.04.2015 11:59:58

Ни кто не думал про асимметричный ответ в виде строкового представления чисел? :lol:
PapaNT
постоялец
 
Сообщения: 167
Зарегистрирован: 11.09.2009 12:06:46
Откуда: Москва

След.

Вернуться в Общее

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 21

Рейтинг@Mail.ru
cron