в статье А. Эдельмана (А. Edelman), опубликованной в журнале SIAM Review 39 (1997), 54-67, описан неизвестный, но очень поучительный "прокол" в чипе Pentium разработки 1994 года, связанный с реализацией программы деления. Минимально достижимое при аппаратной реализации время выполнения операций сложения и умножения исследовалось в работах S. Winograd, JACM 12 (1965), 277-285, 14 (1967), 793-802, R. P. Brent, IEEE lirans. C-19 (1970), 758-759, и R. W. Floyd, EOCS 16 (1975), 3-5 (cm. также раздел 4.3.3E).

УПРАЖНЕНИЯ

1. [42] Изучите раннюю историю классических алгоритмов выполнения арифметических операций по оригинальным произведениям, скажем. Сунь Цю, аль-Хорезми, аль-Уклидиси, Фибоначчи (Fibonacci) и Роберта Рекорде (Robert Recorde), и как можно точнее перескажите их методы на строгом языке алгоритмов.

2. [15] Обобщите алгоритм А таким образом, чтобы он осуществлял сложение в столбик, вычисляя суммы тп неотрицательных тг-разрядных целых чисел. (Предположите, что т < Ь.)

3. [21] Разработайте MIX-программу, реализующую алгоритм из упр. 2, и оцените время ее выполнения как функцию от m и тг.

► 4. [М21] Приведите формальное доказательство корректности алгоритма А, основываясь на методе индуктивных утверждений, описанном в разделе 1.2.1.

5. [21] Алгоритм А выполняет сложение двух вводимых чисел, двигаясь справа налево, но иногда данные более доступны для считывания слева направо. Разработайте алгоритм, который выдает тот же ответ, что и алгоритм А, но порождает разряды результата слева направо и, если происходит перенос, делающий предыдущее значение неверным, возвращается назад, чтобы изменить предыдущее значение. [Замечание. В ранних индусских и арабских манускриптах, посвященных сложению слева направо, используется именно такой способ сложения. Вероятно, причиной тому послужила ориентация алгоритма А на выполнение операций слева направо на абаках. Алгоритм сложения справа налево стал логическим продолжением этого алгоритма благодаря работам аль-Уклидиси, возможно, потому, что арабы пишут справа налево.]

► 6. [22] Разработайте алгоритм, который выполняет сложение слева направо (как в упр. 5), «о никогда не запоминает разряд результата, пока существует возможность его изменения из-за последующих переносов. Уже занесенные значения результата не должны изменяться после запоминания очередного значения любого разряда. [Указание. Следите за количеством последовательных разрядов (Ь-1), которые еще не хранятся в результате.] Алгоритм такого вида удобен, например, в ситуации, если вводимые и выводимые числа считываются и записываются на магнитную ленту или если они появляются в простом линейном списке.

