Арифметика с фиксированной запятой

Эта статья о дробях фиксированной точности. Чтобы узнать об инвариантных точках функции, см. Фиксированная точка (математика) .

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

В представлении с фиксированной запятой дробь часто выражается в той же системе счисления, что и целая часть, но с использованием отрицательных степеней основания b . Наиболее распространенными вариантами являются десятичная (по основанию 10) и двоичная (по основанию 2). Последнее широко известно также как двоичное масштабирование . Таким образом, если n сохранено кратным цифр дроби, значение всегда будет целым числом , b. ^{− п} . Представление с фиксированной точкой также может использоваться для исключения младших цифр целочисленных значений, например, при представлении больших долларовых значений как кратных 1000 долларов США.

Когда десятичные числа с фиксированной запятой отображаются для чтения человеком, цифры дробей обычно отделяются от цифр целой части символом системы счисления (обычно «.» на английском языке, но «,» или какой-либо другой символ на многих других языках). Однако внутри разделения нет, и различие между двумя группами цифр определяется только программами, обрабатывающими такие числа.

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

Представительство

Представление с фиксированной точкой

с масштабом 1/100

Ценить представленный	Внутренний представительство
0.00	0
0.5	50
0.99	99
2	200
−14.1	−1410
314.160	31416

Представление дробного числа с фиксированной запятой по сути представляет собой целое число , которое необходимо неявно умножить на фиксированный коэффициент масштабирования. Например, значение 1,23 можно сохранить в переменной как целое значение 1230 с неявным коэффициентом масштабирования 1/1000 (это означает, что последние 3 десятичные цифры неявно считаются десятичной дробью), а значение 1 230 000 может быть сохранено в переменной. быть представлено как 1230 с неявным масштабным коэффициентом 1000 (с подразумеваемыми цифрами десятичной дроби «минус 3», то есть с 3 неявными нулевыми цифрами справа). Это представление позволяет стандартным устройствам целочисленной арифметики выполнять вычисления рациональных чисел .

Отрицательные значения обычно представляются в двоичном формате с фиксированной запятой как целое число со знаком в представлении с дополнением до двух с неявным коэффициентом масштабирования, как указано выше. Знак значения всегда будет указываться первым сохраненным битом (1 = отрицательный, 0 = неотрицательный), даже если количество дробных битов больше или равно общему количеству битов. Например, 8-битное двоичное целое число со знаком (11110101) ₂ = -11, взятое с битами подразумеваемой дроби -3, +5 и +12, будет представлять значения -11/2. ⁻³ = −88, −11/2 ⁵ = −0. 343 75 и -11/2 ¹² = −0. 002 685 546 875 соответственно.

Альтернативно, отрицательные значения могут быть представлены целым числом в формате «знак-величина» , и в этом случае знак никогда не включается в число битов подразумеваемой дроби. Этот вариант чаще используется в десятичной арифметике с фиксированной запятой. Таким образом, пятизначное десятичное целое число со знаком (-00025) ₁₀ , взятое с подразумеваемыми цифрами десятичной дроби -3, +5 и +12, будет представлять значения -25/10. ⁻³ = −25000, −25/10 ⁵ = -0,00025 и -25/10 ¹² = −0. 000 000 000 025 соответственно.

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

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

Выбор коэффициентов масштабирования

Для большей эффективности коэффициенты масштабирования часто выбираются в качестве степеней (положительных или отрицательных) по основанию b, используемых для внутреннего представления целых чисел. Однако зачастую лучший коэффициент масштабирования определяется приложением. Таким образом, для удобства человека часто используются коэффициенты масштабирования, являющиеся степенями 10 (например, 1/100 для долларовых значений), даже когда целые числа внутренне представлены в двоичном формате. Десятичные коэффициенты масштабирования также хорошо сочетаются с метрической системой (СИ) , поскольку выбор коэффициента масштабирования с фиксированной точкой часто эквивалентен выбору единицы измерения (например, сантиметров или микронов вместо метров ).

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

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

С другой стороны, меньший коэффициент масштабирования означает меньший диапазон значений, которые можно сохранить в данной программной переменной. Максимальное значение фиксированной точки, которое может быть сохранено в переменной, — это наибольшее целое число, которое может быть сохранено в ней, умноженное на коэффициент масштабирования; и аналогично для минимального значения. Например, в таблице ниже указаны предполагаемый масштабный коэффициент S , минимальные и максимальные представимые значения V _min и V _max , а также точность δ = S /2 значений, которые могут быть представлены в 16-битном двоичном формате с фиксированной запятой со знаком, в зависимости от от количества f подразумеваемых дробных битов.

