Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 85
Текст из файла (страница 85)
15. Известная наилучшая верхняя оценка, равная 0(п(!об п)~ !ой1об и), предложена М. Дж. Физлером (М. 3. Рыс)зег) и Л. Дж. Штокмейером (1.. 1. Я»ос)зшеуег) (Х Сошр. аозт Яузе, Яс»1 9 (1974), 317-331]. Рассматриваемая ими конструкция ориентирована на машину Тьюринга с множеством лент: для маппзи с указателямн эта оценка равна 0(н!обп), М. С.
Патерсон (М. Б Расегзоп), М. Дж. Фишер (М. 3. Рыс!зег) и А. Р. Мейер (А. Н. Меуег) получили наилучшую нижнюю оценку порклка и !об и/зок !об и, опубликованную в ЯАМ/АМЯ Ргосеез(зпбз 7 (1974), 97-111. Она применима только к машинам Тьюринга с множеством лент. -Ро 16. Пусть 2" — наименьшая степень 2, которая превышает 2К. Присвоим а~ о-ы '!око и Ь| +- ы, где во = 0 для 1 > К. Нужно вычислить свертки с„= 2„"", о а;Ь., для Ы» -ь- цоуз г = 2К вЂ” 2 — о при 0 < в с К. Свертки можно найти при помощи трех бйстрых преобразовамий Фурье порядка 2~, как описано в разделе.
[Заметим, что такой способ, который иногда называют»с)пгр-преобразование«, пригоден для оперирования любыми комплексмымм числами ы, а не талька корнями из единицы. [См. Ь. 1. В!повсе!и, Хаггбсаог Е!вягаокя йеа олд Епб. Меейвб йесоЫ 10 (1968), 218-219; П, Н. ВМ!еУ апд Р. Х, БвызсгавЬег, ЯЬ4М йео!ем 33 (1991), 369-404,) 17. Зиачемие Р = К«ы — К„удовлетворяет Р1 = 2, Рз« = 20» и Рз«тг = Р . Следовательно, Р = 2«1-'+з, есля и имеет указаммый вид. Отсюда по иидукции ошедует, что К = 3'1+ ~,'»,3«~2«1-«~-'+о, Между прочим, К нечетко я можно умножать и-разрядиое целое число иа (и+ 1)- разрядное целое число, умиожив (К„+ К„+,)/2 1-разрядмых чисел.
Производящая функция К(о) = 2 „, К л«удовлетворяет уравнению зК(з) + о~ = К(о~)(х + 1)(о + 2): отсюда К( — 1) = 1 и К(1) = -. 16. В следующей схеме используется ЗХ+ Я» позиций в рабочем пространстве. Здесь в обозначениях предыдущего упражнения Я~ = О, Ят = Я„и Ят -1 = Я» + 1, т. е. Я» = г~ — е~ -!+ 2- [4 = 1[. Пусть Х = 2и-е, где е равно 0 или 1, и предположим, что Х > 1. Для зэдамиых Х разрядмых чисел и = 2" (/г+ (/о и е = 2" У1 + Уо смачала формируются [Ьо — (/~ [ и [Уо — !) [ в двух и-разрядных областя, начиная с позиций 0- и и-й (ЗХ+ Я» )-разрядной рабочей области.
После этого произведение помещается в рабочую область, мачимая с позиции Зи+ Я . Следующий шаг заключается в формировапии 2(и — е)-разрядмога произведения (/~ Уп начиная с позиции О. С помощью этого произведения изменяем Зи — 2о разрядов, начиная с позиции Зи+ Я», и записываем в них значение (/1 У) — (Ро — Ьг|)((зов У1) + 2"Ь11ь (Заметим, чта Зи — 2е+ Зи+ Я» ы ЗХ+ Я».) В итоге формируется 2и-разрядмое произведение ЫоУо, иачимая с позиции О. Омо добавляется к частичному результату, начиная с позиций 2и + Я» и Зи + Я„. Кроме того, необходимо переместить 2Х-ркорядпый результат иа его окончательное место, сдвинув его вниз ма 2и+Я„позиций. Окончательное перемещение может быть запрещено при помощи оригимальиого способа, который циклически сдвигает выхадмое значение ма заданную величину внутри сформированной рабочей области.
Если 2Х-разрядмое произведение ме должно присоедимятьгя к вспомогательной рабочей области, необходимо иметь еще около Х разрядов памяти (т. е. общее количество разрядов для ввода, вывода и временного храпения должно в этом случае равняться примерно 6Х разрядам вместо ЬХ). См. й. Мэепег, ЬесГвгс Хапм (и Сотар. Яс!. 722 (1993)„69-6Ь, 19. Пусть т = от + г при — о < г < о.
Можно использовать (2) мри (/1 = [и/о), По = и шобо, 1'г = [е/о), Уо = е шайо, а о предоставить роль 2". Если известны знаки чисел Ь'1 — Ьо и 1 о — 16, то известно также, как вычислить произведение [!й — Го[ ['г) — Уо[, которое < ш и нужно ли добавлять его или вычитать. Остается только умпажить результат на о и о~ щ -г. Каждая из этих операций может быть выполнена путем четырех умиажемий и/или делений при помощи способа, оимсамиого в упр, 3,2.1.1-9, мо при этом потребуется талька семь операций, твк как адио из умножений, необходимых для вычисления ос шой ги,— это умножение иа г или г + в.
Таким образом, достаточно 14 операций умножения и/или деления (либо 12 в случае, если и ж е или если и — константа). Не имея возможности сравнивать операнды, мы смогли выполнить работу без едимого дополнительного умножения за счет раздельного вычиглеиия По У! и Ь| 1'о. РАЗДЕЛ 8.4 1. Выполнив сложеиие и умножение в системе счисления с основанием Вз, получаем (...(а Ь, ~ + а ~)Ь т + .. + а~)Ье + аев. (Операции сложения и умножения иа константу в системе счисления со смешанным основанием легко выполияются при помощи простого обобщения обычиого правила переноса; см. упр.
4.3,1-9.) 2. Вычислим (и/Вв), ((и/Ве) /Щ и т. дд остатки суть Ап, А~ и т. д. Деление выполнено в системе счисления с основанием Ьу. Начать с и Разделить иа 16 Разделить на 14 Разделить ца 8 Разделить на 20 Разделить на оо 3 0 О 0 О 0 Остаток = 5 Остаток = 2 Остаток = 1 Остаток = 3 Остаток = 8 Рсзулыпапь 8 длиииых тонн, 3 ющдредвейта, 1 стоун, 2 фунта, 5 унций. 3.
Прсдложеииая Г. Л. Стилом (мл.) (О. Е, бсее)е, Лг.) и Йоиом Л, Уайтом (Лов 1. ЖЫсе) и впервые опубликованная в журнале САСМ 2,7 (1п1у, 1959), 27, процедура обобщает алгоритм Д. Тараито для В = 2. А1. (Начальная установка.) Присвоить М с- О, бо +- О. А2. (Выполнено?) Если и < г или и > 1 — с, то перейти к шаху А4. (В противном случае М-разрядная дробь будет удовлетворять заданным условиям.) А3. (Преобразовать,) Присвоить М +- М+ 1, 11-м +- 1Ви), и+- Вищоб1„с +- Вс и возвратиться к шагу А2. (Это преобразование возвращает иас, по сути, в предыдущее состояние.
Остается решить проблему преобразования дроби и в дробь 1/ по осиоваиию В с минимальным числом разрядов, ио таким, чтобы удовлетворилось неравенство (1/ — и) < г. Заметим, однако, что теперь с может быть > 1; в таком случае можно сразу перейти к шагу А4 и ие сохранять новое значение а) А4. (Округлить.) Если и > -', то увеличить (/-м иа 1. (Если равенство и = -' выпалняетсв точно, то предпочтительнее пользоваться другим правилом округлеиия: 'увеличить П м на 1 только тогда, когда оцо нечетио".
См. раздел 4.2.2.) $ ' й таблице приняты следующие обозначения: Т. — длинные тонны, сюь — яаидредвейты, гав стоуны, 1Ь. — фунты, ою — уники, — Ирам. вере». Начать с нуля Прибавить 3 Умиожить на 24 Прибавить 9 Умножить па 60 Прибавить 12 Умножить иа 60 Прибавить 37 Т. о О о о 0 0 8 8 = 20(сит. 0 о о о 2 2 3 3 = 24(Ь. 9 5 0 0 О 0 = 8(вФ. о о о О 5 5 1 1 = 60(ш. 12 4 21 2 0 О ы 14(!Ь. о о 4 5 9 10 о 2 = 60 в.)) 37 32 45 43 8 0 = 16 оз.))) О 3 8 1 12 8 О 5 Число (/ и ив нате А4 никогда ие будет увеличиваться с  — 1 до В. В этом случае, если (П-и =  — 1) должио бьггь М > О, ии одна из (М -1)-разрядиых дробей ие обеспечивает достаточной точности.
Стил и Уайт в работе ЯОР(.АУ Мог(сая 25,6 (Липе, 1990), 112-126, продолжили анализ преобразоваиий в формате с плавающей точкой. (См. также работу д. Э, Кнута в сборнике Веаису )а Оиг Виилиа, еб1себ Ьу %. Н. Л. реОеп ес а1. (Хну уог)с брппбег, 1990), 233 — 242.) 4. (в) 1/2ь = бь/10ь. (Ь) Все простые делители числа 5 делят В. б. Это возможио только в том случае, когда 10" — 1 < с < ич см, (3). 7. аи < их < аи+ и/н < аи+ 1; следжателъио, (аи) < (их) < (аи+ Ц. Далее, для частного случая, оговоренного выше, имеем их < аи+а и (аи) = (аи+а-с) для 0 < с < а.
(3(ожет случиться только иа первой итерации согласна упр. 7.) (Может быть минус нуль,) якм 9. Пусть Х = 2 . При выполиеиия вычислеиий происходит присвоеиие о+- — —...— (и+1) = ~- — (и+1)~. ) (2я 1) (2ь + 1) (2в + 1) (2я" + 1) ( ) 3 )у' 1 2в ''' 2вь 15 Ю Поэтому ц = '1и/10+с„), где с„= ~ (1 — (и+ 1)/)ь). Так как /9 пки1 10 = 6 и О < с < 1/10 при 0 < и < Х, то д = (и/10) при О < и < /у'+4. Когда и принадлежит этому интервалу, получаем г = и пюб 10+ ) 1 — (и+ 1+ 56 )/Х~, где В„= ьу1(и+ 1) шов( лв. Если 6 велико (к примеру, д„= Ф/8 — 1, где 0 < Г < Х/40), получаем и + 1 ш 51 (по модулю Ж)/8. Таким образом, и + 1 + 56„< К при и < ьУ/2.
В противном случае 6„< Р//8 — Х/40 = М/10, и снова получаем и+ 1+ 6 < Х при и < /У/2. Случаи, когда им Х/2, Х/2+1, Х/2+2 и Ж/2+3, как легко видеть, ие создают проблем. Ио когда и = )у'/2+ 4, иаходим и шоб 10 = 2 и г = 1. (Альтериативиый вариант г ь- и — 86, г ь- г — 29 будет выполияться в ббльшем интервале, ио иа 8-битовом компьютере немного медленнее. Это упражнение освоввио иа идеях Р. А. Воувелса (В, А. Уоие1я), Аивггайап Сошр. Х 24 (1992), 31-85.) 10.
(1) Сдвинуть вправо иа один разряд; (й) извлечь левый бит каждой группы; (п|) сдаииуть иа два разряда результат, получеииый в (Н); (гг) сдвинуть этот результат вправо иа один разряд и сложить сто с результатом (ш); (у) Вычесть результат (! у) из результата (1). 8. ЕИТ1 104 1Н ИШ. ЗЕ ЗТА ИШ 3113 400 14ИИ ЫМ ОЕС1 ЛИР 2Н ЗТЕ Ий П1С1 ЛЕР О О ь1//10ь ТЕИР -10" 6 0 2Р ТЕИР 1 33 433983.1 ТБИР 1 1В 11. 5.778 1 — 1 О 47.781 94 38 3.81 766 ЗО66.1 61З2 24529 Результат: (24529) 1е. 12, Сначала преобразуем число, представленное а троичной системе, е деаятеричиую систему, а затем поступаем так же, как при преобразовании числа из восьмеричной системы счисления и десятичную, но без удаоений. Преобразонаине из десятичной системы а девятеричиую выполняется аналогично. В данном примере имеем следующее. 1219з.гз 1219З 109739 10973 з 9 4 Результатз (987654)~е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
