1.2 Компьютерная алгебра: точная целочисленная и полиномиальная арифметики

Как отмечалось выше, для того чтобы иметь возможность представлять целые числа произвольной точности и выполнять точные арифметические операции, нам необходимо ввести (если их еще нет) соответствующие структуры данных (или воспользоваться модулярной арифметикой, как мы увидим в гл. 2) и избегать чисел с плавающей точкой; это и делается в компьютерной алгебре. В этом разделе мы вводим вычислительную модель для целочисленного и полиномиального представлений и анализируем некоторые алгоритмы «с карандашом и бумагой» выполнения над ними арифметических операций. Очевидно, что для представления целых чисел и полиномов можно пользоваться массивами, но они не являются «динамическими» структурами данных; мы будем обсуждать только их представление в виде списков (Horowitz et al., 1976).

Списки и базисные операции над списками.

Прежде всего рекурсивно определим список над произвольным множеством S как конечную последовательность , в которой каждый элемент является либо элементом множества S, либо списком над S; пустой список представляется символом и соответствует . Когда мы пишем мы интерпретируем это двояко: (1) а рассматривается как указатель на начало списка и (2) а представляет весь список, так что, когда мы пишем где — одна из бинарных операций над скалярами, мы имеем в виду, что операция должна быть произведена над

каждым элементом списка а и скаляром контекста всегда будет ясно, что в данный момент имеется в виду.)

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