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

C=>IANIB].

(1.35)

СОК, причем число модульных операций, необходимых для

деле­

ния двух дробей, в

среднем

равно 12 (п + 1)

и может быть

умень­

шено почти в два

раза при

использовании

двух преобразователей

нако подобный алгоритм

деления

является довольно

разнородным

по своей структуре, что

приводит

к

существенному

усложнению

устройства управления.

группе, весьма

близки по

Способы, относящиеся к третьей

зуем выражение (1.35) "следующим образом:

С = (AN — г)ІВ,

(1.36)

где г = [>17/]ß < ß . Тогда величина

должна удовлетворять

нера­

венству

A N — ВС

В.

(1.37)

где А (0) = А,

а величина

является

решением неравенства:

0

А (0 Рп—і

сп—[В<С.В.

(1.39)

Очевидно, что

;,

поскольку для любых і = 0 , 1........п —1

Л; < Д*. Поэтому для

каждого } = п — I неравенство (1 .с-9) можно

решить путем перебора различных значении

су от 0 (или 1) до

рj —\.

Последовательно вычисляя величины А (0), А (1 ),... ,А {п — 1),

придем к выражению

А(п) =

A N — В (спрп^ і.

! - . . . +

с2р, +

с,) < В.

(1.40)

Сравнивая

неравенства

(1.37)

и (1.40),

можно

заметить, что

С(г

+

1) = С ( і) д ,- і

+

1........л - 1 ,

(1.41)

где С (0) = 0;

С = С(п).

Так как наиболее трудоемкой частью данного алгоритма де­

ления

является

решение неравенств

(1.39),

рассмотрим

пути сокра­

щения

времени,

необходимого

для

вычисления

коэффициентов с„,

..., с,.

Пусть старший ненулевой символ числа В, представленного в

ОПС,

равен blt

где І ^ п . Тогда,

положив

Кі_і=р\,

...

заме­

ним неравенство

(1.39)

на следующее выражение:

0 < [ А (і) Рп-іІКі-г] — c'n_ i b [ < b l .

(1.42)

Следует отметить, что

[ А Р п - і І К і - і ] = ^Kt_ x(A Pn - i) <

P n - i Pi-

Для решения этого неравенства требуется значительно меньше

времени, чем

для

решения неравенства (1.39), так

как все опера­

ции, связанные с определением величины cn_ t ,

можно

выполнять

в сокращенной

СОК, содержащей

не более двух

оснований.

Конечно, в общем случае величины с'п_1 не

разны

искомым

значениям сп .і из-за ошибок

вызванных округлением чисел Арп—і

и В.

Легко убедиться

в том, что

абсолютная

величина

разности

сп_. и ся_(

не

превышает единицы. Поэтому

при

подстановке

в выражение

(1.38) величины

с'н_ 1

вместо

с„_г

получаем

резуль­

тат А' (1+1), лежащий в интервале ( — В, 2В).

Если сп—і =

с'п_ 1+ Др где Д( = 0, + 1,

—1,

то

Д(1 +

1) =

= Лу+і + ДіВ .

В

Поэтому,

сравнивая

величины

Л'(і'+1)

и

и

используя

нера­

венство (1.39),

можно определить

величину

и

знак

ошибки

и

соот­

ветственно определить искомые значения Л(г'+1) и

* Предполагается,

что делимое

обязательно

меньше делителя

(Л < В), так как иначе произойдет переполнение.

с п"- і

+ 1.

Тогда А (I + 1) -

А ” (і +

1) + А\В. где Д '= 0 ,1, 2.

Из

неравенства

(1.39) следует,

что при

наличии ошибок А"(І-И )

В этом случае

величина С, получаемая

из

формулы

(1.41),

при подстановке вместо с„_і значений с' п_і отличается

от

иско­

мого частного С не более чем на единицу.

интервале

(—В, 0),

Действительно,

если А'(і)

оказывается в

что свидетельствует

о наличии

ошибки Д _і= —1,

то по

формуле

Предположим теперь, что на следующем

шаге нет ошибки.

Тогда,

поскольку е,’_ £ отрицательно,

то

С'{і + \) = Рп-іС'{і)

- \с’п_ \

=

= Рп-і (с (0 + 1) — {Рп-1 — с„_г) =

С (і +

1).

Аналогично исправляется ошибка и в том случае, когда

по­

падает

в интервал [Д, 2В). При этом

легко убедиться

в том,

что

значение с'п_ і оказывается равным р п—і + с„_/. Итак,

при замене

коэффициентов с„_/ на с'п_ і

частное

можно вычислять

практи­

чески с тон же

точностью.

сп_ 1

Для

определения коэффициентов

из

неравенства

(1.42)

можно

воспользоваться процедурой, аналогичной

делению

в дво­

ичной системе счисления, гак

как очевидно, что

с'п_і =

{А (і) Рп-іУЬі].

Рассмотрим

рекуррентное выражение

+

=

b

j - 0,1......si,

(1.43)

где nt (0) =

04 (г) Рп-іУ,

st = [Iog2 Pn+i] +

1,

i =

0, 1,.... n—1;

1, е сл и

* i U ) > 0;

—1,

если

U )

<

0,

если

( j )

= 0.

c« - i “ 2 в *СУ)2*г '-

