Вычисления с плавающей точкой что это

Наглядное объяснение чисел с плавающей запятой

В начале 90-х создание трёхмерного игрового движка означало, что вы заставите машину выполнять почти не свойственные ей задачи. Персональные компьютеры того времени предназначались для запуска текстовых процессоров и электронных таблиц, а не для 3D-вычислений с частотой 70 кадров в секунду. Серьёзным препятствием стало то, что, несмотря на свою мощь, ЦП не имел аппаратного устройства для вычислений с плавающей запятой. У программистов было только АЛУ, перемалывающее целые числа.

При написании книги Game Engine Black Book: Wolfenstein 3D я хотел наглядно показать, насколько велики были проблемы при работе без плавающей запятой. Мои попытки разобраться в числах с плавающей запятой при помощи каноничных статей мозг воспринимал в штыки. Я начал искать другой способ. Что-нибудь, далёкое от и их загадочных экспонент с мантиссами. Может быть, в виде рисунка, потому что их мой мозг воспринимает проще.

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

Как обычно объясняют числа с плавающей запятой

Цитирую Дэвида Голдберта (David Goldbert):

Для многих людей арифметика с плавающей запятой кажется каким-то тайным знанием.

Полностью с ним согласен. Однако важно понимать принципы её работы, чтобы полностью осознать её полезность при программировании 3D-движка. В языке C значения с плавающей запятой — это 32-битные контейнеры, соответствующие стандарту IEEE 754. Они предназначены для хранения и выполнения операций над аппроксимациями вещественных чисел. Пока я видел только такое их объяснение. 32 бита разделены на три части:

Три части числа с плавающей запятой.

Пока всё нормально. Пойдём дальше. Способ интерпретации чисел обычно объясняется с помощью такой формулы:

Именно это объяснение чисел с плавающей запятой все ненавидят.

И здесь я обычно начинаю терять терпение. Возможно, у меня аллергия на математическую нотацию, но когда я это читаю, в моём мозгу ничего не «щёлкает». Такое объяснение похоже на способ рисования совы:

Другой способ объяснения

Хоть это изложение и верно, такой способ объяснения чисел с плавающей запятой обычно не даёт нам никакого понимания. Я виню эту ужасную запись в том, что она разочаровала тысячи программистов, испугала их до такой степени, что они больше никогда не пытались понять, как же на самом деле работают вычисления с плавающей запятой. К счастью, их можно объяснить иначе. Воспринимайте экспоненту как окно (Window) или интервал между двумя соседними целыми степенями двойки. Мантиссу воспринимайте как смещение (Offset) в этом окне.

Три части числа с плавающей запятой.

