46370 (Об “арифметических возможностях” компьютера и “компьютерных возможностях” арифметики)

Об “арифметических возможностях” компьютера и “компьютерных возможностях” арифметики

При изучении математики и информатики необходимо акцентировать внимание обучаемых на основные различия действий с числами в обычной, неограниченной (“человеческой”) и ограниченной (“машинной”) разрядной сетке, арифметике, которые часто остаются “за кадром”. Игнорирование этого может приводить к нежелательным последствиям – вплоть до абсолютизации возможностей компьютера и игнорированию адекватных описаний структур данных и операций с ними (например, проверки чётности числа x условием вида int(x/2)=x/2 и т.д.).

Множество чисел ограниченной разрядности является моделью расширенной числовой прямой, т.е. числовой прямой с тремя абстракциями (потенциальной осуществимости): нуль, положительная бесконечность, отрицательная бесконечность.

Целые числа (в математике) и их аналоги в n - разрядных арифметиках тождественны (по отражаемым им количествам) в рамках их представления в этой разрядности. При этом можно отметить основные отличия представления чисел в поле памяти человека и в поле памяти n - разрядной арифметики (компьютера):

бесконечное и счётное (нумеруемое) множество целых чисел Z представляется отрезком [—N;+N], где N - максимальное число, представимое в этой арифметике (многоточие - общее число единиц равное n): N=(111 . . . 1)₂;

бесконечное и несчётное множество действительных чисел (—¥ ;+¥ ), располагающееся на числовой оси равномерно и плотно, представляется в n-разрядной арифметике множеством с неравномерной плотностью (сгущение у нуля и сжатость со стороны меньших чисел);

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

С точки зрения обычной арифметики, например, в интервале (—1;1) имеется бесконечное множество “плотно” расположенных точек, причем в любой окрестности каждой такой точки имеется хотя бы одна точка из этого множества. Такую арифметику называют часто регулярной арифметикой.

Машинная же арифметика нерегулярна - точки интервала сгущаются около нуля. Кроме того, в этом интервале точка х “изолирована” - если взять её любую окрестность (х—а; х+а), где а - число, которое не превосходит машинного нуля (наименьшего представимого в машине числа), то в этом интервале нет других точек (отличных от х). Говоря языком теории вероятностей, плотности распределения чисел в регулярной и нерегулярной арифметике - различны, как, впрочем, плотности распределения целых и вещественных чисел в одной и той же арифметике. Множество вещественных чисел в машинной арифметике представляется как подмножество множества рациональных чисел, определяемое разрядностью арифметики.

Есть и другие особенности этих множеств (связанные, например, с выполнением операций), но указанные выше особенности - основные.

Различия в представлении чисел в обычной и в машинной (n-разрядной) арифметике ограничивают как “арифметические возможности” компьютера, так и “компьютерные возможности” арифметики, математики, использование математических методов, алгоритмов в компьютерах.

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

Так как диапазон n-разрядных чисел системы счисления с основанием p находится в пределах |(x)_p|£ pⁿ—1, то для представления дробных чисел этот диапазон ещё уменьшается, так как часть разрядов необходимо отвести под изображение мантиссы. Таким образом, имеются так называемые “зоны нечувствительности” форм представления чисел в n-разрядных арифметиках.

В 1937 году немецким учёным Конрадом Цузе (разработавшим, кстати говоря, не только ряд положений арифметических основ цифровых машин, но и прототипы ЦВМ – машины “Ц-1”, “Ц-2”) для увеличения диапазона чисел, представимых в арифметике двоичных чисел, а также для повышения точности этого представления чисел было предложено представление чисел в плавающей, нормализованной форме.

Число x представляется в нормализованном виде: x=m´ p^k, где m - мантисса числа, k - целый порядок числа, p^—1£ |m|<1.

Пусть даны два числа x=m´ p^k и y=n´ p^l (k>l). Тогда можно проверить, что результаты выполнения операций будут равны:

x+y=(m+n´ p^l—k)´ p^k ,

x—y=(m—n´ p^l—k)´ p^k ,

