где каждое Sj равно некоторой сумме pi, Xi и ai. Запишем Sj = Tj + Pj, где Tj - сумма Pi и Xi, тогда как /3j равно сумме а,.

Сейчас и{х) выражен в виде полинома от х, Pi, P2m+i с целыми коэффициентами. Поскольку Pi можно выразить как линейные функции от ai,..., а«, множество значений, представленных всеми действительными значениями Pi, • ,P2m+i, содержит множество результатов цепочки. Следовательно, существует максимум 2т + 1 степеней свободы; как показано в упр. 30, этот результат можно улучшить, получив 2т, когда m > 0.

В упр. 25 приведен пример построения согласно теореме М. Подобный результат можно доказать для сложения.

Теорема А (Э. Г. Белага, 1958). Делочка лолинома, содержащая q операций сложения и вычитания, имеет максимум q 1 степеней свободы.

Доказательство. [Проблемы кибернетики 5 (1961), 7-15.] Пусть ki, Кд-это Ai-цепочки, которые соответствуют операциям сложения или вычитания. Тогда

Ki = ±T2i-i±T2i ДЛЯ 1<г<д и и(а;) = Г2,+1, (29)

где каждое Tj - произведение /Cj, Xi и а. Можно записать Tj = AjBj, где Aj - произведение ai и Bj-произведение Ki и Xi. Следующее преобразование можно последовательно произвести по отношению к цепочке для г = I, 2, ..., q: пусть Pi = A2i/A2i-i, тогда Ki = A2i-i(±B2t-i ±/3iB2t). Затем заменим Ki на ±B2i-i ±PiB2i и каждое появившееся к, в формулах T2i+i, T2i+2, ..., T2q+i на A2i-iKi. (Эта замена может изменить значения A2i+i, A2i+2, , Л25+1.)

После того как преобразование проделано для всех г, положим /3,+i = A2q+i; тогда и{х) можно выразить в виде полинома от Pi, /3,+i и х с целыми коэффициентами. Доказательство почти завершено, однако следует быть осторожными, потому что полиномы, полученные, как pi, Pq+i, и определенные для всех действительных значений, могут не включать все полиномы, представленные первоначальной цепочкой (см. упр. 26); возможно получение A2i-i = О для некоторых значений aj, но это делает неопределенным Pi.

Чтобы закончить доказательство, заметим, что множество результатов R первоначальной цепочки можно записать в виде R = Ri U R2 U U Rq U R, где Ri - множество результатов возможных векторов, когда A2t-i = О, и R-множество результатов возможных векторов, когда все не равны нулю. Выше было доказано, что R имеет максимум g -Ь 1 степень свободы. Если A2i-i = О, то T2i-i = 0. Таким образом, число шагов сложения Ki может быть уменьшено, чтобы получить другие цепочки вычисляемого множества результатов Ri. По индукции можно доказать, что каждое множество Ri имеет максимум q степеней свободы. Следовательно, согласно упр. 29 R имеет максимум g -Ь 1 степень свободы.

Теорема С. Если делочка лолинома (24) вычисляет все полиномы п-й степени и{х) = UnX" -\- Uq для некоторого п > 2, то она включает по крайней мере [n/2j -Ь 1 операций умножения и по крайней мере п операций сложения-вычитания.

Доказательство. Пусть существует т шагов умножения. По теореме М цепочка имеет максимум 2т степеней свободы; таким образом, 2т > n -Ь 1. Аналогично по теореме А существует > п сложений-вычитаний.

