06.09.2017 13:44
PatientZero 38 27500 Источник
image

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

При написании книги Game Engine Black Book: Wolfenstein 3D я хотел наглядно показать, насколько был велики были проблемы при работе без плавающей запятой. Мои попытки разобраться в числах с плавающей запятой при помощи каноничных статей мозг воспринимал в штыки. Я начал искать другой способ. Что-нибудь, далёкое от $(-1)^S * 1.M * 2^{(E-127)}$ и их загадочных экспонент с мантиссами. Может быть, в виде рисунка, потому что их мой мозг воспринимает проще.

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

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


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

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

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

  • S (1 бит) для хранения знака
  • E (8 бит) для экспоненты
  • M (23 бита) для мантиссы


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


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

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

$(-1)^S * 1,M * 2^{(E-127)}$


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

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



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


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


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

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

Викторина: сколько точности теряется, когда окно закрывает больший интервал? Давайте возьмём пример с окном [0,1], в котором 8388608 смещений накладываются на интервал размером 1, что даёт нам точность $\frac{(1-0)}{8388608}=0,00000011920929$. В окне [2048,4096] 8388608 смещений накладываются на интервал $(4096-2048) = 2048$, что даёт нам точность $\frac{(4096-2048)}{8388608}=0,0002$.

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


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

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

  • Число 3,14 положительно $\rightarrow S=0$.
  • Число 3,14 находится между степенями двойки 2 и 4, то есть окно числа с плавающей запятой должно начинаться с $2^1$ $\rightarrow E=128$ (см. формулу, где окно — это $2^{(E-127)}$).
  • Наконец, есть $2^{23}$ смещений, которыми можно выразить расположение 3,14 внутри интервала [2-4]. Оно находится в $\frac{3,14 -2 }{4 - 2} = 0,57$ внутри интервала, что даёт нам смещение $M = 2^{23}*0,57 = 4781507$

В двоичном виде это преобразуется в следующее:

  • S = 0 = 0b
  • E = 128 = 10000000b
  • M = 4781507 = 10010001111010111000011b


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

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

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

$3,14 = (-1)^0 * 1,57 * 2^{(128-127)}$


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


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

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

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



Надеюсь, статья была вам полезна!

Комментарии (38)


  1. rkfg
    06.09.2017 17:03
    #10402504
    +7

    Более-менее понятно. Интересное следствие: из такой формы следует, что уже у сравнительно небольших чисел, порядка 2^24, падает точность представления даже целой части (потому что мантисса делит всегда на 2^23 элемента, и если элементов между двумя точками будет больше, то каждому второму не достанется своего значения):


    #include <iostream>

using namespace std;

int main() {
  cout << (16777215.f == 16777216.f) << endl;
  cout << (16777216.f == 16777217.f) << endl;
}

    Выведет 0 и 1, т.е. во float-представлении 16777216 равняется 16777217. Мне кажется, этот пример даже интереснее известного многим 0.1+0.2.


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


    1. ToSHiC
      07.09.2017 00:07
      #10403552
      +1

      В свете вашего комментария стоит отметить, что в javascript все числа — это double. Там, конечно, диапазон целых значений, вычисляемых без погрешности, больше, но он заметно меньше, чем 2^64.


      1. domix32
        07.09.2017 21:41
        #10405608

        После некоторых трюков там можно оперировать 32-битными целыми числами


    1. Ares_ekb
      07.09.2017 07:38
      #10403790
      +1

      Есть ещё интересный пример:

      1/3 + 1/3 + 1/3 = ?
      Складываем 1/3 сначала 3 раза, затем 30 раз, 300 раз и т.д.:

      float floatValue = 1F / 3F;
