Pull to refresh

Арифметика fixed-point на C++

Reading time 3 min
Views 21K
Сегодня расскажу Вам что такое fixed-point, зачем он нужен и как его можно использовать.

Существует такая проблема когда производительность приложения может заметно ухудшиться из-за особенностей вычисления на числах с плавающей точкой. Как правило CPU заточен под целочисленные операции, а сопроцессор FPU (floating point unit) в нем работает на порядке медленнее. Существую такие платформы где вообще отсутствует FPU и эмулирование операций с числами занимало бы много времени. Например, при наличии FPU, умножение чисел с плавающей точкой выполняется всего одной командой fmul, а при отсутствии FPU, умножение выполняется эмулирующей функцией __mulsf3. По сравнению с командой fmul, функция __mulsf3 эмулирует операции над числами с плавающей точкой, при этом вычисления производятся в целочисленном виде, что приводит к увеличению машинного кода и времени на его выполнение, в то время как команда fmul выполнит эту операцию быстро, с использованием аппаратных средств.

Данной проблеме существует решение, которое позволяет проводить вычисления с фиксированной точкой на целочисленном типе.

Принцип данного типа заключается в фиксированном сдвиге числа на N бит, в результате чего дробное число можно представить целым и оно будет иметь точность 2^N после точки. Пример преобразования числа с плавающей точкой в число с фиксированной точкой порядка 8 бит (2^8 = 1024).

Вот пример перевода числа с плавающей точкой в число с фиксированной точкой:

Fixed(12345,6789) = 1024 * 12345,6789 = 12641975,<s>1936</s>

Данное число, после точки, имеет точность 2^8 после запятой.

Пример обратного перевода числа с фиксированной точкой в число с плавающей точкой.

Float(12641975) = 12641975 / 1024 = 12345,678<s>7109375</s>

В данном случае число после обратного перевода имеет вид 12345,6787109375 и является точным в 3 знака после точки, максимальная точность на самом деле равна 2^8 = 1024.

Как происходят вычисления на типе с фиксированной точкой?


Операции суммы и разности эквивалентны обычным целочисленным операциям.

Fixed(x) + Fixed(y) и Fixed(x) - Fixed(y), с любым порядком
(1024 * x) + (1024 * y) и (1024 * x) - (1024 * y)

Умножение таких чисел производится в такой форме.
(Fixed(x) * Fixed(y)) / p, это эквивалентно, с порядком 8 бит
((1024 * x) * (1024 * y)) / 1024

Деление.
(Fixed(x) * p) / Fixed(y), также с порядком 8 бит, это
(1024 * 1024 * x)*(1024 * y)

Переполнение


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

  • Выполнить вычисления в 64-битном целочисленном типе.
  • Выполнить вычисления в «разобранном» виде, например при умножении, (xi+xf)*(yi+yf) = xi*yi+xf*yf+xi*yf+yi*xf, приставки i и f означают целую часть и часть после точки.

Класс для работы с fixed-point на C++


#define DIGITS 1024 // экспонента
#define EPS 20 // константа устанавливающая границы приближенности вычисления корня

using namespace std;
typedef signed int __int32_t;
      
class Fixed {
      signed int x;

      Fixed(signed int a){
            x = a;
      }
      public:
            Fixed(){
                  x = 0;
            }
            static Fixed fromInt(signed int val){
                  return Fixed(val*DIGITS);
            }
            static Fixed fromFloat(float val){
                  return Fixed((signed int)(val*DIGITS));
            }
            float fixed2float(){
                  return ((float)x)/DIGITS;
            }
            Fixed sum(Fixed a,Fixed b){
                  return Fixed(a.x+b.x);
            }
            Fixed diff(Fixed a,Fixed b){
                  return Fixed(a.x-b.x);
            }
            Fixed mul(Fixed a,Fixed b){
                  signed int c=a.x*b.x;
                  if(c/b.x != a.x){
                        // Overflow!
                        signed int i1 = a.x/DIGITS;
                        signed int i2 = b.x/DIGITS;
                        signed int f1 = (a.x&(DIGITS-1));
                        signed int f2 = (b.x&(DIGITS-1));
                        return Fixed((i1*i2)*DIGITS+(f1*f2)/DIGITS+i1*f2+i2*f1);
                  }else{
                        return Fixed(c/DIGITS);
                  }
            }
            Fixed div(Fixed a,Fixed b){
                  if(a.x>(1<<21)){
                        // Overflow!
                        signed int i = a.x/DIGITS;
                        signed int f = (a.x&(DIGITS-1));
                        return Fixed(((i*DIGITS)/b.x)*DIGITS+(f*DIGITS)/b.x);
                  }else{
                        return Fixed((a.x*DIGITS)/b.x);
                  }
            }
            Fixed sqrt(Fixed k){
                  Fixed tmp(0);
                  tmp.x = k.x/2;
                  signed int min = 0;
                  signed int max = k.x;
                  Fixed quick(0);
                  do{
                        tmp.x = (min+max)/2;
                        quick = Fixed::mul(tmp,tmp);
                        if(abs(quick.x-k.x)<EPS) return Fixed(tmp);
                        if(quick.x>k.x){
                              max = tmp.x;
                        }else{
                              min = tmp.x;
                        }
                  }while(true);
            }
};
Tags:
Hubs:
+11
Comments 22
Comments Comments 22

Articles