Ъ.7 7 2 1

- 1 0

4 7.7 2 i

- 9 4

3 8 3.2 i

- 7 6 6

3 О 6 6.i

- 6 13 2

2 4 5 2 9

Результат: (24529) ю.

12. Сначала преобразуем число, представленное в троичной системе, в девятеричную систему, а затем поступаем так же, как при преобразовании числа из восьмеричной системы счисления в десятичную, но без удвоений. Преобразование из десятичной системы в девятеричную выполняется аналогично. В данном примере имеем следующее.

1.7 6 1

4 7 2 3

пока печатаются обе строки.

14. Пусть К{п}-число шагов, требуемых для преобразования п-разрядного десятичного числа в представление в двоичном формате и одновременного вычисления двоичного представления числа 10". Тогда К{2п) < 2К{п) + 0{М(п)). Доказательство. Для данного числа U = (u2n-i ... wo)io за 2К{п) шагов вычисляем U\ = (u2n-i ... Wn)io и Uo = (u„ i ...uo)io, a также 10". Затем за 0{М(п)) шагов вычисляем U = 10"Ui + Uo и 10" = 10" . 10" Отсюда следует, что А(2") = 0(М(2") + 2М(2"-) + 4М(2"-) + ••) = 0(nM(2")).

[Подобным образом, как показал Шёнхаге, за 0(nM(2")) шагов можно преобразовать (2" Ig 10)-битовое число U из двоичного представления в десятичное. Сначала за 0(М(2"-1) -I- М(2"-) + ) = 0(М(2")) шагов формируем число V = Ю"", затем еще за 0(М(2")) шагов вычисляем Uo = {U mod V) и Ui = [U/Vj. После этого преобразуем Uo и Ul.]

17. См работу У. Д. Клингера (W. D. Clinger), SIGPLAN Notices 25, 6 (June, 1990), 92-101, a также работу Стила (Steele) и Уайта (White), цитируемую в ответе к упр. 3.

18. Пусть и = rounds(w, Р)иу = roundi,([7,p). Можно положить, что и > О, так что U > О и V > 0. Случай Lv <и: определим ек. Е такими, чтобы выполнялось неравенство 6" < и < 6 В- <и <В. Тогда и<и + В" и [7 < и - Ь-Р; следовательно, В < р-Ец В~и < Ь~и < Ь. Случай 2, V > и: определим е и Е так, чтобы получить Ь- < U < 6 В- <и < В. Тогда и > [7 - В hU >и + b-f; следовательно,

< в-{и-В-) < В-и < б-и < 6". Таким образом, доказано, что В" < 6" когда V ф и.

Обратно, если В" < Ь", то при доказательстве, проведенном выше, предполагалось, что наиболее подходящим примером, для которого и ф v, будет тот, в котором число и представляется по степеням 6 и в то же время близко к степени В. Получаем ВЬ < ВР-Ь" + - В- - i = (В- + i)(6p - i); следовательно, К а = 1/(1 - Ь) < 1 -I- В~ = /3. Согласно результатам упр. 4.5.3-50 существуют целые числа е и Е, такие, что logg а < е \ogg Ь - Е < logg /3. Отсюда следует, что для некоторых е и Е выполняется неравенство а < ¥/В < /3. Получаем rounds(Ь Р) = В и roundi,(B,p) < 6 [САСМ 11 (1968), 47-50; Ргос. Атег. Math. Soc. 19 (1968), 716-723.]

Например, если 6 = 2" и В = 10 то число и = 2"°* w .100049 • Ю" округляется до [/ = .1 • 10 и (.111111111101111111111)2 • 2 которое округляется до 26408 26398 (Яаилекьший пример округления round((.1111111001)2 • 2"*) = .1011 • 10 round(.1011 10") = (.11111110010)2 • 2* найден Фредом Дж. Тайдеманом (Fred J. Tydeman).)

19. mi = (F0F0F0F0)i6, ci = 1 - 10/16 формирует U = ((u7U6)io •• ("i«0)10)256; тогда тг = (FF00FF00)i6, C2 = 1 - lO/ie формирует U = ((и7ИбИ5И4)1о(изИ2И1Ио)1о)б553б; a тз = (FFFF0000)i6, сз = 1 - 1016 завершает процедуру. [Ср. с алгоритмом Шёнхаге в упр. 14. Эту процедуру предложил Рой А. Кейр (Roy А. Keir) приблизительно в 1958 году.]

РАЗДЕЛ 4.5.1

1. Учитывая, что знаменатели положительны, проверяем выполнение неравенства

uv < uv.

2. Если на с > 1 делятся как u/d, так и v/d, то на cd делятся и и i;.

3. Положим, что число р простое. Если р является делителем чисел uv и uv при е > 1, то либо р\и и p\v, либо р\и и p\v; следовательно, р\gcd(u,i;) gcd(u, и). Обратное утверждение доказывается путем обращения утверждения.

4. Пусть dl = gcd(u, 1;), d2 = gcd(u, i;); тогда ответом будет w = (u/di)(w7d2)sign(i;), w = \{u/d2){v/di}\ с сообщением об ошибке "Деление на нуль" при i; = 0.

5. dl = 10, t = 17 • 7 - 27 • 12 = -205, dz = 5, ш = -41, w = 168.

6. Пусть и" = u/di, v" = v/di. Задача состоит в том, чтобы показать, что gcd(ut;" + uv, dl) = gcd(ui;" + u"v, d\u"v"). Если число p простое и является делителем числа и", то р не будет делителем числа и или v", а потому р не делит uv" + u"i;. Подобное же рассуждение действительно для простых делителей числа v". Таким образом, ни один из простых делителей числа u"v" не оказывает влияния на наибольшее общее кратное.

7. (Л - 1) + (Л - 2) = 2Л - (6Л - 5). Если исходными числами являются п-битовые двоичные целые числа, то для представления числа t может понадобиться 2n + 1 бит.

8. При умножении и делении эти величины будут подчиняться правилам ж/О = sign(a;)oo, (±оо) XX = XX (±оо) = (±оо)/х = ±sign(a;)oo,a;/(±oo) = О, где ж - произвольное конечное число, не равное нулю. Описанные в разделе алгоритмы остаются без изменений. Затем эти алгоритмы можно легко модифицировать так, что О/О = О х (±оо) = (±оо) х О = "(О/О)", где "О/О" служит представлением "неопределенности". Если один из операндов не определен, результат также должен быть не определен.

Поскольку подпрограммы умножения и деления могут удовлетворять этим естественным правилам расширенных арифметических операций, иногда имеет смысл модифицировать также операции сложения и вычитания, чтобы они удовлетворяли правилам ж ± 00 = ±00, X ± (-оо) = ТОО для конечных х; (±оо) + (±оо) = ±оо - (Тоо) = ±оо; более того, (±оо) 4- (Тоо) = (±оо) - (±оо) = (О/О); если одним или обоими операндами служит (О/О), результат также должен быть (О/О). Аналогично можно модифицировать операции проверки равенства и сравнения.

Сделанные выше замечания не относятся к признакам "переполнения". Если для признака переполнения используется оо, то нельзя полагать 1/оо равным нулю, чтобы не принять неверные результаты за правильные. Значительно лучше представить признак переполнения через (О/О) и условиться, что результат любой операции будет неопределенным, если хотя бы один из вводимых операндов является неопределенным. Такой способ индикации переполнения имеет то преимущество, что данные на выходе расширенных операций точно указывают, какой из результатов определен, а какой - нет.

9. Если и/и ф v/v, то 1 < \uv - uv\ = uv\u/u - v/v\ < 2"и/и - 2"v/v\. Две величины, различающиеся более чем на единицу, не могут иметь одинаковую "грань снизу". (Другими словами, 2п первых битов справа от двоичной точки достаточно для того, чтобы охарактеризовать значение двоичной дроби при наличии п-битовых знаменателей. Нельзя повысить ее точность до 2п - 1 бит, так как при п = А получим = (.00010011... )2, п = ( 00010010 ... )2.)

11. Чтобы разделить ненулевые числа i; и i; на (i; 4- vy/E)/v", нужно умножить их на обратное значение (i; - v\/b)v"/{v - Ъи) и выполнить возможные сокращения.

12. ((2- - 1)/1); round(a;) = (0/1) тогда и только тогда, когда ж < 2". Аналогично round(x) = (1/0) тогда и только тогда, когда х > 2".

13. Один подход заключается в ограничении размеров числителя и знаменателя величиной 27 бит. Тогда нужно будет сохранять только 26 бит (так как ведущий бит знаменателя равен 1, за исключением случая, когда длина знаменателя равна 0). При таком подходе остается место для знака и 5 бит для запоминания размера знаменателя. Другой подход заключается в использовании 28 бит для числителя и знаменателя, которые занимают не более семи шестнадцатеричных разрядов вместе со знаком и 3-битовое поле для запоминания количества шестнадцатеричных разрядов в знаменателе.

[С учетом формул, приведенных в следующем упражнении, первый подход дает точно 2 140 040 119 конечных представимых чисел, а второй - 1 830 986 459. Первый подход предпочтительнее, так как он более простой и обеспечивает гладкий переход