double doubleValue = 1D / 3D;
decimal decimalValue = 1M / 3M;
for (int i = 0; i <= 6; i++) {
    float floatResult = 0;
    double doubleResult = 0;
    decimal decimalResult = 0;
    int times = Convert.ToInt32(3*Math.Pow(10,i));
    for (int j = 1; j <= times; j++) {
        floatResult += floatValue;
        doubleResult += doubleValue;
        decimalResult += decimalValue;
    }
    Console.WriteLine("sum 1/3 times: {0}" , times);
    Console.WriteLine("flt = {0}", floatResult);
    Console.WriteLine("dbl = {0}", doubleResult);
    Console.WriteLine("dec = {0}", decimalResult);
    Console.WriteLine();
}
Console.WriteLine("flt = {0}", floatValue*3000000);
Console.WriteLine("dbl = {0}", doubleValue*3000000);
Console.WriteLine("dec = {0}", decimalValue*3000000);


      1. equand
        07.09.2017 16:20
        #10404934

        А вот это интересно, для работы бух софта это учитывается? Хотя там 1/3 не бывает в принципе.


        1. Gumanoid
          07.09.2017 16:56
          #10404986
          +1

          Там используют фиксированную точку (или просто int).


    1. ustaspolansky
      07.09.2017 10:02
      #10403976

      Разве во флоат не до 7 знаков включительно? Возможно это связано с большим кол. во знаков и некорректной обработкой именно на выводе.

      Я не программист, не ругайте.


      1. rkfg
        07.09.2017 11:23
        #10404210
        +2

        Там не в знаках считается, а в битах. В статье сказано, что мантисса составляет 23 бита, так что максимальная достижимая точность на целых числах будет, когда между 2^E и 2^(E+1) (отбросим для простоты -127) будет 2^23 чисел, тогда каждому числу можно противопоставить одно значение мантиссы. Если же этих чисел больше, то можно найти такое число, которому уже не сопоставишь своё выделенное значение мантиссы, вот я для примера выбрал участок, где 2^24 чисел, т.е. в два раза больше. Поэтому у чётных чисел есть своё значение мантиссы, а нечётным уже не хватает, и происходит «округление».


  1. sbnur
    06.09.2017 17:07
    #10402524

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


    1. rfq
      07.09.2017 00:39
      #10403580

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


      1. tyomitch
        07.09.2017 16:03
        #10404906
        +1

        Они с самого начала были в «больших» компьютерах (предназначенных в первую очередь для учёных), но очень долго отсутствовали в ПК (предназначенных в первую очередь для секретарш).


  1. 32bit_me
    06.09.2017 18:53
    #10402926
    +8

    Мне как раз кажется понятной формула, и кажутся непонятными все эти объяснения с картинками. Формула сразу даёт понимание того, как с этими числами работать, то есть как складывать, умножать и делить, пользуясь их бинарным представлением.
    К тому же тема не раскрыта до конца, потому что, кроме описанной здесь нормализованной формы, есть также денормализованная форма и разные нечисла, типа NaN и Inf.


    1. Wano987
      06.09.2017 22:36
      #10403450

      Я, конечно, могу ошибаться, но каждому — своё.
      Лично я односимвольные регистрочувствительные имена переменных/классов без обильных комментариев воспринимаю достаточно посредственно. Так что мне эта статья была небесполезна.


    1. WebConn
      07.09.2017 00:12
      #10403562
      +1

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


      1. rfq
        07.09.2017 00:45
        #10403582
        +4

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


    1. slavap
      07.09.2017 10:02
      #10403978

      Формула ужасна, объяснение, а особенно картинка, отличные. Наверное, нужно быть математиком, чтобы сходу понять, как эти числа делить глядя только на формулу.


    1. Alozar
      07.09.2017 20:55
      #10405536

      Проблема такой математической записи, что она понятна только тем кто понимает. Простите за каламбур. Математическая запись точна, отбрасывает всё лишнее, но обывателю в большинстве случаев вообще не понятна.
      Я например смог понять как с ней работать только после прочтения этой статьи, где было всё объяснено человеческим языком и показано на конкретном примере. Теперь смотря на формулу, всё становится на свои места и понятно, почему она такая и как с ней работать. Но это требует не математического, а «человеческого» объяснения.

      Другой пример — производная функции

      Производная функции — предел отношения приращения функции к приращению независимой переменной при стремлении последнего к нулю (если этот предел существует)

      Определение точно? Точно. Понятно? Нет. В ответ на это определение надо выяснять, что теперь делать с этим произведением и зачем оно вообще надо. Если же сказать, что производная функции — это скорость изменения функции в конкретной точке, становится понятно, но при этом не точно. Аналогичная история происходит в этой статье. Формула нужна для точного понимания, а картинки для первичного понимания сути.


      1. 32bit_me
        08.09.2017 04:44
        #10406120

        Я с вами согласен в том смысле, что формула не даёт понимания, когда смотришь на неё в первый раз. Но для объяснения принципа представления вещественных чисел в формате IEEE 754 в нормализованной форме достаточно разобрать один-два примера.
        От статьи на хабря я обычно жду полноты, то есть, хорошо было бы написать про денормализованные числа, про нечисла и правила их обработки, про разные варианты, предусмотренные стандартом, включая децимальный формат, а также 128- и 256-битные числа, про 80-битный формат, который был принят в x86 изначально, про разные исторические и необычные форматы (типа модульного логарифмического). Вот это было бы интересно.


  1. Varim
    07.09.2017 02:55
    #10403658

    экспонента — расстояние между шагами
    мантиса — номер шага

    в статье не увидел, почему записывают
    3,14 = 1,57 *2 ( 2 в степени 1 равно 2, то есть экспонента 128-127 = 1)

    вместо
    3,14 = 3,14*1 (2 в степени 0 равно 1, то есть экспонента 127-127 = 0)


    1. Varim
      07.09.2017 03:02
      #10403660
      +1

      в двоичном виде мантиса 1.M, то есть выигрывают 1н бит, а в десятичном может быть 1.M или 9.M


  1. Varim
    07.09.2017 03:09
    #10403666

    2в23 * 0,57 = 4781506.56


  1. igormu
    07.09.2017 06:57
    #10403774
    +2

    Нет окна [0, 1]. Есть только [1/2, 1), [1/4, 1/2) и так далее. 0 в нормализованном представлении отобразить нельзя, поэтому он искусственно принят как (E=0, M=0).


  1. GlebSemenov
    07.09.2017 10:02
    #10403980
    +1

    Не могу согласиться с утверждением, что у процессора PDP-11 не было модулей плавающей точки. Был FIS (Floating Instruction Set) и кое-где FPP (Floating Point Processor)


  1. DrAndyHunter
    07.09.2017 10:02
    #10403982

    Статья доходчиво объясняет сложную для понимая вещь. Спасибо за перевод автору!
    Но остался для меня один непонятный момент:

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


    Я не понял, как вычисляется вот эта часть 0,0000001049041748046875?


    1. GarryC
      07.09.2017 10:35
      #10404078

      (1)10010001111....011b = 13170115d /4/2/2.../2 = 3,1400001049041748046875.


    1. Den3D
      07.09.2017 10:49
      #10404106
      +1

      M = 2^23*0.57 = 8388608 *0.57 = 4781506,56
      4781507 — 4781506,56 = 0.44
      0.44*2/8388608 = 0,0000001049041748046875


  1. GalayZloy
    07.09.2017 10:15
    #10404008
    +2

    А есть процессоры или теории с другим представлением чисел с запятой? Вообще описанное представление оптимально или исрользуется по-традиции?


    1. MacIn
      07.09.2017 11:56
      #10404304

      del


  1. Busla
    07.09.2017 10:29
    #10404058
    +1

    В языке C значения с плавающей запятой — это 32-битные контейнеры, соответствующие стандарту IEEE 754

    неправда:
    типов с плавающей запятой несколько
    они платформозависимы
    IEEE 754 в С99 носит рекомендательный характер, а С11 ссылается на более поздние стандарты


  1. MacIn
    07.09.2017 11:50
    #10404278

    Как же вы будете читать статьи типа такой:
    sites.math.washington.edu/~morrow/336_12/papers/ben.pdf

    Если простая матзапись числа с плавающей запятой непонятна?


  1. PaulZi
    07.09.2017 15:20
    #10404826

    Может нубский вопрос, а чем интересно такое представление отличается в плане скорости/точности?
    (-1)^S * 0.S * 10 ^ (E-127)


    1. tyomitch
      07.09.2017 16:09
      #10404918

      Возможно, вы имели в виду: (-1)^S * 0.M * 10 ^ (E-127)
      Такое представление отличается тем, что приведение в него неоднозначно: 0.001 можно записать как 0.001*10^0 или как 0.01*10^-1 или как 0.1*10^-10
      При этом приведение к форме (-1)^S * 1.M * 10 ^ (E-127) однозначно, потому что ведущая единица в числе только одна.


      1. PaulZi
        07.09.2017 17:37
        #10405094

        Да, ошибся. Ну хорошо, допустим:
        (-1)^S * 1.M * 10 ^ (E-127)
        Чем это хуже чем:
        (-1)^S * 1.M * 2 ^ (E-127)
        ?
        С основанием 10 всё понимается в разы легче, по крайней мере для нас, 10-чных людей.


        1. PaulZi
          07.09.2017 17:44
          #10405112
          +1

          Хотя понял что с основанием 1.M не получится представить 2…


          1. firk
            07.09.2017 18:10
            #10405188
            +1

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


        1. tyomitch
          07.09.2017 17:50
          #10405126

          ?


  1. Andronas
    08.09.2017 10:03
    #10406452

    Число 3,14 находится между степенями двойки 2 и 4, то есть окно числа с плавающей запятой должно начинаться с 2^1 >E=128 (см. формулу, где окно — это 2(E?127)).

    откуда тут взялось что 2^1 >E=128 ??? как объяснить не привлекая формулу?


    1. Westimo
      08.09.2017 16:23
      #10407270

      Не привлекая формулу, можно считать так:
      Окно | Е
      …
      [1,2] | 127
      [2,4] | 128
      [4,8] | 129
      …