AOP_Tom2 (1021737), страница 193
Текст из файла (страница 193)
Патерсон (М. Б. Расегооп), М. Дж. Фишер (М. 1 Р!зсйег) и А. Р. Мейер (А. Н. Меуег) получили наилучшую нижнюю оценку порядка и !об и/(об !об и. опубликованную в Б1АМ/АМБ Ргосеесйпбз 7 (1974), 97-111, Она применима толька к машинам Тьюринга с множеством лент. 16. Пусть 2 ' — наименьшая степень 2, которая превышает 2К. Присвоим ас е- ы ' п~ и ь — 1~ш Нк-з — О' г Ь| +- шщ~ ~ О гз, где и~ — — О для 1 > К. Нужно вычислить свертки с, = 2 ' а,б, з для г = 2К вЂ” 2 — э при О < з < К. Свертки можно найти при помощи трек быстрых преобразований Фурье порядка 2~, как описано в разделе. [Заметим, что такой способ, который иногда называют "сЫгр-преобразование", пригоден для оперирования любыми комплексными числами ш, а ие только корнями из единицы.
[См. Ь. 1. В1певге1п, ХоггЛеаэг Е)есггоп!сэ Нея. алс) Епб. Меейлб Яесогг1 10 (1968), 218 — 219; П. Н. Ва1!еу апб Р. Х. БъагхггапЬег, ЯАМ йег1ев ЗЗ (1991), 389-404.) 17. Значение Р = К<~ы — К удовлетворяет Р~ = 2, Рг = 2Р„и Рж~.ь — — Р . Следовательно, Р„= 2'~-'эз, если и имеет указанный вид. Отсюда по индукции следует, что К„= Зм + 2,~ Зп2 ~ — ч '+з. Между прочим, К нечетно и можно умножать и-разрядное целое число на (и+ 1)- разрядное целое число, умножив (К„+ Кью)/2 1-разрядных чисел.
Производящая функция К(х) = 2 ь, К„э" удовлетворяет уравнению зК(з) + х~ = К(х~)(х+ 1)(з+ 2); отсюда К(-1) = 1 и К(1) = -'. 18. В следующей схеме используется 31т'+ Ян позиций в рабочем пространстве. Здесь в обозначениях предыдущего упражнения 8~ = О, Яз = 5 и 5ж-~ = Яп + 1, т. е. 8„= е, — е~ — Г+ 2 — [1= 1). Пусть М = 2п — е, где с равно О или 1, и предположим, что Х > 1. Для заданных Хчрвзрядных чисел и = 2" (ч + По и о = 2" $~~+ Ъо сначала формируются [Пе — У~ [ н [Ъо — 1 ~ [ в двух првзрядных областях, начиная с позиций О- и пй (ЗХ+ Яя )-разрядной рабочей области.
После этого произведение помещается в рабочую область, начиная с позиции Зп + Я„. Следующий шаг заключается в формировании 2(п — е)-рвзрядного произведения Г~ $'и начиная с позиции О. С помощью этого произведения изменяем Зп — 2с разрядов, начиная с позиции Зп+ Я„, и записываем в них значение (Л1) — (Ро — Сч )(и†11) + 2" Ц'г). (Заметим, что Зп — 2с + Зп + Я„ж ЗЖ + Би) В итоге формируется 2п-разрядное произведение Пе1ге, начиная с позиции О. Оно добавляется к частичному результату, начиная с позиций 2п+ Я„и Зп+ Я„.
Кроме того, необходимо переместить 2Ж-разрядный результат на его окончательное место, сдвинув его вниз на 2п+ з позиций. Окончательное перемещение может быть запрещено при помощи оригинального способа. который циклически сдвигает выходное значение на заданную величину внутри сформированной рабочей области. Егли 251-разрядное произведение не должно присоединяться к вспомогательной рабочей области, необходимо иметь еще около дг разрядов памяти (т. е. общее количество разрядов для ввода, вывода и временного хранения должно в этом случае равняться примерно 61з" разрядам вместо 5Ф).
См. В. Маебег, Ьесгиге №сез ш Сошр. Ясй 722 (1993), 59-65. 19. Пусть т = з + г при -е < г < э. Можно использовать (2) при У~ = [и/э). Пе = и шоб з, Ъ) = [о/з), 1ге = в шос) з, а з предоставить роль 2". Егчи известны знаки чисел (ч — Па и 1'~ — 1е, то известно также, как вычислить произведение [У~ — По[[1) — 1е[, которое < ш и нужно ли добавлять его или вычитать. Остается только умножить результат на в и з~ — ш — г. Каждая из этих операций может быть выполнена путем четырех умножений и/или делений при помощи способа, описанного в упр 3.2.1 1 — 9, но при этом потребуется только семь операций, так как одно из умножений, необходимых для вычисления эхшодт,— это умножение на г или т+ з.
Таким образом, достаточно 14 операций умножения и/или деления (либо 12 в случае, егли и = о или если и - — константа). Не имея возможности сравнивать операнды, мы смогли выполнить работу без единого дополнительного умножения за счет раздельного вычисления Поь) и С'~1е. РАЗДЕЛ 4.4 1. Выполнив сложение и умножение в системе счисления с основанием Вм получаем (... (а, Б о + а 1)Ь,„э+ + а1)Ьо+ пол. (Операции сложения и умножения на константу в системе счисления са смешанным основанием легко выполняются при помощи простого обобщения обычного правила переноса; см. упр.
4.3 1-9.) 2. Вычислим (и/Во), ((и/Во)/В~) и т. дз остатки суть Ао, Ао и т. д. Деление выполнено в системе счисления с основанием бм = 24(1ь 9 Начать с и Разделить на 16 Разделить на 14 Разделить на 8 Разделить на 20 Разделить на оо Остаток = 5 0 0 0 0 Остаток = 2 Остаток = 1 Остаток = 3 Остаток = 8 Реэульщогл. 8 длинных тонн, 3 хандредвейта, 1 стоун, 2 фунта, 5 унций 3. Предложенная Е Л.
Стилом (мл.) (С, Ь. Бгее!е, Лг.) и Налом Л Уайтам (Лоп Ь. ЪЧ1йсе) и впервые опубликованная в журнале САСИ 2,7 (Лц(у, 1959), 27, процедура обобщает алгоритм Д. Таранто для В = 2. А1. (Начальная установка.) Присвоить М л — О, 7эо < — О. А2. (Выполнено?) Если и ( е или и > 1 — е, то перейти к шагу А4 (В противном случае М-разрядная дробь будет удовлетворять заданным условиям.) А3. (Преобразовать.] Присвоить М < — М + 1, 17 и л- ',Ви), и < — Ви пшс1 1, е л — Ве и возвратиться к шагу А2. (Эта преобразование возвращает нас, па сути, в предыдущее состояние. Остается решить проблему преобразования дроби и в дробь В по основанию В с минимальным числом разрядов, но таким, чтобы удовлетворялось неравенство )П вЂ” и) < е. Заметим, однако, что теперь е может быть > 1; в таком случае можно сразу перейти к шагу А4 и не сохранить новое значение е.) А4.[Округлить.) Если и > 1, та увеличить П и на 1.
(Если равенство и = †' выполняется точно, то предпочтительнее пользоваться другим правилом округления: "увеличить 17 и на 1 толька тогда, когда оно нечетно". См. раздел 4.2.2.) $ л В таблице приняты следующие обозначения: Т. — длинные тонны, сюк --ханлродлейты, эл— стоуны, Оь — фунты, ол. — унции. — Вриьс верее. Начать с нуля Прибавить 3 Умножить на 24 Прибавить 9 Умножить на 60 Прибавить 12 Умножить на 60 Прибавить 37 Т. 0 0 0 О 0 О 8 8 6.
3 О 0 0 0 0 = 20(сий. 0 0 0 О 2 2 3 3 = 8(оС. О 0 0 0 5 5 1 1 = 60(1п. 12 4 21 2 0 О = 14((Ь. О 0 4 5 9 10 0 2 = 60 э.)) 37 32 45 43 8 0 16 оз.))) О 3 8 1 12 8 0 5 Число ЬГ ы на шаге А4 никогда не будет увеличиваться с  — 1 до В. В этом случае, если (ЬГ и =  — Ц должно быть ЛХ > О, ни одна из (М вЂ” Ц-разрядных дробей не обеспечивает достаточной точности. Стил и Уайт в работе ЯСРЬА!У №11сев 25, б (Лапе, 1990), 112-12б, продолжили анализ преобразований в формате с плавающей точкой, (См. также работу Д.
Э. Кнута в сборнике Веапсу !э Опт Впэгпеш, е!(11еб Ьу 1Ч. Н. Л. Еебеп ес а1. (Ке» Чог)с Брйп8ег, 1990), 233-242.) 4. (а) 1/2 = 5~/10~. (Ь) Все простые делители числа 5 делят В. 5. Это возможно толька в том случае, когда 10" — 1 < с < нд см. (3), 7. аи < их < аи + и/ш < ап + 1! следовательно, (аи) < (их) < (аи + Ц. Далее, для частного случая, оговоренного выше, имеем их < пи+а и (аи) = (пи+а -е) для 0 < е < с!. (Может случиться только на первой итерации согласно упр. 7.) (Может быть минус нуль.) гь+! 9. Пусть 1Ч = 2 . При выполнении вычислений происходит присвоение Поэтому д = (и/10+ г ), где е = —,' (1 — (и+ ц/1Ч).
Так как 1Ч шо!1 10 ы б и О < е„< 1/10 при 0 < н < 1Ч, то д = (н/10) при О < и < )Ч+ 4. Котла и принадлежит этому интервалу, получаем г = и шой 10+ 11 — (и+ 1+ 5В„)/1Ч), где В = лв !(и+ ц шо!1 ф. Если В„велико (к примеру, Ве ж 7Ч/8 — й где 0 < 1 < /Ч/40), получаем а+ 1 = 51 (по модулю Ю)/8. Таким образом, и+ 1 + 5В„< 1Ч при и < Ж/2. В противном случае В„< !'1/8 — 1Ч/40 = 1Ч/10, и снова получаем и+ 1+ В < !Ч прн а < !Ч/2. Случаи, когда н = )Ч/2, )Ч/2 + 1! Ж/2+ 2 и Ю/2 + 3, как легко видеть, не создают проблем. Но когда и = 1Ч/2 + 4, находим и шо!1 10 = 2 и г = 1.
(Альтернативный вариант г г- и — 89, г г — г — 29 будет выполняться в ббльшем интервале, но на 8-битовом компьютере немного медленнее. Это упражнение основано на идеях Р. А. Воувелса (Н. А, !Уо!ге!в)! Ацясгайап Согпр. Л. 24 (1992), 81-85.) 10. (1) Сдвинуть вправо на один разряд, (й) извлечь левый бит каждой группы; (ш) сдвинуть на два разряда результат, полученный в (й); (гу) сдвинуть этот результат вправо на один разряд и сложить его с результатом (й); (т) Вычесть результат (ге) из результата (!). 8. ЕИТ1 ЬРА 1Н ИШ.
38 ЕТА ИОЬ 5ЬАХ АРР БАИИ ЬРА РЕСА ЛИР 28 ЯТА ЬРА 1ИС1 ЛАР 0 0 =1//10 ТЕИР =-10 5 0 2Р ТЕИР 1 ЗВ АИЕИЕЕ. 1 ТЕИР 1 19 (2' — Ц(2'+Ц(г'+Ц (2" +Ц | (8Л вЂ” 1 ц гз" ("+ц~ 15 А ("+ц ' 11. 5.7 72 1 — 10 4 7.72 1 — 9 4 З В З.Е) 766 3066.1 6132 24529 Результате (24529)1о. 12. Сначала преобразуем число, представленное в троичной системе, в девятеричную систему, а затем поступаем так же, как при преобразовании числа из восьмеричной системы счисления в десятичную, но без удвоений.
Преобразование из десятичной системы в девятеричную выполняется аналогично. 1) данном примере имеем следующее. 7654 144 + 1 4 160 + 1 б 109739 — 10973 3 9 4 Резульпеат: (987654)1о. 98 7 б 5 176 (Разделяющая точка в первой строке.) пило о+39 ОРСО -40 10 Сбросить признак переполнения. Установить указатель буфера. Установить счетчик циклов. Начать программу умножения. 0 САЕЕХ (См. упр. 4.3,1-13 с о=10 иИ=О) гА < — следующие девять разрядов. 28 5 Запомнить следующие девять разрядов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
