AOP_Tom2 (1021737), страница 216
Текст из файла (страница 216)
См Ббэсгесе МаСЬ. 23 (1978), 115 — 119. [Эта модель цен соответствует умножению больших чисел классическим методом, подобным алгоритму 4.3.1М. Эмпирические результаты с более общей моделью, в которой цена равна (а>ас)зг>> были получены в работе О. Р. МсСвгСЬу, Масй. Сошр. 46 (1986), 603 — 608: этв модель более близка к методам "быстрого умножения" из раздела 4.3.3, когда два и-битовых числа умножаются за 0(>се) шагов, ио функция цены а,ал ' в действительности подходит я большей степени (см. упр. 4.3.3-13).
Х. Зантема (Н. 2апсеша) проанализировал аналогичную задачу при стоимости Ьго шага, равной а +аь, а не а>аь (см. з. А!Вот!сйшз 12 (1991), 281 — 307). В этом случае оптимальные цепочки имеют общую цену эп+ 0(пмс). Кроме того, оптимальная алдитивная цена прн нечетном и не ниже -(и — 1); она равна этой величине тогда и только 5 тогда, когда и может быть записана как произведение чисел вида 2 + Ц ь ЗЗ. Восемь; четыре пути вычисления 39 = 12 + 12 + 12 + 3 и два пути вычисления 79 = 39+ 39+ 1. 34.
Утверждение истинна. Метками в приведенном графе бинарной цепочки являются [л/2" ] для Ь = ео,, О, в дувльнам графе они равны 1, 2, ..., 2", л. [Аналогично т-врный метод "справа налево» из упр. 9 дуален по отношению к методу "слева направо".] Зб. Бинарной цепочке эквивалентны 2' цепочек; зто число должно составлять 2' ', если еэ = е~ + 1.
Количество цепочек., эквивалентных схеме алгоритма А, равно количеству путей для вычисления суммы ! + 2 чисел, два из которых одинаковы. Эта величина равна 1/ьы + -'/и где /~ — количество способов вычисления суммы т + 1 различных чисел. Учитывая коммутативность, мы видим, что /и равно 2 ™, умноженному на (т + 1)!, умноженному на количество бинарных деревьев из т узлов, так что / (2гл — 1)(2т — 3)... 1. 36. Построим 2 — т — 1 произведений х",...х' для каждой последовательности степеней, таких, что 0 < еь < 1 и е~ + + е,» > 2.
Пусть ль = (Ыьь...4ыЫьа)и Чтобы завершить вычисления, найдем х,'"... х ", затем возведем в квадрат и умножим на хэи... хм~ ' для 1 = Л вЂ” 1, ..., 1, О. [Страус показал в АММ 71 (1964), 807 — 808, что 2Л(и) может быть заменено (1+ г)Л(л) для любого е > 0 посредством обобщения этого бинарного метода на 2 -арный, как в теореме П.] 37. Сначала вычислим 2» для 1 < д < Л(и ), а затем — каждый л = и, при помощи следующего варианта 2~-арного метода: для всех нечетных д < 2" вычислим /э = 2 (2ые' ] А = 2'а], где и = (... 4~4а)з», за не более чем [ь' !8 и] шагав и вычислим л = 2 9/ за не более чем 2 Цд) + 2~ ' последующих шагов.
Количество шагов на адно и, < Я !Зи] + 0(Г»2") и равно Л(и)/ЛЛ(и)+ 0(Л(л)ЛЛЛ(и)/ЛЛ(л) ) при Гс = [1616 л — 3!8!8!Зл]. [Обобщение теоремы Е дает соответствующую нижнюю границу (ИСОЛГР б (1976), 100-103).] 38. Следующее построение Д. Дж. Ньюмена (П. 1. Кеччпап) доказывает наилучшую известную верхнюю границу: пусть Ь = р~... р, — произведение первых г простых чисел. Вычислите Гс и все квадратичные остатки по модулю Ь за 0(2 "к !об Ь) шагов (поскольку имеется примерно 2 "Ь квадратичных остатков). Вычислите также все множители Ь, которые < т~, примерна эа гл /й последующих шагов. Теперь т сложений хватит для 2 вычисления 1~, 2~, ..., т~.
Имеем Ь = ехр(р, + 0(р„/(!обр„)'~~)), где р, получается из ответа к упр. 4.5.4-36 [см,, например, Сгеепе апб КпвСЬ, ЛХасЬ. Гог ГЬе Ала!угЗэ оГА!Зогйбшэ (Воз!оп: В!гЬЬаввег, 1981), 24.1.6]. Так, из выбора г = [(1+ -'!п2/18!Зт) !вт/1и!пт] следует, что Ц1з,...,т~) =т+0(т ехр(-(-., !п2 — «)!пт/!и!пт)). С другой стороны, Д. Добкин (П. ПоЬРбп) и Р. Липтон (В.
Ь!р1оп) показали, чта для любого с > О, ц1,..., т') > т+ тюз ' при достаточно большом т [БГСОМР 9 (1980), 121-125]. 39. Величина Ц[лл лю,,., л,»]) равна минимуму величины дуги — вершины + т, взятой по всем ориентированным графам, имеющим т вершин э„входные степени которых равны нулю, и одну вершину 1 с нулевой выходной степенью, где имеется ровна и, ориентированных путей от ээ до ! для 1 < ) < т. Цил ил..., и„,) представляет собой минимум величины дуги — вершины + 1, взятой по веем ориентированным графам, имеющим одну вершину э> входная степень которой равна нулю, и т вершин !1, выходные степени которых равны нулю, где имеется ровна п, ориентированных путей от э до ! для 1 < ! < пг, Эти задачи дувльны одна по отношению к другой, если изменить направление всех дуг. [См.
Х А!8ог!гЛгпз 2 (1981), 13-21.] Примечание. Х. Х. Пападимитру (С. Н. Рарабппййоа) заметил, что рассмотренная задача является частным глучаем более обшей теоремы. Пусть )у = (па) — матрица неотрицательных целых чисел размера т х р, не имеющая полностью нулевых строк или столбцов. Можно определить 1(Л') как минимальное число умножений, требующихся для вычисления множества иананамов (х,"... х ' ] 1 < !' < р).
Теперь !(!У) является также минимумам величины дуги — вершины + т, взятой по всем ориентированным графам, которые имеют т вершин э; е нулевыми входящими степенями и р вершин !э с нулевыми выхадныии степенями, где нмеетея в точности пп ориентированных путей ат э; к !! для каждых ! и у.
В соответствии с дуальностью имеем !(1г') = 1(!г'г ) + гп — р. [Ввйееш аг !Ле Еигор. Аээос. ТЛеог. Сошр. ЯсЛ 13 (ГеЬгпагу, 1981), 2-3.] Н. Пиппенгер (К. Р!ррепбег) доказал глубокое обобщение результатов упр. 36 и 37. Пусть Л(т, р, и) — максимум 1(1гг), который получен по всем матрицам Ф размера т х р, состоящих из неотрицательных целых чисел пц < и. Тогда Ь(т, р, п) = ш!п(гп, р)!8 и + Н!г !8Н+ Р(т+р+ Н(!об!обН)г!э(1обН) э!э), где Н = тр18(и+ 1). [81СОМР 9 (1980), 230-250.] 40. Согласна упр.
39 достаточно показать, что 1(тгпг + + тгпг) < !(гпг,...,гпг) + !([п„...,п,]). Но это очевидна, поскольку сначала можно построить (хнг',...,х а затем вычислить манонам (х ')"'...(х"")"', Нримечанне. Ниже приведен один строгий способ формулировки теоремы Оливоса: если аа, ..., а, и Ье, ..., Ь, являются произвольныии адлитивными цепочками, та !(~ е„а,Ь!) < г+ э+ ~ со — 1 для любой матрицы размера (с+ 1) х (э+1), состоящей из неотрицательных целых чисел сб. 41. [81СОМР 10 (1981), 638-646.] Указанная формула может быть доказана, только если А > 9т~. Поскольку это полинам от т и поскольку задача поиска минимального покрытия вершин лР-сложна (си.
раздел 7.9), задача вычисления !(пг,..., и,) является КР-полной. [Неизвестно, является ли задача вычисления 1(и) НР-полной. Однако весьма правдоподобна, что оптимальная цепочка для, скажем, 2 ь „' пе ы2"" приведет к появлению оптимальной цепочки для (пм..., п~ ) при достаточно больших А.] РАЗДЕЛ Я.б.Я 1. Присвоить у г- хэ, затем вычислить ((... (иэ„+гу+не г)у+ )у+пг)х. 2.
Замена х в (2) полиномам х + ха приводит к следующей процедуре. С1. Шаг С2 для !г = п, и — 1, ..., 0 (в такам порядке) и остановиться. С2. Присвоить еь +- ню затем присвоить аг +- в! + хаег+г для,!' = Л, !г + 1,..., и — 1 (Когда !г = и, просто присвойте в +- и .) 1 Вычисления оказываются идентичными вычислениям на шагах Н1 и Н2, но выполняются в другом порядке.
(Фактически это воплощение первоначальных идей Ньютона, связанные с использованием схемы (2).) 3. Коэффициент прн х равен полнному от у, который можно вычислить по правилу Горнера; (... (июох+ (н гну+ н„ьо))х+ . )х+ ((... (на, у+ но, -~)у+ )у+ но о). (Для "однородного" полинома, такого как и„х" +ил ~х" 'у+ . +н~ху" '+неу", более эффективна другая схема: если 0 < ]х] < ]у], сначала разделить х на у, вычислить полинам от х/у, а затем умножить на у".] 4. Правило (2) включает 4и или Зи вещественных умножений и 4и нли 7и вещественных сложений; схема (3) хуже: она требует 4и + 2 или 4и + 1 умножений, 4и + 2 или 4и + 5 сложений. 5.
Одно умножение для вычисления х~; (и/2] умножений и ]и/2] сложений для вычисления первой строки; (и/2) умножений и !и/2) — 1 сложений для вычисдения второй строки и одно сложение для суммирования обеих строк. Всего и+ 1 умножений и и сложений. 6. 31. Вычислить н запомнить значения хе, хо, ..., хо 2 в 1е!21 32. Присвоить с! +- вухо ~"~ для 0 < ! < и.
33. При Л = О, 1,..., и — 1 присвоить с! +- с~ + а!+~ при 7' = и — 1, ..., Л + 1, Л. 34. Присвоить с„е- с!х~е"~ э для 0 < / < и. Здесь (и + и)/2 сложений, и+ !и/2) — 1 умножений и и делений. Еше адно умножение и деление можно сэкономить, есви трактовать и„и со как частные случаи (см. ЯСАСТ №нв 7, 3 (Яншшег, 1975), 32-34]. 7.
Пусть х = хо+уй. Рассмотрим (42) и (44). Присвоить у! ь- и(х ) для О < у < и. Для Й = 1, 2,, и (в таком порядке) присвоить уэ < — у! — уз ~ при у = и, и — 1,..., Й (в таком порядке), Присвоить !З! е- у! для всех 71 Тем не менее, как объяснялось в разделе, ошибка округления будет нанвлливаться, даже если операции (5) выполняются с великолепной точностью. Лучшим способом осуществления инициализации, когда (5) выполняется с арифметикой с фиксированной точкой, является выбор !Зо, ..., /! таким образом, что н(хе) во а(хв) + (ля) (ох) о „( где ]со], ]е~], ..., ]в„] настолько малы, насколько зта возможно.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
