Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 86
Текст из файла (страница 86)
98765 (Разделяющая точка в первой строке.) Сбросить признак перелолиения. Установить указатель буфера. Итаноеить счетчик циклов. Начать программу умножения. (См. упр. 4,3.1-13 с «=!О" ни=а) гА з- следующие девять разрядов. 2В 5 Запомнить следующие девять разрядов. Увеличить указатель буфера. Повторить десять раз. Повторять до тех пор, пока печатюотся обе строки, $ 176472 1 16,6472 16 150472 15 О 135472 1354 ХЗ. ЗОР ХОР Ойто зтйзт 107 ЕИТ2 вн еитз 1Н еит1 ЕИТХ 2Н ЗТХ 11Р З(ЛХ СНАВ Зта ЗТХ ХИС2 ОЕСЗ 1ЗР СОТ 12И сзззз «ЗЗ ОРХО -4О 10 0 схиет ВОР+40,2(2:5) ВОР+41,2 2 1 Я ВОР+20, 2(РВХИТЕЕ) ЗВ 987654 + 9 1187654 + 118 1 3 1 6,6 5 4 + 1З16 1448354 + 14483 1604284 + 160428 1 7 6 4 7 2 3 Результат: (1764723)е.
14. Пусть К(н) — число шагов, требуемых для преобразования н-разрядного десятичного числа в представление в двоичном формате и одновременного вычисления двоичного представления числа 10". Тогда К(2н) ( 2К(н) + 0(М(п)). Дамыашельсглео, Для данного числа 0 = (ит ~...ие)~а за 2К(н) шагов вычисляем (/~ = (ие -) и~)~е и Се = (и -)...ие)~в, а также 10".
Затем за 0(М(н)) шагов вычисляем (/ = 10" С~ + Се и 10~" =10" 10" Отсюдаследует,что К(2") жО(М(2")+2М(2" ')+4М(2" т)+ . ) = 0(нМ(2")). ]Подобным образом, как показал Шенхаге, за 0(нМ(2")) шагов мшкно преобразовать (2" 1810)-битовое число С из двоичного представлениа в десятичное. Сначала за 0(М(2" ') +М(2" т)+ ) = 0(М(2")) шагов формируем число К = 10т" ', затем еще за 0(М(2")) шагов вычисляем Се = (О шод Г) и (3 = '1(//Ц. После зтога преобразуем Са и (/ь] 17.
См работу У. Д, Клингера (ЪЧ. О. С!шйег), ЯСР7 АХ Хайсш 25, 6 (Лине, 1990), 92-101, а также работу Стила (8сее!е) и Уайта (1тЪ!ге), цитируемую в ответе к упр. 3. 18. Пусть С = гоипдл(и, Р) и е ж гоиш1ь((/,р), Можно положить, что и > О, так что (/ > 0 и е > О. Случай 1, е < и: определим е н Е такими, чтобы выполнялось неравенство 6' ' < и < 6", Вл ' < (/ < Ва. Тогда и < С+ -'Вл (/ < и — 16~ г; следовательно, В~ ' < В~ ~(/ < В~ ~и < Ь" 'и < Ь". Случай А е > и: определим е и Е так, чтобы получить Ь' ~ < и ( Ь', В~ ( В < Вл.
Тогда и > (/ — -'Вн ~ и (/ > и+ угЬ' в; следовательно, В~ ' < В~ ((/-Вл ) < В~ и <6" 'и <Ьг. Такимабразом,доказано,что В~ ' < Ь" когда е Р и. Обратно„если В~ ' < Ь", то при доказательстве, цроведеннам выше, предполагалось, что наиболее полходящим примером, для которого и Р е, будет тот, в катаром число и представляетсн по степеням 6 и в то же время близко к степени В. Получаем В" 'Ь' < В~ 'Ь + тЬ вЂ” тВ~ ' — 1 = (В~ ' + 1т)(6~ — т); следовательно, 1 < а = 1/(1 — тЬ ~) < 1+ 1тВ' = В.
Согласно результатам упр. 4.5.3-50 существуют целые числа е н Е, такие, что !ойл а ( е )ойл Ь вЂ” Е <!ой и /!. Отсюда следует, что для некоторых е и Е выполняется неравенство о < Ь"/В < В. Получаем гоинбл(6', Р) = Вя н гоипбе(В~,Р) < Ь'. (САСМ 11 (1968), 47-50; Ргос.
Ашег. Мага. Бас. 19 (1968), 716-723.] Например, если 6" = 2'о и В" = 10~, то число и = 2"~~ - .100049 10'~~~ округляется до С = .1 10'вз» ж (.111111111101111111111)т - 2ееи, которое округляется до 2ыы — 2езвв, (Наименьший пример округления саине)((.ШП1100Цг 2ге4) = .1011. 10зз", гаинб(.1011 . 10ззз) = (.1110110010)т . 2мз найден Фредом Дж. Тайлеманам (ргеб Л. Туг)егпа ).) 19. ии - -(РОРОРОРО)~е, с~ = 1 — 10/16 формирует В = ((игие)го., (и~ив)ю)же; тогда тз = (ГРООРРОО)и, сз = 1 — 10 /16 формирует С = ((игиеизи4)~а(изизи~ио)~о)еызе', а глз = (РРРГОООО)ш, сз = 1 — 107/164 завершает процедуру. (Ср. с алгоритмом Шенхаге в упр.
14. Эту процедуру предложил Рой А. Кейр (Ноу Л. Кегг) приблизительно в 1958 голу.] РАЗДЕЛ 8.$.1 1. Учитывая, что знаменатели положительны, проверяем выполнение неравенства ие < йе. 2. Если на с > 1 делятся как и/8, так н е/8, то на сИ делятся и и е. 8. Положим, что число р простое. Есин р' является делителем чисел ие и и'е' при е > 1, то либо р'1и и р'1е', либо р''1и' и р'1е; следовательно, р'~ 8сб(и, е') йсб(и', е). Обратное утверждение доказывается путем обращения утверждения. 4. Пусть И~ = 8сб(и, е), 8т = 8сб(и', е'); тогда ответом будет ш = (и/8г)(е'/8т)а!8н(е), ю' = ](й/8т)(е/А)] с сообщением об ошибке "Деление на нулин при е = О. 5. 4 = 10, 1 = 17 7 — 27 12 = -205, 3т = 5, м = -41, м' = 168.
6. Пусть и" = и'/А, »" = »'/А. Задача состоит в том„чтобы показать, что боб(в»" + и"», 3~) = 8сб(в»ь+ в"», Ав"»»), Если число р простое и является делителем числа и", то р не будет делителем числа и илн»", а потому р не делит и»" + и»». Подобное же рассуждение действительно для простых делителей числа»".
Таким образом, ни один пэ простых делителей числа в" »" не оказывает влияния на наибольшее общее кратное. 7. (Х вЂ” 1)т+(Х вЂ” 2) = 2Х~ — (ОЖ вЂ” 5). Если исходными числами являются и-битовые двоичные целые числа, то для представления числа г может понадобиться 2п+ 1 бнт. 8. Прн умножении и делении зти величины булут подчиняться правилам х/О = шйп(х)оо, (шоо) х х = х х (шею) = (хоо)/з = ше)бп(х)оо х/(жоо) = О, где х — произвольное конечное число, ие равное нулю.
Описанные в разделе алгоритмы остаются без изменений. Затем эти алгоритмы можно легко модифицировать так, что О/О = 0 х (жос) ы (~ос) х 0 = "(О/0)", где "О/О" служит представлением "'неопределенности". Если один из оперы)дов не определен, результат также должен быть не определен. Поскольку подпрограммы умножения и деления могут удовлетворять этим естественным правилам расширенных арифметических операций, иногда имеет смысл модифицировать также операции сложения и вычитания, чтобы они удовлетворяли правилам х х со = жсо, х я (-оо) = ~ос для конечных х; (хоо) + (жоо) = жоо — (+ос) = шоо; более того, (хоо) + ('+~ю) = (шоо) - (жоо) = (О/0); если одним или обоими операндами служит (О/0), результат также должен быть (О/0).
Аналогично можно моднфипировать операции проверки равенства н сравнении. Сделанные выше замечания не относятся к признакам "переполнения". Если для признака переполнения используется оо, то нельзя полагать 1/са равным нулю, чтобы не принять неверные результаты за оравнльиые. Значительно лучше представить признак переполнения через (О/0) и условиться, что результат любой операции будет неопределенным, есзи хотя бы один из вводимых операндов является неопределенным. Такой способ индикации переполнения имеет то преимущество, что данные на выходе расширенных операций точно указывшот, какой из результатов определен, а какой — иет. 9. Если и/и' 14»/»', то 1 < [в»' — и'»[ = в'»'[и/й — »/»'[ < [2жи/в' — 2~" »/»'[, Две величины, различающиеся более чем на единицу, не могут иметь одинаковую "грань снизу", (Другими словамя, 2ц первых битое справа от двоичной точки достаточно для того, чтобы охарактеризовать значение двоичной дроби при наличии и-битовых знаменателей, Нельзя повысить ее точность до 2п — 1 бит, так как при и = 4 получим — э = (.00010011...
)г, 1т ы (.00010010... )и) 11. Чтобы разделить ненулевые числа» и»~ на (» +»»5)/»'~, нужно умножить их на обратное значение (» — » «/5)» '/(»э — 5» ~) и выполнить возможные сокращения. 12. ((2е ' — 1)/1); гоппб(х) м (О/1) тогда и только тогда, когда [х[ < 2' е. Аналогично гонпб(з) = (1/0) тогда н только тогда, когда х > 2т 13. Один подход заключается в ограничении размеров числителя н знаменателя величиной 27 бит. Тогда нужно будет сохранять только 26 бнт (так как ведущий бит знаменатели равен 1, за исключением скучая, когда длина знаменателя равна О). При таком полходе остается место для знака н 5 бит для запоминания размера знаменателя. Другой подход заключается в использовании 28 бит для чисчителя и знаменателя, которые занимают не более семи шестнадцатеричных разрядов вместе со знаком и 3-битовое поле для запоминания количества шестнадцатеричных разрядов в знаменателе. [С учетом формул, приведенных в слезбющем упражнении, первмй подход дает точно 2 140 040 119 конечных представимых чисел, а второй — 1 830 986 459.
Первый подход предпочтительнее, так как он более простой и обеспечивает гладкий переход межлу интервалами. При оперировании 64-битовыми словами общая длина числителя и знаменателя ограничивается величиной 64 — 6 = 58 бит.] 14. Количество чисел, кратных и в интервале (о..Ь], равно ]Ь/и] — ]о/и]. Отсюда, используя метод включений и исключений, получаем решение задачи в виде Яо — Я~ + Яз — ", где Яь равно ~.'( Мт/Р] — ~,М,/Р])(~№/Р] — (№/Р]), просуммированному ~о всем произведениям Р различных простых чисел Ь.
Можно также выразить ответ в виде ьеыммлм р(п) ((Мт/и] — (М~ /и]) (]№/н] — (№/и]). РАЗДЕЛ 4.$.2 1. Везде замените ппп, шах, + иа боб,!сш, х соответственно (предварительно убедитесь, что все тождества справедливы н тогда, когда любав переменная равна нулю). и е 1 10506, 3502 17136, 5712, 1904 5406, 1802 !02, 34 1836, 612, 204, 68 102, 34 0 13634 24140 13634 3502 1904 3502 1904 1802 34 1802 34 68 34 34 Свидетельства того, что боб(40902, 24140) = 34, поразительно! 6. Вероятность того, что оба числа а и е четны, равна 2, вероятность того, что оба числа кратны четырем, равна 1~, и т.
д, Таким образом, велячина А имеет распределение, задаваемое производящей функцией 3 3 3 з 3/4 + — з+ з + 4 16 64 1 — «/4 СРеднее значение Равно з, а сРедиеквадРатвчное отклонение — 6 + - — а = —. Если и $ з и е независимо н равномерно распределены в интервале 1 < в, е < 2л, необходимо внести 2. Для простого числа р пусть в„, ень ..., еер — степени числа р в каноническом разложении чисел и, ш, ..., е, По предпатожению и„< шр + + е ю Необходимо показать, что ир < ппп(и,еж) + + шш(июеер), но зто неравенство действительно вмпатняется, если в„не меньше каждого тт нли в„меньше некоторого сую 3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
