точно подчиняться логарифмическому закону и в действительности вероятность того, что старшая цифра суммы U фУ равна 1, всегда строго меньше logio 2-

16. [НМ28] (П. Дьяконис.) Пусть Ро(п) равно О или 1 для каждого п. Определите "вероятности" Pm+i{n) с помощью повторяющегося усреднения, как в формуле (9). Покажите, что если lim„ ,oo Pi(n) не существует, то не существует и lim„-,oo Pm(n) ДДя любых т.

[Указание. Докажите, что о„ -> О, если только имеем (oiH-----1-о„)/п -> О и o„+i < Оп+М/п

для некоторой фиксированной константы М > 0.]

► 17. [НМ25] (М. Цуджи (М. Tsuji).) Другой способ определения значения вероятности Pr(S(n)) состоит в вычислении величины ип1„-юо(Я,Г5 i[5(/c)] i;); можно показать, что эта гармоническая вероятность существует и равна Рг(5(п)), если только последняя существует в соответствии с определением 3.5А. Докажите, что гармоническая вероятность выражения "(logio ") 1 < существует и равна г. (Таким образом, значения начальных разрядов целых чисел в точности удовлетворяют логарифмическому закону в этом смысле.)

► 18. [НМЗО] Пусть P{S) есть некоторая функция с действительными значениями, определенная на множествах S положительных целых чисел, но необязательно на всех таких множествах, и удовлетворяющая следующим довольно слабым аксиомам.

i) Если Р(5) и Р(Т) определены и 5 П Г = 0, то Р(5 U Г) = Р(5) + Р{Т).

ii) Если Р(5) определена, то P{S -Ы) = P{S), где 5 -Н 1 = {п -Ы п 6 5}. Ill) Если Р(5) определена, то Р(25) = \P{S), где 25 = {2п п б 5}.

iv) Если S есть множество всех положительных целых чисел, то P{S) = 1.

v) Если P{S) определена, то P{S) > 0.

Предположим далее, что P{La) определено для всех положительных целых чисел а, где La есть множество всех положительных целых чисел, для которых десятичное представление начинается с а:

La= {п \ 10"о < п < 10""(о -Н 1) для некоторого целого т} .

(В этом определении m может быть отрицательным, например 1 есть элемент из Lio, но не из Lib) Докажите, что P{La) = logio(l + V") для всех целых чисел а > 1.

19. [НМ25] (Р. Л. Данкэн (R. L. Duncan).) Докажите, что значения ведущих разрядов в числах Фибоначчи подчиняются логарифмическому закону для дробных частей: Pr(10/F„ < г) = logio г.

20. [НМ40] Сформулируйте более строго выражение (16), найдя асимптотическое поведение зависимости Pm(10"s) - Sm(s) при п -> оо.

4.3. АРИФМЕТИКА МНОГОКРАТНОЙ ТОЧНОСТИ

Рассмотрим теперь операции над числами произвольно высокой точности. Для простоты изложения будем считать, что имеются в виду целые числа, а не числа, разделяющая точка которых находится внутри числа.

4.3.1. Классические алгоритмы

В этом разделе будут рассмотрены алгоритмы реализации следующих операций:

a) сложение и вычитание п-разрядных целых чисел с получением п-разрядного результата и разряда переноса;

b) умножение т-разрядного целого числа на п-разрядное целое число с получением (п + т)-разрядного результата;

c) деление (п + т)-разрядного целого числа на п-разрядное целое число с получением (т -I- 1)-разрядного частного и п-разрядного остатка.

Эти алгоритмы можно назвать классическими, так как само слово "алгоритм" на протяжении столетий использовалось в связи с реализацией вычислительных процессов. Термин "п-разрядное целое число" означает любое неотрицательное целое число, меньшее 6", где b есть основание обычной позиционной системы счисления, в которой представляются числа; такие числа в этой системе записываются с использованием не более чем п "разрядов".

Классические алгоритмы для целых чисел можно очевидным образом распространять на числа с разделяющей точкой внутри числа или числа в формате с плавающей точкой, заданные с повышенной точностью (так же, как в машине MIX арифметические операции, определенные для целых чисел, распространяются на эти более общие случаи).

