ДС20в03-представление-с-точкой (1238924)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Представление c точкойОсновы информатикиКомпьютерные основы программированияu.to/DbCmFAНа основе CMU 15-213/18-243:Introduction to Computer Systemsu.to/XoKmFAЛекция 3, 2 марта, 2020Лектор:Дмитрий Северов, кафедра информатики 608 КПМdseverov@mail.mipt.rucs.mipt.ru/wp/?page_id=3461Плавающая точка¢¢¢¢¢¢Основы: Двоичные дробиСтандарт «плавающей точки» IEEE : ОпределениеПримеры и свойстваОкругление, сложение, умножениеПлавающая точка в CиСводка2Двоичные дроби¢Что такое 1011.1012?3Двоичные дроби2i2i-1421•••bi bi-1 ••• b2 b1 b0 b-1 b-2 b-3 ••• b-j¢Представление•••1/21/41/82-j§ Биты справа от «двоичной точки» представляют дробные степени 2§ Представление рациональных чисел:4Двоичные дроби: Примеры¢ЗначениеПредставление5 и 3/4101.1122 и 7/810.11121 и 7/161.0111223/32¢0.101112Важно§ Деление на 2 сдвигом вправо§ Умножение на 2 сдвигом влево§ Числа вида 0.111111…2 меньше 1.01/2 + 1/4 + 1/8 + … + 1/2i + … ➙ 1.0§ Обозначим 1.0 – ε§5(не)Представимые числа (1)¢Ограничения§ Двоичными дробями точно представимы только числа вида n/2k§ Другие дроби представимы бесконечными периодическими«дробями»¢Значение Представление§ 1/3§ 1/5§ 1/100.[01]…20.[0011]…20.0[0011]…26Плавающая точка¢¢¢¢¢¢Основы: Двоичные дробиСтандарт «плавающей точки» IEEE : ОпределениеПримеры и свойстваОкругление, сложение, умножениеПлавающая точка в CиСводка7Плавающая точка IEEE¢Стандарт IEEE 754§ Принят в 1985 как единый стандарт арифметики с плавающей точкойДо этого множество уникальных стандартов§ Поддерживается всеми основными CPU/FPU§¢В основе - вопросы вычислений§ Удачно стандартизованыокругления,§ переполнения,§ потеря значимости§ Сложно сделать быстрым в аппаратуре§ При создании стандарта численные аналитики доминировали надразработчиками аппаратуры§ Есть реализации «с отклонениям軧¢Есть версии и альтернативы8Представление с плавающей точкой¢Численная форма:(–1)s M 2E§ Знаковый бит s определяет положительность/отрицательность§ Мантисса M - обычно дробь в интервале [1.0,2.0).§ Порядок E изменяет значение на степень двойки¢Кодирование§ Наиболее значимый бит s – знаковый§ Поле exp кодирует E, но не совпадает с двоичным значением E§ Поле frac кодирует M, но не совпадает с двоичнымзначением Ms expfrac9Применяемые точности¢Одинарная: 32 битаs exp1¢frac8-битДвойная: 64 битаs exp1¢23-битаfrac11-бит52-битаРасширенная: 80 бит (только для Intel)s exp115-битаfrac63 или 64-бита10Нормализованные значения¢Признак: exp ≠ 000…0 и exp ≠ 111…1¢Порядок кодируется со смещением : E = Exp – Bias§ Exp: беззнаковое значение поля exp§ Bias = 2k-1 - 1, где k - количество бит порядка – смещениеОдинарная точность: 127 (Exp: 1…254, E: -126…127)§ Двойная точность: 1023 (Exp: 1…2046, E: -1022…1023)§¢Код мантиссы подразумевает старшую 1: M = 1.xxx…x2§§§§§xxx…x: биты поля fracМинимальное значение M = 1.0 , когда frac = 000…0Минимальное значение M = 2.0 – ε , когда frac = 111…1Старший бит мантиссы не расходует ресурсы оборудованияНе подразумевается для расширенной точности 80-бит Intel !11Пример нормализованного кода¢Значение: Float F = 15213.0;§ 1521310 = 111011011011012= 1.11011011011012 x 213¢МантиссаM=frac =¢1.11011011011012110110110110100000000002ПорядокE=Bias =Exp =¢13127140 =100011002Результат:0 10001100 11011011011010000000000sexpfrac12Денормализованные значения¢¢¢Признак: exp = 000…0Значение порядка: E = 1–Bias (вместо E = 0 – Bias)Код мантиссы подразумевает старший 0: M = 0.xxx…x2§ xxx…x: биты frac¢Варианты§ exp = 000…0, frac = 000…0Обозначает нулевое значение§ Представление неоднозначно: +0 and –0 (почему?)§ exp = 000…0, frac ≠ 000…0§ числа очень близкие к 0.0§ чем меньше, тем хуже относительная погрешность§ равноотстоящие§13Специальные коды¢Признак: exp = 111…1¢Вариант 1: exp = 111…1, frac = 000…0§§§§¢Обозначает значение ∞ (бесконечность)Результат операции при переполненииЕсть оба варианта: отрицательная и положительнаяE.g., 1.0/0.0 = −1.0/−0.0 = +∞, 1.0/−0.0 = −∞Вариант 2: exp = 111…1, frac ≠ 000…0§ Не число, Not-a-Number (NaN)§ Обозначает случаи когда невозможно определить численноезначение§ Примеры: sqrt(–1), ∞ − ∞, ∞ × 014Коды с плавающей точкой визуально−∞NaN−Нормализов.