Параметры некоторых 16-битных знаковых двоичных форматов с фиксированной запятой

ж	С	д	В мин	В макс.
−3	1/2 −3 = 8	4	− 262 144	+ 262 136
0	1/2 0 = 1	0.5	− 32 768	+ 32 767
5	1/2 5 = 1/32	< 0,016	−1024. 000 00	+1023. 968 75
14	1/2 14 = 1/ 16 384	< 0.000031	−2. 000 000 000 000 00	+1. 999 938 964 843 75
15	1/2 15 = 1/ 32 768	< 0.000016	−1. 000 000 000 000 000	+0. 999 969 482 421 875
16	1/2 16 = 1/ 65 536	< 0.000008	−0. 500 000 000 000 000 0	+0. 499 984 741 210 937 5
20	1/2 20 = 1/ 1 048 576	< 0,000000 5	−0. 031 250 000 000 000 000 00	+0. 031 249 046 325 683 593 75

Форматы фиксированной точки с масштабными коэффициентами вида 2 ^н Считается, что -1 (а именно 1, 3, 7, 15, 31 и т. д.) подходит для обработки изображений и других задач цифровой обработки сигналов. Предполагается, что они обеспечивают более последовательные преобразования между значениями с фиксированной и плавающей запятой, чем обычные 2. ^н масштабирование. Язык программирования Julia реализует обе версии.

Точные значения

Любая двоичная дробь a /2 ^м , например 1/16 или 17/32, может быть точно представлено в фиксированной точке с масштабным коэффициентом степени двойки 1/2. ^н с любым n ≥ m . Однако большинство десятичных дробей, таких как 0,1 или 0,123, представляют собой бесконечно повторяющиеся дроби по основанию 2 и, следовательно, не могут быть представлены таким образом.

Аналогично, любая десятичная дробь a /10 ^м , например 1/100 или 37/1000, может быть точно представлено в фиксированной точке с коэффициентом масштабирования в десятичной степени 1/10. ^н с любым n ≥ m . Этот десятичный формат также может представлять любую двоичную дробь a /2. ^м , например 1/8 (0,125) или 17/32 (0,53125).

В более общем смысле, рациональное число a / b , где a и b относительно простые , а b положительное, может быть точно представлено в двоичной фиксированной точке, только если b является степенью 2; и в десятичной фиксированной точке только в том случае, если b не имеет простых делителей, кроме 2 и/или 5.

Сравнение с плавающей запятой

Вычисления с фиксированной запятой могут быть быстрее и/или использовать меньше оборудования, чем вычисления с плавающей запятой. Если диапазон отображаемых значений известен заранее и достаточно ограничен, фиксированная точка может лучше использовать доступные биты. Например, если для представления числа от 0 до 1 доступны 32 бита, представление с фиксированной запятой может иметь ошибку менее 1,2 × 10. ⁻¹⁰ , тогда как стандартное представление с плавающей запятой может иметь ошибку до 596 × 10 ⁻¹⁰ — потому что 9 бит теряются вместе со знаком и показателем степени динамического масштабного коэффициента. В частности, сравнивая 32-битный звук с фиксированной запятой и звук с плавающей запятой менее 40 дБ , запись, требующая запаса , имеет более высокое соотношение сигнал/шум при использовании 32-битной фиксированной точки.

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

Во многих встроенных процессорах отсутствует FPU, поскольку устройства целочисленной арифметики требуют значительно меньше логических элементов и занимают гораздо меньшую площадь кристалла , чем FPU; а программная эмуляция операций с плавающей запятой на низкоскоростных устройствах будет слишком медленной для большинства приложений. Чипы ЦП для более ранних персональных компьютеров и игровых консолей , таких как Intel 386 и 486SX , также не имели FPU.

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

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

Приложения

Обычно десятичные числа с фиксированной запятой используются для хранения денежных значений, для чего часто возникают затруднения из-за сложных правил округления чисел с плавающей запятой. Например, по этой причине приложение для управления капиталом с открытым исходным кодом GnuCash , написанное на C, перешло с плавающей точки на фиксированную точку, начиная с версии 1.6.

Двоичная фиксированная точка (двоичное масштабирование) широко использовалась с конца 1960-х по 1980-е годы для математически интенсивных вычислений в реальном времени, таких как моделирование полета и в алгоритмах управления атомными электростанциями . Он до сих пор используется во многих приложениях DSP и микропроцессорах, изготавливаемых на заказ. В вычислениях, включающих углы, будут использоваться двоичные угловые измерения .

