8.5. Упражнения

1. Как представлен на вашем компьютере указатель? Как представлен на вашем компьютере указатель null?

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

3. Покажите, как можно применить «часовых», чтобы сделать поиск в спи­ске более эффективным.

4. Почему не была использована операция адресации для фактического па­раметра, являющегося указателем на функцию:

C

float х = integrate(&fun, 1.0, 2.0);

5. Покажите, как можно использовать повисшие ссылки, чтобы разрушить систему типов.

6. Изучите в Ada 95 определение доступности (accessibility) и покажите, как правила предотвращают возникновение повисших ссылок.

7. Напишите программу обработки динамической структуры данных, на­пример связанного списка. Измените программу, чтобы использовать кэш узлов.

8. Изучите документацию вашего компилятора; с помощью каких алгорит­мов исполняющая система распределяет динамическую память? Есть ли какие-либо издержки по памяти при выделении динамической памяти, т. е. выделяются ли лишние слова кроме тех, которые вы запросили? Ес­ли да, то сколько?

9. Если у вас есть доступ к компьютеру, который использует виртуальную память, посмотрите, как долго можно продолжать запрашивать память. При нарушении каких пределов выделение памяти прекращается?

Глава 9

Вещественные числа

9.1. Представление вещественных чисел

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

операций при машинных вычислениях не гарантируются.

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

Прежде всего обратим внимание на то, что десятичные числа не всегда можно точно представить в двоичной нотации. Например, нельзя точно пред-ставить в виде двоичного числа 0.2 (одну пятую), а только как периодическую I двоичную дробь:

0.0011001100110011..

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

• Представлять непосредственно десятичные числа, например, каждому десятичному символу ставить в соответствие четыре бита. Такое пред­ставление называется двоично-кодированным десятичным числом (BCD — binary-coded decimal).

• Хранить двоичные числа и принять как факт то, что некоторая потеря точности иногда может случаться.

Представление BCD приводит к некоторому перерасходу памяти, потому что с помощью четырех битов можно представить 16 разных значений, а не 10, необходимых для представления десятичных чисел. Более существенный не-достаток состоит в том, что это представление не «естественно», и вычисление с BCD выполняется намного медленнее, чем с двоичными числами. Таким образом, мы ограничимся обсуждением двоичных представлений; читателя, интересующегося вычислениями с BCD, можно отослать к таким языкам, как Cobol, которые поддерживают числа BCD.

Числа с фиксированной точкой

Для простоты последующее обсуждение будет вестись в терминах десятичных чисел, но оно справедливо и для двоичных. Предположим, что мы можем представить в 32-разрядном слове памяти семь цифр: пять до и две после де­сятичной точки:

12345.67, -1234.56, 0.12

Такое представление называется представлением с фиксированной точкой. Преимущество чисел с фиксированной точкой состоит в том, что количество знаков после запятой, которое определяет абсолютную ошибку, фиксировано. Если перечисленные выше числа обозначают доллары и центы, то любая ошибка, вызванная ограниченным размером слова памяти, не превышает од­ного цента. Недостаток же состоит в том, что точность представления, то есть относительная ошибка, которая определяется числом значащих цифр, являет­ся переменной. Первое число использует все семь цифр представления, име­ющихся в распоряжении, тогда как последнее число использует только две цифры. Хуже то, что переменная точность представления означает, что мно­гие важные числа, такие как сумма $1532 854.07, которую вы выиграли в лоте­рее, или размер $0.00572 вашего подоходного налога, вообще никак нельзя представить.

Числа с фиксированной точкой используются в приложениях, где сущест­венна абсолютная ошибка в конечном результате. Например, бюджетные вы­числения обычно делаются с фиксированной точкой, так как требуемая точ­ность представления известна заранее (скажем, 12 или 16 цифр), а бюджет должен быть сбалансирован до последнего цента. Числа с фиксированной точкой также используются в системах управления, где для взаимодействия датчиков и силовых приводов с компьютером используются слова или поля фиксированной длины. Например, скорость можно представить 10-битовым полем с диапазоном значений от 0 до 102.3 км/час; один бит будет представ­лять 0.1 км/час.

Числа с плавающей точкой

Ученые, которым приходится иметь дело с широким диапазоном чисел, часто используют так называемую научную нотацию

123.45 х 10³, 1.2345 х 10⁸, -0.00012345 х 10⁷ 12345000.0 х 10⁴

