38. Из условий вытекает, что, когда \z\ = 1, мы имеем либо м„-22" + • • + мо < m„ i-1 < z"+m„-iz"-, либо m„-3z"-4---+mo < Мп-2-1 < z" + m„-22"-. Поэтому согласно теореме Роше [J. Есо/е Po/ytedinique 21, 37 (1858), 1-34] u{z) имеет минимум п-1 или п-2 корня внутри окружности \z\ = 1. Если u{z) приводим, он может быть записан как v{z)w{z), где V и ги - нормированные целые полиномы. Произведения корней v и корней ги представляют собой ненулевые целые числа, так что каждый множитель имеет корень с абсолютной величиной > 1. Следовательно, единственная возможность заключается в том, что и и ги оба имеют в точности по одному такому корню и что Мп-i = 0. Эти корни должны быть действительны, поскольку корнями являются комплексно-сопряженные числа. Значит, u{z) имеет действительный корень zo c\zo\ > 1. Но этого не может быть, так

как, если г = 1/zo, имеем О = \l + Un-2r +----Ьмог" > 1--м„-2Г-м„ зг-----мог" > 1.

[О. Perron, Crelle 132 (1907), 288-307; обобщения даны в А. Brauer, Атег. J. Math. 70 (1948), 423-432, 73 (1951), 717-720.]

39. Сначала докажем утверждение из указания. Пусть полином и{х) = a{x-ai)... (х-Оп) имеет целые коэффициенты. Результант полинома и{х) с полиномом y - t(x) представляет собой детерминант, так что он является полиномом rt{y) = а*(у - t(ai))... (у - t{an)) с целыми коэффициентами (см. упр. 4.6.1-12). Если и{х) делит v{t(x)), то v{t{a\)) = 0. Следовательно, г«(у) имеет общий множитель с v{y). Так что, если v неприводим, мы имеем deg(u) = deg(rt) > deg(D).

Для данного неприводимого полинома и{х), для которого требуется короткое доказательство неприводимости, можно предположить его нормированность согласно упр. 18, а также считать, что deg(u) > 3. Идея заключается в том, чтобы показать существование полинома t{x), такого, что полином v{y) = rt{y) является неприводимым по критерию из упр. 38. Тогда все множители и{х) делят полином v{t{x)), и это доказывает, что и{х) неприводим. Доказательство будет "укорочено", если коэффициенты t{x) достаточно малы.

Можно показать, что полином и (у) = (у - /3i)... (у - /Зп) удовлетворяет критерию упр. 38, если п > 3h/3i.../3„ ф О и если выполняется следующее "условие малости":

< 1/(4п), за исключением случаев, когда j = п или 0j = 0„ и St/3j( < 1/(4п). Вычисления производятся непосредственно, с учетом того факта, что t)o -Ь • • • + in <

(1 + А)...(1 + /Зп).