7. [М26] Определите среднее число случаев, когда выполнение алгоритма из упр. 5 приведет к необходимости возврата при переносе и изменению к разрядов частичного ответа для к = 1, 2, 71. (Предполагается, что оба входных числа имеют независимые и равномерные распределения на интервале О и 6" - 1.)

8. [М26] Разработайте программу для MIX, реализующую алгоритм из упр. 5, и определите среднее время ее работы, исходя из ожидаемого числа переносов, которое подсчитано в тексте.

► 9. [21] Обобщите алгоритм А так, чтобы получившийся алгоритм складывал два тг-раз-рядных числа в системе счисления со смешанным основанием Ьо, bi, ... (спргша налево).

Таким образом, наименее значимый разряд расположен в интервале от О до bi - 1 и т. д. (см. формулу 4.1-(9)).

10. [18] Будет ли правильно работать программа В, если поменять местами команды в строках Об и 07, а также в строках 05 и Об?

11. [10] Разработайте алгоритм сравнения двух неотрицательных тг-разрядных целых чисел и = {Un-i MiUo)i> VI V = {vn-i vivo)b, который определяет, какое из неравенств, и < V, и = V или и > V, выполняется.

12. [16] В алгоритме S предполагается, что заранее известно, какой из двух исходных операндов больше. Даже если информация отсутствует, все равно можно начать и так или иначе выполнить вычитание, но при этом обнаружится, что лишнее "заимствование" сохранилось до самого конца алгоритма. Постройте другой алгоритм, в котором можно было бы использовать (если в конце работы алгоритма S имеется "заимствование") дополнение (Wn-i WiWo)b и поэтому вычислять абсолютное значение разности между и и v.

13. [21] Разработайте программу для MIX, которая умножает (Un-i •. • wiWo)i. на v, где v - произвольное число, представляемое с однократной точностью (т. е. О < v < Ь), и получает в результате {wn WiWo)b- Каково время ее выполнения?

► 14. [М22] Приведите формальное доказательство корректности алгоритма М, основываясь на методе индуктивных утверждений, который описан в разделе 1.2.1 (см. упр. 4). 15. [М20] Если необходимо сформировать произведение двух тг-разрядных дробных частей чисел (.uiM2 . • • Un)b x {-УгУг Vn)b, а в качестве результата получить только тг-разряд-ное приближение (.12 ... и>п)ь, можно при помощи алгоритма М вычислить 27г-разряд-ный результат, который затем округлить до требуемого приближения. Но на это потребуется вдвое больше вычислительных затрат, чем необходимо для достижения приемлемой точности, так как учет произведения UiVj при i + j>n + 2 оказывает лишь незначительное влияние на результат.

Оцените максимальную ошибку, которая может возникнуть, если произведения UiVj при i + j>n + 2B ходе умножения будут полагаться равными нулю вместо того, чтобы вычисляться.

► 16. [20] {Короткое деление.) Постройте алгоритм деления неотрицательного тг-разряд-ного целого числа {un-i uiUo)b на v, где ij -целое число, заданное с однократной точностью (т. е. О < 11 < 6), получив частное {wn-i ШЮо)ь и остаток г.

17. [Л/20] В обозначениях рис. 6 предположим, что Vn-i > 1Ь/2\. Покажите, что если tin = Vn-i, то должно выполняться либо равенство q = b - 1, либо равенство q = Ь - 2.

18. [М20] В обозначениях рис. 6 покажите, что если q = [(и„Ь + Un-i)/{vn-i + 1)J, то q < q.

► 19. [Afi] В обозначениях рис. 6 пусть q - некоторое приближение к g и f = и„Ь -I-

- qvn-i- Предположим, что Vn-i > 0. Покажите, что если qvn-2 > bf + Un-2, то q < q. [Указание. Усовершенствуйте доказательство теоремы А, исследовав влияние

величины Vn-2-]

20. [М22] Используя обозначения и предположения из упр. 19, покажите, что если qVn-2 < bf + Un-2, то q = q или q = q - 1.

► 21. [M23] В обозначениях из упр. 19 и 20 покажите, что если Vn-i > LVJ и qvn-2 < bf+Un-2, но q ф q,Tou mod v > {l - 2/b)v. (Последнее событие происходит с вероятностью, приблизительно равной 2/Ь, так что если b есть размер машинного слова, то в алгоритме D (за крайне редкими исключениями) должно выполняться равенство qj = q.)

► 22. [24] Приведите пример деления четырехразрядного числа на трехразрядное, для которого необходимо включение в алгоритм D шага D6, если основание системы счисления-10.

23. [М23] Докажите, что для заданных целых чисел v и и, таких, что 1 < v < Ь, всегда выполняются неравенства [b/2j < vlb/{v + 1)J < (i; + l)lb/{v + 1)J < b.

24. [M20] Используя закон распределения наиболее значимых разрядов, описанный в разделе 4.2.4, получите приближенную формулу вероятности того, что d = 1 в алгоритме D. (При d = 1 можно, разумеется, опустить большую часть вычислений на шагах D1 и D8.)

25. [26] Напишите программу для MIX, реализуюш;ую шаг D1 алгоритма D, что необходимо для завершения программы D.

26. [21] Напишите программу для MIX, реализующую шаг D8 алгоритма D, что необходимо для завершения программы D.

27. [М20] Докажите, что в начале шага D8 алгоритма D ненормализованный остаток {un-i ... uiuo)i> всегда является точным кратным d.

28. [МЗО] (А. Svoboda, Stroje па Zpracovan/Jnformacj 9 (1963), 25-32.) Обозначим v = (vn-i . ViVo)b для любого целого основания b при Vn-i ф 0. Выполним следующие действия.

N1. Если Vn-\ < b/2, умножим v на [{Ь + l)/{vn-i + 1)J. Обозначим результат этого шага через {vnVn-i . vivo)b.

N2. Если Vn = О, присвоим v *- v + {l/b)\b{b - Vn-i)/{vn-i + и пусть результатом этого шага будет {vnVn-i vq.v- .. .)ь- Будем повторять шаг N2 до тех пор, пока не получим Vn ф 0.

Докажите, что шаг N2 выполнится не более трех раз и что в конце вычислений всегда будет Vn-\K Vn-\ = 0.

[Замечание. Если оба числа ии v умножить на указанные выше константы, значение частного u/v не изменится, а делитель примет вид {lOvn-2 Vo.v-iV-2V-3)b. Такой вид делителя очень удобен, так как в обозначениях алгоритма D в начале шага D3, если {uj+n+i,Uj+n) = (1, 0), в качестве пробного делителя берется q = Uj+n или q = b- 1.]

29. [15] Докажите или опровергните следующее утверждение: в начале шага D7 алгоритма D равенство Uj+n = О выполняется всегда.

► 30. [22] В случае ограниченного объема памяти при выполнении некоторых алгоритмов, описанных в этом разделе, для ввода и вывода информации желательно отводить одни и те же ячейки памяти. Можно ли при выполнении алгоритма А или S хранить числа Wo, wi, Wn-i И Uo, ..., Un-1 ИЛИ vo, ..., Vn-1 B ОДНИХ и тех же ячейках памяти? Можно ли допустить, чтобы при выполнении алгоритма D значения частного qo, .., qm занимали те же ячейки памяти, что и Un, Um+n? Допустимо ли перекрытие ячеек памяти, используемых при выполнении алгоритма М для хранения входных и выходных данных?

31. [28] Пусть основание системы счисления 6 = 3 и и = (um+n-i ••"10)3, v = (vn-i.. .viVo)3 - целые числа, заданные в уравновешенной троичной системе счисления (см. раздел 4.1), причем Vn-i ф 0. Напишите алгоритм деления и на v, вычисляя остаток, абсолютное значение которого не должно превышать \v\. Попробуйте найти алгоритм, достаточно эффективный для аппаратной реализации на компьютере со встроенной уравновешенной троичной арифметикой.

32. [М40] Предположим, что основание системы 6 = 2г, а числа и и v - комплексные числа, представленные в мнимочетверичной системе счисления. Постройте несколько алгоритмов деления и на с возможны.м вычислением остатка и сравните их эффективность.

33. [М40] Составьте алгоритм для извлечения квадратного корня, аналогичный алгоритму D и методу извлечения квадратного корня, который используется при вычислениях вручную.