Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 101
Текст из файла (страница 101)
В таком представлении (и/и') = (и/О') тогда и только тогда, когда и = О и и' = О', Перемножать дроби, конечно, просто. Чтобы найти (и/и') х (г/О') = (нг/ю'), можно просто вычислить пи и и'г'. Два произведения ии и гз'О' могут не быть взаимно простылги, но если обозначить И = йсг)(ггп, гг'О')а, то искомый результат будет равен ю = ггв/г1, ю' = и'ь'/г( (см, упр, 2). В разделе 4.5.2 рассматривается зффсктивнъгй алгоритм вычисления наибольшщ О общего делителя.
Дроби можно перемножить и другим способом, который состоит в том, что находятся значения г(г = ксг)(и, О') и г(з = йсг)(пг, и); тогда результатом будет ю = (и/с(г)(в/г(з), ю' = (и'/г(э)(в'/газ) (см. упр. 3). При перемножении дробей этим методом необходимо вычислить два наибольших общих делителя, но в действительности вычисления по такому методу выполняются не долыпе, чем по первому, В процессе нахождения наибольшего общего делителя осуществляется ряд итераций, количество которых фактически пропорционально логарифму входных чисел, так что количество итераций, необходимых дяя получения чисел ггг и ггз, по существу, равно количеству итераций, необходимых для вычисления одного числа Н.
Бадей того, каждая итерация при определении с(г и с(з, видимо, выполняется быстрее, так как рассматриваются сравнительно малые числа. Если и, й, и и ггг — -.величины с однократной точностью, то этот метод имеет преимущество по сравнению с первым, поскольку, если только допускается представление чисел ю и ю' с однократной точностью, в вычислениях совсем не участвуют числа с удвоенной точностью. Деление может быть выполнено аналогично (см. упр. 4). Операции сложения и вычитания дробей немного сложнее, Обычная процедура ЗаКЛЮЧаЕтСЯ В тОМ, ЧтО ПРИНИМВЕтСЯ (П/П') Ю (О/О') = ((Пиг Ю и'О)/П'О'), а ЗатЕМ данная дробь приводится к несократнмому виду.
Прн этом используется, как и в первом методе, наибольший общий делитель г1 = йети(ио' ю и'н, и'О'). Но, опять же, можно избежать действий со столь большими числами, если начать с вычисления газ = йсг)(п', О'). При г(г = 1 искомыми делимым и делителем будут ю = пв' ю и'н и ю' = и'О'. (Этот случай следует выделить особо, поскольку согласно теореме 4.5.2В, если знаменатели п' и и' распредечены случайно, то г1г равно 1 примерно в 61 случае в здесь н даава дсбП означает наибввьщий общий дсвитваь (вгвагввг сотсоон беьчаог), — призг. перев.
из 100. Если !(! > 1, то положим 1 = и(о /сз!) х р(и'/с(!) и вычислим сЬз = йсг)(г, !(!)! окончательный результат равен ш = !/!зз, ю' = (и'/!1!)(и'/!зз). (В упр. 6 доказывается, что эти значения ш и ш' взаимно просты.) Операции над числами, представленными с однократной точностью, выполняются также с однократной точностью, но 1 может быть числом с двойной точностью или чуть больше (см. упр. 7); учитывая, что йсг)(! 4! ) = йсг1(Ф шос( г1з, 4з), вычисление числа Из не требует двойной точности. Например, чтобы вычислить (7/66) + (17/12), находим !(! = ксс)(66,12) = 6; тогда ! = 7 2+ 17 11 = 201, а Из = пса(201, 6) = 3, так что в результате получим — /( — ° — ) = 67/44.
Проверку подпрограмм, реализующих арифметические операции над рациональными чиспамн, можно выполнить, используи обращение матриц с известной обратной матрицей (наподобие матриц Коши; упр. 1.2.3-41). Опыт вычислений с дробями показывает, что в процессе выполнения операций числа во многих случаях стаповятгя очень большими. Поэтому, если предполагается, что о и и' для каждой дроби (и/и') являются числами с однократной точностью. то очень важно, чтобы в каждую подпрограмму сложения, вычитания, умножения и деления включались проверки переполнения.
При решении задач с числами, для которых важна высокая точность, очень полезен набор подпрограмм для выпачнения арифметических действий над дробями с допустимой произвольном точностью. Методы, рассматриваемые в этом разделе, распространяются также иа другие числовые поля, в частности можно было бы вып!шнять арифметические действия ивд величинами вида (и+ и'з/6)/и", где и, и', ил — целые числа, ксг((и, и', ил) = 1 и ип ) О, илн над величинами вида (и + и'з/2+ ил з/4)/ил' и т.
д, Интересно рассмотреть также (если не упорствовать в применении точных методов) числа в формате с фиксированной дробной чертой и в формате с плавающей дробной чертой„которые являются аналогами чисел с плавающей точкой, но в их основе лежат рациональные,проби, а не дроби, ориентированные на представление в системах счисления с каким-либо основанием Ье. При представлении дроби в двоичном формате с фиксированной дробной чертой числитель и знаменатель дроби содержат не более р бит, где р †заданн целое число.
В случае представления дроби в формате с плавающей дробной чертой сумма битов для числителя и знаменателя не превышает некоторого двлного 4! при этом для определения размера числителя как составной части цепочки из 7 бнт используется другое поле представлении. Бесконечность может быть представлена как (1/О). Чтобы выполнять арифметические действия над такими числами, введем определение х б! р = гоппс((х + у), х ~ р = гоппс((х — у) и т. д., где гопп!1(х) = х, если х представимо. В противном случае в качестве х выбирается одно из представимых чисел в окрестности числа х.
На первый взгляд может показаться, что для определения гоппс((х) лучше всего выбрать представимое число, ближайшее к х, по аналогии с выбором округления в арифметике с плавающей точкой. Но практика " В оригинале используются термины гйкед з!ав!!", "Йоанпй в!авв" и "в!ае!ьагквюез!с", которые в связи с отсутствием в русскоязычной литературе соответствующих устоявшихся терминов мы будем переводить как "4юрмат с фиксированной дробной чертой", "формат с плаваююей дробной чертой", "арифметика в формате с дробной чертой" и "числа в формате с дробной черзой".— При.м.
перев. показала, что лучше всего стремиться к выбору округления в виде "простых" чисел, поскольку числа с малыми числителями и знаменателями встречаются гораздо чаще, чем сложные дроби. Предпочтительно округлять числа до -' чаще, чем до зы-'. В этом случае правило округления, которое оказывается с практической точки зрения наиболее успешным, носит название "меднанное округление" н формулируется следующим образом. Если (и/и') и (и/и') — смежные представимые числа, такие. что для любого и/и' < х < и/и' гоцпс)(х) доджно равняться (и/и') или (и/и'), то процедура округления имеет вид и и+и о иэ О гопш1(х) = — для х < —, гоши!(х) = — для х > —. (1) из з+ и! и' + и' При точном выполнении равенства х = (и+и)/(и'+и') полагаем, что пшпд(х) равно ближайшей дроби с наименьшим знаменателем (или., если и' = и', с наименьшим числителем).
В упр. 4,5.3-43 показано, что пользовв.1ься медианным округлением достаточно просто. Например, предположим, что выполняются арп рметические действия с числами, представленными в формате с фиксированной дробной чертой при р = 8, так что для представимых чисел (и/и') выполняется -] 28 < и < 128 н 0 < и' < 256 и и .Ь и'. Такое округление не обеспечивает высокой точности, но дает предсшвление о механизме арифметики в формате с дробной чертой. Ближайшими к 0 = (О/1) числами будут (-1/255) и (1/255). Согласно правилу медианного округления получаем гоши!(х) = 0 тогда н тачько тогда, когда [х[ < 1/256.
Предположим, что ВыпОЛИЛ1Отся ВычИОЛения, В которых ИспоЛьзуется Вид 1 = 1зэ + 113, при усЛОВИИ ЗЗ ЗЫ 1ЗОО что вычисления осуществлялись с использованием точной арифметики рациональных чисел. Однако при промежуточных вычислениях выполнялось округление до представимых чисел. В этом случае з 14 округлится до (79/40), а зео — до (7/6). 11И Сумма округленных чисел, Я + е = —,„-', в свою очередь, округляется до (22/7). Таким образом, несмотря на выполнение трех операций округления получен правильный результат. Этот пример не был специально подобран, чтобы получился правильный результат. При получении результата решения задачи в виде простой дроби арифметика в формате с дробной чертой обеспечивает компенсапию ошибок промежуточных округлений. Впервые в литературе вопросы точного представления дробей в компьютерах обсуждались П.
Хенрнчи (Р. НепНс1),,!АСМ 3 (1956), 6 — 9. Представление дробей в формате с фиксированной и плавающей дробными чертами было предложено Дэвидом В. Ь!Втулой и опубликовано в книге Арр!гсабопз ОГ !Уип1Ьег ТЬеогу !о Хипзех!св! Апа!уэ!з, е1!!(ес( Ьу 8. К, ЕагешЬВ (Хе1э 1ог!ч Аса4)езп!с Ргезз, 1972), 486-489. Дальнейшее развитие этой идеи рассмотрено Матулой и Корнерупом (Когпегир) в статьях, Опубликованных в журналах Ргос. ХЕЕЕ Бупзр. Сошрисег АП!Ь.
4 (1978), 29-47; Бес!иге Хо!ел ш Сотр. Бс!. 72 (1979), 383-397; Соглрибпй, Бпрр!. 2 (1980), 85— 111; 1ЕЕЕ 21длз. С-32 (1983), 378-388; 1ЕЕЕ 7)эпз. С-34 (1985)., 3-18; !ЕЕЕ Тгапз. С-39 (1990), 1106-1115. УПРАЖНЕНИЯ 1. [15) Предложите приемлемый метод сравнения двух дробей с целью проверки выполнении неравенства (к/и') < (е/е'). 2. [М!5] Докажите, что если 4 =. йсб(и,е), то и/4 и е/1! Взаимно просты. 3. [М30[ Докажите, что из того, что и 1. и' н е.(. е, следует йсй(ие, и е ) = йсб(и, е ) йсб(и, е).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
