ГЛАВА I. МАТЕМАТИЧЕСКИЕ ОСОБЕННОСТИ МАШИННОЙ АРИФМЕТИКИ

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

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

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

§ 1. Позиционные системы счисления

Общий эффект от решения задачи и даже возможность ее решения во многом определяется тем, как в действительности выполняются операции над числами. А это

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

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

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

Несмотря на кажущуюся простоту, такая система явилась продуктом длительного исторического развития. Известный французский математик и физик Лаплас писал: «Мысль выражать все числа девятью знаками, придавая им, кроме значения по форме, еще значение по месту, настолько проста, что именно из-за этой простоты трудно понять, насколько она удивительна. Как нелегко прийти к этой методике, мы видим на примере величайших гениев греческой учености Архимеда и Аполлония, от которых эта мысль осталась скрытой».

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

Зафиксируем некоторое целое положительное число и целые числа Пусть любое неотрицательное число может быть представлено в виде ряда

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

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

В литературе, связанной с вычислительной математикой, слово «позиция» чаще всего заменяется словом «разряд». Нумерация разрядов устанавливается в убывающем порядке подряд слева направо, причем первый разряд слева от запятой имеет нулевой номер. Различаются разряды числа до запятой и разряды после запятой. Число называется основанием системы счисления, числа базисными. Если используется система счисления с основанием то правую часть (1.2) называют р-ичной дробью. Дробь называется бесконечной, если в ее записи (1.2) имеется бесконечно много ненулевых коэффициентов, и конечной в противном случае. Обычно в записи дроби (1.2) опускаются все первые и последние нулевые коэффициенты. Опускается и запятая, если все коэффициенты после нее являются нулевыми.

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

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

Теорема 1.1. Если базисные числа образуют совокупность любое вещественное число может быть представлено в виде р-ичной дроби (1.2).

Доказательство. Покажем, что любое число может быть представлено в виде ряда (1.1). Очевидно, что достаточно рассмотреть лишь положительные числа

Существует целое число такое, что выполняются соотношения

Из совокупности выбираем наибольшее число для которого

Если

то ряд (1.1) получен. Предположим поэтому, что

Находим далее целое число такое, что

и затем из совокупности выбираем число для которого

В силу соотношений (1.4) заключаем, что Если

то получение ряда (1.1) закончено. Поэтому снова рассматриваем случай

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

либо для всех

В силу полноты пространства вещественных чисел, соотношения (1.5), (1.6) означают, что

Числа образуют последовательность ненулевых коэффициентов искомой р-ичной дроби.

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

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

УПРАЖНЕНИЯ

Всюду предполагается, что в качестве базисных взяты числа

1. Написать р-ичную дробь числа

2. Составить таблицы умножения и сложения для двоичной системы счисления.

3. Как по р-ичной дроби числа найти его -ичную дробь, где целое положительное число?

4. Будет ли дробь, конечная в системе счисления с одним основанием, конечной во всех других системах?

5. Какие из рациональных чисел могут быть точно представлены конечными р-ичными дробями?

6. Какую часть числа изображают разряды, стоящие слева (справа) от запятой?

7. Указать какой-нибудь алгорифм выполнения операции деления конечных р-ичных дробей.

8. Какой смысл можно приписать выражению Для какого вначение этого выражения минимально?