показала, что лучше всего стремиться к выбору округления в виде "простых" чисел, поскольку числа с малыми числителями и знаменателями встречаются гораздо чаще, чем сложные дроби. Предпочтительно округлять числа до чаще, чем до ц. В этом случае правило округления, которое оказывается с практической точки зрения наиболее успешным, носит название "медианное округление" и формулируется следующим образом. Если {и/и) и {v/v) - смежные представимые числа, такие, что для любого и/и < X < v/v round(a;) должно равняться {и/и) или {v/v), то процедура округления имеет вид

. U U + V л/ \ v " +

roundfa;) = - для х < ---, roundfa;) = - для х > -----. (Ij

и и +v v и + v

При точном выполнении равенства а; = {u + v)/{u + v) полагаем, что round(a;) равно

ближайшей дроби с наименьшим знаменателем (или, если и = v, с наименьшим

числителем). В упр. 4.5.3-43 показано, что пользоваться медианным округлением

достаточно просто.

Например, предположим, что выполняются ар1ирметические действия с числами, представленными в формате с фиксированной дробной чертой при р - 8, так что для представимых чисел {и/и) выполняется -]28 < и < 128 и О < и < 256 и и ± и. Такое округление не обеспечивает высокой точности, но дает представление о механизме арифметики в формате с дробной чертой. Ближайшими к О = (0/1) числами будут (-1/255) и (1/255). Согласно правилу медианного округления по-•лучаем round(a;) = О тогда и только тогда, когда а; < 1/256. Предположим, что выполняются вычисления, в которых используется вид = + ffij! при условии, что вычисления осуп1,ествлялись с использованием точной арифметики рациональных чисел. Однако при промежуточных вычислениях выполнялось округление до представимых чисел. В этом случае щ округлится до (79/40), а ухз-ДО (7/6). Сумма округленных чисел, § -Ь = Щ, в свою очередь, округляется до (22/7). Таким образом, несмотря на выполнение трех операций округления получен правильный результат. Этот пример не был специально подобран, чтобы получился правильный результат. При получении результата решения задачи в виде простой дроби арифметика в формате с дробной чертой обеспечивает компенсацию ошибок промежуточных округлений.

Впервые в литературе вопросы точного представления дробей в компьютерах обсуждались П. Хенричи (Р. Henrici), JACM 3 (1956), 6-9. Представление дробей в формате с фиксированной и плавающей дробными чертами было предложено Дэвидом В. Матулой и опубликовано в книге Applications of Number Theory to Numerical Analysis, edited by S. K. Zaremba (New York: Academic Press, 1972), 486-489. Дальнейшее развитие этой идеи рассмотрено Матулой и Корнерупом (Kornerup) в статьях, опубликованных в журналах Ргос. IEEE Symp. Computer Arith. 4 (1978), 29-47; Lecture JVotes ir2 Сотр. Sci. 72 (1979), 383-397; Computing, Suppl. 2 (1980), 85-111; IEEE Trans. C-32 (1983), 378-388; IEEE Trans. C-34 (1985), 3-18; IEEE Trans. C-39 (1990), 1106-1115.

УПРАЖНЕНИЯ

1. [15] Предложите приемлемый метод сравнения двух дробей с целью проверки выполнения неравенства {и/и) < {v/v).

2. [М15] Докажите, что если d = gcd(u, v), то u/d и v/d взаимно просты.

3. [М20] Докажите, что из того, что и J-u и v J-v, следует

gcd(uii, иг;) = gcd(u, w)gcd(u,t;).

4. [11] Разработайте алгоритм деления дробей, аналогичный второму способу умножения, который описан в разделе (обратите внимание на то, что должен быть учтен знак числа v).

5. [10] С помощью методов, рекомендуемых в разделе, вычислите (17/120) + (-27/70).

► 6. [М23] Покажите, что из условий и ± и и v ± v следует gcd(uii + vu, uv) = didj, где di = gcd{u,v) и dj = gcd(di, u(v/di) + v{u/di}). (Следовательно, если di = 1, то {uv +vu) ± uv.)

7. [M22] Насколько большим может стать абсолютное значение величины t в методе сложения-вычитания, рекомендованном в разделе, если числители и знаменатели исходных дробей по абсолютной величине меньше N?

► 8. [22] Проанализируйте использование величин (1/0) и (-1/0) для представления оо и -оо и/или для представления переполнения.