x´ y=(m´ n)´ p^k+l ,

x/y=(m/n)´ p^k—l ,

Если из n разрядов, отводимых под изображение чисел, m двоичных разрядов отвести под мантиссу, k - под порядок, один разряд - под знак числа и один разряд - под знак порядка (например, 0 - плюс, 1 - минус), то диапазон представимых в форме с плавающей запятой чисел резко увеличивается (m+k+2=n):

—(0.111 . . . 1)_2´ (10)₂^{+(111 . . . 1)}_2£ x£ +(0.111 . . . 1)_2´ (10)₂^{+(111 . . . 1)}₂

(многоточие соответствует k единицам).

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

Такое представление очень удобно для хранения в ЭВМ, так как на самом деле необходимо хранить не само число, а его знак, мантиссу, порядок и знак порядка и все операции с числами сводятся к операциям с этими, более “компактными”, объектами. Операции с этими объектами достаточно просты: сравнение знаков, увеличение, уменьшение порядка, сложение мантисс, нормализация, т.е. в конечном итоге сводятся к достаточно просто реализуемым операциям сдвига, выравнивания, сравнения разрядов. Это упрощает аппаратную их реализацию и является основой для различных архитектур – микропрограммных, RISC и др.

Пример. В 16-разрядной арифметике двоичных чисел можно представить диапазон целых чисел х: 1—2¹⁵15—1 (старший разряд отвели под знак числа). Если в этой арифметике (не меняя её разрядность) отвести 7 разрядов под мантиссу, а 7 разрядов - под порядок, то уже представим диапазон чисел: —127´ 2¹²⁷127 (два разряда - под знак числа и знак порядка; несколько упрощена и общая картина представления - для наглядности).

К “неудобствам” этой формы представления чисел можно отнести возможность возникновения следующих “особо опасных” ситуаций:

а) если число достаточно мало, например, а=0.12Е+00, то оно может быть представлено любым числом из наименьшего интервала включающего а, в частности, числом 0.120000001 или 0.199999999 и в этом случае сравнивать на равенство “в лоб” нельзя (вещественные числа в форме с плавающей запятой на совпадение опасно сравнивать);

б) порядок выполнения операций может влиять на результат, например, в 4-разрядной арифметике с фиксированной запятой 20.0000+0.0001=20.0001, но при этом 0.2000Е+02+0.1000Е-05=0.2000Е+02;

в) может возникнуть так называемая ситуация “переполнения порядка” при сложении (умножении) “очень больших чисел” или “исчезновения порядка” при сложении (умножении) “очень малых чисел”, например, результат 0.6000Е+39´ 0.1200Е+64 равен 0.9999Е+99 (или не определен) и результат 0.6000Е—35´ 0.0200Е—65 равен 0.9999Е—99 (или не определен) при соответствующим образом определенной разрядности десятичной арифметики;

г) при сложении чисел с плавающей запятой (а в конечном счёте, все операции выполняются, как известно, через сложение, точнее, - через поразрядное сравнение и сдвиги) происходит выравнивание порядков для последующего сложения мантисс, а при выравнивании степеней может происходить потеря (усечение) младших разрядов, например, такая ситуация может возникнуть при сложении одного “очень большого числа” с одним “очень малым числом” (почему?).

Реализация операций в арифметике с плавающей запятой требует необходимости выравнивания порядков при сложении и вычитании и нормализации результатов. Если диапазоны чисел, представимых в арифметике с фиксированной запятой и с плавающей запятой, соизмеримы, то числа с фиксированной запятой могут более точно представлять (кодировать) величины, так как свободны от часто необходимой для чисел с плавающей запятой операции округления. При машинной реализации такая операция обычно выполняется в устройстве-предшественнике (например, сумматор) с высокой точностью (большой разрядностью), а затем отсылается в устройство-преемник (например, регистр) с учётом заданной (например, декларированной в описаниях типов и структур данных) точности или с сохранением всех значащих разрядов. Таким образом, копирование непосредственного результата операции происходит либо с помощью операции округления, либо с помощью операции усечения.

