Файл: Торгашев В.А. Система остаточных классов и надежность ЦВМ.pdf

Скачать файл (4,94Мб)

Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 21.07.2024

Просмотров: 116

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

ставленных в СОК и в § 1.3 при вычислении позиционных' характе ристик n Kj(A). Поэтому одной из основных немодульных операций

в системе остаточных классов является р а с ш и р е н и е с и с т е м ы 0 с н о в а н и и, когда по известным остаткам числа А, соответствую щим некоторым модулям СОК, определяют значения остатков этого же числа для других оснований.

Пусть число А однозначно представлено в СОК с основаниями

Р\.............. рп и общим основанием N:
			А =	{ап- • •>	П;і}д,-
Требуется		представить это число			в	системе		остаточных классов
с основаниями		р\........ рп, Рп + \.......... Рт, т. е. необходимо							определить
остатки а п + і,		а,„.	формулами		(1.10)		и	(1.12),	представим
Воспользовавшись
число А в следующей форме:
		Л - ? + « £ ,+ . . . а 'Г Х - -
Тогда	ап+і— I Л іРп+І= I ° і			+	+	•••+	ап		рп+1<
где і=	1, 2, . .. , т — п.		а°ѵ	....... а"-1
Поскольку		остатки				вычисляются последователь

но, то для определения величин ап+г.......ат удобнее воспользо ваться рекуррентным соотношением

где а1п + . = а,; г = 1, 2,..., т — п; j	= 2, 3,..., л;	О -24)
+	\Pn+t.


		ап+і=		ап+1-
Данный способ	расширения			системы	основании удобен			тем,
что не налагает	никаких		ограничений		на	значения	модулей
р п+і.......рт. К недостаткам		же следует отнести, во-первых, то, что
остатки аІ при I > л и г <		я	вычисляются по различным формулам ■
а во-вторых, использование			в формуле (1.24)			констант	К],	вели

чины которых зависят от порядка следования модулей, существенно ограничивает возможности изменения числа оснований и их взаим

ного расположения.			расширения системы оснований.
Рассмотрим еще один способ			расширения системы оснований.
Обозначим	разность	между числом оснований		в	расширенной
и исходной	СОК через г, а наименьшее общее кратное модулей
Рп+і....... рт — через		R. Далее	определим число	А	такое, что
1А \|;ѵ = А; IА I/? = 0.
Тогда
Следовательно:					< І' 25)
		=	* * # > } * •		0.26)

Используя рекуррентную формулу (1.13) для вычисления *лг(2 ), получим выражения, определяющие любой из остатков ап+і при і = 1, 2, ..., г:

Ді+1		■ £ і -	Pj	J - 1		(1.27)
				рп+ i
an+i		\|(	N) *n+llpn+i>
где a°+i = 0; y '= 1,	2, ...,	n.
Если основания	P\, .. . ,	p n	не	являются взаимно	простыми, то
в формуле (1.27) вместо pj		следует использовать р			но	применять
Этот способ значительно удобнее предыдущего,
его можно лишь в том случае, если N и R не имеют общих делителем.
При помощи рассмотренных выше трех модульных						операций

(сложения, вычитания и умножения), а также операции вычисления позиционных характеристик и расширения системы оснований (сво дящихся, впрочем, к некоторым последовательностям тех же мо дульных операций) можно определять любые другие операции, нс носящие модульного характера, в том числе умножение дробей с по следующим округлением результата, деление, перевод чисел из СОК в произвольную позиционную систему счисления и т. д.

При изложении последующего материала данной главы будут рассматриваться только системы остаточных классов со взаимно про стыми основаниями, но полученные результаты автоматически рас

пространяются и на СОКН					при	замене	модулей		рі	на	р,_, где
і '=	1,	2, ... ,	гп.
	Рассмотрим теперь примеры					расширения		системы		оснований.
С.!	Пример		1.5.	Вычислим	неопределенные			цифры			частных
	и	С5 для	примера 1.2, приведенного в				§1.2. Каждое			из	этих ча
стных		должно быть представлено				в СОКН с основаниями					4, 5 и 6
и общим основанием 44=60. Для						частного С4 не определена цифра,
соответствующая модулю 5. Поэтому положим N — [4, 6] =											12; Я = 5;
Рі = 4; Р2= 6; р3= 5 .
	Поскольку N			и R взаимно просты, для определения							величины
