Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 86
Текст из файла (страница 86)
Р. Муссер (О. Н. Мцвэег) (1п)огшабоп Ргосевэшй 7еггегэ 6 (1977), 151-155]. Предлагались н другие методы деления. 1) "Деление по Фурье" ]2. Ропг1ег, Апа)уэе беэ Едиабопэ Пейегшшбез (Рапв, 1831), з2.2Ц. В этом методе, 'часто используемом в калькуляторах, каждый новый разряд, по существу, получается посредством увеличения на каждом шаге точности представленкя делимого и делителя. Довольно большое количество тестов, выполненных автором, показали, что этот метод хуже описанного выше метода "деления и коррекции", но в некоторых приложениях деление по Фурье вполне приемлемо. (См, статью Д.
Г. Лемера в АММ 33 (1926), 198-206, н книгу Дж. В. Успенского (3. У. Барепэ1су) Тйеогу ог" Ейнасюпз (Нем Уой: Мсбгав-НШ, 1948), 159-164.) 2) В ранних вычислительных машинах, в которых не было команды деления с однократной точностью, для вычисления обратной величины числа широко использовался "метод Ньютона". Его идея состоит в нахождении некоторого начального приближения яе к числу 1/е н выполнении дальнейших вычислений по формуле (!У!О!аш ЯЬвп)св) опубликован 607 десятичных знаков числа т. Он продолжал свои вычисления, пока в 1873 году не определил 707 правильных десятичных знаков т. [См. 1У. ЯЬап1св, СопсИЬис!опв со МасЬетаскя (Ьопс!оп, 1853); Рюс.
Науа! Яос. Ьопс(оп 21 (1873), 318-319; 22 (1873), 45-46; Л. С. У. Нойспапп, Ке!с. 61г тасЛ. ппд па!ига!ав. Ьпсегг(сЫ 26 (1895), 261-264.) Значение числа т с точностью до 707 знаков в течение многих лет широко использовалось в книгах, пока Д. Ф. Фергюсон (Р. Р.
Регйпвоп) не заметил в 1945 году, что в нем имеется несколько ошибок, начиная с 528-го десятичного знака [МасЬ. Свлессе 30 (1946), 89-90]. В 1949 году в рамках проведения Дня труда (1 аЬог 1)ау) Г. Райтввйзнер (С. Не!сабсяпег) с сотрудниками затратил 70 часов машинного времени на ЭВМ ЕХ1АС для вычисления 2 037 правильных десятичных цифр числа т [МвсЬ. ТаЫев апс! ОсЬег А!с(в со Сотр. 4 (1950), 11-15). Ф. Гениус (Р.
Сеппув) в 19об году получил 10 000 цифр после 100 минут вычислений на П)М 704 [СЬ!бсср 1 (1958), 17-22). Вскоре после этого Д. Шэнкс (В. ЯЬап1св) (не путать с Уильямом!) и Дж. У. Ренч (Л, 5'. )УгепсЬ) опубликовали 100 000 цифр, полученных после почти 8 часов вычислений на ЭВМ 1ВМ 7090 и еще 4.5 часов проверки [МасЬ. Сотр. 16 (1962), 76-99]. В результате проверки ими была обнаружена случайная ошибка в схеме, устраненная при повторном счете. В 1973 году, затратив 24 часа машинного времени на ЭВМ СВС 7600, Жан Гилу (Зеап Сшйот!) н Мартин Буйе (Маг!те Вопуег) из французского Центра по атомной энергии вычислили один миллион цифр числа в' [см. А. ЯЬ!Ъаса, Япг!)сляайп 20 (1982), 65-73).
Самое поразительное, что за семь лет до этого д-р И. Дж, Мэтрнкс (Вг. 1. 1. «Маспх) правильно предсказал, что миллионная цифра числа т должна равняться 5 [Матс!и Саус)пег, Хесг МасйепсаНсв! 11!гегв!опв (Яппоп апб ЯсЬпвсег, 1966), приложение к гл. 8].
Миллиардный барьер был преодолен в 1989 году Григорием В, Чудновским (Сгейогу У. СЬпс!поувйу)., Давидом В. Чудновскими (Оау!с! У. СЬпдпоув1су) н независимо Ясумаса Канада (Уаонпава Капаба) и Иошиаки Тамура (УовЬ!а)п Тапшга). В 1991 году после 250 часов вычислений на лично разработанном параллельном компьютере Чудновские расширили свой результат до двух миллиардов цифр. [См.
Н!сЬагс! Ргежоп, ТЬе №и Уогйег 68, 2 (2 МагсЬ 1992), 36 — 67. Новая формула, примененная Чудновскими, описана в Ргос. «Уас. Асад. Яс!. 86 (1989), 8178-8182.) В июле 1997 года Ясумаса Канада и Дэвсуке Такахашн (Ва!вийе ТаЬаЬавГ6), используя два независимых метода, вычислили более 51.5 миллиардов цифр, что потребовало соответственно 29,0 и 37.1 часов вычислений на компьютере Н1ТАСН! ЯВ220! с 1024 процессорами.
Будем ждать новых рекордов в связи с переходом в новое тысячелетие. В этом разделе мы ограничились методами выполнения арифметических операций, которые используются при программировании компьютеров. Сучцествуют многочисленные алгоритмы для аппаратной реализации арифметических операций, которые представляют определенный интерес, но, по-видимому, неприменимы к машинным программам для работы с числами повышенной точности.
(См., например. С. %. Не!са4евпег, "В!пату Аг!сЬтес!с", Ас(уапсав !и Согпрпсегв 1 (Хек Уог1с Асяс!ет!с Ргевв, 1960), 231-308; О. 1.. МасЯог)еу, Ргос. !НЕ 49 (1961), 67-91; С. Месте, 1НЕ Тгвла ЕС-11 (1962), 761-764; Н. 1. Сагпег, еЫптЬег Яувсетв апс! Аг!с!пиес!с", Ас(сансов ш Сотрпсегв 6 (Косе Уогй: Аеас(ет!с Ргевв, 1965)„131-194.) е Г. В. Чулиенекий и д. В. Чулнееекий — ныауекиики Киевского униеереитета.
— Прим. ред. В статье А. Эдельмана (А. Е8е(пшп), опубликованной в журнале ЯАМ Кеьйе» 39 (1997), 54-67, описан неизвестный, но очень поучительный "проков" в чипе РепВппг разработки 1994 года, связанный с реализацией программы деления. Минимально достижимое при аппаратной реализации время выполнения операций сложения и умножения исследовалось в работах 8. Ж1побгаб, ЛКСМ 12 (1965), 277-285, 14 (1967), 793-802, К, Р.
Вгепс, 1ЕЕЕ Тгапэ. С-19 (1970), 758-759, и К. 1Ч. Р1оуб, РОСЕ 16 (1975), 3-5 (ель также раздел 4.3.3Е). УПРАЖНЕНИЯ 1. [43] Изучите рвнюою историю классических алгоритмов выполнения арифметических операций яо оригинальным произведениям, скажем, Сука Цю, аль-деревни, альУклидиси, Фибоначчи (Р1Ьопасст) н Роберта Рекорде (ВоЬегг Кесогбе), н как можно точнее перескажите их методы на строгом язмке алгоритмов. 2.
[И] Обобщите алгоритм А таким образом, чтобы он осуществлял сложение в столбик, вычисляя суммы гп неотрицательных и-разрядных целых чисел. (Предположите, что гп < Ь.) 3. [31] Разработайте И11-программу, реализующую алгоритм из упр. 2, н оцените время ее вьпюлнення как функцию от ш и и. 4. [М31] Приведите формальное доказательство корректности алгоритма А, основываясь на методе индуктивных утверждений, описанном в разделе 1.2.1.
б, [31] Алгоритм А выполняет сложение двух вводимых чисел, двигаясь справа налево. но иногда данные более доступны для считывания глеав направо, Разработайте алгоритм, который выдает тот же ответ, что и алгоритм А, но порождает разряды результата слева направо в, если происходит перенос, делаэзщий предыдущее значение неверным, возвращаэтсэ назад, чтобы изменить предыдущее значение. [Замечание, В ранних индусских и арабских манускриптах„посвященных сложению слева направо, используется именно такой способ сложения.
Вероятно, причиной тому послужила ориентация алгоритма А на выполнение операций слева направо на абаках. Алгоритм сложения справа налево стал логическим продолжением этого алгоритма благодаря работам эль-Уклцзиси, возможно, потому, что арабы пишут справа налево.] й. [33] Разработайте алгоритм, который выполняет сложение слева направо (как в упр. б), ио никогда не запоминает разряд результата, пока существует возможность его изменения нз-за последующих переносов. Уже занесеняые значения результата не должны изменяться после запоминания очередного значения любого разряда, [Указание.
Следите за количеством последовательных разрядов (Ь вЂ” 1), которые еще не хранятся в результате.] Алгоритм такого вида удобен, например, в ситуации, если вводимые и выводимые числа считываются и записывается на магнитную ленту или если они появляются в простом линейном списке. 7. [М33] Определите среднее число случаев, когда выполнение алгоритма нз упр.
5 приведет к необходимости возврата при переносе и изменению Й рэзрядоэ частичного ответа для в = 1, 2, ..., и. (Предполагается, что оба входных числа имеют независимые н равномерные распределения на интервале О и Ь" — 1.) 8. [М36] Разработайте программу для и11, реализующую алгоритм из упр. 5, и определите среднее время ее работы, исходя из ожидаемого числа переносов, которое подсчитано в тексте. й. [31] Обобщите алгоритм А так. чтобы получившийся алгоритм складывал два и-разрядных числа в системе счисления со смеоюнимм основанием Ьо, Ьп ... (справа налево).
Таким образоьс, наименее значимый разряд расположен в интервале от 0 до Ьг — 1 и т. д. (см. формулу 4.1-(9)). 10, [18] Будет ли правильно работать программа В, если поменять местами команды в строках 06 и 07, а также в строках 05 и 062 11. [10] Разработайте алгоритм сравнения двух неотрицательных н-разрядных целых чисел и = (и г... иьио)ь и е = (е„ь... еьоа)ь, который определяет, какое нз неравенств, и < о, и = е или и > е, выполняется.
12. [16] В алгоритме 9 предполагается, что заранее известно, какой из двух исходных операндов больше. Даже если информация отсутствует, все равно можно начать и так или иначе выполнить вычитание, но при этом обнаружится, что лишнее "заимствование" со. хранилось до самого конца алгоритма. Постройте другой алгоритм, в котором можно было бы использовать (если в конце работм алгоритма 8 имеется "заимствование") дополнение (ьоь-ь ... ич же)ь и поэтому вычислять абсолютное значение разности между и и е. 13. [21] Разработайте программу длн 611, которэл умножает (и„с...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
