Быстрые вычисления с целыми числами и полиномами (стр. 3 из 5)

Но мы не учли корректирующие перемножения, которые должны быть выполнены, когда показатель не является степенью двойки. Если n = 2l+1 – 1, нужно добавить к последовательным возведениям в квадрат перемножения всех полученных многочленов. Умножение многочлена степени (2ⁱ-1)d на многочлен степени 2ⁱd вносит свой вклад из ((2ⁱ – 1)d + 1)( 2ⁱd + 1) умножений, которые, будучи собранными по всем корректирующим вычислениям, дают дополнительную сложность:

= =

=

Теперь можно заключить, что дихотомическое возведение в степень не всегда является лучшим способом для вычисления степени многочлена с помощью перемножений многочленов. Число перемножений базисного кольца, которые необходимы, C_sqr(n), - в действительности заключено между ( ) и т.е. между n²d²/3 и 2n²d²/3, тогда как простой алгоритм требует всегда n²d²/2 перемножений. В частности, если исходный многочлен имеет степень, большую или равную 4, возведение в степень наивным методом требует меньше перемножений в базисном кольце, чем бинарное возведение в степень, когда n имеет форму 2^l – 1.

Можно довольно просто доказать, что если nимеет вид 2^l +2^{l – 1} + c (выражения, представляющие двоичное разложение n), то метод вычисления последовательными перемножениями лучше метода, использующего возведение в квадрат (этот последний метод требует корректирующего счёта ценой, по крайней мере, n²d²/9). Всё это доказывает, что наивный способ является лучшим для этого класса алгоритмов, по крайней мере, в половине случаев.

Действительно, МакКарти [3] доказал, что дихотомический алгоритм возведения в степень оптимален среди алгоритмов, оперирующих повторными умножениями, если действуют с плотными многочленами (антоним к разреженным) по модулю m, или с целыми и при условии оптимизации возведения в квадрат для сокращения его сложности наполовину (в этом случае сложность действительно падает приблизительно до n²d²/6 + n²d²/3 = n²d²/2).

3.3 Небольшие оптимизации для произведений многочленов

В принципе вычисление произведения двух многочленов степеней n и m соответственно требует (n +1)(m +1) элементарных перемножений. Алгоритм оптимизации возведения в квадрат состоит просто в применении формулы квадрата суммы:

что даёт n +1 умножений для первого члена и n(n +1)/2 – для второго, или в целом (n +1)(n +2)/2 умножений, что близко к половине предусмотренных умножений, когда n большое.

Для произведения двух многочленов первой степени P = aX+bиQ=cX + d достаточно легко находим формулы U=ac, W=bd, V = (a+ b)(c + d) и PQ = =UX² + (V – U – W)X +W, в которых появляются только три элементарных умножения, но четыре сложения. Можно рекурсивно применить этот процесс для умножения двух многочленов P и Q степени 2^l – 1, представляя их в виде и применяя предыдущие формулы для вычисления PQ в зависимости от A, B, C и D, где каждое произведение AB, CD и (A + B)(C + D) вычисляется с помощью рекурсивного применения данного метода (это метод Карацубы). Всё это даёт мультипликативную сложность M(2^l)и аддитивную сложность A(2^l)такие, что:

M(2^l) = 3M(2^{l – 1}),…, M(2) = 3M(1),M(1) = 1,

A(2^l) =3A(2^{l – 1}) + 3*2^l,…, A(2) = 3A(1) + 6,A(1) = 1.

В этой последней формуле член 3*2^l представляет собой число элементарных сложений, необходимых, чтобы сделать два сложения многочленов степени 2^{l – 1} – 1 (a + b и c + d) и два вычитания многочленов степени 2^l – 1 (U – V – W). Суммируя каждое из этих выражений, находим для n, являющегося степенью двойки:

M(n) = n^log3/log2»n^1,585иA(2) =7 n^log3/log2 – 6n.

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

