Арифметика с фиксированной точкой

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

В вычислениях представление числа с фиксированной запятой является реальным типом данных для числа, которое имеет фиксированное количество цифр после (а иногда и до) точки счисления (после десятичной точки '.' В английской десятичной системе счисления). Представление чисел с фиксированной запятой можно сравнить с более сложным (и более требовательным к вычислениям) представлением чисел с плавающей запятой .

Числа с фиксированной запятой полезны для представления дробных значений , обычно с основанием 2 или основанием 10, когда исполняющий процессор не имеет блока с плавающей запятой (FPU), как в случае со старыми или недорогими встроенными микропроцессорами и микроконтроллерами , если с фиксированной запятой обеспечивает повышенную производительность или точность для данного приложения или, если их использование более естественно для задачи (например, для представления углов ).

Представление [ править ]

Значение типа данных с фиксированной точкой - это, по сути, целое число , масштабируемое неявным конкретным коэффициентом, определяемым типом. Например, значение 1,23 может быть представлено как 1230 в типе данных с фиксированной запятой с коэффициентом масштабирования 1/1000, а значение 1,230,000 может быть представлено как 1230 с коэффициентом масштабирования 1000. В отличие от типов данных с плавающей запятой, коэффициент масштабирования одинаков для всех значений одного типа и не изменяется в течение всего вычисления.

Коэффициент масштабирования обычно равен степени 10 (для удобства человека) или степени 2 (для эффективности вычислений). Однако иногда могут использоваться другие коэффициенты масштабирования, например значение времени в часах может быть представлено как тип с фиксированной точкой с коэффициентом масштабирования 1/3600 для получения значений с точностью до одной секунды.

Максимальное значение типа с фиксированной точкой - это просто наибольшее значение, которое может быть представлено в базовом целочисленном типе, умноженное на коэффициент масштабирования; и аналогично для минимального значения.

Операции [ править ]

Чтобы преобразовать число из типа с фиксированной точкой с коэффициентом масштабирования R в другой тип с коэффициентом масштабирования S , лежащее в основе целое число должно быть умножено на R и разделено на S ; то есть умножается на соотношение R / S . Таким образом, например, чтобы преобразовать значение 1,23 = 123/100 из типа с коэффициентом масштабирования R = 1/100 в единицу с коэффициентом масштабирования S = 1/1000, базовое целое число 123 должно быть умножено на (1/100) / (1/1000) = 10, что дает представление 1230/1000. Если S не делит R (в частности, если новый коэффициент масштабирования S больше, чем исходныйR ), новое целое число придется округлить . Правила и методы округления обычно являются частью спецификации языка.

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

Чтобы умножить два числа с фиксированной точкой, достаточно умножить два лежащих в основе целых числа и предположить, что коэффициент масштабирования результата является произведением их коэффициентов масштабирования. Эта операция не требует округления. Например, умножение чисел 123, масштабированных на 1/1000 (0,123), и 25, масштабированных на 1/10 (2,5), дает целое число 123 × 25 = 3075, масштабированное на (1/1000) × (1/10) = 1/10000. , то есть 3075/10000 = 0,3075. Если два операнда принадлежат одному и тому же типу с фиксированной точкой, и результат также должен быть представлен в этом типе, то произведение двух целых чисел должно быть явно умножено на общий коэффициент масштабирования; в этом случае результат, возможно, придется округлить, и может произойти переполнение. Например, если общий коэффициент масштабирования равен 1/100, умножение 1,23 на 0,25 влечет за собой умножение 123 на 25, чтобы получить 3075 с промежуточным коэффициентом масштабирования 1/10000.Затем это нужно умножить на 1/100, чтобы получить 31 (0,31) или 30 (0,30), в зависимости от используемого метода округления, чтобы получить окончательный масштабный коэффициент 1/100.

Чтобы разделить два числа с фиксированной запятой, берется целое частное их основных целых чисел и предполагается, что коэффициент масштабирования является частным их коэффициентов масштабирования. Первое деление подразумевает округление вообще. Например, деление 3456, масштабированного на 1/100 (34,56), и 1234, масштабированного на 1/1000 (1,234), дает целое число 3456 ÷ 1234 = 3 (округлено) с коэффициентом масштабирования (1/100) / (1/1000) = 10, то есть 30. Можно получить более точный результат, сначала преобразовав дивиденд в более точный тип: в том же примере преобразовав 3456, масштабированный на 1/100 (34,56), в 3,456,000, масштабированный на 1/100000, перед делением на 1234, масштабированный на 1/1000 (1,234), даст 3456000 ÷ 1234 = 2801 (округлено) с коэффициентом масштабирования (1/100000) / (1/1000) = 1/100, то есть 28,01 (вместо 30). Если оба операнда и желаемый результат имеют одинаковый коэффициент масштабирования,тогда частное двух целых чисел должно быть явно умножено на этот общий коэффициент масштабирования.

