Читать «Этюды для программистов» онлайн - страница 102

25

Напомним, что натуральное число — это неотрицательное целое число.

26

Файл ввода/вывода состоит из записей, которые могут быть разной длины. Каждое физическое устройство может накладывать свои ограничения на длину записи. Предполагается, что перед первой операцией ввода/вывода с данным файлом указатель текущей позиции в нем установлен на конец воображаемой нулевой записи. При выводе по мере надобности создаются новые записи.

27

−q нулей и d+q цифр по стандарту Фортрана и Фортрана-77. — Прим. перев.

28

Английское словосочетание to lose patience имеет два значения — «потерять терпение» и «проиграть пасьянс». — Прим. перев.

29

Эта грустная шутка основана на созвучии Las Vegas (Лас Вегас) и lost wages (потерянные зарплаты). — Прим. перев.

30

Фактически поиск максимального в столбце элемента М на шаге 3 алгоритма обращения есть одно из таких изменений. М называется ведущим элементом, а сама операция — выбором ведущего элемента; на самом деле необходимо лишь, чтобы М был ненулевым. Максимальный элемент используется, чтобы уменьшить арифметическую погрешность ЭВМ. При обращении матрицы Гильберта ведущим элементом всегда должен оказываться ; если же алгоритм выбирает в качестве ведущего элемент, лежащий ниже, то это означает, что погрешность уже очень велика.

31

Как здесь не отметить, что самую плодотворную идею по части быстрого умножения вы можете позаимствовать у кроликов. Их многочисленное потомство — тому порука.

32

Дадим небольшое пояснение к рисунку: long — длинный, stack — стек, control — управляющий pop … into — удалить вершину … и поместить в, abort — аварийное окончание. Остальные ключевые слова имеют тот же смысл, что в яэыке Паскаль. — Прим. перев.

33

В алгоритм, вероятно, необходимо внести следующие изменения:

a) на шаге 1 заменить max (m, 2n) на max (2m − 2n, 2n);

b) на шаге 4 заменить 2^3·2i на 2^3·2i−1.

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

34

На самом деле a_i+1 = (a_i/5²) · (2i − 1)/(2i + 1)). Чтобы не выполнять умножение, можно хранить кроме a_i еще одно число b_i, равное (2¹⁰⁰⁰ × 16)/5²ⁱ⁻¹. Тогда переход к следующему члену осуществляется по формулам: b_i+1 = b_i/5², a_i+1 = b_i+1/(2i + 1). — Прим. перев.

35

Эти алгоритмы для очень длинных чисел работают еще быстрее алгоритма Тоома—Кука, затрачивая на умножение n-разрядных чисел время, пропорциональное n log n log log n — Прим. перев.

36

37

В журнале «Наука и жизнь» № 2, 1978, с. 150–151; № 8, 1978, с. 142—143, опубликован вариант этой игры под названием «Быки и коровы». — Прим. перев.

38

Здесь автор имеет в виду вариант той же игры, в котором вместо цифр используются фишки, окрашенные в шесть цветов. — Прим. перев.

39

В оригинале, разумеется, все рассуждения проводятся для английского текста. — Прим. перев.