Этюды для программистов

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

С помощью лишь этих программ сложения и деления можно вычислить многие математические константы: π, e, √2, ∛2, ln 2 и т. д. Реализация такого усеченного варианта потребует, вероятно, не более одной человеко-недели. Сложные динамические структуры данных уже не потребуются; у нас будет всего два-три длинных числа известного размера, для представления которых вполне подойдут массивы Фортрана.

Литература

Ахо, Хопкрофт, Ульман (Aha А. V., Haperoft J. E., Ullman J. D.). The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, MA, 1974. Section 8.2, pp. 279–286. [Имеется перевод: Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. — М.: Мир, 1979, § 8.2, с. 313–320.]

Мы почерпнули алгоритм умножения у Кнута, а алгоритм деления — у Ахо, Хопкрофта и Ульмана; оба алгоритма переработаны для наших целей Эти книги содержат подробную информацию по основам и детальный анализ алгоритмов, включая оценки сложности. Описываются также альтернативные алгоритмы умножения, основанные на быстром преобразовании Фурье[35].

Брент (Brent R. P.). A FORTRAN Multiple-Precision Arithmetic Package, Department of Computer Science, Carnegie-Mellon University, May 1976.

Брент описывает пакет подпрограмм для арифметических действий с высокой точностью, написанных на переносимом, машинно-независимом Фортране. Благодаря включенной в книгу библиографии, вы сможете найти другие работы в этой области. В пакете, предложенном Брентом, не используется алгоритм Тоома—Кука, и автор объясняет почему.

Брент (Brent R. P.). Fast Multiple-precision Evaluation of Elementary Functions, Stanford University, Technical Report STAN-CS-75-515, August 1975.

Томас (Thomas G. В., Jr.). Calculus and Analytic Geometry, 3rd ed. Addison-Wesley, Reading, MA, 1960. Section 16.3—3, pp. 809–812.

Томас приводит сведения по математическому анализу, необходимые для рассмотренных нами вычислений и подобных им; изложение в его книге простое и классическое. Рейтуиснер, а также Шенкс и Ренч — два примера из ряда работ по вычислению π. В обеих работах дается некоторый исторический обзор, обе они используют подход, предлагаемый Томасом. Брент развивает совершенно новые методы вычисления функций sin, cos, log, arctg и т. д., основанные на эллиптических интегралах. Его алгоритмы работают значительно быстрее описанных нами рядов. Работа Брента пока существует в виде технического доклада.

Кнут (Knuth D. E.). The Art of Computer Programming/Seminumerical Algorithms, Addison-Wesley, Reading, MA, 1969. Section 4.3.3, pp. 258–280. [Имеется перевод: Кнут Д. Искусство программирования для ЭВМ. Т. 2. Получисленные алгоритмы. — М.: Мир, 1977, п. 4.3.3., стр. 314–340[36].]

Рейтуиснер (Reitwiesner G. W.). An ENIAC Determination of π and e to More than 2000 Decimal Places, Mathematical Tables and Aids to Computation, 4, pp. 11–15, 1950.

Шенкс, Ренч (Shanks D., Wrench J. W.). Calculation of π to 100 000 Decimals, Mathematics of Computation, 16, pp. 76–99, 1962.

*Кудрявцев Л. Д. Математический анализ. — М.: Высшая школа, 1973.

23. Великий комбинатор, или Оптимальные стратегии для игры с угадыванием

В игре, как и в музыкальном произведении, можно выделить тему и мотивы. Причина успеха самых удачных игр часто состоит в том, что они мастерски соединяют по-новому некоторые из давно известных принципов построения игр. Как и в музыке, старая идея, возрожденная в новом обличье, может выглядеть привлекательней, чем мешанина свежеиспеченных новых веяний. В середине 70-х годов широкую популярность в Англии получила игра великий комбинатор (Mastermind)[37], и она, похоже, станет классикой. Вы и ваш компьютер получите большое удовольствие, сыграв в нее.