НЕЙРОННАЯ СЕТЬ ОСНОВНОГО ДЕЛЕНИЯ МОДУЛЯРНЫХ ЧИСЕЛ
NEUTRON NETWORK FOR MAIN DIVISION OF MODULAR NUMBERS

Изобретение относится к вычислительным модулярным нейрокомпьютерным системам и предназначено для выполнения основной операции деления модулярных чисел, когда делимое и делитель являются произвольными числами.
Известна нейронная сеть для округления и масштабирования чисел, представленных в системе остаточных классов (патент RU 2271570, G06 3/04, опубликованная 10.03.2006, Бюл. №7), содержащая входной слой нейронов, нейронную сеть конечного кольца определения ранга числа, нейронную сеть конечного кольца вычисления остатка по основанию n+1, нейронную сеть конечного кольца вычисления разности между входными остатками и остатками по основанию n+1, n - нейронные сети конечного кольца вычисления масштабированного числа.
Недостатком данной нейронной сети является невозможность вычисления операции основного модулярного деления чисел.
Наиболее близким к данному изобретению техническим решением является устройство, представленное в виде "Нейронной сети для деления чисел, представленных в системе остаточных классов" (Патент RU 2305312 G06 7/52, G06N 3/02, опубликовано 27.08.2008, Бюл.№24).
Недостатком устройства является большой объем оборудования.
1
2
n
1
2
3
Однако такие нейронные сети предназначены для деления модулярных чисел в случаях, когда в качестве делителя используется целое положительное число, попарно простое с p, р, …, p, либо целое положительное число, представляющее собой произведение чисел, попарно простых с p, p, …, p.
Целью данного изобретения является расширение функциональных возможностей известной нейронной сети для выполнения операций модулярного деления чисел в случаях, когда делимое и делитель являются произвольными числами, и сокращение объема оборудования.
i
i
i
i
i
i
i
Поставленная цель достигается тем, что нейронная сеть основного деления модулярных чисел содержит: входные регистры для приема и хранения делимого 1 и делителя 2, на входы которых поступают, соответственно, делимое 3 и делитель 4; нейронную сеть для деления чисел 5, представленных в системе остаточных классов (патент RU 3218239, опубликовано 27.02.2008, Бюл. №6); нейронную сеть для преобразования остаточного кода в двоичный позиционный код 6 (патент RU 3218238, опубликовано 27.02.2008, Бюл. №6), в этом изобретении используются только коэффициенты a, представленные в ОПСС; постоянное запоминающее устройство 7 для хранения цифр приблизительного делителя; сумматор 8 для формирования частного, полученного от деления; блок сравнения промежуточных частных q с нулем 9; блоки умножения делителя на промежуточные значения частных q 10; блоки вычитания произведений делителя b и промежуточного частного q из значения исходного делимого a или промежуточных значений a 11; блок сравнения промежуточного делимого a с величиной b/2 12; ключ 13 для считывания частного и блок запрета 14 для записи в регистр делимого нового промежуточного значения a 14 и шину 15 для значений частного; информационные шины 16-21, 28 для обмена данными между устройствами и схемами нейронной сети основного деления модулярных чисел и шин управления 22-27.
Известные изобретения связаны со специальными случаями и неприменимы в ситуации, когда и делимое, и делитель представляют собой произвольные целые числа.
1
1
1
1
1
1
2
1
2
2
Различные алгоритмы деления целых чисел  можно описать итеративной схемой, используемой так называемый метод спуска Ферма. Конструируется некоторое правило φ, которое каждой паре целых положительных чисел a и b ставит в соответствие некоторое целое положительное q такое, что a-bq=r>0. Тогда деление a на b осуществляется по следующему правилу: согласно операции φ паре чисел a и b ставится в соответствие число q, такое, что a-bq=r≥0. Если r<b, то деление закончено, если же r≥b, то, согласно φ, паре чисел (r,b) ставится в соответствие q, такое, что r-bq=r≥0.
2
2
1
2
3
2
3
3
1
2
3
Если (r<b), то деление завершается, если же (r≥b), то, согласно φ, паре (r,b) ставится в соответствие q такое, что r-bq=r≥0 и так далее. Так как последовательное применение операции φ приводит к строго убывающей последовательности положительных чисел α≥r>r>r…≥0, то процесс является конечным и алгоритм реализуется за конечное число шагов.
В общем случае b может быть и не равным модулю или их произведению. Здесь встает проблема выбора b таким образом, чтобы оно было равным либо модулю, либо их произведению. Если эта проблема будет решена, тогда итерации могут быть сведены к процессу масштабирования, который рассмотрен выше. Для решения этой проблемы вначале рассмотрим без доказательства теорему о границах изменения b.
k-1
k
k
Теорема. Если на K-ом шаге зафиксирован случай 0≤r-bq=r<b, тогда частное q от деления целых чисел a на b будет равно . Если
1
Проблема разработки оптимальных вычислительных алгоритмов деления побуждает к разработке таких операций φ, которые бы минимизировали число шагов спуска Ферма и вместе с тем достаточно просто реализовывались на заданной вычислительной базе. Кроме того, на способ формирования операций φ существенно влияет также принятая система кодирования числовой информации.
Метод, который будет описан ниже, направлен на использование деления на приблизительный делитель . Этот приблизительный делитель будет выбран из значений делителя, допускаемых в применении алгоритма масштабирования. Так как, в основном случае, b не равно , ошибка представлена в частном, которое при выполнении итерации будет уменьшаться до нуля.
Значение для  найдем из соотношения b≤<2b, где  - это допустимый делитель для алгоритма масштабирования.
В алгоритме деления первым этапом является этап вычисления частного по алгоритму масштабирования, при котором .
1
2
3
Найденный таким образом q используется в рекурсивных соотношениях  для получения q, q и так далее.
i
Эта повторяющаяся процедура продолжается пока q≠0. Если это возникает на r-ом шаге повторения, то
где
Действительность этого алгоритма зависит от трех предпосылок:
i
i
1. Или q, или α становятся нулевыми после последнего числа повторений.
2. Ряд  должен быть равным .
3. Для любого b существует подходящий  и этот  можно найти. Подходящий  определен как удовлетворяющий условию b≤<2b и также удовлетворяющий условию алгоритма масштабирования.
Приблизительный делитель  можно найти путем использования наиболее значимой ненулевой цифры, представлен  в полиадической системе счисления. Эту ненулевую цифру заменим ближайшим простым числом или произведением простых чисел. Тогда делитель  можно представить в виде простого числа или произведения простых чисел, что позволит использовать для вычисления частного алгоритм масштабирования.
Для определения  можно составить таблицу приблизительного делителя. В таблице приведен список допустимых значений b для системы модулей 23, 19, 17, 13, 11, 7, 5, 3, 2.
Таблица
Таблица приблизительного деления
Если b<sub>i</sub>=0 для i ≠ p
Если b<sub>i</sub>≠0 для i≠p
b<sub>p</sub>
Q
b<sub>p</sub>
Q
1
1
1
2
2
2
2
3
3
3
3
5
4
5
4
5
5
5
5
3×2
6
3×2
6
7
7
5×2
7
5×2
8
5×2
8
5×2
9
5×2
9
5×2
10
5×2
10
11
11
11
11
13
12
13
12
13
13
13
13
7×2
14
7×2
14
5×3
15
5×3
15
17
16
17
16
17
17
17
17
19
18
19
18
19
19
12
19
7×3
20
7×3
20
7×3
21
7×3
21
7×3
22
11×2
22
23
Пример 1. В остаточной системе, состоящей из модулей 23, 19, 17, 13, 11, 7, 5, 3 и 2 (Р=223092870) делим a=10304312 на b=1401. Округленное частное .
9
8
7
6
Решение. Вначале представим b в обобщенной позиционной системе счисления в порядке уменьшаемой значимости b=0, b=0, b=0, b=0,
5
4
3
2
1
i
b=0, b=0, b=3, b=3, b=21, где b определяем из уравнения
9
8
7
6
5
4
3
2
1
b=b(23·19·17·13·11·7·5·3)+b(23·19·17·13·11·7·5)+b(23·19·17·13·11·7)+b(23·19·17·13·11)+b(23·19·17·13)+b(23·19·17)+b(23·19)+b23+b
1
3
1
1
Используя таблицу с b=b, получаем b==5·19·23=2185, так как b является наиболее значимой ненулевой цифрой обобщенной позиционной системы счисления и определяется выражением  где Q дано в таблице.
Отсюда: ;
i
i
Далее получаем остальные значения a и q
q<sub>3</sub>=607
a<sub>3</sub>=477698
q<sub>4</sub>=218
a<sub>4</sub>=172280
q<sub>5</sub>=78
a<sub>5</sub>=63002
q<sub>6</sub>=28
a<sub>6</sub>=23774
q<sub>7</sub>=10
a<sub>7</sub>=9764
q<sub>8</sub>=4
a<sub>8</sub>=4160
q<sub>9</sub>=1
a<sub>9</sub>=2759
q<sub>10</sub>=1
a<sub>10</sub>=1358
<img file="00000018.tif" he="11" wi="40" img-content="undefined" img-format="tif" />
r
11
r-1
Так как q=0 (то есть q=0), но α≥b, то . Следовательно,
Полученный результат можно легко проверить обычным делением a=10304312 на b=1401. Для вычисления округленного частного потребовалось десять итераций, так как числа были выбраны обдуманно, чтобы получилось много операций. Это происходит в тех случаях, если a - относительно малое число,  - аппроксимация b.
Модифицируем полученный алгоритм на язык кольцевых операций системы остаточных классов. Для этого рассмотрим следующий пример.
Пример 2. В остаточной системе, состоящей из модулей 7, 5, 3, 2 необходимо разделить число a=201→(5, 1, 0, 1) на число b=8→(1, 3, 2, 0).
Округленное частное обозначим как .
Решение. Вначале преобразуем делитель b в ОПСС в порядке уменьшаемой значимости:
4
3
2
1
2
1
b=b(7·5·3)+b(7·5)+b7+b, тогда b=0·(7·5·3)+0·(7·5)+1·7+1, где b=1, b=1.
p
2
i
Используя таблицу 1 с b=b и b≠0 для i ≠ р, получим
где Q=2 или =2·7
Далее по алгоритму деления, изложенному выше, находим ,
где  - это произведение двух модулей 7·2.
1
q=(0,4,2,0)→14.
1,
Используя q найдем
1
0
1
a=a-bq=(5,1,0,1) - (1,3,2,0·0,4,2,0)=(5,4,2,1)→89.
i
i
Далее получаем остальные значения a и q:
6
Так как  то q=1. Следовательно, Действительно
Итак, для основного деления модулярных чисел, при котором делимое и делитель являются произвольными числами, необходимо выбрать приблизительный делитель, представленный в обобщенной позиционной системе счисления в виде простого числа или произведений простых чисел, на основе которых провести округление делимого с целью вычисления ошибки делимого с нулевым остатком, которые в дальнейшем используются в итерациях получения приблизительных и окончательных значений частного.
На чертеже представлена схема нейронной сети основного деления модулярных чисел.
Принцип работы данного изобретения излагается ниже.
Нейронная сеть основного деления модулярных чисел позволяет выполнить операцию деления при произвольных значениях делимого и делителя.
i
i
i
Делимое "a" и делитель "b", представленные в системе остаточных классов, поступают во входные регистры 1 и 2, соответственно, делимое по шине 3, а делитель по шине 4. Делитель b с выхода регистра 2 по шине 17 поступает на преобразователь кода системы остаточных классов в код обобщенной позиционной системы счисления (ОПСС) 6 (патент RU 3218238, опубликовано 27.02.2008, Бюл. №6) и на первый вход схемы умножения делителя b на промежуточное частное q 10. Делитель b, представленный в виде коэффициентов a в ОПСС, по шине 19 с выхода 6 поступает на адресные входы ПЗУ 7, реализующего нахождение  в соответствии с таблицей. Далее, выбранные из ПЗУ значения приблизительного делителя, равного , в качестве разрешающего сигнала поступают по шине 22 на вход блока деления с нулевым остатком 5 (патент RU 3218239, опубликовано 27.02.2008, Бюл. №6), с выхода которого промежуточное частное q по информационной шине 28 поступает на второй вход блока умножения 10 и на входы сумматора 8 и схемы сравнения 9.
i
Если q=0, то схема сравнения 9 формирует сигнал управления "Да", который по шине 24 через ключ 13, выход которого по шине 25 поступает на управляющий вход сумматора 8, на выходе которого, шина 15, формируется результат деления.
i
i
i
Если q≠0, то схема сравнения 9 формирует сигнал управления "Нет", который по шине 23 поступает на разрешающий вход схемы запрета 14, которая разрешает прохождение по шине 18 промежуточного значения a на вход регистра 1 по шине 21. Кроме того, сигнал "Нет" разрешает умножение промежуточного частного q на делитель "b", поступающий по шине 17.
i
2
i
i
2
i
b
b
Результат умножения в блоке 10 по шине 20 поступает на первый вход блока вычитателя 11, на второй вход которого поступает значения a по шине 16 с выхода регистра 1. Результат вычитания по шине 18 поступает на вход схемы сравнения с / блока 12 и на информационный вход схемы запрета 14, с выхода которого по шине 21 a подается на вход регистра 1. Кроме того, a сравнивается с / блока 12, если формируется сигнал "нет", то схема сравнения 12 выдает управляющий сигнал, который по шине 27 через ключ 13 и шину 25 считывает результат деления, шина 15, который сформирован в накапливающем сумматоре 8, если схема сравнения 12 формирует сигнал "Да", то схема сравнения выдает сигнал "1", который по шине 26 подается на вход сумматора, где суммируется с содержимым сумматора 8, на выходе которого просуммированные частные q выдаются на выход, шина 15, которые являются выходом нейронной сети основного деления модулярных чисел.
Время деления определяется количеством итераций, которые выполняются за четыре цикла синхронизации.