Составители:
Рубрика:
−10x
16
+ 28x
20
− 84x
24
) (6.7)
многочлен p
2
имеет меньше слагаемых чем p, а НОД многочлена
p
2
и (p
2
)
0
содержит больше слагаемых, чем каждый из этих много-
членов.
18
Замечание 5. Почти очевидно, что время счёта зависит в зна-
чительной степени от предпринятой подстановки; например, время
развёртывания выражений
(x
1000
+ 1)
2
(6.8)
и
((t − 1)
1000
+ 1)
2
(6.9)
отличается в тысячи раз.
7. Наибольший общий делитель (НОД)
Нетривиальность процесса отыскания НОД двух многочленов
хорошо иллюструется на следующем примере (Brown), где исполь-
зуется алгоритм Евклида. Пусть
P (x) = x
8
+ x
6
− 3x
4
− 3x
3
+ 8x
2
+ 2x − 5, (7.1)
Q(x) = 3x
6
+ 5x
4
− 4x
2
− 9x − 21. (7.2)
Первый шаг состоит в вычислении
P (x) − (
x
2
3
−
2
9
)Q(x) = −
5
9
x
4
+
1
9
2
−
1
9
. (7.3)
Aналогичным образом сделаем следующие шаги:
−117
25
x
2
− 9x +
441
25
, (7.4)
233150
6591
x −
102500
2197
, (7.5)
и окончательно
1288744821
543589225
. (7.6)
Отсюда видно, что в процессе вычислений необходимо часто вы-
числять НОД двух целых чисел.
18
Попытаться дать более эффективную оценку для НОД, чем та, которая приведена в
таблице 1.
47
Страницы
- « первая
- ‹ предыдущая
- …
- 44
- 45
- 46
- 47
- 48
- …
- следующая ›
- последняя »
