а дисперсия равна

g::(i)+g„(i)-g„(i)

lf 2n 26+1 26 + 2 fly 1 /ЦЛ

-4V"+6-l (6-1)2 + (6-1)2 Uj (6-l)2U/j-

Таким образом, при сделанных допущениях число переносов несколько меньше, чем п.

История и библиография. Раннюю историю описанных в этом разделе классических алгоритмов предоставляем читателю в качестве интересной темы для самостоятельного изучения. Здесь же будет прослежена лишь история их внедрения на современных компьютерах.

Использование числа 10" в качестве основания системы счисления применительно к умножению больших чисел на калькуляторе обсуждалась Д. Н. Лемером (D. N. Lehmer) и Дж. Р. Баллантином (J. Р. Ballantine) [АММ 30 (1923), 67-69]. Арифметика с удвоенной точностью для компьютеров впервые была рассмотрена Дж. фон Нейманом (J. von Neumann) и Г. Г. Голдстайном (Н. Н. Goldstine) во введении к руководству по программированию, впервые опубликованному в 1947 году [J. von Neumann, Collected Works 5, 142-151]. Теоремы A и В, изложенные выше, принадлежат Д. А. Поупу (D. А. Pope) и М. Л. Стейну (М. L. Stein) [САСМ 3 (1960), 652-654]. В их статье приведена также библиография более ранних работ, посвященных арифметике с удвоенной точностью. Другие способы выбора пробного частного q рассмотрены А. Г. Коксом (А. G. Сох) и Г. А. Лютером (Н. А. Luther) в САСМ 4 (1961), 353 [деление на Vn-i + 1 вместо Vn-i], а также М. Л. Стейном в САСМ 7 (1964), 472-474 [деление на Vn-i или и„ 1 + 1 в зависимости от величины и„ 2]- Е. В. Кришнамурти (Е. V. Krishnamurthy) [САСМ 8 (1965), 179-181] показал, что исследование остатка от деления с однократной точностью позволяет усилить теорему В. Кришнамурти и Нанди (Nandi) [САСМ 10 (1967), 809-813] предложили способ замены нормализации и денормализации в алгоритме D вычислением q, которое базируется на анализе нескольких ведущих разрядов операндов. Интересный анализ оригинального алгоритма Поупа и Стейна выполнили Г. Э. Коллинз (G. Е. Collins) и Д. Р. Муссер (D. R. Musser) [Information Processing Letters 6 (1977), 151-155].

Предлагались и другие методы деления.

1) "Деление по Фурье" [J. Fourier, AnaJyse des Equations Determinees (Paris, 1831), §2.21]. В этом методе, часто используемом в калькуляторах, каждый новый разряд, по существу, получается посредством увеличения на каждом шаге точности представления делимого и делителя. Довольно большое количество тестов, выполненных автором, показали, что этот метод хуже описанного выше метода "деления и коррекции", но в некоторых приложениях деление по Фурье вполне приемлемо. (См. статью Д. Г. Лемера в АММ 33 (1926), 198-206, и книгу Дж. В. Успенского (J. V. Uspensky) Theory of Equations (New York: McGraw-Hill, 1948), 159-164.)

2) В ранних вычислительных машинах, в которых не было команды деления с однократной точностью, для вычисления обратной величины числа широко использовался "метод Ньютона". Его идея состоит в нахождении некоторого начального приближения Хо к числу 1/v и выполнении дальнейших вычислений по формуле