−Денорм.-0+Денорм.+0+Нормализов.+∞NaN15(не)Представимые числа (2)Непредставимо большиеНормализованныеДенормализованныеНепредставимомалые- Ноль | +Ноль…p-2p-1pp+1p+216Плавающая точка¢¢¢¢¢¢Основы: Двоичные дробиСтандарт «плавающей точки» IEEE : ОпределениеПримеры и свойстваОкругление, сложение, умножениеПлавающая точка в CиСводка17Укороченный пример с плавающей точкой¢sexpfrac14-бита3-бита8-битное представление с плавающей точкой§ Знаковый бит – самый значимый§ следующие четыре бита - показатель со смещением 24-1-1 = 7§ последние три бита - код мантиссы¢Форма таже что в стандарте IEEE§ нормализованные и денормализованные§ обозначаются 0, NaN, бесконечность18Динамический диапазон положительныхs expДеномализ.числаНормализов.числа000…0000…00000…000fracEЗначение0000 0000000 0010000 010-6-6-601/8*1/64 = 1/512 Ближайшее к нулю2/8*1/64 = 2/5120000000000010001110111000001-6-6-6-66/8*1/647/8*1/648/8*1/649/8*1/64====6/5127/512 Наибольшее денорм.8/512 Наименьшее нормализ.9/51201100110011101110111110111000001010-1-100014/8*1/215/8*1/28/8*19/8*110/8*1=====14/1615/16 Ближайшее к 1 снизу19/8Ближайшее к 1 сверху10/877n/a14/8*128 = 22415/8*128 = 240inf1110 1101110 1111111 000Наибольшее нормализ.19Распределение значений¢Шестибитный формат подобный IEEE§ 3 бита порядка§ 2 дробных бита§ смещение: 23-1-1 = 3¢sexpfrac13 бита2 битаСгущение вокруг 08 значений-15-10-5Денормализованные0Нормализованные51015Бесконечность20Распределение значений (крупнымпланом)¢Шестибитный формат подобный IEEE§ 3 бита порядка§ 2 дробных бита§ смещение: 23-1-1 = 3-1-0,5Денормализованныеsexpfrac13 бита2 бита0Нормализованные0,51Бесконечность21Особые свойства кодирования IEEE¢Совпадают коды целочисленного нуля и«положительного» нуля с плавающей точкой§ Все биты - нулевые¢Можно ли сравнить как беззнаковые целые?§ Сравнить знаковые биты§ Учесть −0 = 0§ Решить проблему с NaNNaN код больше любого численного кода§ Что должно выдать сравнение?§ В остальном - OK§ Денормализованные с нормализованными§ Нормализованные с бесконечностью§22Плавающая точка¢¢¢¢¢¢Основы: Двоичные дробиСтандарт «плавающей точки» IEEE : ОпределениеПримеры и свойстваОкругление, сложение, умножениеПлавающая точка в CиСводка23Операции с плав.