Окно сообщает нам, между какими двумя последовательными степенями двойки будет число: [0,1], [1,2], [2,4], [4,8] и так далее (вплоть до [,]. Смещение разделяет окно на сегментов. С помощью окна и смещения можно аппроксимировать число. Окно — это отличный механизм защиты от выхода за границы. Достигнув максимума в окне (например, в [2,4]), можно «переплыть» вправо и представить число в пределах следующего окна (например, [4,8]). Ценой этого будет только небольшое снижение точности, потому что окно становится в два раза больше.

Викторина: сколько точности теряется, когда окно закрывает больший интервал? Давайте возьмём пример с окном [0,1], в котором 8388608 смещений накладываются на интервал размером 1, что даёт нам точность . В окне [2048,4096] 8388608 смещений накладываются на интервал , что даёт нам точность .

На рисунке ниже показано, как кодируется число 6,1. Окно должно начинаться с 4 и заканчиваться следующей степенью двойки, т.е. 8. Смещение находится примерно посередине окна.

Значение 6,1 аппроксимированное с помощью числа с плавающей запятой.

Давайте возьмём ещё один пример с подробным вычислением представлением в виде числа с плавающей точкой хорошо известного всем нам значения: 3,14.

Двоичное представление с плавающей точкой числа 3,14.

То есть значение 3,14 аппроксимируется как 3,1400001049041748046875.

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

И, наконец, графическое представление с окном и смещением:

Окно и смещение числа 3,14.

Интересный факт: если модули операций с плавающей запятой были такими медленными, почему в языке C в результате использовали типы float и double? Ведь в машине, на которой изобретался язык (PDP-11), не было модуля операций с плавающей запятой! Дело в том, что производитель (DEC) пообещал Деннису Ритчи и Кену Томпсону, что в следующей модели он будет. Они были любителями астрономии и решили добавить в язык эти два типа.

Интересный факт: те, кому в 1991 году действительно нужен был аппаратный модуль операций с плавающей запятой, могли его купить. Единственными, кому он мог понадобиться в то время, были учёные (по крайней мере, так Intel понимала потребности рынка). На рынке они позиционировались как «математические сопроцессоры». Их производительность была средней, а цена огромной (200 долларов 1993 года — это 350 долларов в 2016 году.). В результате уровень продаж оказался посредственным.

Источник

Представление чисел с плавающей точкой

Содержание

Плавающая точка [ править ]

Такой метод является компромиссом между точностью и диапазоном представляемых значений. Представление чисел с плавающей точкой рассмотрим на примере чисел двойной точности (double precision). Такие числа занимают в памяти два машинных слова (8 байт на 32-битных системах). Наиболее распространенное представление описано в стандарте IEEE 754.

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

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

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

Числа двойной точности [ править ]

Число с плавающей точкой хранится в нормализованной форме и состоит из трех частей (в скобках указано количество бит, отводимых на каждую секцию в формате double):

Свойства чисел с плавающей точкой [ править ]

Особые значения чисел с плавающей точкой [ править ]

Ноль (со знаком) [ править ]

В нормализованной форме невозможно представить ноль. Для его представления в стандарте зарезервированы специальные значения мантиссы и экспоненты.

Согласно стандарту выполняются следующие свойства:

Бесконечность (со знаком) [ править ]

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

Бесконечное значение можно получить при переполнении или при делении ненулевого числа на ноль.

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

В математике встречается понятие неопределенности. В стандарте double предусмотрено псевдочисло, которое арифметическая операция может вернуть даже в случае ошибки.

Неопределенность можно получить в нескольких случаях. Приведем некоторые из них:

Денормализованные числа [ править ]

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

Начиная с версии стандарта IEEE 754 2008 года денормализованные числа называются «субнормальными» (subnormal numbers), то есть числа, меньшие «нормальных».

Машинная эпсилон [ править ]

Unit in the last place (Unit of least precision) [ править ]

Мера единичной точности используется для оценки точности вычислений.

Погрешность предиката «левый поворот» [ править ]

Определения [ править ]

[math] \exists \tilde <\epsilon>\in D: [/math]

Расчет [math] \tilde <\epsilon>[/math] [ править ]

Теперь распишем это выражение в дабловой арифметике.

[math] |\delta_i| \leq \varepsilon_m [/math]

Заметим, что [math] v \approx \tilde [/math]

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

[math] \tilde <\epsilon>\lt 8 \varepsilon_m \tilde[/math]

Заметим, что это довольно грубая оценка. Вполне можно было бы написать [math] \tilde <\epsilon>\lt 4.25 \varepsilon_m \tilde[/math] или [math] \tilde <\epsilon>\lt 4.5 \varepsilon_m \tilde.[/math]

Источник

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

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

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

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

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

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

где m и e — целые чис­ла, записан­ные в бинар­ном виде в выделен­ных под них битах. Что­бы избе­жать неод­нознач­ности, счи­тает­ся, что 1

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

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

Сло­жение реали­зует­ся срав­нитель­но прос­то:

Здесь опу­щены про­вер­ки на мак­сималь­ное целое для зна­чения e для прос­тоты изло­жения.

Для вычита­ния все чуть‑чуть слож­нее, здесь уже нуж­но учи­тывать переход ниже нуля для без­зна­ково­го целого. То есть нуж­но срав­нить два чис­ла до вычита­ния.

В целом все пока нес­ложно. До умно­жения и деления все всег­да нес­ложно.

Умножение чисел с фиксированной точностью

Ты пом­нишь шко­лу и умно­жение стол­биком? Если нет, самое вре­мя вспом­нить:

Здесь мы опус­каем сла­гаемое A 44 div 10 18 прос­то потому, что оно рав­но нулю.

Ра­зуме­ется, перед каж­дым сло­жени­ем сто­ит про­верить, не вый­дем ли мы за пре­делы MAX_INT64.

К счастью, мы можем опе­риро­вать без­зна­ковым типом uint64_t для всех ком­понент мат­рицы и для про­межу­точ­ного резуль­тата. Все, что нуж­но будет сде­лать в кон­це, — это опре­делить знак резуль­тата s e = s a xor s c и для отри­цатель­ного чис­ла поп­равить целую и дроб­ную часть: целую умень­шить на еди­ницу, дроб­ную вычесть из еди­ницы. Вот, в общем, и все умно­жение, глав­ное — быть очень акку­рат­ным. С ассем­бле­ром все на порядок про­ще, но этот матери­ал выходит за рам­ки «Ака­демии C++».

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

Для упро­щения рас­смот­рим нахож­дение обратно­го чис­ла для положи­тель­ного x.

Ес­ли хотя бы одна из ком­понент x рав­на нулю (но не обе сра­зу), вычис­ления силь­но упро­щают­ся.

ес­ли b = 0, a = 1, то y = e = 1, f = 0;

ecли b = 0, a > 1, то:
y = 1 / a,
e = 0, f = 10 18 div a.

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

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

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

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

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

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

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

От­дель­но сто­ит рас­смот­реть пре­обра­зова­ние в стро­ку и из стро­ки.

Це­лочис­ленная часть, по сути, пре­обра­зует­ся в стро­ку как есть, пос­ле это­го оста­ется толь­ко вста­вить decimal separator и вывес­ти дроб­ную часть как целое, отбро­сив завер­шающие нули.

Так­же мож­но ввес­ти поле «точ­ность» m_precision и записы­вать в стро­ку лишь ука­зан­ное в нем чис­ло десятич­ных зна­ков.

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

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

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

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

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

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

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

Будь вни­мате­лен к точ­ности, ведь точ­ность навер­няка вни­матель­на к тебе!

Источник