Методы определения ранга числа в СОК

1. Занятие № 4 (Лекции 7, 8). Методы определения ранга числа в СОК

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

2.

Для реализации позиционных операций в СОК
используются
признаки
так
называемые
непозиционного
позиционные
кода
(ППНК)
(позиционные характеристики числа). В частности, в
качестве ППНК может служить ранг rA числа
A ( a1 , a2 , ..., an ) , след числа, ядро числа, характер
числа
и
пр.
Перечисленные
позиционные
характеристики числа основываются на принципе
последовательного использования нужных констант.
2

3.

Определение 1. Истинным рангом rA числа
A
называют натуральное число, показывающее, сколько раз
диапазон M
СОК был превзойдён при переходе от
представления числа A в СОК к его представлению в ПСС
через
систему
ортогональных
базисов
Bi .
Такой
полученный rA называют "истинным" рангом числа A .
Истинный ранг rA числа A – натуральное число.
3

4.

Рассмотрим два метода определения ранга числа в СОК
Первый метод
n
Пусть задана СОК основаниями mi (i 1, n ) , а M mi .
i 1
Заданной СОК однозначно соответствует система ортогональных
базисов, Bi (i 1, n ) при которой выполняется равенство (1)
AПСС
n
ai Bi mod M .
i 1
(1)
Соотношение (1) можно представить в виде (2), т.е.
n
AПСС ai Bi rA M
i 1
(2)
4

5.

Первый метод определения ранга rA числа основывается на
реализации соотношения (2). Недостаток первого метода состоит в
следующем. При реализации СОД последовательности операций,
возможно, полагать, что часто определение величины ранга rA
чисел
A
будет производиться непосредственно в процессе
выполнения машинных операций. В этом аспекте рассмотренный
первый метод определения ранга числа по формуле (2) требует
выполнения позиционной операции определения величины числа
A , что нарушает общую процедуру непозиционной обработки
данных (снижается время реализации арифметических операций в
СОК).
5

6.

Второй метод
Вначале, предварительно, рассмотрим следующее утверждение.
Если в СОК заданы два числа A ( a1 , a2 , ..., an ) и B (b1 , b2 , ..., bn ) с
соответствующими рангами rA и rB , то ранг rA B суммы двух чисел
A B определится следующим образом
a b
rA B rA rB i i mi .
i 1 mi
n
(3)
Покажем правильность соотношения (3). Запишем выражения для
определения рангов чисел AПСС и BПСС в виде (2)
n
AПСС ai Bi rA M ,
(4)
i 1
n
BПСС bi Bi rB M .
i 1
(5)
6

7.

Сложим два соотношения (4) и (5), и получим
n
n
i 1
i 1
AПСС BПСС ai Bi rA M bi Bi rB M , или
n
AПСС BПСС ( ai bi ) Bi ( rA rB ) M .
(6)
i 1
С другой стороны, на основании правила вычисления суммы двух
чисел в СОК можно записать, что
a1 b1
a2 b2
A B a1 b1
m1 , a2 b2
m2 , ...
m1
m2
an bn
..., an bn
mn .
mn
(7)
7

8.

Выражение (7) можно представить в виде (8) (см. (2))
ai b i
A B ai bi
mi Bi rA B M .
i 1
mi
n
(8)
Сделаем преобразование выражения (8), с учётом того, что
mi M
, получим
Bi
mi
ai b i
A B ai bi Bi
mi Bi rA B M .
mi
i 1
i 1
n
n
ai b i
mi M
или A B ai bi Bi
mi
rA B M .
mi
mi
i 1
i 1
n
(9)
n
(10)
8

9.

Сравним правые части соотношений (6) и (10) и получим (11)
n
a
i
i 1
bi Bi rA rB M
ai b i
ai bi Bi
mi M rA B M , т.е.
mi
i 1
i 1
n
n
ai b i
rA rB
mi .
mi
i 1
n
rA B
Соотношение
(11)
является
основным,
(11)
позволяющим
определить ранг rA B суммы двух чисел A и B по значениям рангов
rA , rB слагаемых A и B .
9

10.

