|
:: MVP ::
|
|
|
:: RSS ::
|
|
|
Здравствуй пытливый ум. Если ты слышал про числа с фиксированной точностью,
но не знал, как реализовать или никогда не слышал, но открыт для всего нового -
эта статья для тебя!
Меня давно посещала мысль написать модуль для работы с числами фиксированной точности.
Познакомился я с ними давным-давно, разбираясь, как же разработчики игры DOOM смогли
создать целый 3D мир, который можно увидеть на компьютерах до пентиумовской эпохи с
видеокартой без каких либо ускорителей.
С тех пор прошло немало времени, но как оказалось, эта тема не утратила свою актуальность,
и после недолгих раздумий я решился поделиться с вами результатами моих давних изысканий,
и с рвением принялся за дело.
Эпизод первый – предисловие
Заглянув в описание типов данных, которыми оперирует компьютер, видишь, что есть целые числа
с быстрой арифметикой и числа с плавающей запятой и с медленным математическими операциями.
А что делать, если мы пишем 3D игру, где FPS должны быть максимальными и расчеты вести с
использованием тригонометрических функций? Ответ прост - использовать числа с фиксированной
точностью. Но вот незадача – в Delphi такого типа данных просто нет. Значит, будет создавать!
Для начала сформулируем, что же это такое – числа с фиксированной точностью. Фиксированная
запятая – формат представления вещественного числа в памяти ЭВМ в виде целого числа. При
этом само число x и его целочисленное представление x' связаны формулой x = x' * z, где z —
цена (вес) младшего разряда. Простейший пример арифметики с фиксированной запятой — перевод
рублей в копейки. В таком случае, чтобы запомнить сумму 24 рублей 17 копейки, мы записываем
в ячейку памяти число 2417.
Эпизод второй – идея
Integer имеет диапазон значений -2147483648 .. 2147483647 и занимает 32 бита. А вот,
к примеру, в OpenGL сцена (по умолчанию) имеет координаты -1..1. Так вот, почему бы не
использовать 1 бит на знак, 1 бит на целую часть и целых 30! бит на дробную часть?
Вторичной выгодой использования целых чисел будет возможность замены умножения и деления
на сдвиги, что положительно скажется на скорости вычислений.
Эпизод третий – теория
Пусть у нас есть два числа a и b. И мы вводим два уравнения x = a * d и y = b * d, где d = const.
Тогда, если z = c * d
- Для с = a + b : x + y = a * d + b * d = (a+b) * d = c * d = z
- Для с = a - b : x - y = a * d - b * d = (a-b) * d = c * d = z
Здесь все просто и понятно. Дальше интереснее:
- Для с = a * b : x * y = a * d * b * d = ((a * b) * d )*d = c * d * d = z * d
как видим результат отличается в d раз. И самым логичным было бы просто разделить на d.
z = (x * y) / d
Но не все так просто. Мы натыкаемся на проблему нехватки разрядности. Подробнее об этом
будет говориться при разборе примера.
- Для с = a / b : x / y = a * d / (b * d) = a / b = c
И самым логичным было бы просто умножить на d.
z = x / y * d
Но тогда мы натыкаемся на проблему потери дробной части. Решение опять же описано при разборе примера.
С логическими операциями сравнения все тривиально.
- Если a < b тогда x < y
- Если a > b тогда x > y
- Если a <= b тогда x <= y
- Если a >= b тогда x >= y
- Если a = b тогда x = y
- Если a <> b тогда x <> y
Эпизод четвертый – реализация
В примере используются перегрузка операторов, подробнее о которой можно узнать из статьи
Перезагрузка операторов.
Весь модуль описывать не стану, опишу только умножение и деление как наиболее сложные элементы:
class operator TNumber.Multiply( Val1, Val2: TNumber ): TNumber;
begin
Result.FVal := ( Int64( Val1.FVal ) * Int64( Val2.FVal ) ) shr FCap;
end;
class operator TNumber.Divide( Val1, Val2: TNumber ): TNumber;
begin
Result.FVal := ( Int64( Val1.FVal ) shl FCap ) div Val2.FVal;
end;
|
Для того что бы не потерять данные из-за сдвигов или из-за переполнения разрядности
используется 64 битное промежуточное значение. (Примечание: команды процессора поступают
точно так же, к примеру команда mult AX результат возвращает в EAX). В делении операция
умножения (сдвиг влево) делается раньше деления, для предотвращения потери дробной части.
Эпизод пятый – пару слов о разрядности
Применять числа с фиксированной точностью можно везде, где применяются числа с плавающей
запятой, но требуется большая скорость вычислений. Но надо помнить: отдадим много под целое
число, получим огромные погрешности в дробной части. Сделаем большую дробную часть, будем
натыкаться на превышении разрядности при вводе большого числа.
И к подбору разрядности дробной части:
надо подойти ответственно, исходя из данных конкретной задачи. Можно начать с определения
максимального по модулю значения.
Пример: Проект будет строить 3D сцену на экране 1280x1024. 1280 больше чем 2 в 11 степени и
меньше чем 2 в 12 степени. И так отдает под целую часть 12 бит. А под дробную часть 32 – 12 - 1
= 19 бит (один бит резервируем под знак). И устанавливаем:
Эпизод шестой – применение
Типичный вариант использования:
Создаем массив всех значении синусов в градусной мере:
FixSin: array[0..359] Of TNumber;
|
Инициализируем его:
for i := 0 to 359 do
FixSin[i] := TNumber( sin( i*Pi/180 ) );
// Примечание: I*Pi/180 – перевод из градусов в радианы
|
Получение значения синуса 30 градусов:
Заключение
С появлением многопоточных графических процессоров рассчитанных на быстрое вычисление
однотипных операций над числами с плавящей запятой технология работы с фиксированной запятой
используется все реже и реже. Но знания этой технологии и умение ее правильно использовать
может пригодится там, где нет таких мощных процессоров. КПК, Телефоны, Телевизоры уже имеют
в своем распоряжении игры, и такая тенденция продолжиться и в будущем. Ищите, где можете
применить знания, полученные из этой статьи, и кто знает, может сам Билл придет к вам с
прошением о кредите!
Автор: Thunderchild.
.: Пример к данной статье :.
|
|
При использовании материала - ссылка на сайт обязательна
|
|