точкой: Основная идея¢x +f y = Round(x + y)¢x¢Основная идеяfy = Round(xy)§ Сначала вычислить полный результат§ Затем втиснуть его в желаемую точностьВозможно с переполнением, если порядок слишком велик§ Возможно с округлением, чтобы уместиться во frac§24Округление¢¢Режим округления 1.401.50§ К нулю1§ Вниз (−∞)1§ Вверх (+∞)2§ К чётному (по умолч.) 11.601.502.50–112211222232–1–2–1–2В чём преимущества режимов?25Подробнее об округлении к чётному¢Режим округления по умолчанию§ Любой другой режим требует обращения к ассемблеру§ Все остальные режимы дают статистический сдвиг§¢Сумма округлённых устойчиво меньше или устойчиво большеокруглённой суммыПрименяя к десятичным разрядам§ Если точно посередине между двумя возможными значениямиОкругляется так, что младшая цифра чётная§ Например, округление к ближайшей сотой1.23499991.23(Меньше половины - вниз)1.23500011.24(Больше половины - вверх)1.23500001.24(Половина - вверх)1.24500001.24(Половина - вниз)§26Округление двоичных чисел¢Двоичные дроби§ “Чётные” когда наименьший бит = 0§ “Половина” когда биты справа от позиции округления = 100…2¢Примеры§ Округление к 1/4 (2 бита справа от двоичной точки)Значение2 3/322 3/162 7/82 5/8ДвоичноеДвоичноеОкруглённоеОкругление10.00011210.00210.00110210.01210.11100211.00210.10100210.102Действие(<1/2—вниз)(>1/2—вверх)( 1/2—вверх)( 1/2—вниз)Значение22 1/432 1/227Умножение с плавающей точкой¢¢(–1)s1 M1 2E1 x (–1)s2 M2 2E2Полный результат: (–1)s M 2E§ Знак s:s1 ^ s2§ Мантисса M:M1 x M2§ Порядок E: E1 + E2¢Нормализация§ Если M ≥ 2, сдвинуть M вправо, увеличив E§ Если E за рамками, то переполнение§ Округлить M чтобы уложиться в точность frac¢Реализация§ Трудоёмкая часть - перемножение мантисс28Сложение с плавающей точкой¢(–1)s1 M1 2E1 + (-1)s2 M2 2E2§Предположим E1 > E2¢Полный результат: (–1)s M 2EE1–E2§Знак s, мантисса M:Результат знаковоговыравнивания и сложения§Порядок E:E1(–1)s1 M1§¢Нормализация+(–1)s2 M2(–1)s M§Если M ≥ 2, сдвинуть M вправо, увеличив E§Если M < 1, сдвинуть M влево на k разрядов, уменьшив E на k§Если E за рамками, то переполнение§Округлить M чтобы уложиться в точность frac29Математические свойства сложения с ПТ¢Сравним со свойствами абелевой группы§ Замкнута относительно сложения ?Да, но…Может выдавать бесконечность или нечислоКоммутативно ?ДаАссоциативно ?Нет§ Переполнение и округление!Ноль – нейтральный элемент ?ДаКаждый элемент имеет обратный ?Почти§ Кроме бесконечности и нечисл১§§§¢Монотонность§ a ≥ b ⇒ a+c ≥ b+c ?§Кроме бесконечности и нечислаПочти30Математические свойства умножения с ПТ¢Сравним со свойствами коммутативного кольца§ Замкнут относительно умножения ?Может выдавать бесконечность или нечислоУмножение коммутативно ?Умножение ассоциативно ?§ Переполнение и округление!Единица нейтральный элемент умножения ?Умножение дистрибутивно относительно сложения ?§ Переполнение и округление!Д১§§§¢ДаНетДаНетМонотонность§ a ≥ b & c ≥ 0 ⇒ a * c ≥ b *c ?§ПочтиКроме бесконечностей и нечисел31Плавающая точка¢¢¢¢¢¢Основы: Двоичные дробиСтандарт «плавающей точки» IEEE : ОпределениеПримеры и свойстваОкругление, сложение, умножениеПлавающая точка в CиСводка32Плавающая точка в Cи¢Cи гарантирует как минимум два уровня точности§float§double¢одиночнаядвойнаяПреобразования§Преобразование между int, float, и double меняет набор битов§ double/float → intОтсекает дробную часть§ Подобно округлению к нулю§ Не определено для запредельных или NaN: обычно TMin§ int → double§ Точное преобразование, т.к.

