Системы счисления и действия в них

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

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

Несомненные остатки двенадцатеричной системы счисления имеются у англичан: и в системе мер (например, 1 фут=12 дюймам) и в денежной системе (1 шиллинг=12 пенсам)

С математической точки зрения, двенадцатеричная система имеет некоторые преимущества, по сравнению с десятичной, поскольку число 12 делится на 2, 3, 4 и 6, а число 10 только на 2 и 5. Больший запас делителей у числа, служащего основанием системы счисления, создает известные удобства в ее использовании.

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

Все вычисления в цифровых вычислительных машинах производятся над конечными числами и с ограниченной точностью, определяемой разрядностью представления дискретных чисел. Цифровая информация, как правило, представляется при помощи электрических процессов, для которых характерны два состояния (например, включено/выключено, высокий/низкий уровень сигнала, ток есть/тока нет). Каждое такое состояние указывает на равенство значения двоичной переменной нулю или единице.

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

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

Для оценки пригодности той или иной системы счисления в качестве основы для конструирования вычислительной машины имеет значение простота осуществления арифметических операций в ней.

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

сложить 2 числа;

проверить, не является ли число нулем;

скопировать фрагмент данных из одной части памяти компьютера в другую;

операция умножения чисел выполняется комбинацией операций сложения и сдвига (аналогично привычному умножению «в столбик»).

Такие примитивные команды в совокупности составляют язык, на котором люди могут общаться с компьютером. Такой язык называется машинным языком (или языком низкого уровня). Разработчик при создании нового компьютера должен решать, какие команды включить в машинный язык этого компьютера. Это зависит от назначения компьютера, от того, какие задачи он должен выполнять. Обычно стараются сделать машинные команды как можно проще, чтобы избежать сложностей при конструировании компьютера и снизить затраты на необходимую электронику. Так как большинство машинных языков очень примитивны, использовать их трудно и утомительно.

Алфавит Х из р символов и правила записи (изображения) и обработки чисел с помощью символов этого алфавита называются системой счисления (нумерацией) с основанием р. Число х в системе с основанием р обозначается как (х)_р или х_р.

Любая система счисления – это система кодирования числовых величин (количеств), позволяющая выполнять операции кодирования и декодирования, то есть по любой количественной величине однозначно находить его кодовое представление и по любой кодовой записи – восстанавливать соответствующую ей числовую величину.

Все системы счисления строятся по общему принципу: определяется величина р – основание системы, а любое число х записывается в виде комбинации степеней веса р от 0-й до n-й степени следующим образом:

(x)10 = x_npⁿ + x_n–1p^n–1 +... + x₁p¹ + x₀p⁰ .

Наиболее используемые в информатике системы счисления, кроме, естественно, десятичной, – это: 1) двоичная, над алфавитом Х = {0,1}; 2) восьмеричная, над Х = {0, 1, 2, 3, 4, 5, 6, 7}; 3) шестнадцатеричная, над Х = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, А, В, С, D, Е, F}, где символы А, В, С, D, Е, F имеют, соответственно, десятичные веса 10, 11, 12, 13, 14, 15.

Пример. 11012 = 1 * 2³ + 1 * 2² + 0 * 2¹ + 1 * 2⁰ = 8 + 4 + 1 = 1310,

1578 = 1 * 8² + 5 * 8¹ + 7 * 8⁰ = 64 + 40 + 7 = 11110,

A6F16 = 10 * 256 + 6 * 16 + 15 * 1 = 267110.

В большинстве систем счисления вес цифры (или символа алфавита) зависит от ее места в записи числа или слова. Такая система счисления называется позиционной; в противном случае система называется непозиционной.

Пример. Непозиционная система – древняя римская система записи чисел с алфавитом вида Х={I (1), V (5), Х (10), L (50), С (100), D (500), М (1000)}, где в скобках указаны веса символов (не зависящие от позиции символа). Примеры римских чисел (в скобках – обычные десятичные эквиваленты): III (3), IV (4), V (5), VI (6), IX (9), XI (11), DCL (650). Запись числа в этой системе получается двусторонней конкатенацией, причем правая конкатенация ассоциируется с добавлением, а левая конкатенация – с убавлением (например, IV и VI). Поразрядное же выполнение арифметических операций не имеет места (например, XIV + IV не равно XVIII).

Для изображения десятичных дробей используется подобная формула разложения по степеням основания.

Пример. 110,0012 = 1*2² + 1 * 2¹ + 0 * 2⁰ + 0 * 2^-1 + 0 * 2^-2 + 1 * 2^-3 = 6,12510;