Двоичная фиксированная точка используется в STM32G4 серии CORDIC сопроцессорах и в алгоритмах дискретного косинусного преобразования, используемых для сжатия изображений JPEG .

Электронные приборы, такие как счетчики электроэнергии и цифровые часы, часто используют полиномы для компенсации вносимых ошибок, например, из-за температуры или напряжения источника питания. Коэффициенты получаются с помощью полиномиальной регрессии . Двоичные полиномы с фиксированной запятой могут использовать больше бит точности, чем полиномы с плавающей запятой, и делают это в быстром коде с использованием недорогих процессоров. Точность, имеющая решающее значение для приборов, хорошо сравнима с вычислениями с плавающей запятой с эквивалентными битами, если полиномы с фиксированной точкой оцениваются с использованием метода Хорнера (например, y = (( ax + b ) x + c ) x + d ), чтобы уменьшить число раз происходит округление, а при умножении с фиксированной точкой используются слагаемые округления.

Операции

Сложение и вычитание

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

Умножение

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

Например, умножение чисел 123 в масштабе 1/1000 (0,123) и 25 в масштабе 1/10 (2,5) дает целое число 123×25 = 3075 в масштабе (1/1000)×(1/10) = 1/10000. , то есть 3075/10000 = 0,3075. Другой пример: умножение первого числа на 155, неявно масштабированное на 1/32 (155/32 = 4,84375), дает целое число 123×155 = 19065 с неявным коэффициентом масштабирования (1/1000)×(1/32) = 1/32000. , то есть 19065/32000 = 0,59578125.

В двоичном формате обычно используется коэффициент масштабирования, равный степени двойки. После умножения коэффициент масштабирования можно разделить, сдвинув вправо. На большинстве компьютеров переключение происходит просто и быстро. Округление возможно путем добавления «добавки к округлению» половины коэффициента масштабирования перед сдвигом; Доказательство: round(x/y) = Floor(x/y + 0,5) = Floor((x + y/2)/y) = сдвиг-n(x + 2^(n-1)) Аналогично. метод можно использовать при любом масштабировании.

Разделение

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

Например, деление 3456 в масштабе 1/100 (34,56) и 1234 в масштабе 1/1000 (1,234) дает целое число 3456÷1234 = 3 (округленное) с масштабным коэффициентом (1/100)/(1/1000) = 10, то есть 30. Другой пример: деление первого числа на 155, неявно масштабированное на 1/32 (155/32 = 4,84375), дает целое число 3456÷155 = 22 (округленное) с неявным масштабным коэффициентом (1/ 100)/(1/32) = 32/100 = 8/25, то есть 22×32/100 = 7,04.

Если результат неточный, ошибку, вносимую округлением, можно уменьшить или даже устранить путем преобразования делимого к меньшему коэффициенту масштабирования. Например, если r = 1,23 представлено как 123 с масштабом 1/100, а s = 6,25 представлено как 6250 с масштабом 1/1000, то простое деление целых чисел дает 123÷6250 = 0 (округлено) с масштабным коэффициентом ( 1/100)/(1/1000) = 10. Если r сначала преобразовать в 1 230 000 с масштабным коэффициентом 1/1000000, результат будет 1 230 000 ÷ 6250 = 197 (округлено) с масштабным коэффициентом 1/1000 (0,197). Точное значение 1,23/6,25 составляет 0,1968.

Масштабирование преобразования

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

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

Чтобы преобразовать число из типа с фиксированной точкой с коэффициентом масштабирования 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 ), возможно, придется округлить новое целое число .

В частности, если r и s — переменные с фиксированной точкой с неявными масштабными коэффициентами R и S , операция r ← r × s результата на S. требует умножения соответствующих целых чисел и явного деления Возможно, результат придется округлить, и может произойти переполнение.

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

Аналогично, операция r ← r / s потребует деления целых чисел и явного умножения частного S. на Здесь также может произойти округление и/или переполнение.

Преобразование в число с плавающей запятой и обратно

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

Чтобы преобразовать число с фиксированной запятой в число с плавающей запятой, можно преобразовать целое число в число с плавающей запятой, а затем разделить его на коэффициент S. масштабирования Это преобразование может повлечь за собой округление, если абсолютное значение целого числа больше 2. ²⁴ (для двоичных чисел с плавающей запятой IEEE одинарной точности) или 2 ⁵³ (для двойной точности). Переполнение или опустошение могут произойти, если | С | велик соответственно очень или очень мал.

