Жебет С. Ю., к т. н., ведущий инженер-тестировщик, зао «крок»
Скачать 342.84 Kb.
|
^ При описании и использовании основных функций программы с целью упрощения понимания функционирования мы опустилили вопросы, связанные с неободимостью учитывать знаки исходных и возникающих в процессе вычислений чисел. Опишем один из возможных способов уточнения описаний этих операций. При этом заметим, что в процессе работы полученной рекурсией в глубину программы умножения чисел разрядности 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. Как следует из этих описаний вычисления по программе, полученной рекурсией в глубину, требуют область памяти размером  базовых слов, тогда какпрограмма, полученная рекурсией в ширину использует область памяти размером . Таким образом первый способ синтеза программы умножения многоразрядных чисел имеет существенное преимущество.^ Рассмотрим еще одну область машинного синтеза компьютерной программы. В основе преобразования Фурье и преобразования УолшаАдамара бинарного вектора  или  лежит умножение вектор-строки на матрицу Сильвестра Адамара  ,3 что требует  операций сложения или вычитания, так как каждый столбец матрицы имеет 2n ненулевых элементов.Известна схема Грина выполнения этой операции посредством n  указанных элементарных операций [9]. Эта схема основана на факторизации матрицы  в виде ,где  ( операция кронекеровского произведения матриц).В частности,  Матрицы  содержат в каждом столбце только два ненулевых элемента. Умножение вектор-строки на такую матрицу требует 2n+1 элементарных операций (сложения или вычитания), а всего требуется n2n+122n пар таких операций, при больших n имеем n2n<<22n.Программу для вычисления результата умножения вектора  длины m = 2n представим таблицей размером n2n. Строка i этой таблицы определяет последовательность операций сложения и вычитания на этапе вычисления результата умножения вектора (a1, a2,…, am)  , вычисленного после выполнения последовательности действий, описываемых предыдущими строками, на матрицу  . В j-ой клетке этой строки указаны номера компонент этого вектора, участвующих в формировании j-ой компонента вектора-результата. Если номер указан со знаком минус, то компонента с этим номером вычитается из j-ой компоненты результата, если этот знак не указан, то прибавляется.Такая таблица строится по индукции. Базисом индукции является таблица, соответствующая значению n=1. Обозначим ее V1. Она представляет программу для умножения (a1, a2)  и имеет вид приведенный в табл. 4.1. Таблица 4.1. Базис индукции (строение таблицы V1 )
Здесь и ниже индексы 1 и 2 в квадратных скобках соответствуют левой и правой половинам таблиц. Пусть построена таблица Vk 1, kn, Тогда таблица Vk образуется по схеме, приведенной в табл. 4.2. (общий шаг) Таблица 4.2. Общий шаг (построение таблицы Vk)
Здесь 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
Таблица 4.4. Построение таблицы V3 с использованием таблицы V2
По таблице 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. Результирующий вектор по адресам: 912, 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.С.67. 7. Жебет А.Ю., Фролов А.Б. Автоматический синтез программ умножения многочленов над конечным полем. Вестник МЭИ. №6. 2008. С. 59 70. 8. Фролов А.Б.,Жебет С.Ю., Винников А.М. Синтез компьтерных программ алгебраических операций и преобразований в конечных полях.Вестник МЭИ. №6, 2010. С. 9. А.Б.Бабаш, Г.П.Шанкин. Криптография. М: СОЛОН Р, 2002. Таблица 1.1. Схема перемножения многочленов степени менее двух
Таблица 1.2. Схема перемножения многочленов степени менее двух в относительных адресах
Таблица 1.3. Совмещенная схема умножения с прибавлением произведения по двум или более адресам
Таблица 1.4. Совмещенная схема умножения с прибавлением произведения по двум или более относительным адресам
Таблица 1.5. Схема перемножения разностей многочленов}
 Таблица 1.6. Схема перемножения разностей многочленов в относительных адресах
Таблица 1.7. Удвоение схемы из табл. 1. 2
Таблица 1.8. Детализация схемы из табл. 1.7  Таблица 4.1. Базис индукции (строение таблицы V1 )
Таблица 4.2. Общий шаг (построение таблицы Vk)
Таблица 4.3. Построение таблицы V2
Таблица 4.4. Построение таблицы V3 с использованием таблицы V2
Frolov A.B. Zhebet S.Yu.,Vinnikov A.M. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Похожие:
 | Тестировщики выступают в двух ролях одновременно – и как пользователи, и как эксперты по выявлению проблем | | ... |
| Образование: высшее профессиональное («Промышленная теплоэнергетика», «Тепловые электрические станции»). Специальность: инженер-теплоэнергетик,... | | Образование: высшее профессиональное («Промышленная теплоэнергетика», «Тепловые электрические станции»). Специальность: инженер-теплоэнергетик,... |
 | Смолякова Е. Б. – инженер службы гсм, Иващенко Н. Г. – инженер производственного отдела атб, Бондарева О. В. – заведующая общежитием,... | | Ленинградской области слывет медвежьим углом. Места здесь глухие и малонаселенные, что делает их привлекательными для охотников и... |
| Агент по размещению облигаций: Организатор Альфа-Банк, Андеррайтеры: зао «ик «Тройка Диалог», ОАО «ТрансКредитБанк», зао «акб абсолют... | | Уважаемый работодатель! Если Вас заинтересовал данный Соискатель, пожалуйста, обратитесь в Центр содействия трудоустройству выпускников... |
| Ведущий читает задание. Игроки внимательно его слушают и дают ответ. Если ответ верный, ведущий вручает им жетон. Можно разделить... | | Университет экономики и права «крок». Факультет экономический, специализация – финансы. 2000 -2005 гг |