Практика
Числа с фиксированной точностью (запятой)

:: Меню ::
:: На главную ::
:: FAQ ::
:: Заметки ::
:: Практика ::
:: Win API ::
:: Проекты ::
:: Скачать ::
:: Секреты ::
:: Ссылки ::

:: Сервис ::
:: Написать ::

:: 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
  1. Для с = a + b : x + y = a * d + b * d = (a+b) * d = c * d = z
  2. Для с = a - b : x - y = a * d - b * d = (a-b) * d = c * d = z
Здесь все просто и понятно. Дальше интереснее:
  1. Для с = a * b : x * y = a * d * b * d = ((a * b) * d )*d = c * d * d = z * d
как видим результат отличается в d раз. И самым логичным было бы просто разделить на d.
z = (x * y) / d
Но не все так просто. Мы натыкаемся на проблему нехватки разрядности. Подробнее об этом будет говориться при разборе примера.
  1. Для с = a / b : x / y = a * d / (b * d) = a / b = c
И самым логичным было бы просто умножить на d.
z = x / y * d
Но тогда мы натыкаемся на проблему потери дробной части. Решение опять же описано при разборе примера.
С логическими операциями сравнения все тривиально.
  1. Если a < b тогда x < y
  2. Если a > b тогда x > y
  3. Если a <= b тогда x <= y
  4. Если a >= b тогда x >= y
  5. Если a = b тогда x = y
  6. Если 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). В делении операция умножения (сдвиг влево) делается раньше деления, для предотвращения потери дробной части.

Эпизод пятый – пару слов о разрядности

Применять числа с фиксированной точностью можно везде, где применяются числа с плавающей запятой, но требуется большая скорость вычислений. Но надо помнить: отдадим много под целое число, получим огромные погрешности в дробной части. Сделаем большую дробную часть, будем натыкаться на превышении разрядности при вводе большого числа.

И к подбору разрядности дробной части:

TNumber.FCap

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

Пример: Проект будет строить 3D сцену на экране 1280x1024. 1280 больше чем 2 в 11 степени и меньше чем 2 в 12 степени. И так отдает под целую часть 12 бит. А под дробную часть 32 – 12 - 1 = 19 бит (один бит резервируем под знак). И устанавливаем:

TNumber.FCap := 19

Эпизод шестой – применение

Типичный вариант использования:
Создаем массив всех значении синусов в градусной мере:

FixSin: array[0..359] Of TNumber;

Инициализируем его:

for i := 0 to 359 do
   FixSin[i] := TNumber( sin( i*Pi/180 ) );
// Примечание: I*Pi/180 – перевод из градусов в радианы

Получение значения синуса 30 градусов:

FixSin[30].ToFloat

Заключение

С появлением многопоточных графических процессоров рассчитанных на быстрое вычисление однотипных операций над числами с плавящей запятой технология работы с фиксированной запятой используется все реже и реже. Но знания этой технологии и умение ее правильно использовать может пригодится там, где нет таких мощных процессоров. КПК, Телефоны, Телевизоры уже имеют в своем распоряжении игры, и такая тенденция продолжиться и в будущем. Ищите, где можете применить знания, полученные из этой статьи, и кто знает, может сам Билл придет к вам с прошением о кредите!

Автор: Thunderchild.

.: Пример к данной статье :.


При использовании материала - ссылка на сайт обязательна