Двоичное и десятичное [ править ]

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

Чаще всего используются двоичные типы с фиксированной точкой, поскольку операции изменения масштаба могут быть реализованы как быстрые сдвиги битов . Двоичные числа с фиксированной точкой могут точно представлять дробные степени двойки, но, как двоичные числа с плавающей запятой, не могут точно представлять дробные степени десяти. Если требуются точные дробные степени десяти, следует использовать десятичный формат. Например, одна десятая (0,1) и одна сотая (0,01) могут быть представлены только приблизительно двоичными представлениями с фиксированной запятой или двоичными представлениями с плавающей запятой, в то время как они могут быть представлены точно в десятичных представлениях с фиксированной запятой или десятичных представлениях с плавающей запятой. . Эти представления могут быть закодированы разными способами, включая двоично-десятичное (BCD).

Пример работы [ править ]

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

(10,500) (1,050) = 1 * 10,500 + 0,050 * 10,500 = 10,500 + 0,525000 = 11,025000

Обратите внимание, что, поскольку есть 3 десятичных знака, мы показываем нули в конце. Чтобы переопределить это как целочисленное умножение, мы должны сначала умножить на 1000 (10 ^ 3), переместив все десятичные разряды в целые, затем мы умножим на (10 ^ -3), чтобы вернуть их, уравнение теперь выглядит так${\ displaystyle 1/1000}$

(10.500) (10 ^ (3)) (10 ^ (- 3)) (1.050) (10 ^ (3)) (10 ^ (- 3)) (10 ^ (- 3)) (10 ^ (- 3) ))= (10500) (1050) (10 ^ -6)= 11 025 000= 11,025000

Это работает эквивалентно, если мы выберем для вычислений другую базу, в частности, базу 2, поскольку битовый сдвиг аналогичен умножению или делению на порядок 2. Три десятичных цифры эквивалентны примерно 10 двоичным цифрам, поэтому мы должны округлить 0,05 до 10 бит после двоичной точки. Тогда самое близкое приближение - 0,0000110011.

10 = 8 + 2 = 2 ^ 3 + 2 ^ 11 = 2 ^ 00,5 = 2 ^ -10,05 = 0,0000110011_2

Таким образом, наше умножение становится

(1010.100) (2 ^ 3) (1.0000110011) (2 ^ 10) (2 ^ -13)= (1010100) (10000110011) (2 ^ -13)= (10110000010111100) (2 ^ -13)= 1011.0000010111100

Это округляется до 11,023 с тремя цифрами после десятичной точки.

Обозначение [ править ]

Существуют различные обозначения, используемые для представления длины слова и точки счисления в двоичном числе с фиксированной запятой. В следующем списке f представляет количество дробных битов, m количество битов величины или целых чисел, s количество знаковых битов и b общее количество битов.

• Q f : префикс "Q". Например, Q15 представляет собой число с 15 дробными битами. Это обозначение неоднозначно, так как оно не определяет длину слова, однако обычно предполагается, что длина слова составляет 16 или 32 бита в зависимости от используемого целевого процессора. ^[1]
• Q м . f : Однозначная форма записи "Q". Поскольку все слово является целым числом с дополнением до 2, подразумевается знаковый бит. Например, Q1.30 описывает число с 1 целым битом и 30 дробными битами, хранящимися как 32-битное целое число с дополнением до 2. ^{[1] [2]}
• FX м . b : префикс «fx» аналогичен префиксу выше, но использует длину слова как второй элемент в паре с точками. Например, fx1.16 описывает число с 1 битом величины и 15 дробными битами в 16-битном слове. ^[3]
• s : m : f : Другие обозначения включают знаковый бит, например тот, который используется в Руководстве пользователя PS2 GS. ^[4] Он также отличается от обычного использования двоеточием вместо точки в качестве разделителя. Например, в этой записи 0: 8: 0 представляет 8-битовое целое число без знака.
• (p, q) Используется в языке программирования PL / I для указания общего числа p цифр (не включая знак) с q после точки счисления. q может быть положительным или отрицательным, а система счисления может быть двоичной или десятичной.
• <s, p, i> Используется в языке программирования LabVIEW для чисел с фиксированной запятой FXP. Где s равно либо +, либо ±, что означает либо беззнаковое, либо дополнительное число со знаком со знаком до 2 соответственно. В этом формате указано p всего цифр, где i - «целая часть». Примечательно, что этот формат позволяет произвольно размещать места «единиц» - что не обязательно в пределах заданных цифр. То есть; в то время как общее количество битов p должно быть натуральным целым числом, i может быть больше, равно нулю или даже отрицательно - эти ситуации просто соответствуют различным общим коэффициентам масштабирования для числа.

