Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 82
Текст из файла (страница 82)
° 14. [НМ80] Пусть У н У вЂ” случайные нормализованные положительные числа в формате с плавающей точкой, имеющие дробные части с независимым распределением по лога.- рифмическому закону, н пусть рь — вероятность того, что разность их рорядков равна й. Предполшвя, что распределение порядков не зависят от распределения дробных частей, выведите формулу, которая через основание Ь и величины рр, рм рз, ... выражает вероятность того, что при выполнении сложения 1Гш У происходит "переполнение дробной части». Сравните результат с результатом упр.
1 (округление игнорировать). 1б. [»»М88] Пусть (/, У, ро, рм... те же, что и в упр. 14, и пусть используется арифметика по основанию 10. Покажите, что независимо от значений рэ, рм рз,... сумма (гну ие 6рдегв точно подчннаться логарифмическому закону и в действытельностн вероятность того, что старшая цифра суммы У Э У равна 1, всегда строго меньиве 1обва 2. 16.
[НМ28) (П. Дьяконис,) Пусть Ра(и) равно 0 или 1 для каждого и. Определите "веро. ятности" Р +в(и) с помощью повторяющегося усреднения, как в формуле (9). Покажите, что если Овв Р~(и) не существует, то не существует и 1пи Р, (и) длв любых ш. [Указание. Докажите, что а„-в О, если только имеем (ив+" +ав)/и -в О и ав+в с а +М/и для некоторой фиксированной константы М > О.] ° 17. [НМОВ] (М. Цуджн (И. Теи)Ц.) Другой способ определения значения вероятностя Рг($(и)) состоит в вычислении величины 1!ш (Н„~ 2 „" [$(а)]/Й); можно показать, что эта гармонические асралшиасть существуег и равна Рг(Я(и)), если толька последняя существует в ссютветствии с определением 3.5А. Докажите, что гармоничесиш вероятность выражения "(1об,а и) шоб 1 с г" существует и равна г, (Такым абркюм, значения начальных разрядов целых чисел а иючиасшк удовлетворяют логарифмическому закону в этом смысле.) э 18.
[НМВО) Пусть Р($) есть некоторая функция с действительными значениями, определенная на множествах Я положительных целых чисел, по необязательно ыа всех таких множествах, и удовлетворявшая следующим довольно слабым аксиомам, 1) Если Р($) и Р(Т) определены н ЯХТ 9, тоР($иТ) =Р($)+Р(Т). й) Если Р($) определена, то Р($+ 1) = Р($), где $+ 1 = (и+ 1 [ и 6 $).
й) Если Р($) определена, та Р(2Я) ы 2Р($), где 2$: (2и [и 6 Я). 1т) Если Я есть множество всех положительных целых чисел, то Р($) = 1. в) Еглвв Р($) определена, то Р($) > О. Предположим далее, что Р(1,) определено для всех положительных целых чисел а, где Б, есть мыожество всех положительных целых чисел, для которых десятичное представление начинается с а: ь, =(и [10 а с и с 10 (а+1) для некоторого цааогот), (В этом определении т может быть отрицательным, например 1 есть элемент из Бва, но не ыз Ьм.) Докажите, что Р(1 ) (обва(1+ 1/а) длЯ всех целых чисел а > 1. 19. [НМ2$] (Р, Л. Даикэн (11.
Ь. 11ввсав).) Докажите, что значения ведущих разрядов в числах Фибоиаччн подчиняются логарифмическому закону для дробных частей: Рг(10/в'„С г) !айва г. 20. [НМэд] СФормулируйте более строга выражение (16), найдя есимптотическое ловедение зависимости Р (10" в) — Я (в) при и -е со. 4.3. АРИФМЕТИКА МНОГОКРАТНОЙ ТОЧНОСТИ РАССМОТРИМ ТЕПЕРЬ операции над числами произвольно высокой точности.
Лля простоты изложения будем считать, что имеются в виду целые числа, а не числа, разделяющая точка которых находится внутри числа. 4.3.1. Классические алгоритмы В этом разделе будут рассмотрены алгоритмы реализации следующих операций: а) сложение и вычитание и-разрядных целых чисел с получением п-разрядного результата и разряда переноса; Ь) умножение ят-разрядного целого числа на п-рвзрядное целое число с получением (и + гп)-разрядного результата: с) деление (и + гп)-разрядного целого числа на и-разрядное целое число с получе. пнем (т + 1)-рэзрцдного частного и и-разрядного остатка.
Зги алгоритмы можно назвать классическими, так как само слово "алгоритм" на протяжении столетий использовалось в связи с реализацией вычислительных процессов. Термин "п-рвзрядное целое число" означает любое неотрицательное целое число, меньшее 6", где 6 есть основание обычной позиционной системы счисления, в которой представляются числа; такие числа в этой системе записываются с использованием не более чем и "разрядов".
Классические алгоритмы для целых чисел можно очевидным образом распространять на числа с разделяющей точкой внутри числа или числа в формате с плавающей точкой. заданные с повышенной точностью (так же, как в машине И1Х арифметические операции, определенные для целых чисел, распространяются на эти более общие случаи). В настоящем разделе будут рассмотрены алгоритмы выполнения перечисленных операций (а)-(с) нвд целыми чиьтами, представляемыми в позиционной системе по основанию 6, где 6 — заданное целое число, равное или большее 2. Таким образом, эти алгоритмы представляют собой достаточно общие определения арифметических процессов, и в этом качестве они не связаны ни с какой конкретной вычислительной машиной.
Тем не менее рассуждения будут некоторым образом машинно-ориентированными, поскольку нас, в основном, интересуют эффективные методы выполнения при помощи компьютера вычислений с высокой точностью. Хотя приведенные примеры ориентированы на гипотетический компьютер ИХХ, по существу, те же рассуждения применимы почти для любой другой машины. Для понимания сути чисел повышенной точности наиболее существенно то, что их можно рассматривать как числа, записанные в системе счисления по основанию в, где и — размер слова. Например, целое число, заполняющее 10 машинных слов в памяти компьютера, размер слова которой — ю = 10'е, имеет 100 десятичных разрядов.
Однако мы будем рассматривать его как 10-разрядное число по основанию 10'е. Такой подход обосновывается теми же соображениями, что и переход, скажем, от двоичной системы счисления к шестнадцатеричной; мы просто группируем биты (см. выражение 4.1-(5)). С учетом этих соглашений будем рассматривать следующие элементарные операции: ае) сложение и вычитание одноразрядных целых чисел с получением одноразрядного результата и разряда переноса; Ье) умножение одноразрядного целого числа на одноразрядное с получением двух- разрядного результата; се) деление двухразрядного целого числа на одноразрядное, которое обеспечивает получение частного как одноразрядного целого числа и одноразрядного остатка.
После надлежащей установки размера слова, если это необходимо, названные операции будут доступны для выполнения почти на каждом компьютере. Поэтому сформулируем перечисленные выше алгоритмы (а), (Ь) и (с) в терминах элементарных операций (ао), (Ьэ) и (се). В связи с тем, что целые числа повышенной точности воспринимаются как числа по основанию 6, полезно представить себе соответствующую ситуацию при 6 = 10, считая при этом, что арифметические операции выполняются вручную.
Тогда операция (ао) аналогична запоминанию таблицы сложения, операция (Ье) аналогична запоминанию таблицы умножения, а операция (се) — это, по существу, запоминание "обращенной" таблицы умножения. Более сложные операции (а), (Ь) и (с) над числами высокой точности могут быть теперь реализованы на основе простых операций сложения, вычитания, умножения н деления в столбик, которым учат детей в начальной школе. Фактически большинство алгоритмов, которые будут рассматриваться ниже, — не что иное, как механическое воспроизведение знакомых операций, выполняемых при помощи карандаша и бумаги. Конечно, алгоритмы придется формулировать гораздо более тщательно, чем в начальной школе.
Кроме того, необходимо стремиться минимизировать используемую машинную память и время, затрачиваемое на выполнение программ. Во избежание скучных рассуждений и громоздких обозначенпй будем с самого начала полагать, что все используемые числа здесь иеотрицатсльньь Дополнительные меры, необходимые для вычисления знаков и т. д., довольно очевидны, хотя при работе с числами в виде дополнения на компьютере, на котором не используется представление больших чисел в прямом коде, необходимо соблюдать осторожность.
Эти вопросы будут рассмотрены в конце раздела. Начнем со сложения, с, безусловно, очень простой, но все же заслуживающей внимательного изучения операции, так как те же идеи встречаются и в других алгоритмах. Алгоритм А (Слоясение неотрицательных целых чисел). По заданным неотрицательным и разрядным целым числам по основанию 6 (и„-~... и~ив)ь и (е -э . стив)ь этот алгоритм формирует их сумму (в„ю„~... кч юе)м Здесь ю„— разряд переноса, всегда равный О или 1. А1.
(Начальная установка.] Присвоить 1 <- О, 6 +- О. (Переменная 1 будет пробегать позиции различных разрядов, а переменная 6 будет следить за переносами на каждом шаге.) А2. (Сложить разряды ) Присвоить из+-(из+о +6) шоб 6 и 6+- ((и„+из+6)/6). (По индукции, распространяемой на вычисления, всегда выполняется неравенство из + иэ + 6 < (6 — 1) + (6 — 1) + 1 ( 26. Следовательно, 6 присваивается значение 0 или 1 в зависимости от того, произошел (1) или не произошел (0) перенос, т, е.
выполняется присвоение А +- [из + еу + й > 6).) АЗ. [Цикл по 11[ Увеличить у на единицу. Если теперь 1 < п, то вернуться к шагу А2, иначе — присвоить ш„+- 6 и завершить выполнение алгоритма. 1 По поводу формального доказательства корректности алгоритма А обратитесь к упр. 4. Программа для компьютера И11, реализующая эту процедуру сложения, могла бы выглядеть так. Программа А (Слоэссеиие неосприцвтельнмх целых чисел). Пусть 1.0С(иу) ьз О+1, 10с(е.) вз У+,1, 60с(ш1) и и+ 1', гп ги 1 — и, гА аа 6, размер слова ев ь, и ьз п.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