A,B16 = A * 16⁰ + B * 16^-1 = 10 * 1 + 11 * 0,0625 = 10,687510.

Процедура перевода десятичных чисел в р-ную систему счисления:

перевести отдельно целую часть числа х, для чего последовательно делить сперва целую часть [х]₁₀, а затем все частные (получаемые при делении) на р до тех пор, пока не получим в очередном частном число меньшее р; изображение [х]_p получается последовательным приписыванием к последнему частному остатков от деления – от последнего до первого;

перевести отдельно дробную часть (мантиссу) числа, то есть {x}₁₀, для чего последовательно умножать сперва исходную мантиссу, а затем мантиссы получаемых чисел на р до тех пор, пока не получим мантиссу, равную нулю, или нужное количество цифр в {х}_p; изображение {х}_p получается приписыванием к целой части первого произведения второй такой же цифры и т.д., до последней цифры целой части;

результат будет иметь вид (х)_р = [х]_p, {х}_p.

Пример. Найти: 12,810 =?2. Решение:

Переводим целую часть: 12₁₀ =11002;

переводим дробную часть: 0,8 *x 2 = 1,6; 0,6 *x 2 = 1,2; 0,2 *x 2 = 0,4; 0,4 *x 2 = 0,8; 0,810 = 0,1100110...2;

результат перевода: 12,810 = 1100,1100110011...2.

Пример. Найдем 29,2510 =?8. Решение имеет вид 1) 2910 = 358; 2) 0,2510 = 0,28; 3) 29,2510 = 35,28.

Пример. Найдем 79,2610 =?16. Решение: 1) 7910 = 4F16; 2) 0,2610 = 0,4016; 3) 79,2610 = 4F,416. При переводе дробной части мы ограничились нахождением двух значащих цифр после запятой, ибо перевод точно сделать невозможно.

Для перевода из 2-ной в 8-ную и наоборот, из 2-ной в 16-ную и наоборот, из 8-ной в 16-ную и обратно, используется таблица следующего вида:

ОСНОВАНИЕ СИСТЕМЫ
				16(0-F)
	—
	—
	—
	—
	—
	—
	—	—
	—	—
	—	—		A
	—	—		B
	—	—		C
	—	—		D
	—	—		E
	—	—		F

При переводе в 8-ную систему или из нее необходимо группировать в тройки биты, а при переводе в 16-ную или из нее – группировать их в четверки битов. Можно добавлять, если нужно, незначащие нули (слева от целой части и справа от мантиссы) или отбрасывать их.

Пример. Рассмотрим переводы в смешанных системах.

Из 2-ной системы в 8-ную (двоично-восьмеричное изображение):

 

из 8-ной системы в 2–ную (восьмерично-двоичное изображение):

 

из 2-ной системы в 16-ную (двоично-шестнадцатеричное изображение):

 

из 16-ной системы в 2-ную (шестнадцатерично-двоичное изображение):

 

Сложение в двоичной системе счисления осуществляется по правилам

0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, 1 + 1 = 2₁₀ = 10₂ (единица идет в старший разряд).

Таблица вычитания в двоичной системе счисления имеет вид

0 – 0 = 0, 1 – 0 = 1, 1 – 1 = 0, 0 – 1 = 10 – 1 = 1 (единицу забираем у старшего разряда).

Таблица умножения в двоичной системе счисления имеет вид

0 * 0 = 0, 0 * 1 = 0, 1 * 0 = 0, 1 * 1 = 1.

Таблица деления в двоичной системе счисления имеет вид

0: 0 = не определено, 1: 0 = не определено, 0: 1 = 0, 1: 1 = 1.

Обратным кодом числа в системе с основанием р называется число в этой системе, получаемое заменой цифры, символа в каждом разряде числа на его дополнение до максимальной цифры в системе (то есть до р – 1).

Дополнительный код = обратный код + единица в младшем разряде.

Пример.

10011 двоичное число,

01100 обратный код этого двоичного числа,

01101 дополнительный код этого двоичного числа;

457 восьмеричное число,

321 дополнительный код;

А9 шестнадцатеричное число,

57 дополнительный код.

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

Пример. Выполним вычитание напрямую и через сложение (через дополнительный код):

Числа конечной точности.

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

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

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

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

Все вычисления в цифровых вычислительных машинах производятся над конечными числами и с ограниченной точностью, определяемой разрядностью представления дискретных чисел. Цифровая информация, как правило, представляется при помощи электрических процессов, для которых характерны два состояния (например, включено/выключено, высокий/низкий уровень сигнала, ток есть/тока нет). Каждое такое состояние указывает на равенство значения двоичной переменной нулю или единице.