Потеря точности и переполнение [ править ]

Поскольку операции с фиксированной точкой могут давать результаты , содержащие больше цифр, чем операнды , возможна потеря информации. Например, результат умножения с фиксированной запятой потенциально может содержать столько цифр, сколько сумма цифр в двух операндах. Чтобы результат соответствовал тому же количеству цифр, что и операнды, ответ должен быть округлен или усечен . В этом случае очень важен выбор цифр, которые нужно сохранить. При умножении двух чисел с фиксированной запятой в одном и том же формате, например, с целыми цифрами и дробными цифрами, ответ может содержать до целых цифр и дробных цифр.${\ displaystyle I}$${\ displaystyle Q}$${\ displaystyle 2I}$${\ displaystyle 2Q}$

Для простоты многие процедуры умножения с фиксированной точкой используют тот же формат результата, что и операнды. Это дает эффект сохранения средних цифр; я -количество наименее значимых целых чисел, а Q -количество наиболее значимых цифр дробной части. Дробные цифры, потерянные ниже этого значения, представляют собой потерю точности, которая обычна при дробном умножении. Однако если какие-либо целые цифры потеряны, значение будет совершенно неточным. Некоторые пакеты с фиксированной точкой на основе моделей ^[5] позволяют указать формат результата, отличный от входных форматов, что позволяет пользователю максимизировать точность и избежать переполнения.

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

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

Реализации компьютерного языка [ править ]

Очень немногие компьютерные языки включают встроенную поддержку значений с фиксированной запятой, за исключением того, что точка счисления находится непосредственно справа от наименее значащей цифры (т. Е. Целого числа ), потому что для большинства приложений двоичные или десятичные представления с плавающей запятой обычно проще в использовании. и достаточно точный. Представления с плавающей запятой легче использовать, чем представления с фиксированной запятой, потому что они могут обрабатывать более широкий динамический диапазон и не требуют от программистов указания количества цифр после точки счисления. Однако, если они необходимы, числа с фиксированной запятой могут быть реализованы даже в таких языках программирования, как C и C ++ , которые обычно не включают такую ​​поддержку.

Обычно двоично - десятичные числа с фиксированной запятой используются для хранения денежных значений, где неточные значения двоичных чисел с плавающей запятой часто являются помехой. Исторически представления с фиксированной точкой были нормой для десятичных типов данных; например, в PL / I или COBOL . Язык программирования Ada включает встроенную поддержку как с фиксированной точкой (двоичной и десятичной), так и с плавающей точкой. JOVIAL и Coral 66 также предоставляют типы с плавающей и фиксированной запятой.

ISO / IEC TR 18037 ^[6] определяет типы данных с фиксированной точкой для языка программирования C; Ожидается, что в ближайшие годы поставщики реализуют языковые расширения для арифметики с фиксированной запятой. Поддержка фиксированной точки реализована в GCC . ^{[7] [8]}

Не следует путать фиксированную точку с десятичной плавающей точкой в таких языках программирования, как C # и Python .

Почти все реляционные базы данных и SQL поддерживают десятичную арифметику с фиксированной запятой и хранение чисел. PostgreSQL имеет специальныйчисловойтип для точного хранения чисел до 1000 цифр. ^[9]

Примеры программных приложений [ править ]

Этот раздел может содержать примеры неизбирательного , чрезмерного или нерелевантного характера . Пожалуйста, улучшите статью , добавив больше описательного текста и удалив менее подходящие примеры . Дополнительные предложения см. В руководстве Википедии по написанию лучших статей . ( Август 2018 г. )

