Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 82
Текст из файла (страница 82)
(Аиелогичио, если проигнорировать произведения при г+7 > и+ 3, ошибка будет ограничена величиной (и-3) Ь " г, и т д, Но, вообще говоря, для получения правильно округленного результата необходимо вычислять все произведеиия.) Дальнейший анализ показывает, что корректна округленный результат перемножения дробных частей чисел в формате с плавающей точкой почти всегда может быть получен при вычислительных затратах, почти вдвое меиьших, чем при вычислении полного произведения с удвоенной точностью. Более того, выполнив проверку, можно убедиться, что случаи, в которых необходима полная точность, крайне редки.
(См. ЪЧ. КгапойгЛс, Л. К. Ло)гпооп, Ргос. ХАЕВ Яушр. Сошригег Агггбшепс 11 (1993), 228-233.) 18. $1. Присвоить г +- О, / +- и — 1. БЗ. Присвоить ш +- Цгб+ и )/е), г+- (гб+ и-) шод е. $3. Уменьшить / на 1 и, если,~ > О, вернуться к шагу 82. $ 17. и/е > и„б" /(е„, + 1) Ьо ' м Ь(1 — 1/(е„г + 1) ) > 6(1 - 1/(Ь/2)) = Ь вЂ” 2. 18. (и„Ь+и,-г)/(е -г+ 1) < и/(в„г + 1)Ь" ' < и/е. 19. и — Уе < и — уе„-гбь"' — Уе~-гб" г = и~-гб" г + . + ио + гЬ" ' — Уе„-гб" г < Ь' г(и„ г + 1 + ИЬ вЂ” Уе„ г) < О, Поскольку и — Уе < О, то У < д.
20. Если у < у — 2, то и < (у — 1)в < у(е„ гб" ' + (е -г + 1)6" ') — е < уе -гб" ' + Уе„-гб" г+Ь" ' — е <Уе гб" ~+(Ьг+и г)Ь" г+Ь" ' — е = и„Ь" +и -гб" '+и„гЬ" г+ Ь" ' -е < и Ь" + и„гб" '+ и„гЬ" г < и. Другими словами, выходит„что и < и, а это невозможно. 21. (Получено Г. К.
Гоялом (О. К. Ооуа1).) Из неравенства уе -г < бе+ и -г слацует у < (и 6~+ ио гб+ и~-г)/(е гб+ е„г) < и/це„гЬ+ в„г)Ь" г). Отсюда ишобе м и — Уе = е(1 — а), где 0 < а = 1+ У вЂ” и/е < У" — и/в < и(1/Це гб+ ео-г)Ь г) — 1/е) = и(е -гЬ" г+ )/Це гб+е г)6" 'е) < и/(е гбе) < У/(ео гб) < (6-1)/(е„гб), котоРое ограничено величиной 2/Ь, так как е„г > -'(Ь вЂ” 1). 22. Пусть и = 4100, е = 588. Возьмем сначала у = Щ = 8.
Однако видим, что 8 ° 8 > 10(41- 40) + О. Тогда полагаем у = 7 и получаем 7 8 < 10(41-35) + О. Но число 588, умноженное иа 7, равно 4118, так что правильное частное будет у = б. (Между прочим, данный пример показывает, что для Ь = 10 теорема В при данных предположениях не может быть улучшена.) 23. Очевидно, что в1Ь/(в + 1)1 < (в+ 1) 1Ь/(в+ 1)) < Ь, поэтому при в > 6/2 выполняется левая часть неравенства. В противном случае в(Ь/(в+1)) > в(Ь вЂ” в)/(в+ 1) > (Ь вЂ” 1)/2 > (Ь/2) — 1. 24.
Приближенная вероятность равна щего лишь 1оиэ 2, а не -'. (Например, если Ь = 2эз, вероятность того, что в г > 2з', приблизителыш равна ~и. Тем яе менее этого еше достаточно много для того, чтобы оправдать выполнение специальной проверки условия 0 = 1 на шагах Р1 и РЗ алгоритма Р.) гб. 008 еитА 1 1 008 АВВ Ч+И-1 1 004 ЗТА ТБИР 1 008 еитА 1 1 000 107 18 1 Переход, если в„~ ы Ь вЂ” 1. 007 ЕитХ В 1 008 В17 7+И-1 1 Роо 1ОТ Вттвтгийо 010 1И ЗТА В 1 011 ВЕСА 1 1 018 1АМХ *+3 1 Переход, если 0 ф 1, 018 ЗТЕ В+И+И 1 — А Присвоить в +„+- О.
011 1ИР Вг 1 — А 018 еии1 И А Умножить в на Ф. 010 еитх о А 017 2М ЗТХ САЕЕТ Айг 018 1ВА 7+И, 1 АФ 01 У ИШ В А)т Иначе — вычислить (Ь/(в + 1Ц Переход, если в„~ = О, (Как в упр. 13.) 080 11И 2В 087 ЕМИ1 И+И 088 2н Зтх сАиет 089 1.ВА В+И+И, 1 А)7 А А(Ь1+ )7) А(М+ Х) (Теперь гХ = О.) Умножить и на Ы. (Как в упр. 13,) (Остаток сохранится в ячейках от В до В+М"1.) Бови 0 = 1, то закончить.
тП ш,1; 8 +- и — 1. г+- О. гАХ Г- гЬ+ вз. ОУ7 11И 2В 088 Зтх В+И+И 2З. (См. алгоритм в упр. 16.) 101 ВЗ 1ВА В 1 108 ВЕСА 1 1 1РУ ЛАЗ ВОИЕ 1 104 ЕМТ1 И-1 А 108 Еитй В А 106 1И 1ВХ 0,1 Айг 107 В17 В АХ 108 ЗТА В,1 Айг 10У 51АХ 5 АЮ 110 ВЕС2 1 Айг 111 ЗИМ 1В АА" На этом программа деленна упражнении, гАХ ж О. (ву, г) г- ((гАХ/Ф), гАХ шос) 8).
1' -1'+1. Повторить для и > 1' > О. $ завершаетсв, причем, как будет показано в следующем 27. Это число равно с(о шобг(е = Ы(впнк1 о). 28. Предположим (для удобства), .что э имеет десятичную то1ку слева, т. е. что о = (э„.э 1э -э . )ь После завершения шага Х1 получим -' < е < 1+ 1/Ь. Тогда Ь+ ! (Ь+» ( +1/Ь) е„, +1)' — е„, +1 (1/Ь)(о„, + 1) '+ Ь Ь+1 ) э(5+1 — ) 1сэ (Ь+1 — о ) ), ов-1+ 1) еь-1 + 1 Ь эп-1+ 1 Величина в последнем соотношении принимает наименьшее значение при и„1 = 1, так как это выпуклая функция и другое ее экстремальное значение больше.
! Ь(Ь + 1) ! о Формулу на шаге Е2 можно переписать в виде о э- ~ ) -„поэтому, как и выше, иахоаим, что о никогда не будет > 1 + 1/Ь. !...+йЬ После одной итерации шага Х2 минимальное значение и не меньше, чем - ) / — . — ) -- / Ь(Ь+Ц- .,~э /Ь(Ь+1)- .,~ ., /Ь(Ь+1)+1-11/1-1) 1 2 1 7 Ь(Ь+1)+11 = 1+ -+ — — — 1+ Ь Ь Ь( при 1 = е„-1 + 1. Минимум этой величины достигается при 1 Ь/2+ 1, нижняя граница равна 1 - 3/2Ь.
Следовательно, после одной итерации шаха 742 имеем е ~ > Ь вЂ” 2. В итоге получаем (1-3/2Ь)(1+1/Ь) > 1, где Ь > 5, так что потребуется еще не более двух итераций. В случае, когда Ь < 5, утверждение легко проверяется непосредственно. 29. Это утверждение верно, так как (в +„... и )э < о. 30.
Прн выполнении алгоритмов А и Я такое перекрытие возможно, если алгоритмы слегка видоизменить. К примеру, в алгоритме А можно так переписать швг А2: "Присвоить 1 Э- и, + вт + Ь, шх +- 1 плод Ь, Ь +- '11/51". При выполнении алгоритма М значение о; может храниться в том же месте, что и ш~+„. При реализации алгоритма 0 удобнее всего (как в программе Р в упр. 26) принять, что значения г„| ...
го хранятся там же, где и в ю .. вэ, Можно также считать 9,„... 4о такими же, как и и .~.... и„, при условии, что на шаге 06 значения переменных ит». не изменились. (Строка 098 программы В может быть без вреда заменена на э31329", так как величина в~э„в вычислениях, выполняемых на этом шаге, не используется.) 31. РаССМОтрИтЕ СнтуацИЮ, ПрнавдвииуЮ Иа рнС. 6, ПОЛОЖИВ и = (Вэ~ь...ихюп~)З, Каи в алгоритме В. Если велупсие ненулевые разряды чисел и и е имеют один знак, то присваиваем г +- и — е, 9 э — 1; в противном случае присваиваем г э- и+ э, 9 э- -1. Если теперь (г( > )и( или )г) = )и! и знак первого ненулевого разряда чисел из 1... иэ совпадает с первым ненулевым разрядом числа г, то присваиваем д +- О; в противном случае присваиваем иуэ„... в значения разрядов числа г.
32. См. М. ХшНш, СЯСЬ 4 (1961), 192-193; Е. Рап1ай апд А. 1тайпйсх, Войб де 1'Асад. Ро1ооиэе дев Яшепсеэ, С1вээе Ш, 5 (1957), 233-236 (см. также с. 863 — 804), и упр. 4.1-15. 34. См., например, В. Е. Маваг, ТЬе ЛХасйешабса хоцгпа1 6,2 (Брппй, 1996), 32-40; 6,3 (Бпшшег, 1996), 37-43. 36. Имея число ф, заданное с точностью ш2 ~"„ф ', ф ~, ..., значение 1пф можно вычислить, выполняя вычитания до тех пор, пока ф ~ < 2 ". Накэпливаемая при этом ошибка не превысит 2' ". Затем мовгно использовать ряд 1пф = 1п((1+4 )/(1 ф )) = 2(ф э+ -'ф э+ -'ф 'э+ ). [Сэь статью гИ11эш Ясйоойпй, Жар(ег Тегсепгеоагу Мешопа1, е«Ыеа! Ьу С.
О. Кпоьь (Ьопдоп: 1.оп8щапэ, 1915), 337-344.) Но еще лучше (предложено в 1965 голу Дж. У. Ренчем (мл.) (Х %'. ЖгепсЬ, Лг,)) вычислить !пав = з)п((1+5 Ыз)/(1 — 5 Ы~)) = (26 — Ц(5 ~+ ф5 з+ ь5 з+ .). и.„ /(85+1)+ ~ г"-'-«/(ЗЬ+/), «За/а еб«<пГа где а„а« = 2" «а«шос((8)г+ 1). Каждый член в первой сумме может быть аппроксимирован посредством вычисления а 1«при помощи ОПобп) операций (раздел 4.6.3) в пределах 2 "'. После етого получится промасштабнрованное частное (2 аа «/(8)а + /)). Вторая сумма может быть аппроксимировала в пределах 2 в результате вычисления 2 раз ее первых щ/4 членов.
Если па ж 2 !8 и, интервал неопределенности будет равен 1/и, что почти всегда обеспечивает достаточную точность. (Ора«Ь. Сошр. 66 (1997), 963-913.) Праьнечание. Пусть Ь = е П~ ы (1 + а)/«/2 равно корню степени 8 нз еднницм. Рассмотрим значения!, = 1п(1-~1/«/2), Тогда (э = !и(1-1/а/2), (ь = 1г = з !и з-!агсгвп1, (г = !ь = з !и ф — ь агстап(1/Л), !з = Хь = 1 1п з — а агссап(1/3), !а = !п(1+ 1/~/2). КРоме того, -Я /21~~ = -'(1е+ «а(а + .. + ~ 01г) при 1 < 1 < 8 вследствие 1.2.9-(13).
Отсюда 48« — 2Яа — Яь — Яь = 21е — (2 — 2«) 2К + 21а + (2 + 2«) !г = аг. Другие интересные тождества приведены ниже: ~2+ зЯа+ а~э+ 3 зо 28«+ 1«Яе,. 28з + 2$а + э Зе; 3' + з~э+ а ~э + э~г %а — 7Яз+ аЯь — эЯг; Яь — Яз — 7 л» вЂ” 2 Яь,' 1 1 ЗЗь — 8$« — 4бз — ЗЯа — 28ь — 2бь + Яг. !п2 = 1пЗ = !об ж а/2 !п(а/2+ Ц = а/2 агссап(1/а/2) = эгсгап(1/3) = О= 37. Пусть И = 2', так что Ь > а!о„-~ > Ь/2. Вместо нормализации в и о на шаге 01 определяем два ведущих разряда о'е" числа 2'(о, ао зо з)ь посредством его сдвига влево на е бнт. Н» шаге 03 вместо (с ые з) используем (и',в"), а вместо (из+, в;+„«, ку+ з) используем (к, и ', и з), Значенив разрядов н'и" и" вычисляются путем сдвига влево на е бнт числа (вга....
ву+ -з)«Деление на И на шаге 08 опускаем. (В сущности, числа и и и сдвнгаютсв "виртуально". Такой метод снижает объем вычислений, если гп малб по сравнению с и.) 38. Присвоим Ь +- и, г +- О, з +- 1, 1 +- О, аэ а- и. Тогда сохраняется инвариантное отношение ве = 2з" (г+ зз — э) + 2«" "1+2« з"пас прн О < 1ш < 2" и при О < г < 2з. Если условие (г, з) ы (О, 1) больше не выполняется, то до тех пор, пока Ь >-О, положить 4«э = 2" аи' + шл и 41 + ы'е = 2" Е + 1", где О < аэ",1" < 2" и О < 1' < б. Затем присвоить 1 а- !", аи а- ш", з а- 2з, г а- 4«. +1' — з, )а а- )а — 1. Если г < О, присвоить э а- э — 1 и г а- г + 2з, в противном случае, если г > 2з, присвоить г +- г — 2э и э +- з + 1 (эта поправка может понадобиться двахалы).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
