книги из ГПНТБ / Торгашев В.А. Система остаточных классов и надежность ЦВМ

{C }^ = { ^ { ß } ^

=

{ l,6 ,0 } 82{.

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

в том,

что С= 76 = —8, т. е. C/N = —8/21.

Пример 1.8. Решить предыдущий пример, ие расширяя задан­

ную СОК. Положим УѴ|=рі=3; N2—P2=7- Далее представим каж­

дый из числителей

перемножаемых

дробей в

виде пары чисел

Д = Д і З + Д 2 и В В \ 7 В 2.

{Д,}уИ=

{2, 5, 1},4,

Д, =

5;

=

1 , 1},*.

Д2 =

1;

{Ді}лі =

1 5, 2}S4,

Д. = - 2 ;

{Да}лі =

{Д 4, 0),*,

Bs = 4.

произведения

{А\Ві}м — {2, 4, 2}S4,

Д,Д, =

—Ш;

{ A ß . } A f - { 2, 6, 0}84,

Д,Д2 =

20;

{Д2Дi } = {1,5, 2}84,

Д2Д, =

- 2

и позиционные характеристики

{KN,

(7ІіДа)}уѴі “

{2. 2, 2}s4;

{тедг,

=

{2, 6, 3}84.

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

sign (Л) = I— яуу (Л) |я.

Положив

Я ^ 4 ,

это же выражение можно использовать

для

определения

переполнения разрядной

сетки. Так, если |—Д*г(Л)|н =

= 2, то переполнение

произошло

в

отрицательную

сторону, а

при

|я.ѵ(Л )|я = 1—-в положительную.

Для вычисления

знака числа

или

Абсолютную величину числа

можно

определить при помощи

•следующего выражения: |А| =

А (1 — 2 sign (/1)).

ся

Для сравнения

чисел А

и

ß

по абсолютной

величине

требует­

определить

знак

разности

| Л | — |ß |,

выполнив 3(«+1)

модуль­

ных операций (либо 2(п+1), если величины |А|

и )ß | могут вы­

числяться одновременно} ■

Перейдем теперь к рассмотрению вопроса о переводе целых и

дробных чисел

из

обычных

позиционных

систем

счисления

в СОК

и обратно.

в позиционной

системе счисления

Пусть целое число Л задано

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

■ А =

+•■■-(- алр + в<>>

где

0

— 1; і = 0,

1,... ,k — 1

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

условие

p k < М.

{А )м = {а°Ь і +

{а'Р)м +

‘ ' ' +

Обратный перевод целых

чисел из

СОК

в позиционную систему

счисления значительно сложнее.

СОК, равен основанию

Пусть один из модулей, входящий в

Если Д (у + 1) =

[А (у')/р], где у =

0,1,..., А — 1

и Л (0) =

Л, то

aj = IА U)lp.

Для вычисления

каждого символа

а0, .... а/с_і

требуется

опре­

этой дроби

через

Л,, а числитель

равной

ей

дроби, представленной

в СОК, — через А-,. Тогда

A J p k =

A ^ N

и,

следовательно, А.г =

= [A1N jp k],

где

N > p k.

U ) м ■

-IT ]

+

ak—2

1 N

+

L Рг

N

"Г

Г ЛП

(1.46)

+

аі пк—1

+ ао

РкJ

М

операций.

Однако за счет

округления

константы вычисляются с

определенной погрешностью.

Поэтому

значение А2, полученное по>

формуле

(1.46), иногда отличается от

искомого числителя дроби,,

В остальных случаях следует

ввести поправку, определяемую

из следующей формулы:

яд—lik—1 + A7t/2

а о7о + аі7і +

• • •

+

где

I - 0 ......Л - 1 ;

7г = I [ N N J p k- ‘) Ij^,

Nj — произведение некоторых

модулей заданной СОК, таких, что

к {р — 1) < JV, < M ß p .

вода правильных дробей

из одной позиционной

системы

счисления

в другую. Предположим,

что М ^ р М (если это

условие

не выпол­

символы числителя позиционной дроби А\/рк можно

вычислить по

рекуррентным формулам:

А

(О Р

Г

Л

(0 р

А

U +

1) = А

(0 Р —

N

N ; а/г-і = I

N

где і =

1, 2......k',

Аг (1) = Аг.

В целом

процесс перевода потребует nk модульных операций.

Пример

1.10. Перевести десятичную

дробь

Д,/102 = 0,78

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

ш = 3,

р» = 5, р г= 7.

р 4 = П, N = 105 и М = 1155.

Вычислим сначала необходимые константы, приняв

Д7, = 5-7 =

= 35:

7. = 17.

[Nlp*] = 1;

[ N lp ] - 1 0 ;

7о =

1[105-35/100] f3i =

1;

j

g

I ly 7

1 27

Тогда

As = 8-1 +

7.10 = 78; Д =

g-g'---------= 4; {А + Д}лі=

( 82}ш 5= I 1-

2, 5, 4}11051 55*

ЮN <

М.

При этом а, = [82-10/105] = 7; А г (2) = 82-10 — 7-105 =-

= 85;

й0=

[85-10/105] = 8. Итак, И, = 0,78.

бые

другие немодульные операции, и

от времени, затрачиваемого

на

их выполнение, существенно зависит

общая производительность

і

38

Т а б л и ц а

1.1

Н а з в а н и е а р и ф м е т и ч е с к о й

К о л и ч е с т в о М О

К о л и ч е с т в о Э О

о п е р а ц и и

Сложение

...........................

1

1

Вычитание...........................

знака

числа

1

1

Определение

или наличия

переполне-

п

2 п

ния ...................................

абсолютной

Вычисление

п + 1

2 п + 1

величины ...........................

Сравнение

абсолютных ве-

6л +3

личин . . . .

•

. . . .

2

( п + 1 )

Умножение дробей

. . . .

3 (л +3)

10 (л +3)

Деление дробей .

. .

л2+3л

h2] logüA^

2л2+6л+4] logjATf

Перевод дробей

из

пози-

цистной

системы в СОК

f t — 1

2 ( f e —

1 )

Перевод дробей из

СОК в

nk

2 nk

позиционную систему .

условию:

— 1,

где

г = 1 , 2 , . . . , /л; р х....... рт—фиксиро­

ванные натуральные числа.

различных (т. е.

отличающихся хотя бы

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

число

одной компонентой) векторов

такого типа

равно произведению*