Аппаратная поддержка

Масштабирование и перенормировка

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

Ранние компьютеры, такие как IBM 1620 и Burroughs B3500, использовали двоично-десятичное (BCD) представление целых чисел, а именно систему счисления с основанием 10, где каждая десятичная цифра независимо кодировалась 4 битами. Некоторые процессоры, например микроконтроллеры, все еще могут его использовать. В таких машинах преобразование десятичных коэффициентов масштабирования может выполняться путем битового сдвига и/или манипуляции адресом памяти.

Некоторые архитектуры DSP предлагают встроенную поддержку определенных форматов с фиксированной запятой, например, n -битных чисел со знаком с n -1 дробными битами (значения которых могут находиться в диапазоне от -1 до почти +1). Поддержка может включать в себя команду умножения, которая включает в себя перенормировку — преобразование масштабирования произведения из 2 n -2 в n -1 дробных битов. Если ЦП не предоставляет такую ​​возможность, программист должен сохранить результат в достаточно большом регистре или временной переменной и явно закодировать перенормировку.

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

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

В случае переполнения старшие биты обычно теряются, поскольку немасштабированное целое число уменьшается по модулю 2. ^н где n — размер области хранения. В частности, теряется знаковый бит, что может радикально изменить знак и величину значения.

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

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

Поддержка компьютерного языка

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

Большинство этих языков были разработаны между 1955 и 1990 годами. Более современные языки обычно не предлагают никаких типов данных с фиксированной точкой или поддержки преобразования коэффициентов масштабирования. То же самое относится и к нескольким старым языкам, которые до сих пор очень популярны, например FORTRAN , C и C++ . Широкая доступность быстрых процессоров с плавающей запятой со строго стандартизированным поведением значительно снизила потребность в поддержке двоичной фиксированной запятой. Аналогично, поддержка десятичных чисел с плавающей запятой в некоторых языках программирования, таких как C# и Python , устранила большую часть необходимости в поддержке десятичных чисел с фиксированной запятой. В тех немногих ситуациях, когда требуются операции с фиксированной точкой, они могут быть реализованы программистом с явным преобразованием масштабирования на любом языке программирования.

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

Более того, в 2008 году Международная организация по стандартизации (ISO) выступила с предложением расширить язык программирования C типами данных с фиксированной запятой в интересах программ, работающих на встроенных процессорах. Кроме того, коллекция компиляторов GNU (GCC) имеет внутреннюю поддержку фиксированной точки.

Подробные примеры

Десятичное умножение с фиксированной запятой

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

${\begin{aligned}(10.500)(1.050)&=1\times 10.500+0.050\times 10.500\\&=10.500+0.525000=11.025000\end{aligned}}$

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

${\begin{aligned}(10.500)(10^{3})(1.050)(10^{3})(10^{-3})(10^{-3})&=(10500)(1050)(10^{-6})\\&=11\,025\,000(10^{-6})\\&=11.025000\end{aligned}}$

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

${\begin{aligned}10&=8+2=2^{3}+2^{1}\\1&=2^{0}\\0.5&=2^{-1}\\0.05&=0.0000110011_{2}\end{aligned}}$

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

${\begin{aligned}(1010.100)(2^{3})(1.0000110011)(2^{10})(2^{-13})&=(1010100)(10000110011)(2^{-13})\\&=(10110000010111100)(2^{-13})\\&=1011.0000010111100\end{aligned}}$

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

Двоичное умножение с фиксированной точкой

Рассмотрим задачу вычисления произведения 1,2 и 5,6 с двоичной фиксированной точкой, используя 16 дробных битов. Чтобы представить два числа, их нужно умножить на 2. ¹⁶ , получив 78 643,2 и 367 001,6 ; и округляем эти значения до ближайших целых чисел, получая 78 643 и 367 002 . Эти числа удобно вписываются в 32-битное слово со знаком, дополненным до двух.

Умножение этих целых чисел дает 35-битное целое число 28 862 138 286 с 32 дробными битами без округления. Обратите внимание, что сохранение этого значения непосредственно в 32-битной целочисленной переменной приведет к переполнению и потере старших битов. На практике оно, вероятно, будет храниться в знаковой 64-битной целочисленной переменной или регистре .

