Сегодня расскажу Вам что такое 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);
            }
};

Комментарии (18)


  1. picul
    15.05.2019 13:34

    Проблема производительности FP уже не актульна лет 20, сейчас FP-вычисления могут быть даже быстрее целочисленных (это на x86, не знаю как в других). А вот в плане проблем с унификацией результата вычислений это может помочь (если обычный FP может давать разные результаты на разных платформах, то проэмулированый даст один и тот же).


    1. MichaelBorisov
      15.05.2019 14:13

      Проблема мега актуальна для микроконтроллеров, DSP и FPGA, где FPU нет, либо оно медленное, либо затратное по аппаратным ресурсам. Кроме того, еще лет 10 назад операции с плавающей точкой даже на x86 были медленнее, чем целочисленные. Читал в руководстве от Intel по оптимизации с применением MMX, SSE и т.д. Там предлагается в первую очередь отказаться от чисел с плавающей точкой, если это возможно.


      1. picul
        15.05.2019 16:06

        Медленнее максимум в несколько раз, и по-этому бороться с ними эмулятором не получится — разве что полным отказом от FP, как Вы и сказали.


      1. berez
        15.05.2019 18:30

        Читал в руководстве от Intel по оптимизации с применением MMX, SSE и т.д. Там предлагается в первую очередь отказаться от чисел с плавающей точкой, если это возможно.

        И сейчас предлагается. Только причина не в том, что floating point медленный, а в том, что расширения MMX и SSE используют регистры математического сопроцессора. То есть если программа использует и то, и другое, придется постоянно сохранять и восстанавливать регистры сопроцессора, а это много (больше 100 байт, если я правильно помню) и долго.


  1. NeoCode
    15.05.2019 13:39
    +1

    Странно что fixed point не поддерживается на уровне языка c/c++. Я когда-то писал программу для микроконтроллера в которого не было FPU. Конечно написать можно и так, но для каждой переменной и для каждой операции приходилось писать комментарий — сколько тут знаков до запятой и после:)


    1. Mirn
      15.05.2019 15:12

      Да даже если есть в контроллере FPU, то часто бывает супер скалярность и SIMD инструкции когда сразу вычисляется умножение нескольких 16 битных пар X и W с накоплением в аккумулятор 32 битный. Я поступал так: просто завёл два типа 16 и 32 бита int внутри и сделал так чтоб они между собой были не совместимы с ошибками компиляции. И набор функций конвертации — просто сдвиги с явным привидением типа.
      Бонусом то что FPU всегда требует дополнительной конвертации int в флоат и обратно и это не параллелится. Но для fixed SIMD обычная загрузка позволяет загружать до 4 значений X или W сразу и она паралеллится с самой вычисляющей SIMD FMA инструкций — итого по две инструкции за ОДИН такт, и обе из них векторные которые обрабатывают несколько пар.

      Итог:
      на FPU нейросеть на 1000 классов — не более одной FPS ровно,
      на фиксед с SIMD — несколько FPS.
      И это притом что помимо нейросетки необходимо захватывать сырой raw с камеры, дебаеринг, денойз делать, а потом результаты выводить в графический интерфейс с тачами и жестами, окнами и оверлеями в реалтайме. И это всё на одном ядре контроллера. Хотя скоро двуядерные кортекс М7 появятся.


    1. Kyoki
      15.05.2019 15:46

      Работают, из недавних есть P0037R6


    1. lgorSL
      16.05.2019 00:48
      +1

      для каждой переменной и для каждой операции приходилось писать комментарий — сколько тут знаков до запятой и после:)

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


    1. Keroro
      16.05.2019 06:38

      Я пришёл к такой системе:

      struct 
      {
              uint16_t Value;
              uint8_t FixedPoint;
       }fPointVal;
      
      fPointVal Temperature;
      
      Temperature.Value=366;
      Temperature.Point=1;
      
      LCD_print_fixed(0, 0, Temperature.Value, Temperature.Point); //36.6
      
      



      1. Dima_Sharihin
        16.05.2019 13:05

        Добавьте бит знака, сделайте Value 24-битным, FixedPoint — 7-битным и показывающим положение двоичной точки и вы получите IEEE-754 Single-Precision Floating Point


  1. MichaelBorisov
    15.05.2019 14:18

    Спасибо, автор. Тема актуальная.


  1. rogoz
    15.05.2019 15:53
    +1

    typedef signed int __int32_t;
    en.cppreference.com/w/cpp/header/cstdint


  1. mayorovp
    15.05.2019 16:13
    +1

    signed int и DIGITS стоило бы сделать параметрами шаблона.


  1. unC0Rr
    15.05.2019 16:30
    +1

    Интуитивно кажется, что лучше операцию умножения всегда выполнять по ветке с защитой от переполнения, чем при каждом умножении делать дополнительное деление с возможным пересчётом результата.


    1. unC0Rr
      15.05.2019 16:45

      Ещё дополню: операцию возведения в квадрат можно сделать быстрее, чем умножение числа на само себя (три умножения вместо четырёх), а операцию деления можно сделать точнее за счёт более точного вычисления выражения (i*DIGITS)/b.x (по указанной в статье формуле 1 / 3 будет вычислено равным нулю).


  1. sergio_nsk
    15.05.2019 18:21
    +3

    2^8 = 1024???


  1. Temtaime
    15.05.2019 21:33
    +1

    fmul никто уже давно не использует, как и весь x87.
    SSE и mulss.


  1. FGV
    16.05.2019 09:12

    При выполнении операций умножения и деления возможен случай переполнения…

    Все гараздо страшнее — переполнение может возникнуть и при сложении/вычитании.
    А вот умножение и деление кстати можно организовать так что переполнения не будет — через отбрасывание мл. части для умножения и через сдвиг делимого в старшую часть. Для деления правда будут ограничения — делимое должно быть меньше делителя.