Мантисса что это такое в информатике

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

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

Число с плавающей запятой состоит из набора отдельных разрядов, условно разделенных на знак, экспоненту порядок и мантиссу. Порядок и мантисса — целые числа, которые вместе со знаком дают представление числа с плавающей запятой в следующем виде:

Нужно еще разобраться.

Математически это записывается так:

Основание определяет систему счисления разрядов. Математически доказано, что числа с плавающей запятой с базой B=2 (двоичное представление) наиболее устойчивы к ошибкам округления, поэтому на практике встречаются только базы 2 и, реже, 10. Для дальнейшего изложения будем всегда полагать B=2, и формула числа с плавающей запятой будет иметь вид:

Что такое мантисса и порядок?

Мантисса – это целое число фиксированной длины, которое представляет старшие разряды действительного числа. Допустим наша мантисса состоит из трех бит (|M|=3). Возьмем, например, число «5», которое в двоичной системе будет равно 101₂. Старший бит соответствует 2 2 =4, средний (который у нас равен нулю) 2 1 =2, а младший 2 0 =1.

Порядок – это степень базы (двойки) старшего разряда. В нашем случае E=2. Такие числа удобно записывать в так называемом стандартном виде, например «1.01e+2». Сразу видно, что мантисса состоит из трех знаков, а порядок равен двум.

3. Представление чисел с плавающей запятой сегодня

В числах одинарной точности (float/single) порядок состоит из 8 бит, а мантисса – из 23. Эффективный порядок определяется как E-127. Например, число 0,15625 будет записано в памяти как

Рисунок взят из Википедии

Чуть более подробное объяснение:

3.1 Специальные числа: ноль, бесконечность и неопределенность

Неопределенность или NaN (от not a number) – это представление, придуманное для того, чтобы арифметическая операция могла всегда вернуть какое-то не бессмысленное значение. В IEEE754 NaN представлен как число, в котором E=E_max+1, а мантисса не нулевая. Любая операция с NaN возвращает NaN. При желании в мантиссу можно записывать информацию, которую программа сможет интерпретировать. Стандартом это не оговорено и мантисса чаще всего игнорируется.

Как можно получить NaN? Одним из следующих способов:

Источник

Что такое мантисса и порядок в информатике

Содержание статьи

Значение мантиссы

Мантисса – одна из частей числа, которое представлено форматом с плавающей точкой. Второй частью этого числа является показатель степени. По сути, это дробная составляющая логарифма.

Значение мантиссы в том, что по ней находится число, которое является источником логарифма. Целая часть показывает только степень десяти или тривиальный множитель, тогда как сама мантисса показывает, какое именно число должно быть умножено на тривиальный множитель, который имеет вид 0,001 или 100.

Экспоненциальная запись представляет это в следующем виде: N = M*n^p, где мантиссой является M. Для примера можно взять число 3600 и представить его в экспоненциальной записи. Получится следующее: 3600 = 3,6*10^3. Учитывая вышесказанное, мантиссой будет являться число 3,6.

Важно понимать, что число, имеющее плавающую запятую, также имеет изменяющуюся абсолютную точность и фиксированную относительную точность. Использование чисел с плавающей запятой лучше, чем представление чисел с фиксированной запятой, так как есть возможность применения большого диапазона значений, тогда как относительная точность не меняется. Это поможет понять следующий пример: форма, имеющая фиксированную запятую, позволяет представить число, которое занимает 2 разряда после запятой и 8 разрядов в целой части, в виде 8765,43; 123456,78 и так далее. Если же брать формат, имеющий плавающую запятую, можно произвести следующую запись: 1,2345678; 0,000012345678 и так далее. Однако для того, чтобы так сделать, важно иметь двухразрядное дополнительное поле, позволяющее записать показатели степени 10, начиная от 0 и кончая 1610. Общее число разрядов составит 10, то есть 8+2.

Мантисса, как для отрицательных, так и для положительных чисел, выражается в прямом коде. Различие в знаке будет отражено лишь в значении знакового разряда. Однако мантисса числа не может превышать единицы. Обычно точка в мантиссе располагается с левой стороны от старшего разряда. Для того, чтоб получить истинное значение числа, нужно умножить мантиссу на 16 в степени порядка. Порядок, полученный этим путем, называется характеристикой. Получается, что характеристика, которая отсчитывается от 64, будет всегда положительной.

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

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

