Жебет С. Ю., к т. н., ведущий инженер-тестировщик, зао «крок»




Скачать 342.84 Kb.
НазваниеЖебет С. Ю., к т. н., ведущий инженер-тестировщик, зао «крок»
страница3/4
Дата публикации01.06.2013
Размер342.84 Kb.
ТипДокументы
vbibl.ru > Химия > Документы
1   2   3   4

^ 4. Реализация основных функций програм

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

Учитывая принцип наследования знака числа любой его частью, будем записывать по относительному адресу a+r знак (0 если число неотрицательно или 1 если оно отрицательно). В итоге получается, что знак числа многократно (по количеству разрядов числа) повторяется. При этом знаки исходных множителей t-кратно записываются, начиная с относительных адресов r и a+r. Это позволяет уточнить базовые функции следующим образом.

1) equ(P,Q,N)  операция присваивания: [P];=[Q], N базовых слов, записанных, начиная с относительного адреса Q записываются, начиная сотносительного адреса P, и N базовых слов, записанных начиная сотносительного адреса r+N, записываются, начиная с относительного адреса r+P.

2) sub(P,Q,N)  операция вычитания:[P]:=[P][Q], начиная сотносительного адреса P, записывается абсолютное значение разности чисел, абсолютные значения которых записаны по относительным адресам P и Q, а знаки N-кратно повторяются, начиная с отностельных адресов r+P и r+Q соответственно; знак разности записывается, также N-кратным повторением, начиная с относительного адреса r+P.

3) add(P,Q,N)  операция сложения: [P]:=[P][Q], начиная сотносительного адреса P, записывается абсолютное значение суммы чисел, абсолютные значения которых записаны по относительным адресам P и Q, а знаки N-кратно повторяются, начиная с отностельных адресов r+P и r+Q соответственно, знак суммы записывается, (N+1)-кратным повторением, начиная с относительного адреса r+P.

4) mul(P,Q,N)  операция умножения: [P]=[P]*[Q], начиная с относительного адреса P записывается абсолютное значение произведение чисел чисел, абсолютные значения которых записаны по относительным адресам P и Q, а знаки N-кратно повторяются, начиная с отностельных адресов r+P и r+Q соответственно; знак произведения записывается, также 2N-кратным повторением, начиная с относительного адреса r+P.

