Каково точное значение первого типа - в обратном алгоритме быстрого квадратного корня?

Question

Имея этот код (это хорошо известный алгоритм быстрого обратного корня квадратного корня, который использовался в Quake 3), я не могу понять вывод на печать.Я понимаю весь алгоритм поверхностно, но хочу получить глубокое понимание.Каково значение i, когда printf печатает его?Это дает мне 1120403456.Зависит ли это от архитектуры компьютера?Я где-то читал, что подобное наказание типа приводит к неопределенному поведению.На другом сайте я читал, что значение i в этот момент является точным значением битов, которые используются этой переменной.Я смущен этим и искренне ожидал, что значение i будет равно 100. Как мне интерпретировать полученное значение 1120403456?Как мне преобразовать это значение в десятичную 100?Эти биты как-то закодированы?Вот выдержка из кода:

#include<stdio.h>

int main()
{
float x = 100;
float xhalf = 0.5f*x;
int i = *(int*)&x;
printf("%d", i);
i = 0x5f3759df - (i>>1);
x = *(float*)&i;
x = x*(1.5f-xhalf*x*x);
return x;

}

Answer 1

Для интерпретации 1120403456 или любого другого числа как базового 32-разрядного двоичного числа IEEE с плавающей запятой:

• Запись числа в виде 32 битов, в данном случае, 01000010110010000000000000000000.
• Первый бит это знак.0 - это +, а 1 - -.
• Следующие восемь битов представляют собой кодировку показателя степени.Это 10000101, что составляет 133 в десятичном виде.Экспонента кодируется смещением 127, означающим, что фактическая мощность двух представленных составляет 2 ^133−127 = 2 ⁶ .(Если показатель степени равен 0 или 255, это специальное значение, имеющее другое значение.)
• Остальные 23 бита кодируют значение и.Для нормальных показателей (коды от 1 до 254) они кодируют значение и формируются, начиная с «1» и добавляя 23 бита «10010000000000000000000», чтобы получить двоичное число «1.10010000000000000000000».В десятичном формате это 1,5625.
• Полное закодированное значение - это знак со степенью двойки, умноженной на значение: + 2 ⁶ • 1,5625, что равно 64 • 1,5625, то есть100.

Если бы код экспоненты был 0, он представляет 2 ^-126 , и значение и было бы сформировано, начиная с «0» вместо «1».

Если бы код экспоненты был 255, а значимые и биты были равны нулю, объект представлял бы бесконечность (+ ∞ или -∞ в соответствии со знаковым битом).Если бы код экспоненты был 255, а значимые и биты не были нулевыми, объект представлял бы не число (NaN).Есть дополнительная семантика для NaN, не охваченная в этом ответе.

Answer 2

Это намного старше, чем Quake III , хотя точная магическая константа немного изменилась.

Кодирование конечного числа с плавающей запятой одинарной точности числав соответствии с IEEE-754 (который используется большинством современных компьютеров) это

     31 30           23 22                                          0
     ├─┼─┬─┬─┬─┬─┬─┬─┬─┼─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┤
     │S│   Exponent    │                   Mantissa                  │
     └─┴───────────────┴─────────────────────────────────────────────┘

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

Если Exponent и Mantissa оба равны нулю, то значение равно либо 0,0 (если S равно нулю), либо -0,0 (если S равно 1).

Если Exponent равно нулю, но Mantissa ненулевое, у вас есть ненормальное число очень близко к нулю.

Представления, где Exponent - 255 (все установленные биты) зарезервированы для бесконечности (если Mantissa - ноль), а не для числа (если Mantissa не равен нулю).

Для значений Exponent от 1до 254 включительно, Mantissa содержит дробных битов мантиссы с неявным 1 в целой позиции (это то, что означает (1), например, 0 10000001 (1)1011011011011011011011.) Другими словами,значение Mantissa представляет для этих Exponent значений от 1.00000000000000000000000 ₂ (1,0 в десятичном виде) до 1,11111111111111111111111 ₂ (1,999999994 в десятичном виде) включительно.

Теперь, если мы рассмотрим только неотрицательные значения (с полем S), с E = Exponent (между 1 и 254 включительно), and M логическое значение Mantissa (между 1.0 и 1.99999994), затем значение V , представляющее собой плавающую точку одинарной точности, равно

V = 2 ^{E - 127} × M

127 - это смещение показателя степени.Корень квадратный из V равен

√ V = 2 ^{( E - 127) / 2} × √ M = 2 ^{E / 2 - 127} × 2 ⁶³ × √2 × √ M

и обратный квадратный корень, который здесь является целевой операцией,

1 / √ V = 2 ^{(127 - E ) / 2} × 1 / √ M = 2 ^{- E / 2 - 127} × 2 ⁶³ × √2 × 1 / √ М

отмечая, что 2 ^127/2 = 2 ^63,5 = 2 ⁶³ × √2.

Если мы возьмем целочисленное представление и сместим его на один бит вправо, мы фактически уменьшим вдвое E .Чтобы умножить на 2 ⁶³ , нам нужно добавить 63 к показателю степени;63 × 2 ²³ .Однако для операции с квадратным корнем вместо умножения на √2 × √ M мы фактически просто умножаем на M / 2.Это означает, что это (смещение целочисленного представления на один бит вправо, затем добавление 63 к показателю степени) дает оценку квадратного корня, которая отклоняется с коэффициентом от 0,7071067 до 0,75 для аргументов, превышающих 1,0, и с коэффициентом между 0,7071067 и1448,155 для значений от 0 до 1. (Это дает 5,421 × 10 ^-20 для √0 и 0,75 для √1.)

Обратите внимание, что для операции с обратным квадратным корнем мы хотимдля отрицания E .

Оказывается, что если вы сдвинете целочисленное представление вправо на один бит, а затем вычтите это из (1 01111100 1101110101100111011111) ₂ (1597463007в десятичном виде, 0x5f3759df в шестнадцатеричном виде, приближение с плавающей точкой одинарной точности √2 ¹²⁷ ≈ 13043817825332782212), вы получите довольно хорошее приближение обратного корня квадратного (1 / √ V * 1138)*).Для всех конечных нормальных аргументов приближение отклоняется от 0,965624 до 1,0339603 с правильным значением;очень хорошее приближение!Все, что вам нужно, это одна или две итерации метода Ньютона для обратной квадратной операции сверху.(Для f ( X ) = 0 тогда и только тогда X = 1 / √ V вам нужно f ( X ) = 1 / X ^ 2 - V . Таким образом, каждая итерация в X равна X - f ( X ) / f '( X ) = X × (1,5 - 0,5 × V × X × X . Что должно выглядетьдовольно знакомо.)

Answer 3

Значение i, напечатанное после int i = *(int*)&x;, является битовым представлением с плавающей точкой 100.0, к которому был инициализирован x.Поскольку вы используете формат %d в printf, он напечатает это представление в виде десятичного целого числа.

Битовый паттерн 100.0 в 32-битном IEEE float равен 0x42c80000,1120403456 в десятичном