Д. Кнут - Искусство программирования том 1 (1119450), страница 13
Текст из файла (страница 13)
Кэджори (г. Са)оП), А54М 20 (1913), 5 — 14, 35 — 47, 75-84, 107-117, 148-151, 173-182, 205-210. В заключение этого раздела выясним, как вмчпсляп1ь логарифмы. Один способ непосредственно вытекает из соотношения (7): если положить Ь* = р и возвести все части этого соотношения в степень 1Оь, то для некоторого целого гп получим Ь'"<„1О <Ь 11 (16) Таким образом, все, что нам нужно сделать для получения логарифма у, — возвести у в эту огромную степень и найти такое т, чтобы результат лежал между т- и т + 1-й степенями Ь.
Тогда искомый результат будет равен гп/10л с точностью до 6-го десятичного знака. Если несколько модифицировать этот явно непрактичный метод, получим простую и удобную процедуру. Сейчас мы покажем, как вычислить 1обю х и выразить результат в двоичной системе: !ойле х = и+ Ь1/2+ 6г/4+ Ьз/В+ Сначала сдвинем десятичную точку в числе х влево или вправо, чтобы получить 1 < х/10" < 10; таким обРазом мы опРеделим целУю часть числа 1ойш х, т. е. п.
Чтобы найти значения Ьл, 6г, ..., положим хо = х/10" и для 6 > 1 получим Ьл — — О, хь — — хгл „если хг, < 10: Ьл — — 1, хл = хг,/10, если хг, ) 10. (18) Корректность этой процедуры следует из того, что 1 < х = хг /10г 1 +ь~/гз-"з.ь,(г" 1 < 10 для 6 = О, 1, 2,..., а это можно легко доказать по индукции На практике мы должны проводить вычисления только с конечной точностью, поэтому нельзя считать равенство хл = хл, точным.
На самом деле можно считать, г что хл = хг, только приближенно с точностью до некоторого десятичного знака. Например, приведем расчеты для 1ойш2, выполненные с точностью до четырех значащих цифр: хо = 2.000; х| — — 4.000, хг = 1.600, хг = 2.560 х4 = 6.554, хл = 4.295, ь Ьт —— 0; ь Ь, =0; ь = о хо = 1.845, хг = 3.404, хв = 1.159, хо = 1.343, хго = 1.804, ьл = о; Ьг = 1; ь = о; 64 = 0; Ь, = 1; и т.
д. Погрешность вычислений приводит к росту и распространению ошибок; так, например, истинное округленное значение хло равно 1.798. Накопление ошибок в конечном счете приведет к.тому, что 6ш будет вычислено неточно, и мы получим двоичное представление (0.0100110100010000011...)г, соответствующее десятичному представлению 0.301031..., а не истинному значению, которое дается в равенстве (10). Для каждого подобного метода необходимо оценивать величину погрешности вычислений, возникающей из-за ошибок округления. В упр. 27 устанавливается верхняя граница погрешности; а если проводить вычисления с точностьк до четырех чисел после десятичной точки, как было показано в примере выше, то получим гарантию, что значение логарифма будет вычислено с погрешностью, не превышающей 0.00044.
Первоначально полученное значение логарифма является более точным потому, что значения хо, хл, хг и хг были вычислены точно. Приведенный метод просу и довольно интересен, но, скорее всего, это не самый лучший способ вычисления логарифмов на компьютере. Еще один метод описан в упр. 25 УПРАЖНЕНИЯ 1. (00] Чему равно наименьшее положительное рациональное число? 2.
(00] Может ли выражение 1+ 0.239999999... быть десятичным представлением действительного числа? 3. [02] Чему равно ( — 3) з? 4. [05] Чему равно (0.125) з?з? б. [05] Мы определили действительные числа в терминах десятичного представления. Подумайте, как можно определить их в терминах двоичного представления, и приведите аналог соотношения (2). 6. (10] Пусть х = т+ОА0э... и у = и+ Ое~ег...— действительные числа. Сформулируйте правило, которое на основе десятичного представления позволяет определить, какое из неравенств верно: х = у, х ( у или х > у. 7.
(МЙУ] Для заданных целых чисел х и у докажите правила возведения в степень на основе определения (4). 8. (25] Пусть т — целое положительное число. Дакахсите, что у любого положительного действительного числа и есть единственный положительный корень т-й степени, описав метод последовательного вычисления элементов десятичного представления этого корня: п,А,А,.... 9. (МЙУ] Для заданных рациональных чисел х и у докажите правила возведения в степень, предполагая, что эти правила выполняются для целых чисел х и у.
10. [15] Докажите, что 1ойш 2 не является рациональным числом. ь 11. (10] Если Ь = 10 и х = 1обш 2, то сколько десятичных знаков числа х нужно знать, чтобы определить трн первых десятичных знака в десятичном представлении Ь*? (Замечание. Можете использовать результаты упр. 10.] 12. (02] Объясните, почему равенство (10) следует из равенств (8). э 13. (МЙу] (а) Пусть х —,положительное действительное число, а и — положительное целое число.
Докажите неравенство 71+ х — 1 < х/и. (Ь) Используйте полученный результат для доказательства утверждения, следующего за соотношением (7). 14. (15] Докажите равенство (12). 16. (10] Докажите или опровергните следующее равенство; 1обэ х/У = !обэ х — 1ойэ У пРи х,У > О. 16. (00] Как можно вырыить!обюх через 1пх и 1п10? э 17. [05] ЧемУ Равны 1832, 1об„л,!не,!ойэ 1 и 1ойэ(-1)? 18. (10] Докажите или опровергните следующее равенство: 1обэ х = -' 18 х. э 19.
[20] Поместится ли целое число и, десятичное представление которого состоит из 14 цифр, в компьютерном слоне емкостью 47 бит плюс бит знака? 20. (10] Существует ли простое соотношение, связывающее!ойш 2 и 1ой, 10? 21. (!5] (Лагари4ми ага логари15мав.) Выразите 1обэ 1ойэ х через!п1пх., 1п!пЬ и!пЬ. ь 22. [80] (Р. В. Хемминг (К. %. Напцшпй).) Докажите, что 18 х 1а х + 1об»а х с погрешностью, не превышающей !»У»1 (Таким образом, таблицы натуральных н десятичных логарифмов можно использовать и для получения приближенных значений,ввоичных логарифмов.) 23. [М85) С помощью рнс.
б дайте геамеплрическое доказательслво того, что ! и ху = 1и х + 1п у. 24. (15] Объясните, как нужно модифицировать метод вычисления логарифмов по основанию 10, приведенный в конце раздела, чтобы его можно было применить для вычисления логарифмов по основанию 2. 28.
(88] Предположим, что у нас есть двоичный компьютер (т. е. компъютер, в котором испалъзуется двоичная система счисления. — Прим. нерее.) и имеется некоторое число х, 1 < х < 2. Покажите, что следующий алгоритм, в котором используются только операщ»н сдвига, сложения н вычитания в объеме, пропорциональном числу разрядов, которое определяется требуемой степенью точности, можно прил»енить для приближенного вычисления У = !оклх. Ь1. (Инициализация.] Присвоить у +- О, г +- х с помощью сдвига вправо на 1, й» вЂ” 1.
Ь2. (Проверка окончания.] Если х = 1, то прекратить выполнение. Ь3. [Сравнение.] Если х — г < 1, то присвоить г +- г с помощью сдвига вправо иа 1, !г +- (г + 1, и повторить этот шаг. Ь4. [Замещение значений.] Присвоить х» — х — х, г +- х с помощью сдвига вправо на 7», У»- У + !обл(2"/(2 — 1)) и пеРейти к шагУ Ь2. [Зомечаное. Описанный метод очень похож на тот метод, который используется в компьютерах для выполнения операции деления. Эта идея, в сущности, принадлежит Генри Бриггсу (Непгу Вг!88э); он применял данный метод (только не к двоичным, а к десятичным операциям) для вычисления таблиц логарифмов, опубликованных в 1624 году.
Нам нужна дополнительная таблица констант !ой» 2, !ойл(4/3), 1ойл(8/7) и т. д. до значения, равного точности компьютера. В данном алгоритме преднамеренно делается ошибка, так как числа сдвигаются вправо с тем, чтобы в конечном счете х свелось к 1 и выполнение алгоритма прекратилось, В этом упражнении вы должны показать, что алгоритм конечен и вычисляет приближенное значение 1обл х.] 26. [М87] Определите верхние границы точности алгоритма из предыдущего упражнения, взяв за основу точность, используемую в арифметических операциях. ь 27.
(М85] РассмотР»»л» метод вычислениЯ 1ой,о х, описанный в этом Разделе. ПУсть х'„— вычисленное приближенное значение хл, причем ха определяется из соотношения х(1 — б) < 10'ха < х(1+ г), а х', — из соотношений (18), где выражение (х~л») нужно заменить на ул и (х'„,)'(1 — б) < ул < (х'„,) (1+ »), где 1 < ул < 100. В этих формулах б и г — малые константы, соответствующие верю»ей и нижней границам погрешностей округления. Покажите, что если результат вычислений обозначить 1о8' х, то через к шагов мы получим 1об,ох+2!об,а(1 б) — 1/2" < 1об'х < 1о8»ах+2!ая,а(1+ ). 28.
(МЗО] (Р. »уей»»л»ан (К. Реупшаа).) Придумайте метод вычисления б~, где 0 < х < 1, используя только операции сдвига, сложения и вычитания (анйлогично алгоритму из упр. 25), и проанализируйте его точность. 29. (НМЙО) Пусть х — действительное число, большее, чем 1. (а) При каком действительном Ь > 1 величина 6!ойэх минимальна? (Ь) При каком целом 6 > 1 эта величина минимальна? (с) ПРи каком целом 6 > 1 величина (6 + 1) !ойэ х минимальна? 1.2.3. Суммы и произведения Пусть ат, ах,...— произвольная последовательность чисел.
Часто возникает необходимость в изучении сумм вида ат + ат + + а„. Такую сумму более компактно можно записать следующим образом: а, или ~ ~ау. (1) 1<тйп Если и равно нулю, то по определению значение суммы тоже равно нулю. Наше определение суммы можно обобщить. Если Л(т) — это любое соотношение, зависящее от т', то запись (2) лО! обозначает сумму всех а,, где т' — целое чигло, удовлетворяющее условию??(?). Если таких целых чисел не существует, то значение суммы (2) по определению принимается равным нулю. Буква т' в (1) и (2) — -это так называемый немой индекс (или индексная переменная), который вводится только для удобства записи.
Для обозначения индексов суммирования обычно используются буквы т, т',?т, тп, и, г, э, Ь (иногда с надстрочными индексами или штрихами). Занимающие много места обозначения сумм, как в (1) и (2), можно заменить более компактной записью 2 ',"ы, ау или !" л! ! ат. Знак "~ " и немые индексы для обозначения операции суммирования в конечных пределах были введены Ж.
Фурье (2. Роцбег) в 1820 году. СтРого говоРЯ, обозначение 2.',й <„ ат ЯвлЯетсЯ недостаточно четким, так как т йтй ь не совсем ясно, по какому индексу выполняется суммирование — по т' или по п. В данном конкретном случае было бы неразумно считать это суммой значений, для которых и >?'. Но можно привести более сложные примеры, в которых индекс суммирования определен недостаточно четко, как в случае 2.'.< ('.+"„). В подобных ситуациях отличить немые индексы от индексов, имеющих самостоятельное значение (т. е. таких, которые фигурируют не только в записи суммы), можно только по контексту.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
