§ 1.3. Системы символьных вычислении

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

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

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

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

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

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

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

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

Позиционное представление числа по основанию запись

Целые числа представляют собой «цифры» предстг вления числа по основанию b. В компьютере числу отвечает список, каждый элемент которого содержит цифру пре; ставления числа по основанию Напомним, что цифры — это целые числа с простой точностью, и поэтому компьюте

умеет обращаться с ними. Число элементов списка зависит от величины

Разумеется, мы хотим не просто представлять большие целые числа в компьютере, а еще и оперировать с ними. Сложение чисел в системе счисления с основанием 6 можно выполнять точно так же, как и сложение в десятичной системе. Нужно позаботиться только о переносе в следующий разряд.

Пусть мы хотим сложить два положительных целых числа

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

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

Более того, если это число больше 6, то вновь появится цифра переноса 1, которую нужно учитывать при подсчете цифры Процесс продолжается до тех пор, пока не исчерпаются все цифры по основанию b у обоих слагаемых.

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

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

В этих комментариях чрезвычайно важная и быстро развивающаяся область взаимодействия между программированием и математикой лишь затронута. Фундаментальное описание методов вычислений с большими числами см. в [28] (на русском языке это можно посмотреть в книге . Более краткое изложение, содержащее, однако, подробное обсуждение представления целых чисел в виде списков, можно найти в [2] ([Д.1]).