Слайды лекций - 2014 (лектор - Белеванцев А. А.) (1107979), страница 6

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

Текст из файла (страница 6)

Как правило, этот вызов может бытьоптимизирован компилятором в цикл.int fact (int n) {if (n == 0)return 1;elsereturn n*fact (n-1);}int fact (int n) {return tfact (n, 1);}int tfact (int n, int acc) {if (n == 0)return acc;return tfact (n-1, n*acc);}int fact (int n) {int t_n = n, t_acc = 1;/* tfact встроена в fact и оптимизирована в цикл */start:if (t_n == 0)return t_acc;t_acc = t_n * t_acc;t_n = t_n – 1;goto start;}20Ключевое слово inline: встраиваемые функции (C99)#include <stdio.h>inline static int max (int a, int b){return a > b ? a : b;}int main (void){int x = 5, y = 17;printf ("Наибольшим из чисел %d и %d является %d\n",x, y, max (x, y));return 0;} При обычной реализации inline приведенная программа эквивалентна:#include <stdio.h>inline static int max (int a, int b){return a > b ? a : b;}int main (void){int x = 5, y = 17;printf ("Наибольшим из чисел %d и %d является %d\n",x, y, (x > y ? x : y));return 0;21}Указатели на функциюКаждая функция располагается в памяти поопределенному адресу.

Адресом функции является ееточка входа (при вызове функции управление передаетсяименно на эту точку).Присвоив значение адреса функции переменной типауказатель, получим указатель на функцию.Указатель функции можно использовать вместо ее именипри вызове этой функции. Указатель «лучше» имени тем,что его можно передавать другим функциям в качестве ихаргумента.Имя функции f()без скобок и аргументов (f) поопределению является указателем на функцию f()(аналогия с массивом).int (*pf) (const char*, const char*);char *s1, *s2;int x = (*pf) (s1, s2);int y = pf (s2, "string constant");22Указатели на функциюПример.

Сравнение двух строк символов, введенныхпользователем (функция check()).#include <stdio.h>#include <string.h>static void check (char *a, char *b,int (*pf) (const char*, const char*)) {printf ("Проверка на совпадение: ");if (! pf (a, b))printf ("равны\n");elseprintf ("не равны\n");}int main (void) {char s1[80], s2[80];printf ("Введите две строки \n");fgets (s1, sizeof (s1), stdin); s1[strlen (s1) - 1] = 0;fgets (s2, sizeof (s2), stdin); s2[strlen (s2) - 1] = 0;check (s1, s2, strcmp);return 0;}23Объявление int (*p)(const char *, const char *);сообщает компилятору, что p – указатель на функцию, имеющуюдва параметра типа const char * и возвращающую значениетипа int.Скобки вокруг *p нужны, так как операция * имеет более низкийприоритет, чем (): если написать int *p(...), получится, чтообъявлен не указатель на функцию, а функция p, котораявозвращает указатель на целое.(*cmp)(a, b) эквивалентно cmp(a, b).У функции check три параметра: два указателя на тип char иуказатель на функцию pf.

Указатель pf и функция strcmp имеютодинаковый формат, что позволяет использовать имя функциив качестве аргумента, соответствующего параметру pf.В данном случае использование указателя на функциюпозволяет не менять программу сравнения, и тем самымполучается более общий алгоритм.int compvalues (const char *a, const char *b) {return atoi (a) != atoi (b);}Массивы указателей на функцию: гибкая обработка событий24Курс «Алгоритмы и алгоритмические языки»1 семестр 2014/2015Лекция 91Вычисления с плавающей точкойПредпосылки: дробные двоичные числаСтандарт арифметики с плавающей точкой IEEE 754:ОпределениеПример и свойстваОкругление, сложение, умножениеПлавающие типы языка СиВыводы2Дробные двоичные числаЧто такое 1011.1012 ?1× 23 + 0 × 2 2 + 1× 21 + 1× 20 + 1× 2 −1 + 0 × 2 −2 + 1× 2 −3 =5= 11 = 11.62583Дробные двоичные числаЧерное пятнышко – двоичная точкаБиты слева от точки умножаются на положительные степени 2Биты справа от точки умножаются на отрицательные степени 24Дробные двоичные числа0.111111…2 = 1.0−ε (ε →0), так как1 + 1 + 1 + ...

+ 1 n + ... → 12482при n → ∞xТочно можно представить только числа видаОстальные рациональные числа представляютсяпериодическими двоичными дробями:2k1 = 0.(0011)25Иррациональные числа представляютсяапериодическими двоичными дробями и могут бытьпредставлены только приближенно5Представление чисел с плавающей точкой (IEEE 754)Числа с плавающей точкой представляются внормализованной форме: (-1s) M 2es – код знака числа (он же знак мантиссы)M – мантисса ( 1 ≤ M < 2 )e – (двоичный) порядокПервая цифра мантиссы в нормализованном представлениивсегда 1.