Как можно использовать эту нотацию на компьютере? Сначала обратите вни­мание на то, что здесь присутствуют три элемента информации, которые дол­жны быть представлены: знак, мантисса (123.45 в первом числе) и экспонента.

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

Однако, как можно заметить, конечные нулевые цифры мантиссы, боль­шей 1.0 (и ведущие нулевые цифры мантиссы, меньшей 1.0), можно отбро­сить, если изменить значение (не точность!) экспоненты. Другими словами, мантиссу можно неоднократно умножать или делить на 10 до тех пор, пока она находится в форме, которая использует максимальную точность пред­ставления; при каждой такой операции экспонента будет уменьшаться или увеличиваться на 1 соответственно. Например, последние два числа можно записать с помощью мантиссы из пяти цифр:

-0.12345 х10⁴ 0.12345 х10¹²

Для вычислений на компьютере удобно, когда числа представляются в такой

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

В чем основной недостаток вычислений, использующих числа с плаваю­щей точкой? Рассмотрим число 0.12345 х 10'°, которое является нормализо­ванной формой с плавающей точкой для числа

1 234 500 000

и предположим, что таким образом банк представил ваш депозит в размере

$1 234 567 890

Управляющий банком был бы горд тем, что относительная ошибка:

67 890

1 234 567 890

является очень малой долей процента, но вы оправданно потребовали бы ва­ши $67 890, которые составляют абсолютную ошибку.

Однако в научных вычислениях относительная ошибка намного важнее абсолютной погрешности. В программе, которая контролирует скорость ра-кеты, требование может состоять в том, чтобы ошибка не превышала 0,5%, Хотя это составляет несколько километров в час во время запуска, и несколь-ко сотен километров в час при приближении к орбите. Вычисления с плаваю­щей точкой используются гораздо чаще, чем с фиксированной точкой, пото-му что относительная точность требуется намного чаще, чем абсолютная. По Этой причине в большинстве компьютеров есть аппаратные средства, которые Непосредственно реализуют вычисления с плавающей точкой.

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

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

-0.101100111 х2¹⁵

При типичной реализации на 32-разрядном компьютере 1 бит выделяется для знака, 23 бита — для мантиссы и 8 битов — для экспоненты. Поскольку для хранения одной десятичной цифры требуется Iog₂ 10 = 3.3 бита, то точность представления составит 23/3.3 = 7 цифр. Если необходима большая точность, то с помощью 64-разрядного двойного слова с 52-разрядной мантиссой мож­но получить приблизительно 15 цифр точности представления.

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

Экспонента со знаком представляется со смещением так, чтобы пред­ставление было всегда положительным, и помещается в старшие разряды сло­ва после знакового бита. Это позволяет упростить сравнения, потому что можно воспользоваться обычными целочисленными сравнениямии не выде­лять специально поля экспоненты со знаком. Например, 8-разрядное поле экспоненты со значениями в диапазоне 0 .. 255 представляет экспоненты в ди­апазоне -127 .. 128 со смещением 127.

Мы можем теперь расшифровать битовую строку как число с плавающей точкой. Строка

1 1000 1000 0110 0000 0000 0000 0000 000

расшифровывается следующим образом.

• Знаковый бит равен 1, поэтому число отрицательное.

• Представление экспоненты равно 1000 1000 = 128 + 8 = 136. Удаление смещения дает

136-127 = 9

• Мантисса равна 0.10110 ... (обратите внимание, что восстановлен скры­тый бит), т. е.

1/2+1/8+.1/16 = 11/16

• Таким образом, хранимое число равно 2⁹ х 11/16 = 352.

Как и для целых чисел, для чисел с плавающей точкой переполнение (over­flow) происходит, когда результат вычисления слишком большой:

(0.5x2™) • (0.5 х 2⁸⁰) = 0.25 х 2¹⁵⁰

Так как самая большая экспонента, которая может быть представлена, равна 128, происходит переполнение. Рассмотрим теперь вычисление:

(0.5 х2^-70) • (0.5 х 2^-80) = 0.25 х 2^-150

Говорят, что при вычислении происходит потеря значимости (underflow), ког­да результат слишком мал, чтобы его можно было представить. Вы можете воскликнуть, что такое число настолько мало, что его можно принять равным нулю, и компьютер может интерпретировать потерю значимости именно так, но на самом деле потеря значимости часто говорит об ошибке, которая требу­ет обработки или объяснения.