AOP_Tom2 (1021737), страница 214
Текст из файла (страница 214)
2. Положим, что входное значение х находится в регистре А, а и — в памяти по адресу МИ; выходное значение помещается в регистр Х. А1. Инициализация. У+- 1. г -х. Ю+- и. Переход к шагу А2. В противном случае ответ равен 1. Ю э- [Ф1'2]. Аб. Возведение Е в квадрат. Е ь- У х Ушобю. А2. Деление Х погюлам. Переход к шагу А5 при четном У. Переход, если 17 = 1. Аг +- [У/2]. АЗ. мн ение У а Е У э-гхУ б . Переход к шагу А5.
Окончательное умножение. 5 Время работы составляет 215 + 16К + 8, где Е = А[и) на единицу меньше количества битов в двоичном представлении и, а К = и(и) — количества единичных битов в таком представлении. Для последовательной программы можно положить, что и достаточно мвлб для размещения и индексном регистре; в противном случае последовательное возведение в степень выходит за рамки данной задачи. Приведенная ниже программа помещает выходное значение в регистр А. г11 ~- и.
Х < — х. 1 1 1 17 — 1 1'г' — 1 Х Х 01 61 201 МИ 02 В ТА Х ОЯ 1ИР 2Р 04 1Н ИШ Х 05 ВШАХ 6 Об 2Н ОЕС1 1 07 ЛР 1В гА х Хшобю -г гА. гП +- гП вЂ” 1. Опять умножить при гП > О. 5 Время ее рабаты составляет 14Х вЂ” 7; эта программа работает быстрее предыдущей при и < 7 и медленнее — при и > 8. 3. Последовательности показателей степени для этих методов следующие: [а) 1, 2, 3, 6, 7, 14, 15, 30, 60, 120, 121, 242, 243, 486, 487, 974, 975 [!б умножений]; [Ь) 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 умножений]; [б) 1, 2, 3, 6, 12, 15, ЗО, 60, 75, 150, 300, 600, 900, 975 [13 умножений). [Наименьшее возможное чиста умножений равно 12, "оно может 01 А1 ЕМТХ 1 02 ВТХ Т ОЯ ВТА 2 04 1.0А ИИ 05 ЯАР 2Р 00 1ИР ООМЕ 07 ВИ ВНВ 1 00 ВТА М ОУ Аб СОА 2 10 ИШ.
2 11 ВТХ 2 12 А2 ХОА И 1Я 2Н ЯАЕ 68 14 ВВВ 1 15 А4 1А2 4Р 1б ВТА М 17 АЗ ЬРА 2 1В И01. Т 10 ВТХ Т 20 ЯИР АВ АТ 4Н 1Л)А 2 ВВ ИЯ. Т 1 1 1 1 1 0 5+1 — К С+1 — К Б Б Е Е 2+1 К К К вЂ” 1 К вЂ” 1 К вЂ” 1 К вЂ” 1 К вЂ” 1 1 1 быть получено путем комбинирования метода множителя с бинарным методом, поскольку 975 = 15 (2 + 1).] 4 (777777)в = 2гв 5. Т1.[Инициализация.] Установить 1.|ИКО[Я +- 0 для 0 < 1 < 2' и установить В +- О, ЫИКВ[0] +- 1, Ь1ИКВ[Ц < — О. 'Г2.(Изменение уровня.] (Теперь уровень В дерева связан слева направо, начиная с 11ИКВ[0].) Если В = г, алгоритм завершается. В противном случае установить и+- 51ИКВ(0], т +- О.
ТЗ. (Подготовка и.] (Теперь п — узел уровня В и гп указывает на крайний справа в данный момент узел уровня В+ 1.) Установить 9 г- О, в < — и, Т4. (Уже в дереве?) (Теперь в — узел на пути от корня дерева до и,) Если ЫИКО(п+ в] Ф О, перейти к шагу Тб (значеиие и + в уже имеется в дереве). Тб. (Вставка под и.] Если д = О, установить т' +- и + в. Затем установить 11ИКВ[п + в]+-д, ЫИКО[п + в] в- и, д е- и+ в. Тб. (Перемещение вверх,) Установить в +- 51ИКО(в]. Если в ф О, вернуться к шагу Т4.
Т7. [Присоединение группы.] Если д ~ О, установить 1.1ИКВ[т] +- д, гп +- т'. 'ГВ. (Перемещение и.] Установить и+- 1.1ИКВ[п]. Если и ф О, вернуться к шагу ТЗ. ТО. (Конец уровня.[ Установить 1.1ИКВ[т] е- О, В +- В+ 1 и вернуться к шагу Т2. 3 6.
Докажем па индукции, что путем к числу 2'в + 2" + .. + 2" при ео > ег » ег > 0 является последовательность 1, 2, 2г, ..., 2", 2ы+ 2", ..., 2'в +2" +. + 2". Кроме того, последовательность показателей степеней на каждом уровне рассортирована в убывающем лексикографическом порядке, 7. Бинарный метод и метод множителя требуют при вычислении хг" на адин шаг больше. чем при вычислении х"; метод дерева степеней требует не более одного дополнительного шага. Следовательно, (а) 15 2; (Ь) ЗЗ 2"; (с) 23 2; В = О, 1, 2, 3, .... 8.
Дерево степеней всегда включает узел 2т иа уровень ниже т, кроме случая, когда он уже встречался иа том же или иа одном из предыдущих уровней; кроме того, дерево всегда включает узел 2т + 1 иа один уровень ниже узла 2т, если только его нет на там же уровне или на одном из предыдущих. (Неверно, что 2т является дочерним узлом т в дереве степеней для всех т; иаимеиьший пример, когда это не так, — т = 2138, который появляется иа уровве 15, в то время как узел 4276 появляется на уровне 16 в,зругам месте. В действительности 2т иногда встречается даже на том же уровне, что и т, наименьший такой пример — т = 6029 ] 8.
Начнем с устаиовок гУ +- и, Я в- х и 1' +- 1 для 1 < д < т, где д — нечетко; в общем слУчае полУчим х" = Угуз~)'в~... У~,~Я~ после выполнении алгоРитма. ПолагаЯ, что Х > О, установим В +- Л' шобт, 1г" +- [гг/т]. Затем, если В = О, установим И +- Е и повторим шаг; в противном случае, если Й = 2ва, где д — нечетко, установим Я +- Ег", У„+- У'г . 3 и, если М > О, Установим Е +- Ег' " и повтоРим шаг И наконец Установим Ув г- 1'в Ув+г для В = т — 3, т — 5, ..., 1. Искомый ответ — г)г(Ув)гв... К г) .
(Около т/2 умножений представляют собой умножеиия на 1.) 10. Примените представление РАВВИТ, обсуждавшееся в разделе 2.3.3; используйте табли- пу р[у] 1 < .1 < 100, такую, что р[1] = О и р[г] является номером узла, распаложениога непосредственно над У дяя 1 > 2. (Тот факт, что каждый узел этого дерева имеет степень, ие превышающую двух, не влияет на эффективность представления. Это только улучшает внешний вид дерева, используемога в качестве иллюстрации.) 11. 1, 2, 3, 5, 10, 20, (23 или 40), 43; 1, 2, 4, 8, 9, 17, (26 или 34), 43, 1, 2, 4, 8, 9, 17, 34, (43 или 68), 77; 1, 2, 4, 5, 9, 18, 36, (41 или 72), 77.
Если бы любой из двух последних путей имелся в дереве, и = 43 было бы невозможно, поскольку дерево должно содержать либо 1, 2, 3, 5, либо 1, 2, 4, 8, 9. 12. Такое дерево невозможно, поскольку 1(п) ф Г(п) для некоторых и. 13. для случая 1 используйте цепочку типа 1, за которой следует 2 + + 2в+с+ 2 + 2в, либо воспользуйтесь методом множителя. Для случая 2 используйте цепочку типа 2, за которой следует 2л+с+' + 2 + + 2 + 2 . Для случая 3 используйте либо цепочку типа 5, в+с л в за которой следует 2 + 2я ', либо метод множителя.
Для случая 4 и = 135 2п, так что можно использовать метод множителя. 14. (а) Легко убедиться, что о«агн г — 1 и г — 2 не являются мапыми. Это позволяет считать, что шаг г — 1 является малым, а шаг г — 2 — нет. Если с = 1, то Л(а, «) = Л(а„«), так чтой = 2; апоскольку4 < п(а ) = и(а, «)+и(а„«)-1 < п(а «)+1, имеем п(а, «) > 3, делан «оаг г — 1 звездным (чтобы цепочка ао, ап..., а, з, а «не включала талька один малый шаг). Тогда а, « — — а, з + а, з для некоторого д, и, если заменить а, з, а, и а« на а«з, 2а«з, 2а«з + а, э = а„получится другая цепочка-контрпример, в которой шаг г является малым. Однако это невозможно. С другой стороны, если с > 2, то 4 < п(а«) < п(а, «)+ п(а, «) — 2 < ««(а, «); следовательно, и(а,-«) = 4, и(а, «) = 2 н с = 2.
Это легко приводит к невозможной ситуации, возникающей в результате рассмотрения шести типов из доказательства теоремы В. (Ь) Если Л(а, «) < гл — 1, имеем с > 3, так что п(а««) + п(а««) > 7 согласно (22); поэтому как п(а„«), так и «(а, «) оба > 3. Все малые шаги дщ«жны быть < г — Ь, а Л(а, «) = щ — Ь+ 1. Если Ь > 4, необходимо иметь с = 4, Ь = 4, и(а, «) = п(а««) = 4. Таким образом, а, «> 2 +2м '+2~ но« вЂ” «должно быть равна 2м+2м '+2 з+2 но из а, «> — 'а,-«вьггекает, что а«« = 8а,-я Значит, Ь = 3 н а, «> 2 + 2м Поскольку а, з < 2 и а,-з < 2м ', шаг г — 1 должен быть удвоением, однако шаг г — 2 не является удвоением, так как а, ~ ~ 4а«-з. Кроме того, поскольку п(а„з) > 3, г — 3 является звездным шагом и иэ а, з = а, з + а«з должна следовать, что а, « = 2м Поэтому необходимо получить а«з = а,-з+а«ь Как и в подобном случае, рассмотренном в тексте раздела, единственная возможность заключается в том, чтобы выполнялось а 2 з+2 з, а«-з = 2 з+2 «+2+'+2~, а, « — — 2 +2 '+2~т~+2~т', но и это невозможно.
15. Ахим Фламменкамп (АсЬ«ш Р!ашшепйашр) ]Р!р!ошвгЪей !п Ма«Ьешаг!сэ (В!е!е1е!6 Бп!тегз!!у, 1991), Рахг Ц показал, что все числа и с Л(п) + 3 = 1(п) < Г(п) имеют вид 2я + 2в + 2с + 2п + 2в, где А > В > С > Р > Е и В + Е = С+ Р3 более того, они точно описываются как не соответствующие ни одному иэ восьми шаблонов (здесь ]е] < 1): 2л + 2л-з + 2с + 2с-«+ 2зс+з-я 2я + 2л-«+ 2с + 2п+ 2с«о««-л 2л + 2в+ 2зв-я+э+ 2зв+т-л + 2«в+з-зл 2л + 2в+2зв-л«+ 2п+ 2в+о+.— л 2л + 2в 2в-«+ 2п Я 2п-«2л Я2в+ 2в — э+ 2п+ 2п-з (А > В+ Ц 2л + 2в + 2с + 2зв+ -л + 2в+с — л 2я+2в+2с+2в+с+.-л+2зс+ -л 16. 1в(п) = Л(п) + п(п) — 1, так что. если и = 2", 1в(п)/Л(п) = 1, но если и = 2«+' — 1, 1в(п)/Л(п) = 2 17. Пусть 1«« 1«. Удалим все интервалы 1«, которые можно удалить без изменения объединения П '«! .
0 уо (Интервал (у« ..1«] может быть удален, если /«««< либо у«< (з < и 1««, < 1«п) Теперь объединим перекрывающиеся интервалы (/л .. Ь],..., (ул .. «4] в интервал Ц ..1] = (13 ..1л] и заметим, что а, <а (1+б)" 1'+ мы ы <а (1+б)~!' ПОСКОЛЬКУ Каждая тОЧКа (дч .. Р] ПОКРЫВавтея ОбЪЕднНЕНИЕМ (/, М] 0- 0 (да., 1З] НЕ бОЛЕЕ двух раз. 13. Назовем /(т) "хорошей" функцией, если (!об/(т))/т -+ О при т -э оо. Произвольный полипом от т является "хорошим". Произведение хороших функций — хорошая функция. Если д(гп) -+ О и с — положительная константа, то с"'к~~1 — хорошая функция; хороша также и ( ~ 1), так как с учетом аппроксимации Стирлинга это эквивалентно утверждению д(т) 1об(1/д(т)) -Ф О.
Теперь заменим каждый член суммы максимальным па э, й е членом. Общее число членов — хорошее, так же как и (,э'), ('~"') < 2'+" и ~3~", потому что (1+ е)/т -+ О. И наконец (~ ~'1 ) < (2гл)ы/В < (4ет~/1)', где (4е)' — хорошая функция. Замещая 1 его верхней границей (1 — е/2)ш/Л(т), показываем, что (т~/1)' < 2жц '~Ю/(гп), где /(гл)— хорошая функция. Следовательно, вся сумма меньше, чем и для больпшх т, если а = 2' ",гдеО<п< -'е. 19.
(а) М П Ж, М 0 Ж, М Э1 гГ соответственно; см. 4.5.2-(6), 4.5 2 — (7). (Ь) /(к)д(х), 1сш(/(х),д(л)), бей(/(л),д(х)). (По тем же причинам, что и в п. (а), потому что нормированные неприводимые полиномы над полем комплексных чисел в точности представляют собой полиномы е — С) (с) Законы коммутативности: А Ь В ж В Ю А, А 0 В = В 0 А, А Гз В = В Г1 А.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