Арифметика, применяемая в компьютерах, отличается от арифметики, которая используется людьми:

компьютеры выполняют операции над числами, точность которых конечна и фиксирована;

в большинстве компьютеров используется не десятичная, а двоичная система счисления.

Когда люди выполняют какие-либо арифметические действия, их не волнует вопрос, сколько десятичных разрядов занимает то или иное число. Физики, к примеру, могут вычислить, что во Вселенной присутствует 10⁷⁸ электронов, и их не волнует тот факт, что полная запись этого числа потребует 79 десятичных разрядов. Никогда не возникает проблемы нехватки бумаги для записи числа.

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

Для примера, рассмотрим ряд положительных целых чисел, которые можно записать тремя десятичными разрядами без десятичной запятой и без знака. В этот ряд входит ровно 1000 чисел: 000,001, 002, 003,..., 999. При таком ограничении невозможно выразить определенные типы чисел:

1. Числа больше 999.

2. Отрицательные числа.

3. Дроби.

4. Иррациональные числа.

5. Комплексные числа.

Одно из свойств набора всех целых чисел — замкнутость по отношению к операциям сложения, вычитания и умножения. Другими словами, для каждой пары целых чисел i и j числа i+j, i-j и i×j — тоже целые числа. Ряд целых чисел не замкнут относительно деления, поскольку существуют такие значения i и j, для которых i/j не выражается в виде целого числа (например, 7/2 или 1/0).

Числа конечной точности не замкнуты относительно всех четырех операций. Рассмотрим операции над трехразрядными десятичными числами:

600+600=1200 (слишком большое число);

003-005=-2 (отрицательное число);

050×050=2500 (слишком большое число);

007/002=3,5 (не целое число).

Отклонения можно разделить на два класса:

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

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

Из четырех примеров, приведенных выше, первые три относятся к первому классу, а четвертый — ко второму классу.

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

Алгебра чисел конечной точности отличается от обычной алгебры. В качестве примера рассмотрим ассоциативный закон арифметики: a+(b-c)=(a+b)-c. Вычислим обе части выражения для а =700, b =400 и с =300. В левой части сначала вычислим значение (b-с). Оно равно 100. Затем прибавим это число к а и получим 800.

Чтобы вычислить правую часть, сначала вычислим (a+b). Для трехразрядных целых чисел получится переполнение. Результат будет зависеть от компьютера, но он не будет равен 1100. Вычитание 300 из какого-то числа, отличного от 1100, не даст результата 800. Ассоциативный закон не имеет силы. Таким образом, приходим к выводу, что важен порядок записи арифметической операций.

Аналогично можно рассмотреть другой закон — дистрибутивный:
а×(b-c)=a×b-a×c, для а = 5, b = 210 и с =195. В левой части 5 × 1 × 5=75. В правой части 75 не получится, поскольку a×b выходит за пределы ряда.

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

С точки зрения обычной арифметики, например, в интервале (–1; 1) имеется бесконечное множество "плотно" расположенных точек, причем в любой окрестности каждой такой точки имеется хотя бы одна точка из этого множества. Такую арифметику называют часто регулярной арифметикой. Машинная же арифметика имеет следующие особенности. Она нерегулярна – точки интервала сгущаются около нуля; кроме того, в этом интервале точка х "изолирована" – если взять любую ее окрестность (х – а; х + а), где а – число, которое не превосходит машинного нуля (наименьшего представимого в машине числа), то в этом интервале нет других точек (отличных от х). Говоря языком теории вероятности, плотности распределения чисел в регулярной и нерегулярной арифметике – различны, как, впрочем, плотности распределения целых и вещественных чисел в одной и той же арифметике. Множество вещественных чисел в машинной арифметике представляется как подмножество (определяемое разрядностью арифметики) множества рациональных чисел. Есть и другие особенности этих множеств (связанные, например, с выполнением операций), но указанные выше особенности – основные.

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

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

Так как диапазон n-разрядных чисел системы счисления с основанием p находится в пределах , то для представления дробных чисел этот диапазон еще снижается, поскольку часть разрядов необходимо отвести под изображение мантиссы. Таким образом, имеются так называемые "зоны нечувствительности" форм представления чисел в n-разрядных арифметиках.

В 1937 году Конрадом Цузе для увеличения диапазона чисел, представимых в арифметике двоичных чисел, а также для повышения точности этого представления чисел было предложено представление чисел в плавающей, нормализованной форме – число x представляется в виде: , где m – мантисса числа, k – целый порядок числа,

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

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

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

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

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

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

при умножении чисел возможно образование порядка числа, превосходящего максимально возможный – переполнение.