(1.44)

j = o

3 Заклз № 107

33

лд-

Для

вычисления

каждой

из

позиционных

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

(Л (0 Рп-і)

требуется Z + 1

модульных

операции при усло­

вии,

что

І К іРп—і <

М.

Однако

при I = п

это

условие может

и не выполняться.

Для

того чтобы в этом

случае не расширять

ТСКВ- 1 ( л (0 Рп-і) “

1(Л (0).

(1-45)

где К п_і I — Kn-'ilРп—ѵ

^ = lj 2 ,.....

При L=

0 это равенство становится несправедливым. Поэтому

сначала вычислим характеристику

(Д), а

затем характери­

стику тс/ся—2 (яр;| (-4) />л),

полагая эту

величину

примерно равной

ъ кп-і(.АРп)-

Тогда для

определения

позиционных

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

потребуется

не

более

п

модз'льных

операций для

і = 1......п — 1

и 2п операций

для і = 0; всего для деления двух

положительных

шить, если вычислять коэффициенты с'п_ 1 каким-либо

табличным

способом. Однако, как правило, в

этом

случае

резко

возрастают

аппаратурные затраты.

Если знаки делимого и делителя произвольны, то сначала

вычислим их абсолютные

величины,

выполним

деление рассмот­

ренным выше способом и присвоим

результату

необходимый

знак с помощью умножения частного на —1 (при

различных зна­

ках исходных величин). Переход к

абсолютным

величинам А и В

можно выполнять одновременно с

вычислением

(Ар,,) и Ь[,

умножая их на

—1, если

соответствующий

знак

окажется отри­

цательным.

Одновременно с частным в процессе выполнения деления вы­

числяется и остаток |/ПѴ|в, равный А(гі).

Пример 1.9. Пусть задана СОК с основаниями

= 4, р г = 5,

р, = 7,

р і = 3,

N = 4-5-7 =

140; М =

N-3 =

420. Вычислить част­

ное от

деления

дроби A /N =

5°/,40

на

величину

B /N =

10°/j4o-

Прежде всего определим

величину

старшего ненулевого раз­

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

ък ^(Арг):

{ М л

-

{[100/4-5]}«. -

{1,0,5, 2}«»,

і , - 5;

Ш м = {[50/5]}4SO =

{2, 0, 3 ,1}420,

(/1) = 10;

(АРа))м Ä

{[10• 7/4г]}4ао =

О- 2, 3, 2 } 42о > ид-5 (Ар3) ~ 17.

«i = [log,7] + 1 =

3,

s2 =

[log, 5] + 1 =

3, s3 =

[log, 4] + 1 = 3,

" .(!)

=

1 7 - 2 » - 5 =

- 2 3 ,

a , ( 0 ) - l ;

*0 (2) =

- 2 3

+

22-5 = - 3 ,

a0( l ) -------1;

".(3)

=

- 3

+

2-5 =

7,

u0 (2) =

— 1;

" . (4) =

7 - 5

=

2,

u0(3) =

1;

c^ =

2s — 2a — 2 +

1 = 3.

Следует

отметить, что

величину гс0 (4)

можно

не вычислять,

поскольку она не влияет на ход дальнейших вычислений.

{А (1)>ж = {50-7 — 3- 100},2о =

{2, 0,1, 2}12o,

A (1) -

50;

! ci\M = {3}4,o =

{3 ,3 ,3 ,

0 }420,

С'(1) =

3;

KKi (AIPi) = WUjpi] =

12;

c2 = 23—22— 2' +

1 = 3 ;

{/1(2)}Л1 =

{50-5 -3 .100}420=

{2,0, 6, 1}420,

A (2) =

- 5 0 ;

{c' (2)}AJ =

{3 ■5 +

3}420 ^

{0,4, 3, 0}42o},

c' (2) =

18;

KKi (AzPi) — [AtjPi\ — — 10; Cg =

— 23 + 22 +

21 =

— 2;

i A

Г

{ -

50' 4 +

2 - l°0}42o =

{°. °. °- °}42o-

A (3) = 0;

К

=

( 18-4 -

2)420 =

I2, 0. 0 ,1}420,

c' (3) =

70.

сел из

позиционных систем

счисления

(десятичной

или двоичной) в

СОК,

а при выводе — обратное преобразование из

СОК в

позици­

онную

систему, хотя для

некоторых

управляющих ЦВМ

можно

классов.

немодульных операций (так же

Покажем, что любая из этих

как умножение и деление дробей)

может быть представлена в виде

3

35