1з = \| С4\|б воспользуемся формулами (1.27). Модули									р, =		4 и р 2= 6,
входящие в состав СОК с общим основанием N, не являются
взаимно простыми.				Поэтому	определим		р х = 4; р г = 3. Из прило

жения найдем обратные мультипликативные величины;

I ѵ*|. = 1; 1'M s = 4; I V. la =-2.

Далее по формулам (1.14) и (1.27) вычислим

сс° = а, = 3; а“ = 0; а° = | 3 |, = 0;

= К — 3) -1 |з --= 0;

Рі

( —•3)6- 4 |s =

a| =

1(3 — 0)•2[6=

р 1

-WІб =

12 J

= 3;

T. — I 3-11, — 3.

Итак, {Ci}M = {3, 3,3}co.

Для частного Cs не

определена

цифра по

модулю р = 3. По

этому положим

рі =

р3 — 5;

N = 20; р3 =

R = 6. Поскольку N

и R имеют общин делитель, то для

определения величины if, =

I С516 воспользуемся

формулами

(1.14) и

(1.24);

“1 =

“° =

а° =

« '=

| М / 4 |6= 4

“з =

“1 =

(“з +

“2^1 I/Jа =

П +

4-4 |0=

= 5.

Тз — “з

Итак, {С,}Л -{ 1 ,0 ,5 } ,0.

Пример 1.6. Пусть

число А — {1, 0, 0,

представлено

в СОК

основаниями р, = 3, р2 =

р 3=

5 и р4=

(Д) в

той же

Представим

позиционную

характеристику

системе остаточных классов. Для этого сначала изменим индексы

оснований		СОК, положив р, = 5, ра = 7, р, = 3,					р4 ■==4, N — 5-7 =
=35	и R =	3 - 4 = 12.
	В примере 1.3 была вычислена позиционная характеристика
представленная в СОК с общим основанием N :								(Л) = {3,1 }35.
	Из приложения найдем:
	I7sl,	=	3;	I ' M , =	2; \| ‘М , = 1;	\| Ѵт [, — I;		\| ' / 7 \| * - 3 .
	Далее	по	формулам		(1.14) и (1.27)	определим а° = 3; а2 =			1;
“з =	0; “з =		2;	\| ( - Л 0 «ЦЛ - 2; « J - 1; ^ =			0;	\| ( - Ю « \|\|Л -	0.

Следовательно, {яд-з (Д)}^ = {2,0}12. Переходя снова к исходной

СОК, получим {**, (Д)}л, = {2, 0,3, 1}42„.

Данный результат легко	проверить, если вспомнить, что Д =
- = 100 и, следовательно,	(Д) = [100/12] = 8.

1.5. УМНОЖЕНИЕ ДРОБНЫХ ЧИСЕЛ

Известно, что при умножении правильных дробей не возникает переполнения разрядной сетки. Именно поэтому в ЦВМ обычно ис пользуются числа, по абсолютной величине меньшие единицы.


В §	1.1 рассматривались		некоторые способы представления
дробей	в системе остаточных		классов и, в частности, способ пред
ставления		дробных чисел с	фиксированным знаменателем IV;
Щ м = т		-

Для того чтобы эти дроби были правильными при любом А должно выполняться условие: | Д | < N. Если числители А могут изменяться в интервале ( — Lu І 2), то условие правильности дроби примет вид: N шах (£„ А2).

Чаще всего диапазоны изменения положительных и отрицатель ных чисел, представленных в ЦВМ, принимаются одинаковыми. По этому примем N = L ^ = L 2.

Но для однозначного представления числителя А в СОК интер

вал L = Li-j-L2 не должен превышать общее основание AI.	Поэтому
М > 2М.	(1.28)

Рассмотрим произведение двух дробей AjN и B/N, пусть А и В положительны:

C_j _ A _ J 3 ____ 1 ( Л В \ N = N N - N \ N .)■

Очевидно, что С должно быть целым положительным числом. Поэто му в тех случаях, когда произведение AB не кратно N, примем:


	С =		[AB/N] = кд, (AB).			(1.29)
Если для вычисления позиционных характеристик используется
один из способов, рассмотренных в §				1.3, то в качестве знаменате
ля /V следует принять			произведение	некоторых	модулей	задан
ной СОК.	N = pI ...	рп. Тогда для выполнения неравенства				(1.28)
Пусть
достаточно	положить	pn+ i= Pm= 2, если ни один			из остальных мо

дулей СОК не является четным. В этом случае каждому числу, пред ставленному в СОК, соответствует некоторая правильная дробь. Если же использовать больший по величине модуль рп+1 (или в об щем случае группу модулей р„ +1, .. . , рт), то среди чисел, пред ставленных в СОК, окажутся и неправильные дроби с ненулевыми целыми частями. За счет увеличения М при постоянном N появляет ся возможность легко обнаруживать переполнения при сложениях и вычитаниях, корректировать ошибки округления для некоторых способов умножения дробей и, как будет показано в гл. 2, обнару живать и исправлять ошибки, возникающие в ходе вычислений.

Процесс умножения дробей с фиксированным знаменателем в, любой системе счисления можно разбить на два основных этапа: умножение числителей и округление полученного результата путем деления на знаменатель. В позиционных системах счисления наибо лее сложным этапом является непосредственно умножение, а округ ление чаще всего сводится к простому отбрасыванию младших раз рядов. В системе же остаточных классов, наоборот, легко можно перемножить числители, являющиеся целыми числами, и значительно труднее округлить полученное произведение.

Если заданы два положительных числа {А}.^ и то их

произведение в соответствии с формулой (1.29) запишется в сле дующей форме:

= {"* ІАЩ%-

Но прежде чем вычислять позиционную характеристику, необходимо

определить произведение числителей AB.	Поскольку	A < N и B<_N,
то это произведение можно получить,	используя	одну модульную

операцию умножения при условии, что M~>N2.

Хотя на практике такое условие и может иногда выполняться, но чаще всего основание М значительно меньше квадрата знаменате ля. Поэтому приходится искать другие способы формирования про изведения AB и соответствующей ему позиционной характеристики.

Первый метод, предложенный А. Свободой [20], заключается в том, что исходная СОК с основанием М расширяется путем добав

ления	модулей	................ Рт+(,	произведение				которых			равно
R', так, чтобы общее основание M’= M R '					полученной СОК было ие
менее чем N2.
Расширение системы основании			выполняется				для		обоих сомно
жителей. Далее		вычисляется произведение {АВ}М и позиционная
характеристика		{пЛ, (ЛД)}уИ,/;Ѵ. Определив				величину			{кд, (AB)}N
путем	расширения системы оснований			и	отбросив			символы		числа
ядг (AB), соответствующие модулям рт +и ...,						р т+[,		получим иско
мое округленное		произведение дробей		[С }^.

Для определения остатков, соответствующих каждому из со множителей в СОК с основанием М', требуется п модульных опе раций. Столько же операций требуется и для вычисления пози

ционной характеристики			(AB)jM,iN, так			как N = К п. Число
операций, необходимых для вычисления величины ^тсд/
определяется	тем,	насколько		велики	модули	СОК с основанием
M '[N . В частности,		если среди		них найдутся		п модулей',	произве
дение которых	не	менее,	чем	N, то	можно	утверждать,	что для

последней операции расширения потребуется также не более п

модульных	операций.
В целом операцию		умножения	двух дробей можно		выполнить
за время,	пропорциональное величинам: 4/1+ 1,			если	расширение
системы оснований для		каждого из	сомножителей	осуществляется

последовательно. 3/t+l при параллельном выполнении этих операций и 2л + 1, если исходная СОК позволяет сразу получить произведение

{ДД}м.

Произведение С, вычисленное по формуле (1.29), является за ниженным, так как округление всегда производится в меньшую сто рону. Для того чтобы погрешности обоих знаков были равновероят

ны,	к произведению {AB} м следует прибавить константу, рав
ную	[IV/2].
	Рассмотрим теперь случай, когда один или оба сомножителя яв
ляются		отрицательными.
	В §	1.2 было показано, что умножение целых чисел в СОК осу

ществляется одинаково при любых знаках сомножителей. К сожале

нию, для дробей	это несправедливо	из-за	операции	расширения
системы оснований.
Предположим, что отрицательное число А представлено в СОК
с основанием М : {А}аі — [М — МІ}уцРасширим				эту систему,
добавив модули, соответствующие СОК с основанием R'. В ре
зультате в новой	СОК с основанием	М' =	M R ' окажется пред

Смотрите также файлы

LEKTsIYa_1__kopia.doc

Троицкий О.А. Радиация и прочность твердых тел.pdf

LEKTsIYa_2.doc

LEKTsIYa_9.doc

Устинов А.Н. Исследование поршневых колец дизелей.pdf

Файл: Торгашев В.А. Система остаточных классов и надежность ЦВМ.pdf

Смотрите также файлы

Информация

Списки файлов

Дополнительно