Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 67
Текст из файла (страница 67)
00000)з = О, если ее выполнение ироды<жать неограниченно долго, Значения -' и — „-' представляют собой единстве<пгые 2-аднческие числа, которые после формалы<ого умножения на 7 дают соответственно 1 и -1. Зна- чения „-" и —,'„есть примеры 2-аднческих чисел, не являющихся 2-адическими "пелымн", так как они имеют ненулевые биты справа от разделяющей точки. Приведенные два значения </-7, получающиеся одно из другого в результате перемены знака, являются единственными 2-адическнми числами, которые после формального возведения в квадрат дают (... 1111111111ПОО!)<.
а) Докажите, что любое 2-едическое число к можно разделить на произв<шансе иену- левое 2-адическое число о, чтобы вычислить 2-адическое число и:, удовлетворяюп<ее равенству о = ою. (Следовательно, множество 2-едических чисел образует поле; см. раздел 4.6.1.) Ь) Докажите, что 2-адическое предста<ление рационального числа — 1/(2п + 1)., где и— положительное целое число, можно получить следующим образом. Сначала находим обычное двоичное разложение числа +1/(2п+ 1), которое имеет вид периодической дроби (О.ацп... )г (а — некоторая строка из нулей и единиц).
Тогда (... оно)< буде~ 2-адическим представлением числа -1/(2п+ 1). с) Докажите, что 2-аднческое представление числа в периоднчно (т. е. «я+х = ви для всех больших Х при некотором А > 1) тогда и только тогда, когда и рапионально (к е. и = и</и для некоторых целых чисел <и и и), <1) Докажите, что если и — целое число, то </й является 2-адическим числом только в том случае, если для иекоторога неотрицательного целого числа и оно удовлетворяет условию ппкк12ы+ = 2ы.
(Таким образом, либо пщо<18 = 1, либо пщо<)32 = 4, и т. д.) 32. (М40) (И. 3. Рупа (1. Е. )1вхза).) Сформируйте бесконечно много целых чисел, в троичных представлениях которых используются только нули и единицы, а в четверичном представлении — тачько нули, единицы и двойки. <1) Докажите, что последовательность 7, -13 2, 7 2<, — 13 2з, ..., 7 2ы, — 13 2ы+<, является бинарным базисом, и найдите предста<ьтение числа и = 1. ь 31.
(МУЗ) Одно обобщение представления пюел в обратном двоичном коде, известное как "2-аднческие числа", было предложено в работе К. Напев!, Сгейе 127 (1904), 51-84. (В действительности К. Гензель предложил р-адоческне коала для любого простого числа р.) 2-алическое число можно рассматривать как двоичное число 33. (Мед) (Д.
А. Кларнер (11. А. К1агпег).) Пусть множество 11 — произвольное множество целых чисел, Ь вЂ” любое положительное целое число, а ܄— количество различных целых чисел, которые могут быть записаны как и-разрядные числа (а„-~...а~ос)ь по основанию Ь с цифрами о; в 11. Докажите, что последовательность (Ь„) удовлетворяет линейному рекуррентному соотношению, н поясните, как вычислить производящую функцию ~,„йьзь. Пронллюстрируйте разработанный алгоритм, показав, что в случае, когда Ь = 3 и Х> = (-1, 0,3), число Ьь есть число Фнбоначчи.
ь 34. (йй) (Г. В. Райтвайзнер (С. Ж, Ке(свйеяюг), 1960.) Поясните, как представить заданное целое число п в виде (... азотов)м где каждое нз а; есть -1, 0 либо 1, используя наименьшую ненулевую цифру. 4.2. АРИФМЕТИКА ЧИСЕЛ С ПЛАВАЮЩЕЙ ТОЧКОЙ В этом РАзделе рассмотрены основные принципы выполнения арифметических операций над числами с "плавающей точкой" и проанализирован внутренний механизм таких вычислений, Вероятно, у многих читателей данная тема не выювет слишком большого интереса либо потому, что в вычислительных машинах, на которых онн работают, имеются встроенные команды операций над числами с плавающей точкой, либо потому, что нужные подпрограммы содержатся в операционной системе, Но не следует считать, что материал этого раздела относится исключительно к компетенции инженеров — конструкторов ЭВМ или узкого круга лиц, которые пишут системные подпрограммы для новых машин.
Каждый грамотный программист должен иметь представление о том, что происходит при выполнении элементарных шагов арифметических операций иад числами с плавающей точкой. Предмет этот совсем не так тривиален, как принято считать; в нем удивительно мною интересного.
4.2.1. Вычисления с однократной точностью А, Обозначение чисел с плавающей точкой. В разделе 4.1 были рассмотрены различные способы обозначения чисел с фиксированной точкой. При таком способе обозначения программист знает, где положено находиться разделяющей точке в числах, с которыми выполняются те или иные операции. В некоторых ситуациях при выполнении программы значительно удобнее сделать положение разделяющей точки динамически изменяющимся, иными словами, сделать точку "плавающей" и связать с каждым чииюм информацию о ее положении.
Эта идея уже давно использовалась в научных расчетах, в особенности для представления очень больших чисел наподобие числа Авогадро Х = 6.02214 х 10эз или таких очень малых чисел, как постоянная Планка Ь = 6.6261 х 10 ш эрг.с. В этом разделе речь пойдет о р-разрядных числах с плавающей 1почкой по основанию Ь с избмшкам й. Такое число представляется парой величин (е, У), которой отвечает значение (е, у) = у х Ь' '. (1) Здееь е — целое число, изменяющееся в соответствующем интервале значений, а У— дробное число со знаком. Условимся, что И<1, иными словами, разделяющая точка в позиционном представлении 1 находится в крайней слева позиции. Точнее говоря, соглашение о том, что мы имеем дело с р-разрядными числами, означает, что Ьгу — целое число и (2) -Ь~ с Ь~У< Ь'.
Термин "двоичное число с плавающей точкой", как всегда, будет означать, что Ь = 2, термин "десятичное число с плавающей точкой" — что Ь = 10 и т. д. Используя 8-разрядные десятичные числа с плавающей точкой с избытком 50, можно, например, написать число Авогадро А' = (74, +.60221400); постоянная Планка Ь = (24, +.66261000).
Две компоненты, е и 1, числа с плавающей точкой называются его порядком и дробной частью соответственно. (Ииогда используются и друтие названия, особенно "характеристика" и "мантисса"; одиако слово "маитиссае для обозначения дробной части приводит к путаиице в терминологии, так как этот термин употребляется совсем в другом смысле в теории логарифмов и, кроме того, английское слово "шапОзза" означает "мало дающее добавление",) В компьютере И1Х числа с плавающей точкой имеют вид (4) Это представление с плавающей точкой по основанию Ь с избытком е, с четырьмя зиачашими "цифрами", где Ь есть размер байта (т, е. Ь = 64 или Ь = 100) и д равияется ЯЬ) . Дробная часть равва х у у 1 1, а порядок и е находится в иитервале 0 < е < Ь.
Такое внутреннее представлеиие-" типичный пример соглашений, которые приняты в большиистве существующих компьютеров, хотя осиовавие Ь здесь гораздо болыпе, чем обычно используемое. В. Нормализованные вычисления. Число с плавающей точкой (е, у) является иормализоваиным, либо если иаиболее значимая цифра в представлеиии у отлична от нуля, так что 1/Ь < Щ < 1, (5) либо если ~ = О, а е принимает наименьшее возможиое зиачеяие. Чтобы устввовить, какое из двух нормализованных чисел с плавающей точкой имеет большую величииу, достаточно сравиить их порядки; только если порядки раины, пужио анализировать и дробные части. Большинство ныне применяемых стандартных подпрограмм работает почти исключительио с нормализованными числами: предполагается, что входные значения для подпрограмм нормализованы, а результаты всегда иормализуются. При реализации этих соглашений в системных библиотеках мы теряем возможиость представлять некоторые числа очень малой величииы (иапример, значение (О, .00000001) ие может быть нормализовано без формирования отрицательного порядка), ио мы выигрываем в скорости, единообразии и получаем возможность сравнительно легко ограиичить отиосительиую ошибку вычислений.
(Арифметика иеиормализоваииых чисел с плавающей точкой будет рассмотрена в разделе 4.2.2.) Рассмотрим теперь арифметические операции иад нормализованными числами с плавающей точкой подробнее. Попутно затронем и структуру подпрограмм, реализукяцих эти операции (предполагая, что в нашем распоряжении имеется компьютер без аппарат~юй реализации этих арифметических операций).
В стандартных подпрограммах для выполяеиия арифметических действий иад числами с плавающей точкой, написанных иа машинном языке, в очень большой степени используются крайне специфические особенности конкретной модели компьютера. Именно поэтому так мало схцдства между двумя подпрограммами, скажем, сложения чисел с плавающей точкой, иаписвииыми для разных машии. Все же тщательный анализ большого числа подпрограмм как для двоичиых, так и для десятичных компьютеров показывает, что в действительиости даииые программы имеют много общего, и обсуждение этой темы, вполне возможно, ие зависит от конкретной машины. Рис.
2. Сложение чисел с плавающей точкой, Первый (и наиболее трудный!) из алгоритмов, обсуждаемых в этом разделе,— это процедура сложения чисел с плавающей точкой: (б) (е,У„) Ю(е Ук) = (е У ). Ввиду того что арггфметпческие действггя яад числами с плавающей точкой являкггся по самой своей сути приближенными, а не точяымн, д, я обозначения оперений сложения, вычитания, умножения и деленно с плавающей точкой здесь будут использоваться "округленные" символы чтобы отличать приближенные операции от точных. Идея., лежащая в основе сложения с плавающей точкой, довольно проста.
По. латая, что е~ ) ек, формируем результат по принципу еи ек~ Ук Уи + Уюф (таким образом, выравнивается положение разделяющих точек и соответственно положение разрядов слагаемых), а затем норма.лизуем результат. Может возникнуть н~ккопько ситуаций, которые делают выполнение этого процесса нетривиальным; более. точное описание метода дается в следующем алгоритме. Алгоритм А (Слолсение чисел с плавающей точкой). Для заданных р-рвзрядных нормализованных чисел с плавающей точкой и = (е„, У„) и о = (е„, у„) по основанию 6 с избытком о строится сумма эо = и а о, Данный алгоритм (рис.
2) можно использовать и для вычитания чисел с плавающей точкой, если о заменить на -о. А1. [Распаковать.) Выделить порядок и дробную часть в представлениях для и и о, А2. [Обеспечить выполнение условия е„> е„.] Если е„с е„поменять местами и и ш (Во многих случаях удобнее совместить шаг А2 с шагом А1 илн с какимннбудь из последующих шагов.) А3. [Ъстановить ем.] установить еж Ф- еи. А4. [Проверить е„— е„.] Если е„— е, > р+ 2 (большая разница в порядках), установить У,„е- У„и перейти к шагу А7.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
