Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 108

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 108)

(с) Простая индукция по», но близкие шаги требуют более пристального внимания. Будем говорить, что ги обладает свойством Р(а), если все единицы в его бинарном представлении располагшотся в последовательных блоках > а в строке. Если т и т' обладают свойством Р(а), то нм обладает и т ь. т', если т обладает свойством Р(а), то р(т) обладает свойством Р(а+ б). Следовательно, В, обладает свойством Р(1+ бс»). И наконец, если п» обладает свойством Р(а), то л(р(т)) < (а+б)п(т)/а, для г (ги) = щ+.. +и», где каждый размер блока ьу > а. Следователъно, и(р(т)) < (щ+б)+ +(и +б) < (1+б/а)»»+ .+(1+б/а)и.

(»1) Пусть / = Ь„+ с„— число неудвоений, а э — число малых шагов. Если / > 3.271 18» (и), то э > 18» (и), как и требовалось, в соответствии с (16), В противном случае а, < (1+ 2 )»'2" +~" дли 0 < а < г. Значит, и < ((1+ 2 ~)/2) '2" и г > 18 и+ ܄— Ь, !8(1+ 2 ~) > 18 и+ 18 л(и)— !8(1+бе,) — Ь,18(1+ 2»), Пусть б = !!8(/+ 1)!; тогда 1л(1+ 2 ) < Ь»(1+1/(/+1)) < 1/(/+1) < б/(1+б/). Отсюда следует, что !8(1+бх)+(/-х) !8(1+2 ~) < !8(1+б/) для 0 < х < /. Поэтому окончательно !(и) > 18 и+!8 и(и)- !8(1+(3.271 !8 и(и)) !!8(1+3.271 )8 и(и)))).

(ТЛеогебса! Совр. Яс!. 1 (1975), 1-12.) 29. В толъко что процитированной рабате Шенхаге усовершенствовал метод из упр. 28 для доказательства того, что !(и) > 18 и+ 18» (и) — 2.13 для всех т». Может ли оставшийся пробел быть закрытым? 30. и = 31 представляет собой наименьший пример; !(31) = 7, но цепочка со сложением н вычитанием 1, 2, 4, 8, 16, 32, 31 имеет длину б. (После доказательства теоремы Е Эрдеш (Егббэ) указал, что тот же результат справедлив и для алдитивно-вычитательных цепочек. Шенхаге распространил ннжнюв границу из упр. 28 на цепочки со сложением и вмчитаннем с и(и), замененные Р(и), как определено в упр. 4.1 — 34, Обобщенный бинарный метод возведения в степень справа налево, в котором используется Л(и) + Р(и) — 1 умножений, когда заданы и х, и х ', может основываться на представлении а„из этого упражнения.) 32. Сч. О!эсгеге Мэй.

23 (1978), 115-119. [Эта модель цен соответствует умножению больших чисел классическим методом, подобным алгоритму 4.3.1М, Эмпирические результаты с более общей моделью, в которой цена равна (а!а»)лгг, были получены в работе )у, Р. МсСэг»Ьу, Маей. Сошр. 46 (1986), 603-608; эта модель более близка к<b>Текст обрезан, так как является слишком большим</b>.

Характеристики

Список файлов книги