9. [М23] Для 1 < и, v < 2" покажите, что из [2"-u/ui = [2v/vi следует и/и = v/v.

10. [41] Усовершенствуйте подпрограммы, предложенные в упр. 4.3.1-34, таким образом, чтобы они были применимы к "произвольным" рациональным числам.

11. [М23] Рассмотрите дроби вида {и + иу/5)/и", где и, и, и" - целые числа, gcd(u, и, и") = 1 и и" > 0. Объясните, как разделить две такие дроби и как получить частное в таком же виде.

12. [М16] Чему равно максимальное число, представленное в формате с плавающей дробной чертой, если длина его числителя ограничена числом q и задана длина знаменателя? Какие числа округляются до (0/1)?

13. [20] (Матула (Matula) и Корнеруп (Kornerup).) Рассмотрите представление чисел с плавающей дробной чертой для 32-битового слова.

14. [М23] Объясните, как вычислить точное количество пар целых чисел {и,и), таких, что Ml < и < М2 и Ni < и < N2 и и ± и. (Данное объяснение может быть использовано для определения количества чисел, представимых в формате с дробной чертой. Согласно теореме 4.5.2D это число равно примерно (6/7г)(Л/2 - Mi){N2 - М))

15. [42] Модифицируйте на своем компьютере один из компиляторов так, чтобы он заменял все вычисления с числами, представленными в формате с плавающей точкой, вычислениями с числами, представленными в формате с плавающей дробной чертой. Проведите эксперименты с использованием арифметики в формате с дробной чертой, применив выполняющие программы, написанные программистами, которые ориентировались на арифметику чисел, представленных в формате с плавающей точкой. (При обращении к подпрограммам, реализующим алгоритмы наподобие алгоритмов вычисления квадратного корня или логарифма, ваша система должна перед выполнением подпрограмм автоматически преобразовать числа, представленные в формате с дробной чертой, в числа, представленные в формате с плавающей точкой, и после их выполнения снова вернуться к представлению в формате с дробной чертой. При этом должна быть предусмотрена возможность вывода на печать чисел, представленных в формате с дробной чертой. Тем не менее в случае, когда в программы для пользователей не вносилось никаких изменений, должна быть предусмотрена также возможность вывода на печать чисел, представленных в формате с дробной чертой, в виде десятичной дроби.) Станут ли результаты при замене чисел, представленных в формате с плавающей дробной чертой, лучше или хуже?

16. [40] Поэкспериментируйте с интервальной арифметикой над числами, представленными в формате с дробной чертой.

4.5.2. Наибольший общий делитель

Если числа и и v целые, такие, что одно из них не равно нулю, то говорят, что их наибольший общий делитель, gcd(u,u), есть наибольшее целое число, на которое числа и и V делятся без остатка. Данное определение имеет смысл, так как если U 7 О, то самым большим числом, на которое число и делится без остатка, является Но числа и и V делятся также на целое число 1, следовательно, должно существовать самое большое число, на которое делятся оба эти числа. Когда оба числа и и V равны нулю, то нуль делится нацело на любое целое число, так что данное выше определение к этому случаю неприменимо. Условимся считать

gcd(0,0)=0. (1)

Из введенных выше определений очевидным образом следует, что

gcd{u,v) =gcd{v,u), (2)

gcd(u,i;) =gcd(-u,u), (3)

gcd(u,0) = u. (4)

В предыдущем разделе задача представления рационального числа с минимальными членами свелась к поиску наибольшего общего делителя числителя и знаменателя этого числа. Другие применения наибольшего общего делителя упоминались, например, в разделах 3.2.1.2, 3.3.3, 4.3.2 и 4.3.3. Таким образом, понятие наибольшего общего делителя gcd(u, v) имеет важное значение и заслуживает тщательного изучения.

С понятием наибольшего общего делителя тесно связано важное понятие наименьшего общего кратного двух целых чисел и и г;, обозначаемого 1ст(и,г;). Оно определяется как наименьшее положительное целое число, кратное как и, так и v. lcm(u,0) = lcm(0,u) = 0. Классический метод обучения детей сложению дробей и/и + v/v состоит в том, чтобы научить их находить "наименьший общий знаменатель", т. е. 1cm(и, v).

Согласно "фундаментальной теореме арифметики" (доказанной в упр. 1.2.4-21) любое положительное целое число и может быть выражено в виде

и = 2"3"5"7"Ч1"" ... = П р", (5)

р простое

где показатели степеней иг, из, ...-однозначно определенные неотрицательные числа, только конечное число которых не равно нулю. Из этого канонического разложения положительного целого числа сразу следует один из способов вычисления наибольшего общего делителя чисел и и v. В силу соотношений (2)-(4) можно считать, что и и v - положительные целые числа, и если оба эти числа разложены на простые множители, то

gcd{u,v)= П (6)

р простое

lcm{u,v)= П pmax(u„«,). (7)

р простое