3.4 Вычисление многочленов

Рассмотрим общую задачу вычисления многочлена n-й степени

u(x) = u_nxⁿ + u_{n – 1}x^{n – 1} + ... + u₁x + u₀, u_n¹ 0, (1)

3.4.1 Схема Горнера

u(x) = (…(u_nx + u_{n – 1})x + …)x + u₀. (2)

Весь этот процесс требует n умножений и n сложений.

Было предложено несколько обобщений схемы Горнера. Посмотрим сначала, как вычисляется в случае, когда – комплексное число, а коэффициенты вещественны. Комплексное сложение и умножение можно очевидным образом свести к последовательности обычных операций над вещественными числами:

вещественное + комплексное требует 1 сложение,

комплексное + комплексное требует 2 сложения,

вещественное * комплексное требует 2 умножения,

комплексное * комплексное требует 4 умножения и 2 сложения

или 3 умножения и 5 сложений.

Следовательно, схема Горнера (2) требует 4n – 2 умножений и 3n – 2 сложений или 3n – 1 умножений и 6n – 5 сложений для вычисления u(z), когда z комплексное. Вот другая процедура для вычисления u(x + iy):

a₁ = u_n, b₁ = u_{n – 1}, r = x + x, s = x² + y²; (3)

a_j = b_{j – 1} + ra_{j –1}, b_j = u_{n – j} – sa_{j –1}, 1 < j£n.

Легко доказать индукцией по n, что u(z) = za_n + b_n. Эта схема требует 2n + 2 умножений и 2n + 1 сложений, так что при n³ 3 она лучше схемы Горнера.

Рассмотрим процесс деления многочлена u(x) на многочлен x – x₀. В результате такого деления мы получаемu(x) = (x – x₀)q(x) + r(x); здесь deg(r) < 1, поэтому r(x) есть постоянная, не зависящая от x и u(x₀) = 0*q(x₀) + r = r. Анализ этого процесса деления показывает, что вычисления почти те же самые, что в схеме Горнера для определения u(x₀). Аналогично, когда мы делим u(z) на многочлен (z – z₀)(z – z₀) = z² – 2x₀z + x₀² + y₀², то соответствующие вычисления эквивалентны процедуре (3); мы получаем

u(z) = (z – z₀)(z – z₀)q(z) + a_nz + b_n;

следовательно,

u(z₀) = a_nz₀ + b_n.

Вообще, когда мы делим u(x) на, f(x) получая u(x) = f(x)q(x) + r(x), то из равенства f(x₀) = 0 следует u(x₀) = r(x₀); это наблюдение ведёт к дальнейшим обобщениям правила Горнера. Мы можем положить, например, f(x) = x² – x₀²; это даст нам схему Горнера «второго порядка»

u(x) = (…(u_{2ën/2 û} x² + u_{2ën/2 û – 2})x² + u₀ +

+((….u_{2én/2 ù - 1} x² + u_{2én/2 ù - 3})x²+ … +)x²u₁)x. (4)

3.4.2 Интерполяционная формула Ньютона и табулирование значений многочлена

Рассмотрим специальный случай вычисления многочлена. Интерполяционный многочлен Ньютона степени n, определяемый формулой

u^[n](x) = a_n(x – x₀) (x – x₁)…(x – x_{n – 1}) +…+ a_n (x – x₀) (x – x₁) + a₁ (x – x₀) + a₀, (5)

является единственным многочленом степени £n от x, который принимает предписанные значения y₀, y₁, …, y_nв заданных n + 1 различных точках x₀, x₁, …, x_n соответственно. После того, как значения постоянных a найдены, интерполяционная формула Ньютона становится удобной для вычислений, так как мы можем, обобщив правило Горнера, записать

u^[n](x) = ((…(a_n(x – x_{n – 1}) + a_{n – 1})(x – x_{n – 2}) + …)(x – x₁) + a₁)*