Если результат необходимо сохранить в том же формате, что и данные, с 16 дробными битами, это целое число следует разделить на 2. ¹⁶ , что дает примерно 440 401  0,28, а затем округляется до ближайшего целого числа. Такого эффекта можно добиться, добавив 2 ¹⁵ а затем сдвигаем результат на 16 бит. Результат — 440 401 , что соответствует значению 6. 719 985 961 914 062 5 . Принимая во внимание точность формата, это значение лучше выразить как 6,719986 ± 0,000008 (не считая ошибки, возникающей из-за аппроксимации операндов). Правильный результат будет 1,2 × 5,6 = 6,72.

В качестве более сложного примера предположим, что два числа 1,2 и 5,6 представлены в 32-битном формате с фиксированной запятой с 30 и 20 дробными битами соответственно. Масштабирование на 2 ³⁰ и 2 ²⁰ дает 1 288 490 188,8 и 5 872 025,6 , что округляет до 1 288 490 189 и 5 872 026 соответственно. Оба числа по-прежнему помещаются в 32-битную целочисленную переменную со знаком и представляют собой дроби.

1. 200 000 000 186 264 514 923 095 703 125 и

5. 600 000 381 469 726 562 50

Их продуктом является (точно) 53-битное целое число 7 566 047 890 552 914 , которое имеет 30+20 = 50 битов подразумеваемой дроби и, следовательно, представляет собой дробь.

6. 720 000 458 806 753 229 623 609 513 510

Если мы решим представить это значение в знаковом 16-битном фиксированном формате с 8 дробными битами, мы должны разделить целое произведение на 2. ^50-8 = 2 ⁴² и округлить результат; чего можно добиться добавлением 2 ⁴¹ и сдвиг на 42 бита. Результат — 1720, что соответствует значению 1720/2. ⁸ = 6,71875 или приблизительно 6,719±0,002.

Обозначения

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

• Язык программирования COBOL изначально поддерживал десятичную фиксированную точность с произвольным размером и десятичное масштабирование, формат которого задавался «графически» с помощью Директива PIC . Например, В PIC S9999V99 указано шестизначное десятичное целое число со знаком и двумя цифрами десятичной дроби.
• Конструкция ДЕЙСТВИТЕЛЬНЫЙ ФИКСИРОВАННЫЙ ДВОИЧНЫЙ ( p , ж ) используется в языке программирования PL/I для указания двоичного типа данных с фиксированной запятой и общим числом p бит (не включая знак) с f битами в дробной части; это целое число со знаком p +1 бит с масштабным коэффициентом 1/2. ^ж . Последнее может быть положительным или отрицательным. Можно было бы указать КОМПЛЕКС вместо НАСТОЯЩИЙ и ДЕСЯТИЧНОЕ вместо Двоичный код по основанию 10.
• В языке программирования Ada числовой тип данных может быть указан, например, с помощью type F is delta 0.01 range -100.0 .. 100.0, что означает представление с фиксированной запятой, состоящее из двоичного целого числа со знаком в формате дополнения до двух с 7 битами подразумеваемой дроби (обеспечивая коэффициент масштабирования 1/128) и общим количеством не менее 15 бит (обеспечивая фактический диапазон от -128,00 до почти +128,00) .
• Обозначение Q было определено компанией Texas Instruments . Один пишет Q f для указания знакового двоичного значения с фиксированной точкой и f дробными битами ; например, Q15 задает целое число со знаком в записи с дополнением до двух с коэффициентом масштабирования 1/2. ¹⁵ . Код Q м . f дополнительно указывает, что число имеет m бит в целой части значения, не считая знакового бита. Таким образом Вопрос 1.30 будет описывать двоичный формат с фиксированной запятой с 1 целым битом и 30 дробными битами, который может быть сохранен как 32-битное целое число, дополненное до 2, с коэффициентом масштабирования 1/2. ³⁰ . Аналогичное обозначение использовалось в ARM , за исключением того, что они учитывали знаковый бит в значении m ; поэтому тот же формат, что и выше, будет указан как Вопрос 2.30 .
• Обозначения B m используется для обозначения фиксированного двоичного формата с m битами в целочисленной части; остальная часть слова представляет собой дробные биты. Например, максимальные и минимальные значения, которые могут храниться в подписанном Числа B16 составляют ≈32767,9999847 и −32768,0 соответственно.
• Компания ВисСим использовала FX м . b для обозначения двоичного значения с фиксированной точкой с общим числом b бит и m битами в целочисленной части; то есть b -битное целое число с коэффициентом масштабирования 1/2. ^{б - м} . Таким образом fx1.16 будет означать 16-битное число с 1 битом в целой части и 15 в дробной.
• GS В руководстве пользователя PS2 ( «Графический синтезатор» ) используются обозначения s. : м : f , где s указывает наличие (0 или 1) знакового бита. Например, 0:5:3 представляет собой 8-битное целое число без знака с коэффициентом масштабирования 1/2. ³ .
• Язык программирования LabVIEW использует обозначение < с , б , м > для указания параметров чисел с фиксированной запятой «FXP». Компонент s может быть либо «+», либо «±», обозначая либо беззнаковое, либо знаковое число, дополняемое до 2, соответственно. Компонент b — это общее количество бит, а m — количество бит в целой части.