Хп+1 = - vx. Этот метод обеспечивает быструю сходимость к 1/v, так как из равенства л;„ = (1 - e)/v следует, что Xn+i = (1 - Порядок сходимости равен

трем, т. е. решение можно найти по формуле

Хп+1 =Хп + Хп{1 - VXn) + Хп{1 - VXnf

= л;„ (1 + (1 - vxn){l + (1 - VXn))),

заменив на каждом шаге е на 0{t). Аналогичные формулы получены для четвертого порядка сходимости (см. Р. Rabinowitz, САСМ 4 (1961), 98). Для выполнения вычислений с очень большими числами метод Ньютона со вторым порядком точности (с последующим умножением на и) может действительно оказаться намного быстрее алгоритма D, если на каждом шаге повысить точность вычисления Хп и, кроме того, воспользоваться программами быстрого умножения из раздела 4.3.3 (см. алгоритм 4.3.3R). Несколько родственных итеративных схем рассмотрено в статье Е, В. Кришнамурти, опубликованной в журнале ШЕЕ Trans. С-19 (1970), 227-231.

3) Ряд методов деления основан на разложении числа :~ в ряд v + e V \ \v/ \v/ \v/

(См. статью Г. Г. Лофлина (И. И. Laughlin) в журнале АММ 37 (1930), 287-293.) Мы уже применяли эту идею для вычислений с удвоенной точностью (см. выражение 4.2.3-(2)).

Помимо упомянутых работ, отметим следующие статьи, посвященные арифметике с многократной точностью. Программы арифметики с высокой точностью в формате с плавающей точкой, использующие обратный код, описаны в работе А. Н. Stroud, D. Secrest, Сотр. J. 6 (1963), 62-66. Имеется описание подпрограмм повышенной точности, предназначенных для использования в программах, написанных на языках FORTRAN (I. Blum, САСМ 8 (1965), 318-320) и ALGOL (М. Tienari, Suokonautio, BIT 6 (1966), 332-338). Арифметические операции над целыми числами с неограниченной точностью с привлечением методов связного распределения г1амяти были элегантно реализованы Г. Э. Коллинзом (G. Е. Collins) [САСМ 9 (1966). 578-589]. Для ознакомления с более обширным набором операций над числа.ми с многократной точностью, включая логарифмы и тригонометрические функции, обратитесь к работам R. Р. Brent, ACM Trans. Math. Software 4 (1978), 57-81: D. M. Smith, ACM TYans. Math. Software 17 (1991), 273-283.

Достижения человечества в технике вычислений традиционно оцениваются количеством десятичных разрядов числа тг, известным на данный момент истории. В разделе 4.1 упоминалось о нескольких ранних достижениях в решении этой задачи. В 1719 году Тома Фанте де Ланьи (Thomas Fantet de Lagny) вычислил число тг др 127 десятичных знаков [Afemoires Acad. Sci. Paris (1719), 135-145; в 113-м знаке была допущена типографская ошибка].

Когда были изобретены более совершенные формулы для вычисления числа гг, знаменитому вычислителю из Гамбурга Захариусу Дазе (Zacharias Dase) в 1844 году потребовалось менее двух месяцев для вычисления 200 правильных десятичных знаков числа ж [Crelle 27 (1844), 198]. После этого в 1853 году Уильям Шэнкс

(William Shanks) опубликовал 607 десятичных знаков числа ж. Он продолжал свои вычисления, пока в 1873 году не определил 707 правильных десятичных знаков тт. [См. W. Shanks, Contributions to Mathematics (London, 1853); Proc. Royal Soc. London 21 (1873), 318-319; 22 (1873), 45-46; J. C. V. Hoffmann, Zeit. fiir math, und naturwiss. Unterricht 26 (1895), 261-264.]

Значение числа тг с точностью до 707 знаков в течение многих лет широко использовалось в книгах, пока Д. Ф. Фергюсон (D. F. Ferguson) не заметил в 1945 году, что в нем имеется несколько ошибок, начиная с 528-го десятичного знака [Math. Gazette 30 (1946), 89-90]. В 1949 году в рамках проведения Дня труда (Labor Day) Г. Райтвайзнер (G. Reitwiesner) с сотрудниками затратил 70 часов машинного времени на ЭВМ ENIAC для вычисления 2 037 правильных десятичных цифр числа ж [Math. Tables and Other Aids to Сотр. 4 (1950), 11-15]. Ф. Гениус (F. Genuys) в 1958 году получил 10 ООО цифр после 100 минут вычислений на IBM 704 [ChifFres 1 (1958), 17-22]. Вскоре после этого Д. Шэнкс (D. Shanks) (не путать с Уильямом!) и Дж. У. Ренч (J. W. Wrench) опубликовали 100 ООО цифр, полученных после почти 8 часов вычислений на ЭВМ IBM 7090 и еще 4.5 часов проверки [Math. Сотр. 16 (1962), 76-99]. В результате проверки ими была обнаружена случайная ошибка в схеме, устраненная при повторном счете. В 1973 году, затратив 24 часа машинного времени на ЭВМ CDC 7600, Жан Гилу (Jean Guilloud) и Мартин Буйе (Martine Bouyer) из французского Центра по атомной энергии вычислили один миллион цифр числа ж [см. А. Shibata, Surikagaku 20 (1982), 65-73]. Самое поразительное, что за семь лет до этого д-р И. Дж. Мэтрикс (Dr. I. J. Matrix) правильно предсказал, что миллионная цифра числа тг должна равняться 5 [Martin Gardner, New Mathematical Diversions (Simon and Schuster, 1966), приложение к гл. 8]. Миллиардный барьер был преодолен в 1989 году Григорием В. Чудновским (Gregory V. Chudnovsky), Давидом В. Чудновским* (David V. Chudnovsky) и независимо Ясумаса Канада (Yasumasa Kanada) и Иошиаки Тамура (Yoshiaki Tamura). В 1991 году поспе 250 часов вычислений на лично разработанном параллельном компьютере Чудновские расширили свой результат до двух миллиардов цифр. [См. Richard Preston, The New Yorker 68,2 (2 March 1992), 36-67. Новая формула, примененная Чудновскими, описана в Proc. JVat. Acad. Sci. 86 (1989), 8178-8182.] В июле 1997 года Ясумаса Канада и Дэисуке Такахаши (Daisuke Takahashi), используя два независимых метода, вычислили более 51.5 миллиардов цифр, что потребовало соответственно 29.0 и 37.1 часов вычислений на компьютере HITACHI SR2201 с 1024 процессорами. Будем ждать новых рекордов в связи с переходом в новое тысячелетие.

В этом разделе мы ограничились методами выполнения арифметических операций, которые используются при программировании компьютеров. Существуют многочисленные алгоритмы для аппаратной реализации арифметических операций, которые представляют определенный интерес, но, по-видимому, неприменимы к машинным программам для работы с числами повышенной точности. (См., например, G. W. Reitwiesner, "Binary Arithmetic", Advances in Computers 1 (New York: Academic Press, 1960), 231-308; O. L. MacSorley, Proc. IRE 49 (1961), 67-91; G. Metze, IRE Trans. EC-11 (1962), 761-764; H. L. Garner, "Number Systems and Arithmetic", Advances in Computers 6 (New York: Academic Press, 1965), 131-194.)

* Г. B. Чудновский и Д. В. Чудновский- выпускники Киевского университета.- Прим. ред.