AOP_Tom2 (1021737), страница 86
Текст из файла (страница 86)
Э. Коллинз (С. Е. Со!!!па) н Д. Р. Муссер (П. И. Мпваег) [1пгогтаг!оп Ргосеззт81еггегз 6 (1977), 151 †1] Предлагались н другие методы деления. 1) "Деление по Фурье" [Л. Ропбег, Апа!узе с(ея Ейцаг!опз 11егегпипееа (Раба, 1831), 12.21]. В этом методе, 'часто используемом в калькуляторах, каждый новый разряд, по существу, получается посредством увеличения на каждом шаге точности представления делимого н делителя. Довольно большое количество тестов, выполненных автором, показали, что этот метод хуже описанного выше метода "деления и коррекции", но в некоторых приложениях деление по Фурье вполне приемлемо.
(См. статью Д. Г. Лемера в АММ 33 (1926), 198-206, и книгу Дж. В. Успенского (3. Ъ'. Парепзку) ТЛеогу ог" Еоиагюпз (Хенч Уогк: МсСга~ч-Н!!1, 1948), 159 — 164.) 2) В ранних вычислительных машинах, в которых не было команды деления с однократной точностью, для вычисления обратной величины числа ши!юко использовался "метод Ньютона". Его иден состоит в нахождении некоторого начального приближения хв к числу 1/с и выполнении дальнейших вычислений по формуле х„+~ —— 2х„— гх~. Этот метод обеспечивает быструю сходимость к 1/г, так как из равенства я„= (1 — г)/о следует, что х„+1 = (1 — еэ)/е. Порядок сходимости равен трем, т. е. решение можно найти по формуле х„э1 — — х„+ х„(1 — пх„) + х„(1 — вх ) = х„(1 + (1 — сх„)(1 + (1 — вх„))), заменив на каждом шаге е на 0(ез). Аналогичные формулы получены для четвертого порядка сходимости (см.
Р. НаЬ1пож!1г, САСМ 4 (1961), 98). Для выполнения вычислений с очень большими числами метод Ньютона со вторым порядком точности (с последующим умножением на и) может действительно оказаться намного быстрее алгоритма П, если на каждом шаге повысить точность вычисления х, и. кроме того, воспользоваться программами быстрого умножения из раздела 4.3.3 (см.
алгоритм 4.3.3Н). Несколько родственных итеративных схем рассмотрено в статье Е. В. Кришнамурти, опубликованной в журнале 1ЕЕЕ Тгапа С-19 (1970), 227-231. 3) Ряд методов деления основан на разложении числа —" в ряд я ~-е (См. статью Г. Г. Лофлина (Н. Н. 1 апЗЬ11п) в журнале АММ 37 (1930), 287 — 293.) Мы уже применяли эту идею для вычислений с удвоенной точностью (см. выражение 4.2.3 †(2)).
Помимо упомянутых работ, отметим следующие статьи, посвященные арифметике с многократной точностью. Программы арифметики с высокой точностью в формате с плавающей точкой, использующие обратный код, описаны в работе А. Н. 81гопб, П. Бесгеэ1, Соп1р. Х 6 (1963), 62 — 66. Имеется описание подпрограмм повышенной точности, предназначенных для использования в программах, написанных на языках РОНТНА 4 (1. В!шп, САСМ 8 (1965), 318 — 320) и АЬООЬ (М, Т1епагй Зпойопан11о, В1Т 6 (1966), 332-338). Арифметические операции над целыми числами с неогрпниченной точностью с привлечением методов связного распределения памяти были элегантно реализованы Г. Э.
Коллинзом (О. Е. Со1йпэ) (САСМ 9 (1966). 578 — 589). Для ознакомления с более обширным набором операций над чисчамп с многократной точностью, включая логарифмы и тригонометрические функции. обратитесь к работам В.. Р. Вгеп1, АСМ Тгапа Ма~8. Яойиаге 4 (1978), 57 — 81: П. М. Бпп1Ь, АСМ Тгапа Ма1Ь. $ойи'аге 17 (1991), 273 — 283.
Достижения человечества в технике вычислений традиционно оцениваются количеством десятичных разрядов числа я, известным на данный момент истории. В разделе 4.1 упоминалось о нескольких ранних достижениях в решении этой задачи. В 1719 году Тома Фанте де Ланьи (ТЬошаз Раптет бе кайлу) вычислил число я до 127 десятичных знаков (Ыето7гез Асад. Ясб Рапэ (1719), 135 — 145; в 113-м знаке была допущена типографская ошибка]. Когда были изобретены более совершенные формулы для вычисления числа т, знаменитому вычислителю из Гамбурга Захариусу Дазе (ХасЬаг1аэ Паве) в 1844 году потребовалось менее двух месяцев для вычисления 200 правильных десятичных знаков числа я (Сге))е 27 (1844), 198).
После этого в 1853 году Уильям Шэнкс (%с!!!аш ВЬап!ся) опубликовал 607 десятичных знаков числа я. Он продолжал свои вычисления, пока в 1873 году не определил 707 правильных десятичных знаков я. [См. 1У. ВЬап!ся, СопспЬиссаля са Мнсйетас!ся (Ьопдоп, 1853); Ргос. Науа! Вос. Ьолбол 21 (1873), 318 — 319; 22 (1873), 45 — 46; 3. С. У. НоС(шапа, Ее!с. Гйг тай. ш1е! пасигнчяя. Нпсегпсйс 26 (1895), 261-264.[ Значение числа я с точностью до 707 знаков в течение многих лет широко использовалось в книгах, пака Д. Ф.
Фергюсан (В. Р. Регбляап) не заметил в 1945 гаду, что в нем имеется несколько ошибок, начиная с 528-го десятичного знака [Май. СагеССе 30 (1946), 89 — 90]. В 1949 году в рамках проведения Дня труда (ЬаЬог Вау) Г. Райтвайзнер (6. Нейнчеяпег) с сотрудниками затратил 70 часов машинного времени на ЭВМ ЕЛг1АС для вычисления 2 037 правильных десятичных цифр числа я [Май. ТаЫея апе( Ойег А!г!я со Сотр. 4 (1950), 11-15[. Ф. Гениус (Р. 6елнуя) в 1958 году получил 10 000 цифр после 100 минут вычислений на 1ВМ 704 [СЬ!!ггея 1 (1958), 17-22[.
Вскоре после этого Д. Шэнкс (О. ВЬапсся) (не путать с Уильямом!) и Дж. У. Ренч (1. 11г. 1УгепсЬ) опубликовали 100 000 цифр, полученных после почти 8 часов вычислений на ЭВМ 1ВМ 7090 и еще 4.5 часов проверки [МасЛ. Сотр. 16 (1962)., 76 — 99[. В результате проверки ими была обнаружена случайная ошибка в схеме, устраненная при повторном счете.
В 1973 году, затратив 24 часа машиннога времени на ЭВМ СЬсС 7600, .Жан Гилу (1еал Сн!!сонй) и Мартин Буйе (Магг!пе Вонуег) из французского Центра ло атомной энергии вычислили один миллион цифр числа я [см. А. ВЬсЬаса, Впгйаяа!гп 20 (1982), 65-73[. Самое поразительное, что за семь лет до этога д-р И. Дж. Мэтрикс (Гсг. 1. 3. Маспх) правильно предсказал, что миллионная цифра числа я должна равняться 5 [Матс!и Сагс!пег, Лен Масйетас!са! Поедя!аля (Вллоп апй ВсЬнясег, 1966), приложение к гл.
8), Миллиардный барьер был преодолен в 1989 году Григорием В. Чудновским (Сгебогу У. СЬпг!поен!су), Давидом В. Чудновским* (Ьсао!с! У. СЬцс!паеяйу) н независимо Ясумаса Канада (Ъ'аяшпаяа Калле!а) и Иошиакр. Тамура (УояГйаЫ Тапшга). В 1991 году после 250 часов вычислений на лично разработанном параллельном компьютере Чудновские расширили свой результат до двух миллиардов цифр.
[См. Н!сЬаге! Ргеясоп, ТЬе №и 1ог)гег 68, 2 (2 МагсЬ 1992), 36 — 67. Новая формула, примененная Чудновскими, описана в Ргас. Лас. Асай Вой 86 (1989), 8178 — 8182.[ В июле 1997 года Ясумаса Канада и Дэнсуке Такахашн (Ь!а!ян!се Та!ел!сняйй), используя два независимых метода, вычислили более 51.5 миллиардов цифр, что потребовало соответственно 29.0 и 37.1 часов вычислений на компьютере Н1ТАСН1 Ж2201 с 1024 процессорами. Будем ждать новых рекордов в связи с переходом в новое тысячелетие.
В этом разделе мы ограничились методами выполнения аряфметических операций, которые используются прн программировании компьютеров. Существуют многочисленные алгоритмы лля аппаратной реализации арифметических операций, которые представляют определенный интерес, но, по-видимому, неприменимы к машинным программам для работы с числами повышенной точности, (См., например, С. %. Ве!си4еяпег, "В!лагу Аг!сЬтес!с'", Аесгялсея !л Согпрнсегя 1 (Хеж Уог!с Асае!етгс Ргеяя, 1960), 231-308; О.
Ь. МасВог!еу, Ргос. )НЕ 49 (1961), 67 -91; С. МеСсе, 1ЙЕ Тгнпя. ЕС-11 (1962), 761 — 764; Н. Ь. Сагпег, "МнтЬег Вуягепзя апе! АпсЬтес!с", Абгапсея т Сотрисегя 6 (Лсеи Ъогсс Аеас!вийе Ргеяя, 1965), 131-194.) е Г. В. Чудновский и д. В, Чудновский — выпускники Киевского университета.— Прим. ред. В статье А.
Эдельмана (А. Ейе1шап), опубликованной в журнале ЯАМ Нелеп 89 (1997), 54 — 67, описан неизвестный, но очень поучительный "прокол" в чипе Репйшп разработки 1994 года, связанный с реализацией программы деления. Минимально достижимое при аппаратной реализации время выполнения операций сложения и умножения исследовалось в работах 8. %'[побгай, 3АСМ 12 (1965), 277-285, 14 (1967), 793 — 802, К.
Р. Вгепс, 1ЕЕЕ Тгапэ. С-19 (1970), 758 — 759, и К. Ч~. Г1оу8, ЕОС8 16 (1975), 3 — 5 (см. также раздел 4.3,3Е). УПРАЖНЕНИЯ 1. [48] Изучите раннюю историю классических влгоритмюв выполнения арифметических операций по оригинальным произведениям, скажем, Сунь Цю, аль-Хорезми, вльУклидиси, Фибоначчн (Р~Ъопасс~) н Роберта Рекорде (КоЪегг Кесогбе), и как можно точнее перескажите их методы на строгом языке алгоритмов. 2.
[15] Обобщите алгоритм А таким образом, чтобы он осуществлял сложение в столбик, вычисляя суммы т неотрицательных и-разрядных целых чисел. (Предположите. что пэ < Ь.) В. [в1] Разработайте 81Х-программу, реэлиэуюшую алгоритм нз упр, 2, н оцените время ее выполнения как функцию от пэ и и. ° 4. [Мйу] Приведите формальное доказательство корректности алгоритма А, основываясь на методе индуктивных утверждений, описанном в разделе 1.2.1. 5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