В настоящем разделе будут рассмотрены алгоритмы выполнения перечисленных операций (а)-(с) над целыми числами, представляемыми в позиционной системе по основанию 6, где b-заданное целое число, равное или большее 2. Таким образом, эти алгоритмы представляют собой достаточно общие определения арифметических процессов, и в этом качестве они не связаны ни с какой конкретной вычислительной машиной. Тем не менее рассуждения будут некоторым образом машинно-ориентированными, поскольку нас, в основном, интересуют эффективные методы выполнения при помощи компьютера вычислений с высокой точностью. Хотя приведенные примеры ориентированы на гипотетический компьютер MIX, по существу, те же рассуждения применимы почти для любой другой машины.

Для понимания сути чисел повышенной точности наиболее существенно то, что их можно рассматривать как числа, записанные в системе счисления по основанию W, где W - размер слова. Например, целое число, заполняющее 10 машинных слов в памяти компьютера, размер слова которой - w = 10°, имеет 100 десятичных разрядов. Однако мы будем рассматривать его как 10-разрядное число по основанию 10°. Такой подход обосновывается теми же соображениями, что и переход, скажем, от двоичной системы счисления к шестнадцатеричной; мы просто группируем биты (см. выражение 4.1-(5)).

С учетом этих соглашений будем рассматривать следующие элементарные операции:

ао) сложение и вычитание одноразрядных целых чисел с получением одноразрядного результата и разряда переноса;

bo) умножение одноразрядного целого числа на одноразрядное с получением двухразрядного результата;

Со) деление двухразрядного целого числа на одноразрядное, которое обеспечивает получение частного как одноразрядного целого числа и одноразрядного остатка.

После надлежащей установки размера слова, если это необходимо, названные операции будут доступны для выполнения почти на каждом компьютере. Поэтому сформулируем перечисленные выше алгоритмы (а), (Ь) и (с) в терминах элементарных операций (ао), (bo) и (со).

В связи с тем, что целые числа повышенной точности воспринимаются как числа по основанию 6, полезно представить себе соответствующую ситуацию при b = 10, считая при этом, что арифметические операции выполняются вручную. Тогда операция (ао) аналогична запоминанию таблицы сложения, операция (bo) аналогична запоминанию таблицы умножения, а операция (cq)-это, по существу, запоминание "обращенной" таблицы умножения. Более сложные операции (а), (Ь) и (с) над числами высокой точности могут быть теперь реализованы на основе простых операций сложения, вычитания, умножения и деления в столбик, которым учат детей в начальной школе. Фактически большинство алгоритмов, которые будут рассматриваться ниже, - не что иное, как механическое воспроизведение знакомых операций, выполняемых при помощи карандаша и бумаги. Конечно, алгоритмы придется формулировать гораздо более тщательно, чем в начальной школе. Кроме того, необходимо стремиться минимизировать используемую машинную память и время, затрачиваемое на выполнение программ.

Во избежание скучных рассуждений и громоздких обозначений будем с самого начала полагать, что все используемые числа здесь неотрицательны. Дополнительные меры, необходимые для вычисления знаков и т. д., довольно очевидны, хотя при работе с числами в виде дополнения на компьютере, на котором не используется представление больших чисел в прямом коде, необходимо соблюдать осторожность. Эти вопросы будут рассмотрены в конце раздела.

Начнем со сложения, с, безусловно, очень простой, но все же заслуживающей внимательного изучения операции, так как те же идеи встречаются и в других алгоритмах.

Алгоритм А (Сложение неотрицательных целых чисел). По заданным неотрицательным п-разрядным целым числам по основанию b (un-i.. UiUo)b и (vn-i... viVo)b этот алгоритм формирует их сумму (ш„ш„ 1... wiWo)b- Здесь w„ -разряд переноса, всегда равный О или 1.

Al. [Начальная установка.] Присвоить j <- О, к <- 0. (Переменная j будет пробегать позиции различных разрядов, а переменная к будет следить за переносами на каждом шаге.)

А2. [Сложитьразряды.] npiiCBOKTbWj<-(uj+Vj+k)modbiik<-[{Uj+Vj+k)/b\. (По индукции, распространяемой на вычисления, всегда выполняется неравенство

Uj + vj + k<{b-l) + {b-l) + l< 2b.