int имеет разрядность ≤ 53 бит§ int → float§ Округляется в соответствии в режимом§¢x86: вычисления выражения в 80-битном представлении33Головоломки плавающей точки¢Для каждого следующего выражения Си объясните:§ либо почему оно верно для любых значений аргументов§ либо почему неверно• x == (int)(float) x• x == (int)(double) xint x = …;• f == (float)(double) ffloat f = …;double d = …;• d == (float) dПринять, чтони d ни f не есть NaN• d < 0.0⇒((d*2) < 0.0)• d > f⇒-f > -d• f == -(-f);• 2/3 == 2/3.0• d * d >= 0.0• (d+f)-d == f34Плавающая точка¢¢¢¢¢¢Основы: Двоичные дробиСтандарт «плавающей точки» IEEE : ОпределениеПримеры и свойстваОкругление, сложение, умножениеПлавающая точка в CиСводка35Сводка¢¢¢Плавающая точка IEEE имеет ясные математическиесвойства.

Почти!Представимы числа вида (-1)S M x 2EОперации [не]зависимы от реализации§ Если все выполнены с двойной точностью и затем округлены¢Не совпадают с вещественной арифметикой§ Нарушены свойства ассоциативности/дистрибутивности§ Создаёт сложности для разработчиков компиляторов иответственных численных приложений36Дополнения37Создание числа с плав. точкой¢Шаги§ Нормализовать до получения старшей 1§ Округлить до укладывания в мантиссу§ Перенормализовать для учёта округления¢Пример§ Преобразовать 8 битовые беззнаковые числа в формат сплавающей точкой128131533351386310000000000011010000111100010001000100111000101000111111sexpfrac14 бита3 бита38НормализацияЗначение12815171913863Двоичное100000000000111100010001000100111000101000111111sexpfrac14 бита3 битаДробь1.00000001.11100001.00010001.00110001.00010101.1111100Порядок73447539Округление1.BBGRXXXGuard bitSticky bit: ИЛИ остальных битRound bit: 1-й удалённый¢Правила округления§ Round = 1, Sticky = 1 ➙ > 0.5§ Guard = 1, Round = 1, Sticky = 0 ➙ округление к четномуЗначение12815171913863ДробьGRSДобав.Округлённое1.00000001.11100001.00010001.00110001.00010101.1111100000100010110011111NNNYYY1.0001.1111.0001.0101.00110.00040Перенормализация¢Проблема§ Округление может вызвать переполнение§ Решается одиночным сдвигом точки вправо и увеличениемпорядкаЗначение12815171913863Округленное1.0001.1111.0001.0101.00110.000Пор.734475Уточнённое1.000Результат12815162013464 (пор.

Характеристики

Тип файла PDF

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

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

Список файлов лекций