Реферат: Быстрые вычисления с целыми числами и полиномами

Предварительное заключение, которое можно вывести из предыдущих вычислений, складывается в пользу дихотомического возведения в степень: если n есть степень двойки (гипотеза ad hoc), этот алгоритм ещё выдерживает конкуренцию, даже если эта победа гораздо скромнее в данном контексте (n ² d ² /3 против n ² d ² /2), чем когда работаем в Z/p Z (2log₂ n против n ).

Но мы не учли корректирующие перемножения, которые должны быть выполнены, когда показатель не является степенью двойки. Если 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_n xⁿ + u_{n – 1} x^{n – 1} + ... + u ₁ x + u ₀ , u_n ¹ 0, (1)

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

u (x ) = (…(u_n x + 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_n z + b_n ;

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

u (z ₀ ) = a_n z ₀ + 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)