Теорема утверждает, что не существует ни одного метода, имеющего меньше [n/2J +1 умножений или меньше п сложений, с помощью которого можно вычислить все возможные полиномы степени п. Результат упр. 29 позволяет нам усилить это утверждение и сказать, что не существует ограниченной совокупности таких цепочек полиномов, которые достаточны для всех полиномов заданной степени. Конечно, некоторые специальные полиномы можно вычислить более эффективно; мы действительно полностью доказали, что полиномы с алгебраически независимыми коэффициентами в том смысле, что они не удовлетворяют нетривиальному полиномиальному уравнению, требуют [n/2J -I-1 умножений и п сложений. К несчастью, коэффициенты, с которыми мы имеем дело на компьютере, - всегда рациональные числа, так что приведенные выше теоремы не имеют реального применения. На самом деле, в упр. 42 показано, что всегда можно достичь 0{\/п) умножений (и, скорее всего, огромного числа сложений). С практической точки зрения ограничения теоремы С относятся к "почти всем" коэффициентам, и они, оказьтается, применимы ко всем разумным схемам вычисления. Более того, можно получить нижние грани, соответствующие теореме С, даже в рациональном случае. Согласно приведенному выше усиленному доказательству У. Штрассен (V. Strassen) показал, например, что полином

и{х) = J2 2"" (30)

*:=0

нельзя вычислить любой полиномиальной цепочкой длины < n/lgn, если цепочка не имеет хотя бы - 2 умножений и n - 4 сложений [SICOMP 3 (1974), 128-149]. Коэффициенты (30) очень велики; однако можно найти такие полиномы, коэффициенты которых равны только нулям и единицам и каждая вычисляющая их цепочка полиномов включает по крайней мере i/n/(41gn) умножений в цепочке для всех достаточно больших п, даже когда параметры Qj могут быть произвольными комплексными числами. [См. R. J. Lipton, SICOMP 7 (1978), 61-69; С.-Р. Schnorr, Lecture Notes in Сотр. Sci. 53 (1977), 135-147.] Жан-Поль Ван де Виль (Jean-Paul van de Wiele) показал, что оценки определенных 0-1 полиномов требуют, в общем, cn/logn арифметических операций для некоторого с > О [FOCS 19 (1978), 159-165].

Все еще существуюшее расхождение между нижней гранью теоремы С и действительным числом операций, как известно, достигается во всех ситуациях, кроме тривиального случая, когда п = 2. Теорема Е дает [n/2j -I- 2 умножений, а не [n/2j -Ь 1, хотя она доводит до минимума количество сложений. Наши специальные методы для п = 4 и п = 6 имеют минимальное число умножений, но одно дополнительное сложение. Когда п нечетное, то несложно доказать, что нижних граней теоремы С нельзя одновременно достичь для умножений и для сложений (см. упр. 33). Для п - 3, 5 и 7 можно показать, что необходимо по крайней мере [n/2j -Ь 2 умножений. В упр. 35 и 36 показано, что обе нижние грани теоремы С не могут быть достигнуты одновременно при п = 4 или п = 6; таким образом, обсуждаемые методы будут наилучшими для п < 8. Для четного п Моцкин (Motzkin) доказал, что достаточно [n/2j -Ь 1 умножений, но его конструкция включает неопределенное количество сложений (см. упр. 39). Оптимальную схему для п = 8 нашел В. Я. Пан, доказавший, что в этом случае необходимо и достаточно п -Ь 1 сложений, когда существует [n/2j -Ь 1 умножений; он также показал, что [n/2j -Ь 1 умножений и

n + 2 сложений достаточно для всех четных п > 10. В работе Пана [STOC 10 (1978), 162-172] также установлено необходимое точное минимальное количество умножений и сложений, когда вычисления производятся полностью с комплексными числами, а не с действительными для всех степеней п. В упр. 40 обсуждается интересная ситуация, возникающая при нечетных значениях п > 9.

Ясно, что результаты, полученные для цепочек полиномов с одной переменной, можно без труда применить к полиномам с многими переменными. Например, если нужно найти оптимальную схему вычисления полинома без адаптации коэффициентов, можно рассматривать полином и{х) как полином от п -Ь 2 переменных x,Un, ,ui,uo; в упр. 38 показано, что в этом случае необходимо п умножений и п сложений. В самом деле, А. Бородин [Theory of Machines and Computations, edited by Z. Kohavi] и A. Паз (A. Paz) [New York: Academic Press, 1971, 45-58] доказали, что правило Горнера (2) является, по существу, только методом вычисления и{х) за 2п операций без предварительных условий.

С незначительными изменениями приведенные выше методы могут быть так же хорошо обобщены для цепочек, включающих деление, т. е. для рациональных функций, как и для полиномов. Любопытно, что цепные дроби, аналогичные правилу Горнера, оказались оптимальными с точки зрения вычислительных операций, если скорости вьшолнения операций умножения и деления одинаковы, даже при дополнительных условиях (см. упр. 37).

Иногда деление полезно во время вычисления полиномов, даже если полиномы определены только в терминах умножения и сложения (соответствующие примеры приводятся в алгоритмах Шо-Трауба для производных полинома). Другим примером является

х" + + X + 1.

Поскольку этот полином можно записать в виде (х" - 1)/{х - 1), его можно вычислить, выполнив 1{п + 1) операций умножения (см. раздел 4.6.3), две операции вычитания и одно деление, в то время как технический прием во избежание деления, кажется, требует приблизительно втрое больше операций (см. упр. 43).

Специальные полиномы от нескольких переменных. Определитель матрицы размера пхп можно рассматривать как полином от переменных Xij, 1 < i,j < п. Если Хп ф О, то

/Х22 - (X2i/a;ii)a;i2 Х2п- (x2i/xu)xin>

Х32 - (X3l/Xu)xi2 ... ХЗп - (X3l/xn)xin

\Хп2 - (Xnl/Xu)xi2 ...Хпп - {Xnl/xn)xin/

(31)

Поэтому определитель матрицы размера п хп можно найти, вычислив определитель матрицы размера (п - 1) х (п - 1) и выполнив дополнительно (п - 1) -Ь1 умножений, (п - 1)2 сложений и п - 1 делений. Поскольку определитель размера 2x2 можно вычислить с помощью двух операций умножения и одной операции сложения, определитель почти всех матриц (т. е. матриц, для которых нет необходимости в делении на нуль) можно вычислить, выполнив максимум (2п - Зп + 7п - 6)/6 операций умножения, (2п - Зп +п)/6 операций сложения и (п - п - 2)/2 делений.