Пусть Qi, ..., Or -действительные числа, а Qr+i, ..., «г+л -комплексные, где п = г + 2s и Or+j+j = Qr+j для 1 < J < S. Рассмотрим линейные выражения S,(ao,... ,an-i), определенные как 31(ЁГ=Го "•i) 1 < j < r + s и {J27=o r + s <j <n. Если

0<ai<bHB = r™ax"riЕ.СоМа.Р!) имеем S,(ai,... ,a„-i) < bB. Таким образом, если выбрать b > (16пВ)"~, должны существовать различные векторы (оо,... ,a„-i) и (ao,...,a„ i), такие, что [8п5; (ао,..., a„ i)J = L8nSj(ao,..., aUi)J для 1 < j < n, поскольку имеется Ь" векторов, но не более (16пЬВ)"" < Ь" возможных (п-1)-элементных наборов значений. Пусть t{x) = [ао - ао) + + (On-i - aj, i)a:"" и /3j = t{aj). Тогда "условие малости" удовлетворено. Кроме того, Д ф О; в противном случае t{x) должно делить и{х). [J. Algorithms 2 (1981), 385-392.]

40. В данном множителе-кандидате v{x) = х + ad-ix~ + + ао заменим каждый aj рациональной дробью (по модулю р) с числителем и знаменателем < В. Затем выполним умножение на наименьщий общий знаменатель и посмотрим, осуществляет ли полученный полином деление и{х) над кольцом целых чисел. Если нет, то не существует множителя и{х) с коэффициентами, ограниченными В, которые сравнимы по модулю р с кратным v{x).

41. Дэвид Бойд (David Boyd) заметил, что 4х+Ах+х*+4х+4 = {2х*+4х+5х+4х+2) х {2х* - 4х + Ъх -4х + 2), и нащел пример более высокой степени для доказательства того, что с > 2, если оно существует.

РАЗДЕЛ 4.6.3

1. ж™, где т = г-*"- -наивысшая степень 2, меньшая или равная п.

2. Положим, что входное значение х находится в регистре А, а n - в памяти по адресу NN; выходное значение помещается в регистр X.

Время работы составляет 21L + 16АГ + 8, где L = A(n) на единицу меньше количества битов в двоичном представлении п, а АГ = i/(n) - количество единичных битов в таком представлении.

Для последовательной программы можно положить, что п достаточно малб для размещения в индексном регистре; в противном случае последовательное возведение в степень выходит за рамки данной задачи. Приведенная ниже программа помещает выходное значение в регистр А.

Время ее работы составляет 14JV - 7; эта программа работает быстрее предыдущей при n < 7 и медленнее - при n > 8.

3. Последовательности показателей степени для этих методов следующие: (а) 1, 2, 3, 6, 7, 14, 15, 30, 60, 120, 121, 242, 243, 486, 487, 974, 975 [16 умножений]; (Ь) 1, 2, 3, 4, 8, 12, 24, 36, 72, 108, 216, 324, 325, 650, 975 [14 умножений]; (с) 1, 2, 3, 6, 12, 15, 30, 60, 120, 240, 243, 486, 972, 975 [13 умножений]; (d) 1, 2, 3, 6, 12, 15, 30, 60, 75, 150, 300, 600, 900, 975 [13 умножений]. [Наименьшее возможное число умножений равно 12; оно может

быть получено путем комбинирования метода множителя с бинарным методом, поскольку 975 = 15 (2« + 1).]

4. (777777)8 = 2* - 1.

5. Т1. [Инициализация.] Установить LINKU[j] О для О < j < 2 и установить к Q,

LINKR[0] <- 1, LINKR[1] <- 0.

Т2. [Изменение уровня.] (Теперь уровень к дерева связан слева направо, начиная с LINKR[0].) Если к = г, алгоритм завершается. В противном случае установить n-(-LINKR[0], m 0.

ТЗ. [Подготовка п.] (Теперь п - узел уровня кит указывает на крайний справа в данный момент узел уровня к + 1.) Установить g <- О, s <- п.

Т4. [Уже в дереве?] (Теперь s- узел на пути от корня дерева до п.) Если LINKU[n + з]фО, перейти к шагу Т6 (значение п + s уже имеется в дереве).

Т5. [Вставка под п.] Если g = О, установить т i- п + s. Затем установить LINKR[n +s]<-q, LINKU[n + s] п, q <-п + s.

Т6. [Перемеш;ение вверх.] Установить s LINKU[s]. Если s ф О, вернуться к шагу Т4.

Т7. [Присоединение группы.] Если g # О, установить LINKR[m] g, m m.

T8. [Перемеш;ение п.] Установить п LINKR[n]. Если п О, вернуться к шагу ТЗ.

Т9. [Конец уровня.] Установить LINKR[m] О, к i- к + 1 и вернуться к шагу Т2.

6. Докажем по индукции, что путем к числу 2° +2° Н-----Ь2 при ео > ei > • > et > О

является последовательность 1, 2, 2 ..., 2°, 2° + 2", ...,2° + 2+----h 2=. Кроме того,

последовательность показателей степеней на каждом уровне рассортирована в убываюш;ем лексикографическом порядке.

7. Бинарный метод и метод множителя требуют при вычислении ж" на один шаг больше, чем при вычислении ж"; метод дерева степеней требует не более одного дополнительного шага. Следовательно, (а) 15 2*=; (Ь) 33 • 2*; (с) 23 • 2*=; А; = О, 1, 2, 3, ... .

8. Дерево степеней всегда включает узел 2т на уровень ниже т, кроме случая, когда он уже встречался на том же или на одном из предыдуш;их уровней; кроме того, дерево всегда включает узел 2т + 1 на один уровень ниже узла 2т, если только его нет на том же уровне или на одном из предыдуш;их. [Неверно, что 2т является дочерним узлом т в дереве степеней для всех т; наименьший пример, когда это не так, - т = 2138, который появляется на уровне 15, в то время как узел 4276 появляется на уровне 16 в другом месте. В действительности 2т иногда встречается даже на том же уровне, что и т; наименьший такой пример - т - 6029.]

9. Начнем с установок N<~n, ZxnYq-l для 1 < g < m, где g - нечетно; в общем случае получим ж" = У1УзУ5 ... Y™Zi Z после выполнении алгоритма. Полагая, что iV > О, установим к <~ N modm. Л <- lN/m\. Затем, если к = Q, установим Z Z™ и повторим шаг; в противном случае, если к = 2q, где g - нечетно, установим Z <- Z, У, У, • Z и, если JV > О, установим Z <г- Z~ и повторим шаг. И наконец установим Yk -h-Yk- Yk+2 для = m - 3, m - 5, ..., 1. Искомый ответ -У1(УзУ5 ... Ym-\f. (Около m/2 умножений представляют собой умножения на 1.)

10. Примените представление PARENT, обсуждавшееся в разделе 2.3.3: используйте таблицу P[j], 1 < j < 100, такую, что р[1] = О и p[j] является номером узла, расположенного непосредственно над j для j >2. (Тот факт, что каждый узел этого дерева имеет степень, не превышающую двух, не влияет на эффективность представления. Это только улучшает внешний вид дерева, используемого в качестве иллюстрации.)