Эти две основные операции (кроме арифметических операций) вводятся следующим образом:

усечение, отбрасывание цифр числа до определённого разряда, например, до ближайшего, меньшего целого числа и т.п.;

округление, усечение с коррекцией числа по определённым правилам, например, до числа кратного заданному числу, до ближайшего целого и т.п.

Пример. Операция взятия целой части числа x (функция Антье - [x] или int(x)) - операция усечения, [2.65]=2, [—1.999]=—2. Операция взятия целой части числа x+0.5 вместо значения числа х есть округление {x} до ближайшего целого, {1.05}={0.91}=1, {2.61}=[2.6+0.5]=3.

Задачи и упражнения

Задайте 20 - ую систему счисления и выполните операции над числами в этой системе.

В саду 1000 деревьев - 140 яблонь и 420 груши. В какой системе счисления посчитаны эти деревья? Найдите общее число деревьев в саду в шестнадцатеричной системе.

Имеются ящики: 4 черных, 3 красных, 2 желтых и 1 зеленый (ящики посчитаны в десятичной системе). В каждом черном ящике - (21)_p шара, красном - (23)_p шара, жёлтом - (23)_p шара, зелёном - (111)_p шара. Определить основание p системы счисления, в которой были посчитаны шары, если всего было (244)_p шаров. Чему равно общее число шаров в восьмеричной системе?

Число х=(176)_p (рассматриваемая в системе счисления с основанием р, 1<р<20) делится нацело на 7. Найти р (не перебирая все указанные р). Вычислить х в восьмеричной системе.

Найти основание системы р (в которой было выполнено сложение) и неизвестные цифры (обозначены *), если 24**1+*235*=116678.

Какова разрядность двоичной системы счисления, в которой представим лишь диапазон чисел из интервала (—255; 255)?

Найти числа, соответствующие понятиям “нуль” и “бесконечность” в 10-разрядной десятичной системе счисления и сравнить их. Указать эти числа для двоичной, восьмеричной и шестнадцатеричной систем.

Сформулировать какие-то признаки делимости на 8 (на 11) числа x записанного в системе счисления с основанием p=12, не переводя эти числа в десятичную систему. Рассмотреть другое значение р.

Найти число х, записанное в системе счисления с основанием р, если оно совпадает со своим дополнительным кодом. При каких р это возможно?

Найти все ошибки в следующих утверждениях и объяснить все причины их появления:

а) 1111111111=2¹⁰ —1,

б) 7777777777=7´ 1111111111=7´ (2¹⁰—1),

в) 7777777777=8¹⁰—1,

г) из б) и в) следует, что 7´ 2¹⁰— 6=8¹⁰ или 2³⁰=7168 (!).

Запишите числа 0, 42, 1000, 1, -25, -100 в формате целых чисел в шестнадцатеричную ячейку памяти, изобразив ее схематически.

Запишите числа 99, 12.5, 0.025, -4.18, -0.01 в формате вещественных чисел с фиксированной запятой (ячейка памяти- 16-разрядна, разряды 1-8 отводятся под целую часть, разряды 9-15 - под мантиссу, 0 - знак). Оцените погрешность такого представления чисел.

Какое максимально положительное и минимально отрицательное число можно записать в указанную для задачи 12 ячейку памяти?

Запишите числа 99, 9999, 12.7, 0.005, -64.5, -0.002, 0 в формате чисел с плавающей запятой в ячейку памяти разрядности 16 (нулевой разряд - знак числа, первый разряд - знак порядка, 2-12 разряды - мантисса, 13-15 разряды - порядок). Оцените погрешность такого представления чисел.

Какое максимально положительное и минимально отрицательное число можно записать в ячейку памяти, указанную в задаче 14?

Какой минимальной разрядности должна быть ячейка памяти у условной трехадресной ЭВМ с однородной памятью, если она имеет набор из 50 различных команд и 2 мегабайта адресуемой памяти, а адресуется каждый байт.

Список литературы

Для подготовки данной работы были использованы материалы с сайта http://www.kaziev.by.ru/