ПОД (пособие) (1184372), страница 56
Текст из файла (страница 56)
k -k (mod m)Как отрицательный остаток -k, так и положительный k в равной мере подходят дляпредставления этого класса эквивалентности. По традиции выбирается отрицательныйостаток. Таким образом, в компьютере количество отрицательных целых чисел на единицубольше, чем количество положительных. Так как m = 232 = 4294967296, то k = 231 =2147483648, и симметричная система остатков состоит из элементов-2147483648, -2147483647, ..., -2, -1, 0, 1, 2, ..., 2147483647.Вещественные переменные187Вещественные числа представляются в компьютере в так называемой экспоненциальной,или плавающей, форме. Вещественное число r имеет видr = ±2e* mПредставление числа состоит из трех элементов:знак числа - плюс или минус. Под знак числа отводится один бит в двоичномпредставлении, он располагается в старшем, т.е.
знаковом разряде. Единица соответствуетзнаку минус, т.е. отрицательному числу, ноль - знаку плюс. У нуля знаковый разряд такженулевой;показатель степени e, его называют порядком или экспонентой. Экспонента указываетстепень двойки, на которую домножается число. Экспонента может быть какположительной, так и отрицательной (для чисел, меньших единицы). Под экспонентуотводится фиксированное число двоичных разрядов, обычно восемь или одиннадцать,расположенных в старшей части двоичного представления числа, сразу вслед за знаковымразрядом;мантисса m представляет собой фиксированное количество разрядов двоичной записивещественного числа в диапазоне от 1 до 2:1 m<2Следует подчеркнуть, что левое неравенство нестрогое - мантисса может равнятьсяединице, а правое - строгое, мантисса всегда меньше двух. Разряды мантиссы включаютодин разряд целой части, который ввиду приведенного неравенства всегда равен единице, ификсированное количество разрядов дробной части.
Поскольку старший двоичный разрядмантиссы всегда равен единице, хранить его необязательно, и в двоичном коде онотсутствует. Фактически двоичный код хранит только разряды дробной части мантиссы.Несколько примеров представления вещественных чисел в плавающей форме:1.0 = +20*1.0Здесь порядок равен 0, мантисса - 1.
В двоичном коде мантисса состоит из одних нулей, таккак старший разряд мантиссы (всегда единичный) в коде отсутствует. Порядок хранится вдвоичном коде в смещенном виде, он равен 127 в случае float и 1023 в случае double;3.5 = +21*1.75Порядок равен единице, мантисса состоит из трех единиц, из которых в двоичном кодехранятся две: 1100...0; смещенный порядок равен 128 для float и 1024 для double;0.625 = +2-1*1.25Порядок отрицательный и равен -1, дробная часть мантиссы равна 0100...0; смещенныйпорядок равен 126 для float и 1022 для double;100.0 = +26*1.5625Порядок равен шести, дробная часть мантиссы равна 100100...0; смещенный порядок равен133 для float и 1029 для double.При выполнении сложения двух положительных плавающих чисел происходят следующиедействия:выравнивание порядков.
Определяется число с меньшим порядком. Затем последовательноего порядок увеличивается на единицу, а мантисса делится на 2, пока порядки двух чисел несравняются. Аппаратно деление на 2 соответствует сдвигу двоичного кода мантиссывправо, так что эта операция выполняется быстро. При сдвигах правые разряды теряются,из-за этого может произойти потеря точности (в случае, когда правые разряды ненулевые);сложение мантисс;нормализация: если мантисса результата стала равна или превысила двойку, то порядокувеличивается на единицу, а мантисса делится на 2.
В результате этого мантисса попадает в188интервал 1 m<2. При этом возможна потеря точности, а также переполнение, когда порядокпревышает максимально возможную величину.Вычитание производится аналогичным образом. При умножении порядки складываются, амантиссы перемножаются как целые числа, после чего у результата правые разрядыотбрасываются.Погрешности при вычислениях чисел на параллельных системах.Оценить полную ошибку суммирования положительных чисел.Источники погрешности при вычислениях на параллельных системах.В общем случае, арифметические операции над элементами дискретного подмножествавещественных чисел F не корректны.Результат арифметических операций чисел с плавающей запятой может:- иметь абсолютное значение, больше M (максимального числа) - машинное переполнение;- иметь ненулевое значение, меньшее m (минимального числа) по абсолютной величине машинный нуль;- иметь значение в диапазоне [m:M] и тем не не менее не принадлежать множеству F(произведение двух чисел из F, как правило, записывается посредством 2t либо 2t-1значащих цифр);Поэтому, на множестве чисел с плавающей запятой определяются и "плавающие"арифметические операции, за результаты которых, если они не выходит за границымножества F, принимается ближайшие по значению элементы F.
Примеры изчетырехразрядной десятичной арифметики по Н. Вирту.А) Пусть x=9.900 y=1.000 z=-0.999 и тогда:1 (x+y)+z = 9.9102 x+(y+z) = 9.901В) Пусть x=1100. y=-5.000 z=5.001 и тогда:1 (x*y)+(x*z) = 1.0002 x*(y+z)= 1.100Здесь операции + и * - плавающие машинные операции. Такие 'чиcленные' процессыназывают иногда 'неточными', здесь нарушаются ассоциативный и дистрибутивный законыарифметики..39.
Оценить полную ошибку для суммирования положительных чисел.Пример расчета полной ошибки для суммирования положительных чиселФормула полной ошибки для суммирования положительных чисел Ai(i=1,..,n) имеет вид:Ds = A1*da1 + A2*da2 +...+ An*dan + d1*(A1+A2) +..+ d(n-1)*(A1+..+An) + dn , гдеdai - относительные ошибки представления чисел в ЭВМ, а di - относительные ошибкиокругления чисел при каждой следующей операции сложения.
Пусть: все dai = da и di = d , aKs = A1+A2+..+An, тогда: Ds = da*Ks + d*[(n-1)*A1+(n-1)*A2 +...+ 2*A(n-1) + An]Очевидно, что наибольший "вклад" в сумму ошибок вносят числа, суммируемые вначале.Следовательно, если суммируемые положительные числа упорядочить по возрастанию,максимально возможная ошибка суммы будет минимальной. Изменяя порядоксуммирования чисел можно получать различные результаты. Но если даже слагаемыеотличаются друг от друга незначительно, на точность результата может оказать влияниеспособ суммирования.
Пусть суммируются 15 положительных чисел, тогда ошибкарезультата: Ds = da*Ks + d*(14*A1+14*A2+13*A3+....+2*A14+A15).Слагаемое da*Ks не зависит от способа суммирования, и далее не учитывается. Пустьслагаемые имеют вид: Ai = А0+ei, где i=1,...,15, тогда: Dss = 199*(A0+em)*d, где em =max(ei), d - ошибка округления при выполнении арифметической операции сложения.189Если провести суммирование этих чисел по группам (три группы по четыре числа и однагруппа из трех чисел), то ошибки частных сумм имеют вид:Ds1 = d*(3*A1+3*A2+2*A3+A4) <= 9*d*(A0+em)Ds2 = d*(3*A5+3*A6+2*A7+A8) <= 9*d*(A0+em)Ds3 = d*(3*A9+3*A10+2*A11+A12) <= 9*d*(A0+em)Ds4 = d*(3*A13+2*A14+A15) <= 5*d*(A0+em)а полная оценка ошибок округления будет Ds <= 32*d*(A0+em), что меньшеDss.
Итак суммирование по группам дает меньшую ошибку результата.Например, разделив процесс суммирования массива положительных чисел на параллельныепроцессы, и затем получив сумму частных сумм, можно получить результат, отличный отпоследовательного суммирования в одном процесс.Точность плавающей арифметики. Машинный эпсилон.Действия с плавающими числами из-за ошибок округления лишь приближенно отражаютарифметику настоящих вещественных чисел. Так, если к большому плавающему числуприбавить очень маленькое, то оно не изменится. Действительно, при выравниваниипорядков все значащие биты мантиссы меньшего числа могут выйти за пределы разряднойсетки, в результате чего оно станет равным нулю.
Таким образом, с плавающими числамивозможна ситуация, когдаa+b = a при b 0Более того, для сложения не выполняется закон ассоциативности: a+(b+c) = (a+b)+cДействительно, пусть ε - максимальное плавающее число среди чисел, удовлетворяющихусловию 1.0+ε = 1.0 (приведенные выше рассуждения показывают, что такие числасуществуют). Тогда (1.0+ε)+ε 1.0+(ε+ε) поскольку левая часть неравенства равна единице, аправая строго больше единицы (это следует из максимальности числа ε).Число ε часто называют машинным эпсилоном или, чуть менее корректно, машиннымнулем, поскольку при прибавлении к единице оно ведет себя как ноль.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