5) exchg(P,Q,N) перемещения (N базовых слов, записанных, начиная с относительного адреса Q относительного адреса P взаимно перемещаются, как и N базовых слов, записанных начиная с относительного адреса r+N и относительного адреса r+P.

Как следует из этих описаний вычисления по программе, полученной рекурсией в глубину, требуют область памяти размером базовых слов, тогда какпрограмма, полученная рекурсией в ширину использует область памяти размером . Таким образом первый способ синтеза программы умножения многоразрядных чисел имеет существенное преимущество.
^ 5. Схема Грина быстрых преобразований Фурье и Уолша-Адамара

Рассмотрим еще одну область машинного синтеза компьютерной программы. В основе преобразования Фурье и преобразования УолшаАдамара бинарного вектора или лежит умножение вектор-строки на матрицу Сильвестра  Адамара ,3 что требует операций сложения или вычитания, так как каждый столбец матрицы имеет 2n ненулевых элементов.

Известна схема Грина выполнения этой операции посредством n указанных элементарных операций [9]. Эта схема основана на факторизации матрицы в виде

,

где (  операция кронекеровского произведения матриц).

В частности,



Матрицы содержат в каждом столбце только два ненулевых элемента. Умножение вектор-строки на такую матрицу требует 2n+1 элементарных операций (сложения или вычитания), а всего требуется n2n+122n пар таких операций, при больших n имеем n2n<<22n.

Программу для вычисления результата умножения вектора длины m = 2n представим таблицей размером n2n. Строка i этой таблицы определяет последовательность операций сложения и вычитания на этапе вычисления результата умножения вектора (a1, a2,…, am) , вычисленного после выполнения последовательности действий, описываемых предыдущими строками, на матрицу . В j-ой клетке этой строки указаны номера компонент этого вектора, участвующих в формировании j-ой компонента вектора-результата. Если номер указан со знаком минус, то компонента с этим номером вычитается из j-ой компоненты результата, если этот знак не указан, то прибавляется.

Такая таблица строится по индукции.

Базисом индукции является таблица, соответствующая значению n=1. Обозначим ее V1. Она представляет программу для умножения

(a1, a2)

и имеет вид приведенный в табл. 4.1.

Таблица 4.1. Базис индукции (строение таблицы V1 )

V1 [1]

V1 [2]

1; 2

1;  2


Здесь и ниже индексы 1 и 2 в квадратных скобках соответствуют левой и правой половинам таблиц.

Пусть построена таблица Vk 1, kn, Тогда таблица Vk образуется по схеме, приведенной в табл. 4.2. (общий шаг)

Таблица 4.2. Общий шаг (построение таблицы Vk)

Vk [1]

Vk [2]

Vk1

Vk1+(2k1 ; sign 2k1)

1 ; 1+2k1

2;

2+2k1

….

2k1;

2k1+2k1

1 ; 12k1

2;

22k1

….

2k1;

2k12k1

Здесь Vk1+(2k1 ; sign 2k1)  таблица, получающаяся из таблицы Vk1 заменой элементов Vk1[i,j] = {c; d}: прибавлением к первому с и второму d числам чисел 2k1 и sign 2k1 соответственно (sign  знак числа d заменяемого элемента Vk1[i,j]).

Примеры таблиц V2 и V3 приведены ниже, см. табл. 4.3 и табл. 4.4.

Таблица 4.3. Построение таблицы V2

V2 [1]

V2 [2]

1; 2

1;2

3; 4

3; 4

1; 3

2; 4

1; 3

2; 4


Таблица 4.4. Построение таблицы V3 с использованием таблицы V2

V3 [1]

V3 [2]

1; 2

1; 2

3; 4

3 ;4

5; 6

5 ;6

7; 8

7; 8

1; 3

2; 4

1; 3

2; 4

5; 7

6; 8

5; 7

6 ;8

1; 5

2; 6

3; 7

4; 8

1; 5

2; 6

3 ;7

4; 8

По таблице Vm можно автоматически синтезировать последовательную программу умножения бинарного вектора на матрицу Сильвестра – Адамара. Например, по таблице V2 формируется следующий код:
add(5, 1, 2)

sub(6, 1, 2)

add(7, 3, 4)

sub(8, 3, 4)

add(9, 1, 3)

add(10, 2, 4)
sub(11, 1, 3)

sub(12, 2, 4)
Исходный вектор находится по адресам 1 4. Результирующий вектор  по адресам: 912, add(N,P,Q)  сложение чисел по адресам P и Q, результат занести в ячейку N, sub(N,P,Q)  вычитания чисел по адресам P из Q, результат занести в ячейку N.

Список литературы

1. Gathen J. von zur, Gerhard J. Modern computer algebra. Cambrige University Press, 1999.

2. Болотов А.А, Гашков С.Б., Фролов А.Б., Часовских А.А., Элементарное введение в эллиптическую криптографию. Алгебраические и алгоритмические основы, Москва, КомКнига, 2006.

3. Карацуба А.А., Офман Ю.П. Умножение многозначных чисел на автоматах. Доклады Академии Наук СССР, т. 145, № 2, 1962, 293-294.

4. Болотов А.А, Гашков С.Б., Фролов А.Б., Часовских А.А., Программные и схемные методы умножения многочленов для эллиптической криптографии. Известия РАН. Теория и системы управления. 2000. №5. С. 66  75.

5. М.И. Фомичев. Научный руководитель – А.Б. Фролов, Автоматизация процесса синтеза схем умножения многочленов над полем Галуа GF(2) на базе метода Карацубы. 5 Московская международная телекоммуникационная конференция молодых ученых и студентов «Молодежь и наука». Московский государственный инженерно-физический институт (технический университет). 2001. http://molod.mephi.ru/2001/reports.asp?rid=157

6. Дроздов А.Б. Автоматическое построение декомпозиционных схем умножения многочленов над полем GF(2), основанных на методе Карацубы// Четвертая Всероссийская научная интернет-конференция. Компьютерное и математическое моделирование в естественных и технических науках. 2002. Вып. 17.С.67.

7. Жебет А.Ю., Фролов А.Б. Автоматический синтез программ умножения многочленов над конечным полем. Вестник МЭИ. №6. 2008. С. 59  70.

8. Фролов А.Б.,Жебет С.Ю., Винников А.М. Синтез компьтерных программ алгебраических операций и преобразований в конечных полях.Вестник МЭИ. №6, 2010. С. 

9. А.Б.Бабаш, Г.П.Шанкин. Криптография. М: СОЛОН Р, 2002.


Таблица 1.1. Схема перемножения многочленов степени менее двух



=













с c+1

c+1c+2

c+1


Таблица 1.2. Схема перемножения многочленов степени менее двух в относительных адресах



=







abc




0 1

1 2

1


Таблица 1.3. Совмещенная схема умножения с прибавлением произведения по двум или более адресам



=







a b c d




c+0 c+1

c+1 c+2

c+1







d+0 d+1

d+1 d+2

d+1


Таблица 1.4. Совмещенная схема умножения с прибавлением произведения по двум или более относительным адресам












a b c d

=

0 1

1 2

1


Таблица 1.5. Схема перемножения разностей многочленов}