В стандарте принято решение не записывать впредставление числа эту единицу (тем самым мантисса как быувеличивается на разряд).Экономия связана с тем, что в представление числазаписывается не M, а frac = M – 16Представление чисел с плавающей точкойЧтобы не записывать отрицательных чисел в полепорядка, вводится смещение bias = 2 k −1 − 1 , где k –количество бит в поле для записи порядка, и вместопорядка e записывается код порядка exp, связанныйс e соотношением e = exp – bias.Нормализованное число (-1s) M 2e упаковывается вмашинное слово (структуру) с полями s, frac и expШирина поля s всегда равна 1.Ширина полей exp и frac зависит от точности числа7Представление чисел с плавающей точкойОдинарная точность (32 бита):8 битbias = 127;-126 ≤ e ≤ 127 ;1 ≤ exp ≤ 254Двойная точность (64 бита):11 битbias = 1023;23 бита52 бита-1022 ≤ e ≤ 1023 ;1 ≤ exp ≤ 2046Повышенная точность (80 бит):15 бит64 бита8Представление чисел с плавающей точкойПример Значениеfloat f = 15213.01521310 =111011011011012 =1.11011011011012 × 213 Значащая частьM= 1.11011011011012,frac =110110110110100000000002 Порядокe=bias =exp =13127140 = 100011002 Результат9Представление нуляДля типа float код порядка exp изменяетсяот 00000001 до 11111110(значению 00000001 соответствует порядок e = - 126,значению 11111110 – порядокe =127)Код exp = 00000000, frac = 000…0представляет нулевое значение; в зависимости отзначения знакового разряда s это либо +0 либо -0А какое значение представляют кодыexp = 00000000, frac ≠ 000…0?exp = 11111111?10Большие числаПусть exp = 111…1если при этом frac = 000…0, то коду будетсоответствовать значение ∞ (со знаком s)если же frac ≠ 000…0, то код не будетпредставлять никакое число(«значение», представляемое таким кодом, так иназывается: «не число» – NaN – Not a number)11Денормализованные числаЭто числа, представляемые кодамиexp = 00000000, frac ≠ 000…0exp вносит в значение такого числа постоянныйвклад 2-k-2,frac меняется от 000…01 до 111…1 ирассматривается уже не как мантисса, а какзначение, умножаемое на expРассмотрим это на модельном примере:128-разрядные числа с плавающей точкой (положительные)138-разрядные числа с плавающей точкойЦентральная область более крупно14Важные частные случаиexpfracЧисленное значение Нуль00…0000…000.0 Наим.

положит. денорм. float ≈ 1.4×10-45 double ≈ 4.9×10-32400…0000…01 Наиб. положит. денорм. float ≈ 1.18×10-38 double ≈ 2.2×10-30800…00 Наим. положит. норм. float double00…01 Единица01…11 Наиб. положит. норм. float ≈ 3.4×1038 double ≈ 1.8×103082-23×2-1262-52×2-102211…11(1.0 - ε)×2-126(1.0 - ε)×2-102200…001.0×2-1261.0×2-102200…001.0(2.0 - ε)×2127(2.0 - ε)×2102315Операции над числами с плавающей точкойx + FP y = Round ( x + y )x × FP y = Round ( x × y )где Round() означает округлениеВыполнение операцииСначала вычисляется точный результат(получается более длинная мантисса, чемзапоминаемая, иногда в два раза)Потом фиксируется исключение(например, переполнение)Потом результат округляется, чтобыпоместиться в поле frac16Умножение чисел с плавающей точкой(−1) s1 ⋅ M 1 ⋅ 2e1 × (−1) s 2 ⋅ M 2 ⋅ 2e 2Точный результат ( −1) s ⋅ MЗнак sЗначащие цифры MПорядок eПреобразованиеЕсли M ≥ 2, сдвиг M вправо с одновременнымувеличением еЕсли е не помещается в поле exp,переполнениеОкругление M, чтобы оно поместилосьв поле fracОсновные затраты на перемножение мантисс17⋅ 2es1 ∧ s2M1 × M2e1+ e2Сложение чисел с плавающей точкой(−1) s1 ⋅ M 1 ⋅ 2e1 + (−1) s 2 ⋅ M 2 ⋅ 2e 2Пусть e1 > e2Точный результат(−1) s ⋅ M ⋅ 2eЗнак s и значащиецифры M вычисляются как показанона рисункеПорядок суммы – e1ПреобразованиеЕсли M ≥ 2, сдвиг M вправо с одновременнымувеличением еЕсли M < 1, сдвиг M влево на k позицийс одновременным вычитанием k из еЕсли е не помещается в поле exp, переполнениеОкругление M, чтобы оно поместилось в поле frac18Плавающие типы языка Сиfloat, double, long doubleОперации над данными с плавающей точкой.Одноместные: изменение знака («одноместный минус»: –),одноместный плюс (+).Двухместные:сложение (+), вычитание (–), умножение (*),деление (/).Порядок выполнения арифметических операций ввыражениях (приоритет).самый низкий приоритет у двуместных + и –,более высокий приоритет у двуместных * и /,еще более высокий приоритет у одноместных + и –.В выражениях без скобок операции с более высокимприоритетом выполняются раньше.Скобки позволяют изменить порядок выполнения операций.19Пример 1.

Вычисление суммы 5 чисел типа float(мантисса – 6 десятичных цифр, порядок – 2 десятичных цифры):0.231876*1002 + 0.645391*10-03 + 0.231834*10-01 + 0.245383*10-02 +0.945722*10-03 =a) 0.231876*1002 + 0.645391*10-03 + 0.231834*10-01 + 0.245383*10-02 +0.945722*10-03 = 0.232147*1002;23.1876 + 0.000645391 = 23.188245391 = 23.1882 = 0.

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

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