домножим P на множитель целости (integerizing factor) c1+Ql-°2, то получившийся многочлен можно будет поделить на Q алгоритмом div-terms, получив результат, в котором не будет никаких дробей. Операция домножения делимого на такую константу, а затем деления, иногда называется псевдоделением (pseudodivision) P на Q. Остаток такого деления называется псевдоостатком (pseudoremainder).

Упражнение 2.96.

a.Напишите процедуру pseudoremainder-terms, которая работает в точности как remainder-terms, но только прежде, чем позвать div-terms, домножает делимое на множитель целости, описанный выше. Модифицируйте gcd-terms так, чтобы она использовала pseudoremainder-terms, и убедитесь, что теперь в примере из упражнения 2.95 greatest-common-divisor выдает ответ с целыми коэффициентами.

b.Теперь у НОД целые коэффициенты, но они больше, чем коэффициенты P1. Измените gcd-terms, чтобы она убирала общий множитель из коэффициентов ответа путем деления всех коэффициентов на их (целочисленный) НОД.

Итак, вот как привести рациональную функцию к наименьшему знаменателю:

•Вычислите НОД числителя и знаменателя, используя версию gcd-terms из упражнения 2.96.

•Когда Вы получаете НОД, домножьте числитель и знаменатель на множитель целости, прежде чем делить на НОД, чтобы при делении не получить дробных коэффициентов. В качестве множителя можно использовать старший коэффициент НОД, возведенный в степень 1 + O1 - O2, где O2 - порядок НОД, а O1 - максимум из порядков числителя и знаменателя. Так Вы добьетесь того, чтобы деление числителя и знаменателя на НОД не привносило дробей.

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

Упражнение 2.97.

a.Реализуйте этот алгоритм как процедуру reduce-terms, которая принимает в качестве аргументов два списка термов n и d и возвращает список из nn и dd, которые представляют собой n и d, приведенные к наименьшему знаменателю по вышеописанному алгоритму. Напишите, кроме того, процедуру reduce-poly, подобную add-poly, которая проверяет, чтобы два poly имели одну и ту же переменную. Если это так, reduce-poly откусывает эту переменную и передает оставшуюся часть задачи в reduce-terms, а затем прикрепляет переменную обратно к двум спискам термов, которые получены из reduce-terms.

b.Определите процедуру, аналогичную reduce-terms, которая делает то, что делала для целых чисел исходная make-rat:

(define (reduce-integers n d)

(let ((g (gcd n d)))

(list (/ n g) (/ d g))))

и определите reduce как обобщенную операцию, которая вызывает apply-generic и диспетчирует либо к reduce-poly (если аргументы - многочлены), либо к reduce-integers (для аргументов типа scheme-number). Теперь Вы легко можете заставить

62Изящный и чрезвычайно эффективный метод вычисления НОД многочленов был открыт Ричардом Зиппелем (Zippel 1979). Этот метод - вероятностный алгоритм, подобно быстрому тесту на простоту числа, описанному в главе 1. Книга Зиппеля Zippel 1993 описывает этот метод, а также другие способы нахождения НОД многочленов.

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

(define pi (make-polynomial x ((i i)(0 i)))) (define p2 (make-polynomial x ((3 i)(0 -i)))) (define p3 (make-polynomial x ((i i))))

(define p4 (make-polynomial x ((2 i)(0 -i))))

(define rfi (make-rational pi p2)) (define rf2 (make-rational p3 p4))

(add rfi rf2)

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

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