Арифметические основы

Выбор системы счисления.

Возникает естественный вопрос, является ли общепринятая система счисления с основанием 10 оптимальной? Если да, то с каких позиций? Вопрос заслуживает внимания, т.к. одна из первых ВМ (ENIAC) использовала именно десятеричную систему.

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

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

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

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

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

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

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

Очевидно, что можно, не сужая области применения ЭВМ, задаться величиной некоторого самого большого числа. Пусть это будет число M. Воспользуемся позиционной системой счисления с основанием " p ", и тогда потребуется " n " разрядов, чтобы представить все M чисел:

Оборудование, которое нужно для хранения любого числа от 0 до M пропорционально произведению основания системы счисления на количество разрядов.

Таким образом, при заданном числе M количество цифроразрядов при основании " p ":

p*n = p* logpM,     (6.1)

где:

цифроразряд - эквивалент оборудования,

p*n - число устойчивых состояний элемента памяти,

n - число разрядов в числе.

Рассмотрим пример:

Пусть есть 24 цифроразряда.

1*1*...*12 = 409510
\________/
    12

2*2*...*23 = 656010
\________/
    8

3*3*...*34 = 409510
\________/
    6

5*5*5*56 = 129510
\______/
   4

7*7*78 = 51110
\____/
  3

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

Считаем " p " - величиной непрерывной. Находим производную от (6.1) по величине " p ". Берем вторую производную по " p ". Увидим, что первая производная обращается в нуль, а вторая - больше нуля при p = e. Т.е. получаем минимум при p = e.

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

Но е = 2,718...

Поэтому оптимальной является система с основанием р = 3.

Построим функцию, характеризующую отношение оборудования в системе с основанием " p " относительно системы с основанием " 2 ".

Т.е. 10-я система является более чем в 1,5 раза неэкономичной по отношению ко 2-ой системе, а 3-я система оказывается лишь на 5% экономичнее 2 й.

Действительное обоснование экономичности той или иной системы выглядит несколько сложнее.

Когда говорим об экономичности, то, прежде всего, имеем ввиду объем оборудования, сосредоточенный в АУ и ЗУ. Объем оборудования УУ не находится в столь простой зависимости от " p " да и в АУ учитывается лишь оборудование, связанное с элементами хранения информации, но не логическое оборудование.

Более детальный анализ показывает, что наиболее эффективными являются системы с основанием, кратным 2, т.е. 2, 4, 8, 16. Специфика построения схем ЭВМ показывает, что наиболее эффективной является 16-ая система. Именно она и применяется в современных машинах.

Мы же будем считать эффективной систему с основанием 2 по причине ее наибольшего распространения.

Вот основные соображения в пользу этой системы:

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

Если " p " - основание системы счисления, то максимальная цифра в одном разряде - (p-1).

Если N - максимальное число, то для его изображения требуется logpN разрядов.

Для того чтобы выполнить операцию умножения, например, потребуется (p-1)*logpN операций сложения. Если сравнить это число операций в системе с основанием " p " и отнести его к числу операций в системе с основанием " 2 ", то может получиться следующая функция:

(p-1)*logpN        p-1
     ___________       _____
f(p)=              =          
       1*log2N         log2p

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

Перевод чисел из одной системы счисления в другую.

Всякий раз, когда используется для вычислений система счисления, отличная от фактической, необходимо выполнить перевод 10 => p, p => 10.

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

Этот перевод может быть выполнен:

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

Итак, имеем дело с позиционной системой счисления с основанием " p ", с естественными весами разрядов.

В качестве промежуточной используется, естественно, десятичная система. Вначале число переводится из системы " p " в 10-ую, затем из 10-ой в систему с нужным основанием.

Мы отступим от этого правила и воспользуемся алгоритмом непосредственного перевода из системы с основанием " p " в систему с основанием " q ".

Обычно произвольное число, содержащее целую и дробную части, переводят по частям: вначале целую, затем дробную часть.

Рассмотрим перевод целых чисел:

Перевод осуществляется по следующему правилу: исходное число, записанное в системе с основанием " p " и его частные последовательно делятся на число " q ", представленное в системе " p ". Деление производится в системе с основанием " p " и продолжается до получения результата, меньшего " q ". Первый остаток, меньший " q ", дает старшую цифру числа Nq. Остатки от деления дают остальные цифры числа Nq.

Пример:

3110 => 2;   3110 = 111112

318 => 3;  318 = 2213 = 
2*32 + 2*31 + 1*30 = 18 + 6 + 1 = 2510.

318 => 10;  318 = 2510.

1111112 => 10;  1111112 = 6310.

Перевод дробных чисел из системы с основанием " p " в систему с основанием " q " выполняется по следующему правилу: исходное число Dp последовательно умножается на число " q ", записанное в системе " p ". Целые части получаемых произведений дают " p "-ые записи " q "-х цифр, начиная со старшей. Умножение производится в системе с основанием " p " до получения необходимой точности.

Пример:

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

Как мы уже знаем, в ЭВМ наибольшее применение находит система с основаниями 2, 4, 8, 16, т.е. системы которые кратны степени 2. Поэтому целесообразно рассмотреть лишь правила перевода чисел в этих системах. Аналогичные правила будут справедливы и для других систем. Допустим, что имеется некоторое целое число N8 в 8-ой системе. Оно может быть представлено в виде:

N8 = a1*8n-1 + a2*8n-2 + a3*8n-3 + ... 
   + an-2*82 + an-1*81 + an*80.

Пусть каким-либо образом мы получили запись этого числа в виде двоичного, т.е.:

N2 = b1*2k-1 + b2*2k-2 + ... 
   + bk-2*22 + bk-1*21 + bk*20.

Разделим эти выражения на 23 = 8:

a1*8n-2 + a2*8n-3 + a3*8n-4 + ... + an-1*80 + an*8-1
                                         -------
                                         дробная часть

b1*2k-4 + b2*2k-5 + ... + bk-3*20 + bk-2*2-1 + bk-1*2-2 + bk*2-3
                                 -------------------------
                                             дробная часть

Так как числа были равны, то получается одинаковые частные и одинаковые остатки:

an*8-1 = bk-2*2-1 + bk-1*2-2 + bk*2-3. (6.2)

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

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

Пример:

62,7538 = 110010,1111010112

Аналогично для 4-ой системы:

321,22334 = 111001,101011112

Аналогично для 16-ой системы:

1D876,72 = 00011101100001110110,011100102

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

Если умножить последние соотношения (6.2) на 8, то:

an*8-1*8 = (bk-2*2-1 + bk-1*2-2 + bk*2-3)*23
an = bk-2*22 + bk-1*21 + bk*20