Компьютерная графика :: Теория 2D :: Числа с фиксированной точкой

Компьютерная графика

теория, алгоритмы, примеры на С++ и OpenGL

2D теория

3D теория

OpenGL

Обратная связь / Авторам

Мы vkontakte.ru

Друзья

Словарь синонимов русского языка

Числа с фиксированной точкой

Большим преимуществом чисел в формате плавающей точкой является точность. Но, анализируя некоторые алгоритмы, приходим к выводу, что точности в четыре знака после запятой более чем достаточно. (Яркий пример такого класса алгоритмов – алгоритмы растеризации). А обеспечить такую точность можно всего двумя байтами. Действительно, требуется хранить 10000 градаций: 0.0000 – 0.9999, в то время как 2 байта позволяют хранить 65536.

Идея арифметики с фиксированной точкой состоит в следующем. Возьмем четырехбайтный тип данных (тип int в 32-разрядном компиляторе С++). Будем использовать старшие два байта (слово) под целую часть числа, а младшие – под вещественную.

Пример. Число 123.654 представится в виде:

123

654

Число 123.654 * 2¹⁶ = 8060928 + 42860 = 8103788

Заметим, что числа, хранящиеся в таком представлении, можно:

складывать и вычитать между собой;
делить и умножать на целые числа в обычном представлении.

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

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

Ниже приведена реализация чисел с фиксированной точкой на языке С++:

// fixed.h
#ifndef __FIXED__
#define __FIXED__

#include "math.h"

#define fixed int
#define round(x) floor(x + 0.5)
#define roundf(x) floor(x + 0.5f)

// представляет целое число в формате чисел с фиксированной точкой
inline fixed int_to_fixed(int value)
{
      return (value << 16);
}

// целая часть числа с фиксированной точкой
inline int fixed_to_int(fixed value)
{
      if (value < 0) return (value >> 16 - 1);
      if (value >= 0) return (value >> 16);
}

// округление до ближайшего целого
inline int round_fixed(fixed value)
{
      return fixed_to_int(value + 5 << 15);
}

// представляет число с плавающей точкой в формате чисел с фиксированной точкой
// здесь происходят большие потери точности
inline fixed double_to_fixed(double value)
{
      return round(value * (65536.0));
}

inline fixed float_to_fixed(float value)
{
      return roundf(value * (65536.0f));
}

// записывает отношение (a / b) в формате чисел с фиксированной точкой
inline fixed frac_to_fixed(int a, int b)
{
      return (a << 16) / b;
}

#endif

Прим. Округление до ближайшего целого можно сделать так: округляем вниз (floor) число плюс 0.5. Выше это делается директивой #define:

#define round(x) floor(x + 0.5)

При этом можно складывать и вычитать два числа в формате fixed. С умножением и делением все немного сложнее. Умножать имеет смысл только fixed на int. Делить можно fixed на int, тогда получится снова fixed. Если разделить fixed на fixed, получится int.

Пример:

fixed a, b, c;
int d;

a = int_to_fixed(100);
b = int_to_fixed(10);
d = a / b; // d будет содержать 10 в формате int
c = a / 10; // с будет содержать 10 в формате fixed

c = a + b; // c будет содержать 110.0 в формате fixed

Скачать библиотеку (fixed.h) и исходный текст демонстрационной программы