16. Пусть 2* -наименьшая степень 2, которая превышает 2К. Присвоим at <- о; щ и bt <- о;-- где щ = О для t > К. Нужно вычислить свертки Сг = Z]j=oД- г = 2К - 2-3 при О < S < А". Свертки можно найти при помощи трех быстрых преобразований Фурье порядка 2*, как описано в разделе. [Заметим, что такой способ, который иногда называют "chirp-преобразование", пригоден для оперирования любыми комплексными числами Ui, а не только корнями из единицы. [См. L. I. Bluestein, Northeast Electronics Res. and Eng. Meeting Record 10 (1968), 218-219; D. H. Bailey and P. N. Swarztrauber, SIAM Review 33 (1991), 389-404.]

17. Значение Z)„ = Kn+i - Kn удовлетворяет Di = 2, D2n = 2Z)„ и Z)2n+i = Dn. Следовательно, Dn = 21-+, если n имеет указанный вид. Отсюда по индукции следует, что Кп = З! -(-Е(=2 32-"+-

Между прочим, Кп нечетно и можно умножать п-разрядное целое число на {п + 1)-разрядное целое число, умножив (Кп + Kn+i)/2 1-разрядных чисел. Производящая функция K{z) = Еп>1 Enz" удовлетворяет уравнению zK(z} + z = K{z)(z + l){z + 2); отсюда A(-l) = 1 и A(l) = f

18. В следующей схеме используется 3N + Sn позиций в рабочем пространстве. Здесь в обозначениях предыдущего упражнения Si = О, Sin = 5„ и 52n-i = 5п -I- 1, т. е. 5„ = ei-et-t + 2 - [t = l]. Пусть N = 2п - е, где е равно О или 1, и предположим, что N > 1. Для заданных iV-разрядных чисел и = 2"[/i +Uo nv = 2"Vi +Vo сначала формируются \Uo -Ui\ и Vb - Ti в двух п-разрядных областях, начиная с позиций О- и п-й (3iV-- 5л)-разрядной рабочей области. После этого произведение помещается в рабочую область, начиная с позиции Зп -I- 5п. Следующий шаг заключается в формировании 2(п - е)-разрядного произведения UiVi, начиная с позиции 0. С помощью этого произведения изменяем Зп-2е разрядов, начиная с позиции Зп -I- 5„, и записываем в них значение UiVi - {Uo - Ui){Vo -Vl) + 2"-UiVi. (Заметим, что Зп - 2e + Зп + Sn = 3N + Sn-) В итоге формируется 2п-разрядное произведение UqVo, начиная с позиции 0. Оно добавляется к частичному результату, начиная с позиций 2п + Sn и Зп + Sn- Кроме того, необходимо переместить 27У-разрядпый результат на его окончательное место, сдвинув его вниз на 2n -I- Sn позиций.

Окончательное перемещение может быть запрещено при помощи оригинального способа, который циклически сдвигает выходное значение на заданную величину внутри сформированной рабочей области. Если 2N-pa3pHflHoe произведение не должно присоединяться к вспомогательной рабочей области, необходимо иметь еще около N разрядов памяти (т. е. общее количество разрядов для ввода, вывода и временного хранения должно в этом случае равняться примерно 6N разрядам вместо 5N). См. R. Maeder, Lecture Notes in Сотр. Sci. 722 (1993), 59-65.

19. Пусть m = s + г при -s < г < s. Можно использовать (2) при Ui = [u/sj, Uo = umods, Vl = [v/s\, Vo = i;mods, a s предоставить роль 2". Если известны знаки чисел Ul - Uo к Vl - Vo, то известно также, как вычислить произведение \Ui - Uo\ \Vi - Vo\, которое < m и нужно ли добавлять его или вычитать. Остается только умножить результат на S и s = -г. Каждая из этих операций может быть выполнена путем четырех умножений и/или делений при помощи способа, описанного в упр. 3.2.1.1-9, но при этом потребуется только семь операций, так как одно из умножений, необходимых для вычисления si modm, - это умножение на г или г + з. Таким образом, достаточно 14 операций умножения и/или деления (либо 12 в случае, если и = i; или если и - константа). Не имея возможности сравнивать операнды, мы смогли выполнить работу без единого дополнительного умножения за счет раздельного вычисления UoVi и UiVo.

РАЗДЕЛ 4.4

1. Выполнив сложение и умножение в системе счисления с основанием Bj, получаем

(. . . (Ombm-l + am-l)bm-2 Ч-----Ь ai)6o + Оо*.

(Операции сложения и умножения на константу в системе счисления со смешанным основанием легко выполняются при помощи простого обобщения обычного правила переноса; см. упр. 4.3.1-9.)

2. Вычислим [u/BoJ, LLV-oJ/SiJ и т. д.; остатки суть Ао, А\ и т. д. Деление выполнено в системе счисления с основанием bj.

Результат. 8 длинных тонн, 3 хандредвейта, 1 стоун, 2 фунта, 5 унций.

3. Предложенная Г. Л. Стилом (мл.) (G. L. Steele, Jr.) и Ионом Л. Уайтом (Jon L. White) и впервые опубликованная в журнале САСМ 2,7 (July, 1959), 27, процедура обобщает алгоритм Д. Таранто для 5 = 2.

А1. [Начальная установка.] Присвоить М <- О, [/о <- 0.

А2. [Выполнено?] Если и < е или и > 1 - е, то перейти к шагу А4. (В противном случае М-разрядная дробь будет удовлетворять заданным условиям.)

A3. [Преобразовать.] Присвоить М <- М -I- 1, U-m <- [Ви\, и <- Su mod 1, е <- Be и возвратиться к шагу А2. (Это преобразование возвращает нас, по сути, в предыдущее состояние. Остается решить проблему преобразования дроби и в дробь и по основанию В с минимальным числом разрядов, но таким, чтобы удовлетворялось неравенство \U - и\ < е. Заметим, однако, что теперь е может быть > 1; в таком случае можно сразу перейти к шагу А4 и ие сохранять новое значение е.)

А4. [Округлить.] Если и > 5, то увеличить U-m на 1. (Если равенство и = 5 выполняется точно, то предпочтительнее пользоваться другим правилом округления: "увеличить U-m на 1 только тогда, когда оно нечетно". См. раздел 4.2.2.)

* В таблице приняты следующие обозначения: Т. -длинные тонны, cwt. - хандредвейты, st. -стоуны, /6. - фунты, 0Z.-унции. - Прим. перев.

Число U~m на шаге А4 никогда не будет увеличиваться с В - 1 до В. В этом случае, если (U-m = В - 1) должно быть М > О, ни одна из (М - 1)-разрядных дробей не обеспечивает достаточной точности. Стил и Уайт в работе SIGPLAN Notices 25,6 (June, 1990), 112-126, продолжили анализ преобразований в формате с плавающей точкой. (См. также работу Д. Э. Кнута в сборнике Beauty is Our Business, edited by W. H. J. Feijen et al. (New York: Springer, 1990), 233-242.)

4. (a) 1/2* = 5*/10*. (b) Все простые делители числа 6 делят В.

5. Это возможно только в том случае, когда 10" - 1 < с < u); см. (3).

7. аи < их < аи + u/w < аи + I; следовательно, [аи\ < [их} < [аи + 1J. Далее, для частного случая, оговоренного выше, имеем их < аи+а и [auJ = [au+a -eJ для О < е < а.

8. ENT1 О LDA и

1Н HUL =1 10= ЗН STA TEMP

MUL =-10=

SLAX 5

ADD и

JANN 2F

LDA TEMP (Может случиться только

DECA 1 на первой итерации

JMP ЗВ согласно упр. 7.)

2Н STA ANSWER, 1 (Может быть минус нуль.) LDA TEMP INCl 1

JAP IB I

9. Пусть N = г*"*. При выполнении вычислений происходит присвоение

(2-1) (2 + 1) (2 + 1) (2 +1) 21 2* 2* 2*

Поэтому q = [u/lO + CuJ, где Си = j(l - (и + 1)/7V). Так как TVmodlO = 6 и О < Cu < 1/10 при О < U < iV, то q = [u/lOJ при О < и < iV + 4.

Когда и принадлежит этому интервалу, получаем г = и mod 10 + [1 - (и + 1 + Ъви)/М\, где ви = {и + 1) mod f. Если ви велико (к примеру, ви = ЛГ/8 - t, где О < f < N/40), получаем и + 1 = 5f (по модулю Л)/8. Таким образом, и + 1 + Ъви < N при и < N/2. В противном случае ви < N/8 - N/40 = N/10, и снова получаем и + 1 + ви < N при и < N/2. Случаи, когда и = N/2, N/2 +1, N/2 + 2 и Л72 + 3, как легко видеть, не создают проблем. Но когда и = N/2 + 4, находим и mod 10 = 2 и г = 1.

[Альтернативный вариант г <- и - 8q, г <- г - 2q будет выполняться в ббльшем интервале, но на 8-битовом компьютере немного медленнее. Это упражнение основано на идеях Р. А. Воувелса (R. А. yowels), Australian Сотр. J. 24 (1992), 81-85.]

10. (i) Сдвинуть вправо на один разряд; (ii) извлечь левый бит каждой группы; (iii) сдвинуть на два разряда результат, полученный в (ii); (iv) сдвинуть этот результат вправо на один разряд и сложить его с результатом (iii); (v) Вычесть результат (iv) из результата (i).