Примеры применения программного обеспечения

• Популярный формат шрифта TrueType использует 32-битную двоичную фиксированную точку со знаком и 26 битов слева от десятичной точки для некоторых числовых значений в своих инструкциях. Этот формат был выбран, чтобы обеспечить минимальную точность, необходимую для подсказок и по соображениям производительности.
• За исключением Nintendo 64 , все 3D-игры для игровых консолей пятого поколения , включая 3DO Interactive Multiplayer , PlayStation , Saturn и Jaguar. используйте арифметику с фиксированной запятой, поскольку в системах отсутствуют аппаратные модули с плавающей запятой. Сопроцессор преобразования PlayStation поддерживает 16-битную фиксированную запятую с 12 дробными битами, тогда как сопроцессоры Sega Saturn VDP использовали 32-битный формат с фиксированной запятой, резервируя младшие 16 бит для дробной части.
• Программное обеспечение для набора текста TeX , широко используемое учеными и математиками, использует 32-битную двоичную фиксированную точку со знаком и 16 дробных битов для всех вычислений позиции. Значения интерпретируются как доли типографского пункта . В файлах метрик шрифтов TeX используются 32-битные числа с фиксированной запятой и 12 дробными битами.
• Tremor , Toast и MAD — это программные библиотеки, которые декодируют Ogg Vorbis , GSM Full Rate и MP3 аудиоформаты соответственно. Эти кодеки используют арифметику с фиксированной запятой, поскольку многие аппаратные устройства декодирования звука не имеют FPU.
• Аудиокомпрессор без потерь WavPack использует арифметику с фиксированной запятой. Выбор был оправдан, среди прочего, опасениями, что разные правила округления с плавающей запятой на разном оборудовании могут испортить характер сжатия без потерь.
• Библиотека утилит Nest Labs, предоставляет ограниченный набор макросов и функций для чисел с фиксированной запятой, особенно при работе с этими числами в контексте выборки датчиков и выходных данных датчиков.
• Спецификация OpenGL ES 1.x включает профиль с фиксированной точкой, поскольку это API, предназначенный для встроенных систем, которые не всегда имеют FPU.
• Программы dc и bc представляют собой калькуляторы произвольной точности , но отслеживают только (заданное пользователем) фиксированное количество дробных цифр.
• Fractint представляет числа как Q2.29 , числа с фиксированной точкой для ускорения рисования на старых ПК с процессорами 386 или 486SX , у которых не было FPU.
• Doom был последним шутером от первого лица от id Software, в котором использовалось представление с фиксированной точкой 16,16 для всех нецелочисленных вычислений, включая систему карт, геометрию, рендеринг и движение игрока. Это представление до сих пор используется в современных Doom исходных портах .
• Язык программирования Q# для Azure квантовых компьютеров , реализующих квантовые логические вентили стандартную числовую библиотеку для выполнения арифметических операций с фиксированной запятой над регистрами кубитов , содержит .

См. также

• Q (числовой формат)
• Libfixmath — библиотека, написанная на C для математики с фиксированной точкой.
• Логарифмическая система счисления
• Минипоплавок
• Блокировать масштабирование с плавающей запятой
• Операция по модулю
• алгоритм μ-закона
• Алгоритм A-закона

Дальнейшее чтение

• Уоррен-младший, Генри С. (2013). Хакерское наслаждение (2-е изд.). Аддисон Уэсли / Pearson Education, Inc. ISBN  978-0-321-84268-8 .

Внешние ссылки

• Простая математика с фиксированной точкой
• Арифметика с фиксированной запятой — введение
• Представление с фиксированной точкой и дробная математика
• Расчетный взгляд на арифметику с фиксированной запятой , (PDF)