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