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