Списочное представление целых чисел.

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

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

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

разрядов; однако при изучении деления длинных целых чисел наиболее значимая -цифра будет в начале списка. Знак , зависит от того будет или т.е. знак числа i «хранится» только в

Например, предположим, что т.е. компьютерное слово может содержать только три десятичные цифры, и что нам нужно запомнить число Мы можем разместить его в памяти, как показано на рис. 1.2.1.

Рис. 1.2.1. Внутреннее представление целого числа в компьютере, слово которого может содержать только три десятичные цифры.

Стрелки на рис. 1.2.1 указывают, что звенья, или ячейки (состоящие из одного или нескольких машинных слов) ссылаются на следующие. Ко всей структуре адресуются с помощью переменной . Аналогично, рациональное число представляется списком , где и d - целые числа и d, представленные списками.