• Библиотека Nest Labs Utilities предоставляет ограниченный набор макросов и функций для чисел с фиксированной запятой, особенно при работе с этими числами в контексте выборки датчиков и выходных сигналов датчиков.
• GnuCash - это приложение для отслеживания денег, написанное на C. Начиная с версии 1.6, оно перешло с представления денег с плавающей запятой на реализацию с фиксированной запятой. Это изменение было сделано для того, чтобы использовать менее предсказуемые ошибки округления представлений с плавающей запятой для большего контроля над округлением (например, до ближайшего цента ).
• Tremor , Toast и MAD - это программные библиотеки, которые декодируют аудиоформаты Ogg Vorbis , GSM Full Rate и MP3 соответственно. Эти кодеки используют арифметику с фиксированной точкой, потому что многие аппаратные устройства декодирования звука не имеют FPU (частично для экономии денег, но в первую очередь для экономии энергии - целочисленные блоки намного меньше в области кремния, чем FPU), а декодирование звука требует высокой производительности до такой степени. программная реализация операций с плавающей запятой на низкоскоростных устройствах не будет производить вывод в реальном времени.
• Все движки 3D-графики на оригинальной PlayStation от Sony , Saturn от Sega , Game Boy Advance от Nintendo (только 2D ), Nintendo DS (2D и 3D), Nintendo Gamecube ^[10] и системах видеоигр GP2X Wiz используют арифметику с фиксированной точкой по той же причине, что и Tremor and Toast: для увеличения пропускной способности в архитектуре без FPU (например, PlayStation включила аппаратную поддержку 4,12-битных значений в свой сопроцессор преобразования).
• Спецификация OpenGL ES 1.x включает профиль с фиксированной точкой, поскольку это API, предназначенный для встраиваемых систем, которые не всегда имеют FPU.
• TeX использует фиксированную точку с 16 битами после двоичной точки в единицах точек для всех вычислений положения. Файлы метрик шрифтов TeX используют 32-битные числа с фиксированной запятой со знаком, с 12 битами слева от десятичной дроби.
• Программы dc и bc - это калькуляторы произвольной точности , но они отслеживают только (заданное пользователем) фиксированное количество цифр дробной части.
• VisSim Визуально программируемый язык блок-схем, поддерживающий набор блоков с фиксированной точкой, позволяющий моделировать и автоматически генерировать код операций с фиксированной точкой. И размер слова, и точка счисления могут быть указаны на основе оператора.
• Fractint представляет числа как числа с фиксированной точкой Q2.29 ^[11], чтобы ускорить рисование на старых ПК с процессорами 386 или 486SX , в которых отсутствовал FPU.
• Doom был последним шутером от первого лица от id Software, который использовал представление с фиксированной точкой 16.16 для всех своих нецелочисленных вычислений, включая систему карт, геометрию, рендеринг, движения игрока и т. Д. Это было сделано для того, чтобы игра была воспроизводится на процессорах 386 и 486SX без FPU. По причинам совместимости это представление все еще используется в современных исходных портах Doom .
• Wavpack - это аудиокомпрессор без потерь с фиксированной точкой. Его создатель, Дэвид Брайант, оправдывает решение реализовать фиксированную вместо плавающей запятой: «Я считаю, что целочисленные операции менее подвержены тонким вариациям от чипа к чипу, которые могут нарушить природу сжатия без потерь». ^[12]
• числа с фиксированной точкой иногда используются для хранения изображений и видеокадров и управления ими. Процессоры с модулями SIMD, предназначенными для обработки изображений, могут включать в себя инструкции, подходящие для обработки упакованных данных с фиксированной точкой.
• Язык программирования Q # для квантовых компьютеров Azure , реализующих квантовые логические вентили , содержит стандартную числовую библиотеку для выполнения арифметических операций с фиксированной точкой над регистрами кубитов . ^[13]
• Формат шрифта TrueType использует формат F26Dot6 (32-битная фиксированная точка со знаком с 26 битами слева от десятичной дроби) для некоторых числовых значений в своих инструкциях. ^[14] Этот формат был выбран для обеспечения минимальной точности, необходимой для хинтинга, и по соображениям производительности. ^[15]
• Пакет FixedPointNumbers для Julia реализует масштабированные числа с фиксированной запятой как 2 ^{n, так} и 2 ⁿ -1. Последние используются в качестве основы для обработки изображений, чтобы обеспечить согласованный масштаб как для «целочисленных», так и для значений интенсивности с плавающей запятой, что позволяет избежать неявного «255 == 1.0» (неуравнение), присутствующего во многих других структурах обработки изображений.

См. Также [ править ]

• Двоичное масштабирование
• Q (числовой формат)
• Libfixmath - библиотека, написанная на C для математики с фиксированной точкой
• Арифметика с плавающей точкой
• Логарифмическая система счисления

Ссылки [ править ]

Дальнейшее чтение [ править ]

• Уоррен-младший, Генри С. (2013). Восторг хакера (2-е изд.). Эддисон Уэсли - ISBN Pearson Education, Inc.  978-0-321-84268-8.

Внешние ссылки [ править ]

В Викибуке с плавающей запятой есть страница на тему: Числа с фиксированной запятой

В Wikibook Embedded Systems есть страница по теме: Арифметика с фиксированной точкой

• Простая математика с фиксированной точкой
• Арифметика с фиксированной точкой - Введение
• Представление с фиксированной точкой и дробная математика
• Расчетный взгляд на арифметику с фиксированной точкой , (PDF)
• Обоснование Ada '83, 5.3.2: Типы с фиксированной точкой
• Числа с фиксированной точкой для Юлии