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

Сегодня расскажу Вам что такое 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);
            }
};
Поделиться публикацией
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама

Комментарии 20

    +2
    Проблема производительности FP уже не актульна лет 20, сейчас FP-вычисления могут быть даже быстрее целочисленных (это на x86, не знаю как в других). А вот в плане проблем с унификацией результата вычислений это может помочь (если обычный FP может давать разные результаты на разных платформах, то проэмулированый даст один и тот же).
      +2
      Проблема мега актуальна для микроконтроллеров, DSP и FPGA, где FPU нет, либо оно медленное, либо затратное по аппаратным ресурсам. Кроме того, еще лет 10 назад операции с плавающей точкой даже на x86 были медленнее, чем целочисленные. Читал в руководстве от Intel по оптимизации с применением MMX, SSE и т.д. Там предлагается в первую очередь отказаться от чисел с плавающей точкой, если это возможно.
        0
        Медленнее максимум в несколько раз, и по-этому бороться с ними эмулятором не получится — разве что полным отказом от FP, как Вы и сказали.
          0
          Читал в руководстве от Intel по оптимизации с применением MMX, SSE и т.д. Там предлагается в первую очередь отказаться от чисел с плавающей точкой, если это возможно.

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

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

          0
          Да даже если есть в контроллере 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 появятся.
            +2
            Работают, из недавних есть P0037R6
              +3
              для каждой переменной и для каждой операции приходилось писать комментарий — сколько тут знаков до запятой и после:)

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

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

                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
                
                


                  +3

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

                0
                Спасибо, автор. Тема актуальная.
                  +4
                  typedef signed int __int32_t;
                  en.cppreference.com/w/cpp/header/cstdint
                    +3

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

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

                        2^8 = 1024???

                          +1

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

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

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

                              0
                              12 лет назад писал библиотеку FixedPoint для embedded-камня без FPU. Надо поковыряться, поискать, где она у меня. Была поддержка прямой и обратной тригонометрии и несколько других приятных плюшек.
                                0
                                typedef signed int __int32_t;

                                Зачем изобретать велосипед? Есть же int32_t.

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

                                Самое читаемое