Форма мантиссы

Есть две формы, позволяющие понять место применения мантиссы. Первая — нормальная форма числа. Эта форма, которая имеет мантиссу без учета знака на полуинтервале, то есть [0; 1) (0le a

Число с плавающей запятой состоит из:

* Мантиссы (выражающей значение числа без учёта порядка)
* Знака мантиссы (указывающего на отрицательность или положительность числа)
* Порядка (выражающего степень основания числа, на которое умножается мантисса)
* Знака порядка

[править] Нормальная форма и нормализованная форма

Что ты хочешь узнать?

Ответ

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

Нормализация мантиссы результата независимо от режима не выполняется.

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

00111001000100100000000000000000 – нули слева убираем:
111001000100100000000000000000 – нормализуем мантиссу:
1.11001000100100000000000000000 х 2^29.

Источник

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

В далекие времена, для IT-индустрии это 70-е годы прошлого века, ученые-математики (так раньше назывались программисты) сражались как Дон-Кихоты в неравном бою с компьютерами, которые тогда были размером с маленькие ветряные мельницы. Задачи ставились серьезные: поиск вражеских подлодок в океане по снимкам с орбиты, расчет баллистики ракет дальнего действия, и прочее. Для их решения компьютер должен оперировать действительными числами, которых, как известно, континуум, тогда как память конечна. Поэтому приходится отображать этот континуум на конечное множество нулей и единиц. В поисках компромисса между скоростью, размером и точностью представления ученые предложили числа с плавающей запятой (или плавающей точкой, если по-буржуйски).

Арифметика с плавающей запятой почему-то считается экзотической областью компьютерных наук, учитывая, что соответствующие типы данных присутствуют в каждом языке программирования. Я сам, если честно, никогда не придавал особого значения компьютерной арифметике, пока решая одну и ту же задачу на CPU и GPU получил разный результат. Оказалось, что в потайных углах этой области скрываются очень любопытные и странные явления: некоммутативность и неассоциативность арифметических операций, ноль со знаком, разность неравных чисел дает ноль, и прочее. Корни этого айсберга уходят глубоко в математику, а я под катом постараюсь обрисовать лишь то, что лежит на поверхности.

1. Основы

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

Число с плавающей запятой состоит из набора отдельных разрядов, условно разделенных на знак, экспоненту порядок и мантиссу. Порядок и мантисса — целые числа, которые вместе со знаком дают представление числа с плавающей запятой в следующем виде:

Математически это записывается так:

Основание определяет систему счисления разрядов. Математически доказано, что числа с плавающей запятой с базой B=2 (двоичное представление) наиболее устойчивы к ошибкам округления, поэтому на практике встречаются только базы 2 и, реже, 10. Для дальнейшего изложения будем всегда полагать B=2, и формула числа с плавающей запятой будет иметь вид:

Что такое мантисса и порядок? Мантисса – это целое число фиксированной длины, которое представляет старшие разряды действительного числа. Допустим наша мантисса состоит из трех бит (|M|=3). Возьмем, например, число «5», которое в двоичной системе будет равно 101₂. Старший бит соответствует 2 2 =4, средний (который у нас равен нулю) 2 1 =2, а младший 2 0 =1. Порядок – это степень базы (двойки) старшего разряда. В нашем случае E=2. Такие числа удобно записывать в так называемом «научном» стандартном виде, например «1.01e+2». Сразу видно, что мантисса состоит из трех знаков, а порядок равен двум.

Допустим мы хотим получить дробное число, используя те же 3 бита мантиссы. Мы можем это сделать, если возьмем, скажем, E=1. Тогда наше число будет равно

2 = 10 (в двоичной системе) = 1.000e+1 = 0.100e+2 = 0.010e+3. (E=1, E=2, E=3 соответственно)

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

Это экономит один бит, так как неявную единицу не нужно хранить в памяти, и обеспечивает уникальность представления числа. В нашем примере «2» имеет единственное нормализованное представление («1.000e+1»), а мантисса хранится в памяти как «000», т.к. старшая единица подразумевается неявно. Но в нормализованном представлении чисел возникает новая проблема — в такой форме невозможно представить ноль.

Строго говоря, нормализованное число имеет следующий вид:

Качество решения задач во многом зависит от выбора представления чисел с плавающей запятой. Мы плавно подошли к проблеме стандартизации такого представления.

2. Немного истории

В 60-е и 70-е годы не было единого стандарта представления чисел с плавающей запятой, способов округления, арифметических операций. В результате программы были крайне не портабельны. Но еще большей проблемой было то, что у разных компьютеров были свои «странности» и их нужно было знать и учитывать в программе. Например, разница двух не равных чисел возвращала ноль. В результате выражения «X=Y» и «X-Y=0» вступали в противоречие. Умельцы обходили эту проблему очень хитрыми трюками, например, делали присваивание «X=(X-X)+X» перед операциями умножения и деления, чтобы избежать проблем.

Инициатива создать единый стандарт для представления чисел с плавающей запятой подозрительно совпала с попытками в 1976 году компанией Intel разработать «лучшую» арифметику для новых сопроцессоров к 8086 и i432. За разработку взялись ученые киты в этой области, проф. Джон Палмер и Уильям Кэхэн. Последний в своем интервью высказал мнение, что серьезность, с которой Intel разрабатывала свою арифметику, заставила другие компании объединиться и начать процесс стандартизации.

Все были настроены серьезно, ведь очень выгодно продвинуть свою архитектуру и сделать ее стандартной. Свои предложения представили компании DEC, National Superconductor, Zilog, Motorola. Производители мейнфреймов Cray и IBM наблюдали со стороны. Компания Intel, разумеется, тоже представила свою новую арифметику. Авторами предложенной спецификации стали Уильям Кэхэн, Джероми Кунен и Гарольд Стоун и их предложение сразу прозвали «K-C-S».

Практически сразу же были отброшены все предложения, кроме двух: VAX от DEC и «K-C-S» от Intel. Спецификация VAX была значительно проще, уже была реализована в компьютерах PDP-11, и было понятно, как на ней получить максимальную производительность. С другой стороны в «K-C-S» содержалось много полезной функциональности, такой как «специальные» и «денормализованные» числа (подробности ниже).

В «K-C-S» все арифметические алгоритмы заданы строго и требуется, чтобы в реализации результат с ними совпадал. Это позволяет выводить строгие выкладки в рамках этой спецификации. Если раньше математик решал задачу численными методами и доказывал свойства решения, не было никакой гарантии, что эти свойства сохранятся в программе. Строгость арифметики «K-C-S» сделала возможным доказательство теорем, опираясь на арифметику с плавающей запятой.

Компания DEC сделала все, чтобы ее спецификацию сделали стандартом. Она даже заручилась поддержкой некоторых авторитетных ученых в том, что арифметика «K-C-S» в принципе не может достигнуть такой же производительности, как у DEC. Ирония в том, что Intel знала, как сделать свою спецификацию такой же производительной, но эти хитрости были коммерческой тайной. Если бы Intel не уступила и не открыла часть секретов, она бы не смогла сдержать натиск DEC.

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

3. Представление чисел с плавающей запятой сегодня

Разработчики «K-C-S» победили и теперь их детище воплотилось в стандарт IEEE754. Числа с плавающей запятой в нем представлены в виде знака (s), мантиссы (M) и порядка (E) следующим образом:

Замечание. В новом стандарте IEE754-2008 кроме чисел с основанием 2 присутствуют числа с основанием 10, так называемые десятичные (decimal) числа с плавающей запятой.

Чтобы не загромождать читателя чрезмерной информацией, которую можно найти в Википедии, рассмотрим только один тип данных, с одинарной точностью (float). Числа с половинной, двойной и расширенной точностью обладают теми же особенностями, но имеют другой диапазон порядка и мантиссы. В числах одинарной точности (float/single) порядок состоит из 8 бит, а мантисса – из 23. Эффективный порядок определяется как E-127. Например, число 0,15625 будет записано в памяти как

Рисунок взят из Википедии

3.1 Специальные числа: ноль, бесконечность и неопределенность

Неопределенность или NaN (от not a number) – это представление, придуманное для того, чтобы арифметическая операция могла всегда вернуть какое-то не бессмысленное значение. В IEEE754 NaN представлен как число, в котором E=E_max+1, а мантисса не нулевая. Любая операция с NaN возвращает NaN. При желании в мантиссу можно записывать информацию, которую программа сможет интерпретировать. Стандартом это не оговорено и мантисса чаще всего игнорируется.

Вернемся к примеру. Наш E_min=-1. Введем новое значение порядка, E=-2, при котором числа являются денормализованными. В результате получаем новое представление чисел:

Интервал от 0 до 0,5 заполняют денормализованные числа, что дает возможность не проваливаться в 0 рассмотренных выше примерах (0,5-0,25 и 1,5-1,25). Это сделало представление более устойчиво к ошибкам округления для чисел, близких к нулю.

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

3.4 Очередность чисел в IEEE754

Одна из удивительных особенностей представления чисел в формате IEEE754 состоит в том, что порядок и мантисса расположены друг за другом таким образом, что вместе образуют последовательность целых чисел для которых выполняется:

4.2 Неассоциативность арифметических операций

В арифметике с плавающей запятой правило (a*b)*c = a*(b*c) не выполняется для любых арифметических операций. Например,

Допустим у нас есть программа суммирования чисел.

Некоторые компиляторы по умолчанию могут переписать код для использования нескольких АЛУ одновременно (будем считать, что n делится на 2):

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

4.3 Числовые константы

Помните, что не все десятичные числа имеют двоичное представление с плавающей запятой. Например, число «0,2» будет представлено как «0,200000003» в одинарной точности. Соответственно, «0,2 + 0,2 ≈ 0,4». Абсолютная погрешность в отдельном
случае может и не высока, но если использовать такую константу в цикле, можем получить накопленную погрешность.

4.4 Выбор минимума из двух значений

4.5 Сравнение чисел

Очень распространенная ошибка при работе с float-ами возникает при проверке на равенство. Например,

Ошибка здесь, во-первых, в том, что 0,2 не имеет точного двоичного представления, а во-вторых 0,2 – это константа двойной точности, а переменная fValue – одинарной, и никакой гарантии о поведении этого сравнения нет.

Лучший, но все равно ошибочный способ, это сравнивать разницу с допустимой абсолютной погрешностью:

Недостаток такого подхода в том, что погрешность представления числа увеличивается с ростом самого этого числа. Так, если программа ожидает «10000», то приведенное равенство не будет выполняться для ближайшего соседнего числа (10000,000977). Это особенно актуально, если в программе имеется преобразование из одинарной точности в двойную.

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

5. Проверка полноты поддержки IEE754

Думаете, что если процессоры полностью соответствуют стандарту IEEE754, то любая программа, использующая стандартные типы данных (такие как float/double в Си), будет выдавать один и тот же результат на разных компьютерах? Ошибаетесь. На портабельность и соответствие стандарту влияет компилятор и опции оптимизации. Уильям Кэхэн написал программу на Си (есть версия и для Фортрана), которая позволяет проверить удовлетворяет ли связка «архитектура+компилятор+опции» IEEE754. Называется она «Floating point paranoia» и ее исходные тексты доступны для скачивания. Аналогичная программа доступна для GPU. Так, например, компилятор Intel (icc) по умолчанию использует «расслабленную» модель IEEE754, и в результате не все тесты выполняются. Опция «-fp-model precise» позволяет компилировать программу с точным соответствием стандарту. В компиляторе GCC есть опция «-ffast-math», использование которой приводит к несоответствию IEEE754.

Заключение

Напоследок поучительная история. Когда я работал над тестовым проектом на GPU, у меня была последовательная и параллельная версия одной программы. Сравнив время выполнения, я был очень обрадован, так как получил ускорение в 300 раз. Но позже оказалось, что вычисления на GPU «разваливались» и обращались в NaN, а работа с ними в GPU была быстрее, чем с обычными числами. Интересно было другое — одна и та же программа на эмуляторе GPU (на CPU) выдавала корректный результат, а на самом GPU – нет. Позже оказалось, что проблема была в том, что этот GPU не поддерживал полностью стандарт IEEE754 и прямой подход не сработал.

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

Источник

Всё, точка, приплыли! Учимся работать с числами с плавающей точкой и разрабатываем альтернативу с фиксированной точностью десятичной дроби

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

Куда уплывает точка

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

Мантисса — это, по сути, число, записанное без точки. Экспонента — это степень, в которую нужно возвести некое число N (как правило, N = 2), чтобы при перемножении на мантиссу получить искомое число (с точностью до разрядности мантиссы). Выглядит это примерно так:

Чтобы избежать неоднозначности, считается, что 1 = 4 503 599 627 370 496 и спокойно вмещает в себя все 32-разрядные целые, давая сбой только на действительно больших 64-разрядных целых (19 десятичных знаков), где погрешность в сотнях единиц уже, как правило, несущественна. Если же нужна большая точность, то мы в данной статье обязательно в этом поможем.

Теперь что касается экспоненты. Это обычное бинарное представление целого числа, в которое нужно возвести 10, чтобы при перемножении на мантиссу в нормализованном виде получить исходное число. Вот только в стандарте вдобавок ввели смещение, которое нужно вычитать из бинарного представления, чтобы получить искомую степень десятки (так называемая biased exponent — смещенная экспонента). Экспонента смещается для упрощения операции сравнения, то есть для одинарной точности берется значение 127, а для двойной 1023. Все это звучит крайне сложно, поэтому многие пропускают главу о типе с плавающей точкой. А зря!

Примерное плаванье

Чтобы стало чуточку понятнее, рассмотрим пример. Закодируем число 640 (= 512 + 128) в бинарном виде как вещественное число одинарной точности:

Задание на дом: разобраться в двоичной записи следующих констант: плюс и минус бесконечность (INF — бесконечность), ноль, минус ноль и число-не-число (NaN — not-a-number).

За буйки не заплывай!

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

Другое дело проблема точности. Жалкие 23 бита под мантиссу дают погрешность уже на 8-м знаке после запятой. Для чисел с двойной точностью ситуация не столь плачевная, но и 15 десятичных знаков очень быстро превращаются в проблему, если, например, при обработке данных требуется 6 фиксированных знаков после точки, а числа до точки достаточно большие, под них остается всего лишь 9 знаков. Соответственно, любые многомиллиардные суммы будут давать значительную погрешность в дробной части. При большой интенсивности обработки таких чисел могут пропадать миллиарды евро, просто потому, что они «не поместились», а погрешность дробной части суммировалась и накопила огромный остаток неучтенных данных.

Если бы это была только теория! На практике не должно пропадать даже тысячной доли цента, погрешность всех операций должна быть строго равна нулю. Поэтому для бизнес-логики, как правило, не используют C/C++, а берут C# или Python, где в стандартной библиотеке уже встроен тип Decimal, обрабатывающий десятичные дроби с нулевой погрешностью при указанной точности в десятичных знаках после запятой. Что же делать нам, программистам на C++, если перед нами стоит задача обработать числа очень большой разрядности, при этом не используя высокоуровневые языки программирования? Да то же, что и обычно: заполнить пробел, создав один небольшой тип данных для работы с десятичными дробями высокой точности, аналогичный типам Decimal высокоуровневых библиотек.

Добавим плавающей точке цемента

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

Сегодня в учебных целях мы рассмотрим, как создать представление вещественных чисел с гарантированной точностью до 18 знаков после точки. Это достигается простым комбинированием двух 64-разрядных целых для целой и дробной части соответственно. В принципе, никто не мешает вместо одного числа для каждой из компонент взять массив значений и получить полноценную «длинную» арифметику. Но будет более чем достаточно сейчас решить проблему точности, дав возможность работать с точностью по 18 знаков до и после запятой, зафиксировав точку между двумя этими значениями и залив ее цементом.

Отсыпь и мне децимала!

Сначала немного теории. Обозначим наше две компоненты, целую и дробную часть числа, как n и f, а само число будет представимо в виде

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

Операции с типом десятичной дроби

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

NB: здесь и далее все записи в форме 1e — целые числа.

Здесь [n] — это получение целой части числа, а — получение дробной части. Все бы хорошо, но вспоминаем про ограничение целых чисел. Значение 1e+18 уже близко к грани значений беззнакового 64-битового целого типа uint64_t (потому мы его и выбрали), но нам никто не мешает чуточку упростить выражение, чтобы гарантированно оставаться в границах типа, исходя из начальных условий:

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

Введем матрицу для упрощения вычисления умножения:

Здесь мы опускаем слагаемое A₄₄ div 10 18 просто потому, что оно равно нулю. Разумеется, перед каждым сложением стоит проверить, не выйдем ли мы за пределы MAX_INT64. К счастью, мы можем оперировать беззнаковым типом uint64_t для всех компонент матрицы и для промежуточного результата. Все, что нужно будет сделать в конце, — это определить знак результата s_e = s_a xor s_c и для отрицательного числа поправить целую и дробную часть: целую уменьшить на единицу, дробную вычесть из единицы. Вот, в общем, и все умножение, главное — быть очень аккуратным. С ассемблером все на порядок проще, но этот материал выходит за рамки Академии C++.

Алгоритм деления без регистрации и СМС

Для упрощения рассмотрим нахождение обратного числа для положительного x. Если хотя бы одна из компонент x равна нулю (но не обе сразу), вычисления сильно упрощаются. Если a = 0, то:

Для более общего случая, когда x содержит ненулевые дробную и целую части, в этом случае уравнение сводится к следующему:

Теперь нужно найти максимальную степень 10, которая будет не больше a, и итерационно выполнять следующее действие:

Здесь мы всего лишь используем умножение и деление дроби на одинаковый множитель — степень десятки, а затем пошагово вычисляем деление и остаток от деления для очередной степени десятки.

Очень полезно будет завести массив степеней десяток от 0 до 18 включительно, поскольку вычислять их совершенно излишне, мы их знаем заранее и требоваться они нам будут часто.

Преобразования типов

Мы знаем и умеем достаточно, чтобы теперь превратить расплывчатые float и double в наш новенький decimal.

Здесь 103 является, по сути, той погрешностью, за которой double перестает быть точным. При желании погрешность можно еще уменьшить, здесь 10 18-15 нужно для наглядности изложения. Нормализация после преобразования нужна будет все равно, поскольку точно double заведомо ниже даже дробной части decimal. Кроме того, нужно учитывать случай, когда double выходит за пределы int64_t, при таких условиях наш decimal не сможет правильно преобразовать целую часть числа.

Все целые числа преобразовываются в decimal без проблем, просто инициализируя поле m_integral. Преобразование в обратную сторону для целых чисел также будет просто возврат m_integral, можно добавить округление m_fractional.

Преобразование из decimal в double и float сводится к вышеуказанной формуле:

Отдельно стоит рассмотреть преобразование в строку и из строки. Целочисленная часть, по сути, преобразуется в строку как есть, после этого остается только вставить decimal separator и вывести дробную часть как целое, отбросив завершающие нули. Также можно ввести поле «точность» m_precision и записывать в строку лишь указанное в нем число десятичных знаков.

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

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

GITHUB

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

Не уплывай, и точка!

В заключение скажу лишь то, что подобный тип в C/C++ может появиться в весьма специфической задаче. Как правило, проблемы чисел с большой точностью решаются языками типа Python или C#, но если уж понадобилось по 15–18 знаков до запятой и после, то смело используй данный тип.

Получившийся тип decimal решает проблемы с точностью вещественных чисел и обладает большим запасом возможных значений, покрывающим int64_t. С другой стороны, типы double и float могут принимать более широкий интервал значений и выполняют арифметические операции на уровне команд процессора, то есть максимально быстро. Старайся обходиться аппаратно поддерживаемыми типами, не залезая в decimal лишний раз. Но и не бойся использовать данный тип, если есть необходимость в точном вычислении без потерь.

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

Впервые опубликовано в журнале Хакер #192.
Автор: Владимир Qualab Керимов, ведущий С++ разработчик компании Parallels

Источник