Очевидно, что если:
ai b i
1,
ai bi mi , то
mi
(12)
ai b i
ai bi mi , то
0.
mi
(13)
Последовательность определения ранга rA числа состоит в
следующем. К исходному числу A ( a1 , a2 , ..., an ) в СОК, ранг
rA которого необходимо определить, последовательно
прибавляются константы t ( i ) (i 1, n ) , представленные в СОК, в
виде минимальных чисел типа
t ( i ) (0, 0,..., 0, ti , ti 1 ,..., tn ) .
10

11.

В этом случае эта величина в ПСС будет равна
(i)
t ПСС
m1 m2 ... mi 1
В частности получим, что
t (1) min(t1 , t2 , ..., tn ) (1, 1, ..., 1) ;
t (2) min(0, t2 , ..., tn ) (0, m1, m2 , ..., mi 1 ) ;
t (3) min(0, 0, t3 , t4 , ..., tn ) (0, 0, m1 m2 (mod m3 ),
m1 m2 (mod m4 ), ..., m1 m2 (mod mn )
и т.д., где t ( n ) (0, 0, ..., 0, tn ) .
(n)
В ПСС это значение равно tПСС
m1 m2 ... mn 1 .Числа t (i ) и их
ранги ri определяются основаниями m1 , m2 ,...mn заданной СОК. 11

12.

Покажем,
процедуру
получения
значения
An (0, 0, ..., 0) . Вначале процедуры к исходному числу
A прибавляем константу t (1) (t1 , t2 , ..., tn ) столько раз,
сколько потребуется для того, чтобы выполнялось
условие a1 0 . Пусть для этого потребуется k1 сложений
типа A t . В этом случае получим, что
(1)
A1 A k1 t (1) .
В результате полученное число A1 имеет ранг rA1 .
Тогда по формуле (11) получим, что rA1 rA w1 , где w1 –
известная величина.
12

13.

Далее производим k2 раз сложений величины константы t (2) (0, t2 , ..., tn ) с
числом A1 до получения нулевого остатка по основанию m2 , т.е. получим
a2 0 . Имеем число A2 A1 k2 t (2) с рангом rA2 rA w2 , где w2 – известная
величина.
Полный алгоритм получения числа
A (0, 0, ..., 0) представлен
соотношением (14)
A1 A k1 t (1) ,
Г A1 Г A 1 ;
A 2 A1 k2 t (2) ,
Г A2 Г A1 2 ;
...
(14)
(i )
A i A i 1 ki t ,
Г A Г A i ;
i
i 1
...
A n An 1 kn t ( n ) ,
Г A n Г An 1 n .
13

14.

Продолжая процедуру по всем остаткам числа
A , в результате получим число A (0, 0, ..., 0) M .
В этом случае значение i ( i 1, n ) – это
известная
величина,
последовательно
исходного
в
числа
определяется
которая
процессе
преобразования
A ( a1 , a2 , ..., an )
в
число
An M (0, 0, ..., 0) .
14

15.

В соответствии с выражением (2) имеем, что
n
AПСС ai Bi rA M ,
i 1
n
An ai Bi rA M ,
i 1
n
(0, 0, ..., 0) ai Bi rA M ,
i 1
M 0 rA M ,
rA 1.
(15)
15

16.

Таким образом, промежуточный ранг
rA числа An (0, 0, ..., 0) равен. rA 1. С другой
стороны было показано (14), что ранг равен
rA wn . В этом случае имеем
rA wn 1 ,
(16)
rA 1 wn .
(17)
Тогда ранг rA числа A ( a1 , a2 , ..., an ) в СОК
определяется в соответствии с формулой (17).
16

17.

Таким образом, суть второго метода
определения
ранга
числа
A ( a1 , a2 , ..., an ) состоит в следующем. К
исходному числу A ( a1 , a2 , ..., an ) в СОК,
ранг rA которого необходимо определить,
последовательно
прибавляя
константы
(i )
t (i 1, n ) до тех пор пока в конечном итоге
не
получим
числа
An (0, 0, ..., 0) ,
промежуточный ранг rA которого равен
rA 1. Далее, по формуле (17), определяется
истинный ранг числа.
17

18.

Примеры определения расчётного ранга числа A . В таблице 1
представлены основания СОК mi , i 1, 3 , ортогональные базисы
Bi и их веса mi . В таблице 2, для заданной СОК, даны
минимальные константы t ( i ) и их ранги rt ( i ) . В этом случае
3
M mi 3 5 7 105 .
i 1
Таблица 1
m1 3
m1 2
B1 70
Таблица 2
t (1) (1, 1, 1)
r1 1
m2 5
m3 7
m2 1
B2 21
m3 1
B3 15
t (2) (0, 3, 3)
r2 1
t (3) (0, 0, 1)
r3 0
18

19.

Ранги минимальных констант t ( i ) вычисляются заранее по формуле
(2). Так определим значения минимальных констант для СОК,
заданной в таблице 1:
t (1) (1, 1, 1) 1 B1 1 B2 1 B3 (70 21 15) mod105 106 r M
106 1 105 . В этом случае rt (1) 1 (табл. 2).
t (2) (0, 3, 3) 0 B1 3 B2 3 B3 0 70 3 21 3 15 108
3(mod105) 108 r 105 . В этом случае rt ( 2 ) 1 (табл. 2).
t (3) (0, 0, 1) 0 B1 0 B2 1 B3 15 15 r 105 . В этом случае
rt ( 3) 0 (табл. 2).
19

20.

Пример 1. В соответствии с данными табл. 1, 2 найти ранг rA
числа A (2, 1, 1) 71 .
I этап. Обнуление остатка a1 2 по первому модулю m1 3 .
Сложим число A с t (1) .
A t (1) (2, 1, 1) (1, 1, 1) (0, 2, 2) .
20

21.

Ранг суммы определится по формуле (11)
ai b i
r ( rA rt (1) )
mi
mi
i 1
3
a1 b1
a3 b3
a2 b2
( rA rt (1) )
m1
m2
m3
m2
m3
m1
2 1
1 1
1 1
( rA 1)
2
1
1
5
7
3
( rA 1) (1 2 0 1 0 1) rA 1 2 rA 1 .
21

22.

Ранг суммы определится по формуле (11)
ai b i
r ( rA rt (1) )
mi
mi
i 1
3
a1 b1
a3 b3
a2 b2
( rA rt (1) )
m1
m2
m3
m2
m3
m1
2 1
1 1
1 1
( rA 1)
2
1
1
5
7
3
( rA 1) (1 2 0 1 0 1) rA 1 2 rA 1 .
При этом имел место один переход через первое основании m1
(формулы (12), (13)).
22

23.

II этап. Обнуление остатка a2 2 по второму модулю m2 5
числа (0, 2, 2) . Сложим два числа
(0, 2, 2) t (2) (0, 2, 2) (0, 3, 3) (0, 0, 5) .
Ранг суммы двух чисел определяется следующим образом
r ( rA 1) rt ( 2 )
( rA 1) rt ( 2 )
ai b i
mi
mi
i 1
3
a1 b1
a3 b3
a2 b2
m1
m2
m3
m2
m3
m1
0 0
2 3
2 3
( rA 1 1
2
1
1
5
7
3
rA (0 2 1 1 0 1) rA 1 .
При этом имел место один переход через второе основание m2 .
23

24.

III этап. Обнуление остатка a3 5 числа (0, 0, 5) . Сложим два числа
(0, 0, 5) t (3) (0, 0, 5) (0, 0, 1) (0, 0, 6) .
Ранг суммы двух чисел равен
ai b i
r ( rA 1) rt ( 3)
mi
mi
i 1
3
a1 b1
a3 b3
a2 b2
( rA 1) rt ( 3)
m1
m2
m3
m2
m3
m1
0 0
0 0
5 1
( rA 1) 0
2
1
1
5
7
3
rA 1 0 0 0 0 rA 1 .
24

25.

Так как остаток a3 5 числа (0, 0, 5) не обнулился, то добавим
ещё раз значение t (3) . Сложим два числа
(0, 0, 6) t (3) (0, 0, 6) (0, 0, 1) (0, 0, 0) .
Ранг суммы двух чисел равен
ai b i
mi
r ( rA 1) rt ( 3)
mi
i 1
3
a1 b1
a3 b3
a2 b2
m3
m2
m1
( rA 1) rt ( 3)
m2
m3
m1
rA 1 0 0 0 1 1 rA 2 .
25

26.

При этом имел место один переход через третье m3 основание
СОК. В соответствии с (13) и (14) имеем
rA 2 1 ,
или rA 1 .
Проверка (см. (2))
A (2, 1, 1) 2 B1 1 B2 1 B3 2 70 1 21 1 15 176 rA M
176 1 105 176 105 71.
26

27.

Пример 2. В соответствии с исходными данными (табл. 1, 2) найти
ранг rA числа A (1, 1, 5) 61 .
I этап. Произведём обнуление остатка a1 1 по первому модулю
m1 . Сложим два числа (табл. 2). A t (1) (1, 1, 5) (1, 1, 1) (2, 2, 6) .
Ранг суммы определится по формуле (11)
ai b i
r ( rA rt (1) )
mi
mi
i 1
3
a1 b1
a3 b3
a2 b2
( rA rt (1) )
m1
m2
m3
m2
m3
m1
1 1
1 1
5 1
( rA 1)
2
1
1
5
7
3
( rA 1) 0 2 0 1 0 1 rA 1 .
27

28.

Так, как остаток a1 1 числа A (1, 1, 5) не обнулился, то
добавим ещё раз значение контакта t (1) . Сложим два числа
(2, 2, 6) t (1) (2, 2, 6) (1, 1, 1) (0, 3, 0) .
Ранг суммы двух этих равен
ai b i
r rA 1 rt (1)
mi
mi
i 1
3
a1 b1
a3 b3
a2 b2
rA 1 1
m1
m2
m3
m2
m3
m1
rA 1 1 1 2 0 1 1 1 ( rA 1) 1 2 1 rA 1 .
При этом имело место два перехода. Через первое основание
m1 и через третье основание m3 .
28

29.

II этап. Обнуление остатка a2 3 числа (0, 3, 0) . Сложим два числа
(0, 3, 0) t (2) (0, 3, 0) (0, 3, 3) (0, 1, 3) .
Ранг суммы двух чисел определяется так
r ( rA 1) rt ( 2 )
( rA 1) rt ( 2 )
ai b i
mi
mi
i 1
3
a1 b1
a3 b3
a2 b2
m1
m2
m3
m2
m3
m1
0 0
3 3
0 3
( rA 1) 1
2
1
1
5
7
3
rA 1 1 0 2 1 1 0 1 rA 1.
Имел место один переход через основание m2 .
29

30.

Так, так остаток a2 3 числа (0, 3, 0) не обнулился, то сложим
два числа
(0, 1, 3) t (2) (0, 1, 3) (0, 3, 3) (0, 4, 6) .
Ранг суммы двух чисел равен
r ( rA 1) rt ( 2 )
ai b i
mi
mi
i 1
3
0 0
1 3
3 3
( rA 1) 1
2
1
1
5
7
3
rA 1 1 (0 2 0 1 0 1) rA .
30

31.

Переходов (переполнений) по остаткам (основаниям) нет. Так,
как остаток a2 3 числа (0, 3, 0) не обнулился, то вновь сложим два
числа
(0, 4, 6) t (2) (0, 4, 6) (0, 3, 3) (0, 2, 2) .
Ранг суммы двух чисел равен
r rA rt ( 2 )
ai b i
mi
mi
i 1
3
0 0
4 3
6 3
rA 1
2
1
1
5
7
3
rA 1 (0 2 1 1 1 1) rA 1 2 rA 1 .
31

32.

Имеет место два перехода (переполнения) через основания m2
и m3 . Так, как остаток a2 не обнулился, то реализуется операция
сложения двух чисел
(0, 2, 2) t (2) (0, 2, 2) (0, 3, 3) (0, 0, 5) .
Ранг суммы двух чисел равен
r ( rA 1) rt ( 2 )
ai b i
mi
mi
i 1
3
0 0
2 3
2 3
( rA 1) 1
2
1
1
5
7
3
rA 1 1 0 2 1 1 0 1 rA 1 1 1 rA 1 .
Имело место одно переполнение по основанию m2 .
32

33.

III этап. Обнуление остатка a3 5 числа (0, 0, 5) . Сложим два
числа
(0, 0, 5) t (3) (0, 0, 5) (0, 0, 1) (0, 0, 6) .
Ранг суммы двух чисел равен
ai b i
r ( rA 1) 0
mi
mi
i 1
3
0 0
0 0
5 1
rA 1 0
2
1
1
5
7
3
rA 1 0 0 2 0 1 0 1 rA 1 .
Переполнений основ не было.
33

34.

Так, как остаток a3 не обнулен, то реализуется операция
сложения двух чисел
(0, 0, 6) t (3) (0, 0, 6) (0, 0, 1) (0, 0, 0) .
Ранг суммы определится следующим образом
ai b i
mi
r ( rA 1) 0
mi
i 1
3
0 0
6 1
0 0
1
1
2
rA 1 0
7
5
3
rA 1 0 0 2 0 1 1 1 rA 2 .
34

35.

Имеется одно переполнение в остатке a3 по основанию m3 .
В соответствии с (15) и (16) имеем
rA 2 1 , rA 1 .
Проверка (см. (2)). A (1, 1, 5) . В ПСС имеем, что
A a1 B1 a2 B2 a3 B3 (1 70 1 21 5 15) mod105
166 rA 105 166 1 105 61 .
rA 0
A M
rA 1
A
rA 2
A
2M
3M
35

36.

Имеется одно переполнение в остатке a3 по основанию m3 .
В соответствии с (15) и (16) имеем
rA 2 1, rA 1.
Проверка (см. (2)). A (1, 1, 5) . В ПСС имеем, что
A a1 B1 a2 B2 a3 B3 (1 70 1 21 5 15) mod105
166 rA 105 166 1 105 61.
rA 0
A M
rA 1
A
rA 2
A
2M
3M
36
33

37.

Позиционный признак n A непозиционного кода (ППНК)
Пусть СОК задан совокупностью {mi}, i 1, n , попарно простых чисел.
Наибольший общий делитель (НОД) любой пары оснований mi и mj ( i, j 1, n; i j )
равен единице, т.е., НОД (mi, mj)=1. Для общности рассуждений пусть СОК будет
упорядочена, т.е. mi mi 1 .
ППНК основывается n A на принципе параллельного использования констант.
Суть процесса формирования ППНК числа AСОК состоит в том, что первоначально
исходное числа AСОК посредством констант вида KH m( Ai ) ( a1' , a2' ,..., ai' 1 , ai , ai' 1 ,..., an' )
приводятся к числу
Ami AСОК KH m( Ai ) ( a1 , a2 ,..., ai 1 , ai , ai 1 ,..., an )
(1)
(1)
( a1' , a2' ,..., ai' 1 , ai , ai' 1 ,..., an' ) ( a1(1) , a2(1) , ..., ai(1)
1 ,0, ai 1 ,..., an )
кратному одному определенному mi модулю СОК.
37

38.

Далее,
посредством
0, mi , 2 mi ,...,( N 2) mi , ( N 1) mi
основанию
mi ,
из
проводятся
совокупности
N
констант,
операции
кратных
вычитания
Ami K A mi Z K( AA) ( K A ) 0, N 1) т.е.
Ami
Ami
Ami
A
mi
Am
i
0 mi Z 0( A) ,
1 mi Z1( A) ,
2 mi Z
( A)
2
,
...
( N 2) mi Z N( A )2 ,
( N 1) mi Z N( A )1;
38

39.

n
где N mi mk ( N mi - количество двоичных разрядов
k 1;
k i .
в записи такого однорядного кода (ОК) K
количество
сумматоров,
( nA )
N mi
необходимых
или
для
осуществления операции вида Ami K A mi Z K( AA) .
39

40.

Таким образом, формируется ОК вида двоичной
последовательности
K
( nA )
N mi
{Z
( A)
N mi 1
Z
( A)
N mi 2
... Z
( A)
2
Z
( A)
1
Z
( A)
0
} для числа AСОК ,
при этом только одно значение Z
( A)
KA
0 . В случае,
если Ami n A mi 0 . Остальные значения Z
если Ami mi 0 ,
0, N 1 ,
( A)
KA
1,
nA .
40

41.

В этом случаи ОК вида K
( nA )
N mi
представляет
собой последовательность, состоящую из N mi
двоичных разрядов. В этой последовательности
двоичных символов только один двоичный разряд
нулевой,
а
остальные
–
единичные.
Местоположения нулевых разрядов ОК
K N( nmA )
i
определяют ППНК n A числа А.
41

42.

Практическое использование ППНК n A
Метод арифметического сравнения чисел в СОК
Рассмотрим метод арифметического сравнения чисел
A (a1 a2 ... ai 1 ai ai 1 ... an ) и
B (b1 b2 ... bi 1 bi bi 1 ... bn )
в СОК, основанный на использовании ППНК.
42

43.

Суть метода заключается в том, что для произвольного
модуля mi СОК исходные числа A
и В
посредством
констант вида
KH m( Ai ) ( a1' a2' ... ai' 1 ai ai' 1 ... an' ) и
KH m( Bi ) (b1' b2' ... bi' 1 bi bi' 1 ... bn' )
приводятся к числам
43

44.

Ami AСОК KH m( Ai ) ( a1 a2 ... ai 1 ai ai 1 ... an )
(1)
(1)
( a1' a2' ... ai' 1 ai ai' 1 ... an' ) [a1(1) a2(1) ... ai(1)
0
a
...
a
1
i 1
n ]
и
Bmi BСОК КН m( Bi ) (b1 b2 ... bi 1 bi bi 1 ... bn )
(1)
(1)
(b1' b2' ... bi' 1 bi bi' 1 ... bn' ) [b1(1) b2(1) ... bi(1)
0
b
...
b
1
i 1
n ],
кратным модулю mi СОК.
44

45.

Далее,
посредством
совокупности
0,1 mi ,2 mi ,...,( N 2) mi ,( N 1) mi из N констант, кратных основанию
mi , параллельно во времени проводятся
операции вычитания
Ami K A mi Z K( AA) и Bmi K B mi Z K( BB ) ( K A ( K B ) 0, N 1) т.е.
Ami
Ami
Ami
A
mi
Am
i
0 mi Z 0( A) ,
1 mi Z1( A) ,
2 mi Z 2( A) ,
...
(18)
( N 2) mi Z N( A )2 ,
( N 1) mi Z N( A )1;
45

46.

Bmi
Bmi
Bmi
B
mi
Bm
i
0 mi Z 0( B ) ,
1 mi Z1( B ) ,
2 mi Z 2( B ) ,
...
(19)
( N 2) mi Z N( B )2 ,
( N 1) mi Z N( B )1 ,
n
где N mi mk - количество двоичных разрядов в записи ОК K N( nmA ) и
k 1;
k i .
K N( nmB ) или количество сумматоров, осуществляющих операции
i
вида
i
Ami K A mi Z K( AA) или Bmi K B mi Z K( BB ) .
46

47.

Для
числа
K N( nmA ) {Z N( Am) 1 Z N m ( A2) ... Z 2( A) Z1( A) Z 0( A) }
i
i
формируется
A
в
виде
ОК
двоичной
i
последовательности, состоящей только из нулей и единиц, при этом из
всех возможных значений Z K( AA) ОК только одно значение Z K( AA) 0 . Это
происходит только в случае, если Ami n A mi 0 . Остальные значения
Z K( AA) 1, если Ami mi 0 ,
для
числа
B
0, N 1 ,
n A . Аналогичным образом
формируется
ОК
вида
K N( nmB ) Z N( Bm) 1 Z N( Bm) 2 ... Z 2( B ) Z1( B ) Z 0( B ) . При этом значение Z K( BB ) 0 (если
i
i
i
Bmi nB mi 0 ), а остальные значения Z K( BB ) 1 , если Bmi mi 0
( 0, N 1 ,
nB ).
47

48.

В этом случаи ОК вида K N( nmA ) и K N( nmB ) представляет собой
i
i
последовательность, состоящую из N mi двоичных разрядов.
В этой последовательности только один двоичный разряд
нулевой, а остальные – единичные.
Местоположения нулевых разрядов ОК K N( nmA ) и K N( nmB )
i
i
определяют значения n A и nB ППНК соответственно чисел
А и В.
48