=







(c, d),







e e+1

e+1 e+2

e+1



Таблица 1.6. Схема перемножения разностей многочленов в относительных адресах



=



[1.1; 1,1]2

[(0.0). (1.1); (0,0),(1,1)]2

a b c d e




0 1

1 2

1


Таблица 1.7. Удвоение схемы из табл. 1. 2



=







a b c




0 2

2 4

2


Таблица 1.8. Детализация схемы из табл. 1.7


Таблица 4.1. Базис индукции (строение таблицы V1 )

V1 [1]

V1 [2]

1; 2

1;  2


Таблица 4.2. Общий шаг (построение таблицы Vk)

Vk [1]

Vk [2]

Vk1

Vk1+(2k1 ; sign 2k1)

1 ; 1+2k1

2;

2+2k1

….

2k1;

2k1+2k1

1 ; 12k1

2;

22k1

….

2k1;

2k12k1


Таблица 4.3. Построение таблицы V2

V2 [1]

V2 [2]

1; 2

1;2

3; 4

3; 4

1; 3

2; 4

1; 3

2; 4


Таблица 4.4. Построение таблицы V3 с использованием таблицы V2

V3 [1]

V3 [2]

1; 2

1; 2

3; 4

3 ;4

5; 6

5 ;6

7; 8

7; 8

1; 3

2; 4

1; 3

2; 4

5; 7

6; 8

5; 7

6 ;8

1; 5

2; 6

3; 7

4; 8

1; 5

2; 6

3 ;7

4; 8

Frolov A.B. Zhebet S.Yu.,Vinnikov A.M.
1   2   3   4

Похожие:

Жебет С. Ю., к т. н., ведущий инженер-тестировщик, зао «крок» iconТестировщик, тестер, qa-инженер, Software Quality Assurance Engineer...
Тестировщики выступают в двух ролях одновременно – и как пользователи, и как эксперты по выявлению проблем

Жебет С. Ю., к т. н., ведущий инженер-тестировщик, зао «крок» iconКрасноярский государственный технический университет англо-русский...
...

Жебет С. Ю., к т. н., ведущий инженер-тестировщик, зао «крок» iconЗаконы и иные нормативно-правовые акты, определяющие основные направления...
Образование: высшее профессиональное («Промышленная теплоэнергетика», «Тепловые электрические станции»). Специальность: инженер-теплоэнергетик,...

Жебет С. Ю., к т. н., ведущий инженер-тестировщик, зао «крок» iconЗаконы и иные нормативно-правовые акты, определяющие основные направления...
Образование: высшее профессиональное («Промышленная теплоэнергетика», «Тепловые электрические станции»). Специальность: инженер-теплоэнергетик,...

Жебет С. Ю., к т. н., ведущий инженер-тестировщик, зао «крок» iconСообщение о существенном факте
Смолякова Е. Б. – инженер службы гсм, Иващенко Н. Г. – инженер производственного отдела атб, Бондарева О. В. – заведующая общежитием,...

Жебет С. Ю., к т. н., ведущий инженер-тестировщик, зао «крок» iconN194 slonov net games dracula dracula 003 1 baza jpg
Ленинградской области слывет медвежьим углом. Места здесь глухие и малонаселенные, что делает их привлекательными для охотников и...

Жебет С. Ю., к т. н., ведущий инженер-тестировщик, зао «крок» icon• Статус эмиссии: в обращении
Агент по размещению облигаций: Организатор Альфа-Банк, Андеррайтеры: зао «ик «Тройка Диалог», ОАО «ТрансКредитБанк», зао «акб абсолют...

Жебет С. Ю., к т. н., ведущий инженер-тестировщик, зао «крок» iconИнженер по технике безопасности, инженер по охране труда
Уважаемый работодатель! Если Вас заинтересовал данный Соискатель, пожалуйста, обратитесь в Центр содействия трудоустройству выпускников...

Жебет С. Ю., к т. н., ведущий инженер-тестировщик, зао «крок» iconВ 5-6 классах
Ведущий читает задание. Игроки внимательно его слушают и дают ответ. Если ответ верный, ведущий вручает им жетон. Можно разделить...

Жебет С. Ю., к т. н., ведущий инженер-тестировщик, зао «крок» iconРоманчук Лариса Ивановна
Университет экономики и права «крок». Факультет экономический, специализация – финансы. 2000 -2005 гг

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
vbibl.ru
Главная страница