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




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

^ 2. Рекурсивные программы умножения многоразрядных чисе

Рассматриваемые ниже программы вычисления произведения [a,b]2m представляют собой линейные последовательности строк вида op(P,Q,N), где op  обозначение операции, P относительный адрес первого операнда и результата, Q относительный адрес второго операнда, N разрядность (по основанию 2s операндов:

equ(P,Q,N)  операция присваивания: [P];=[Q],

sub(P,Q,N)  операция вычитания:[P]:=[P][Q],

add(P,Q,N)  операция сложения:[P]:=[P]+[Q],

mul(P,Q,N)  операция умножения: [P]=[P]*[Q].

Исключение составляет команда exchg(P,Q,N) перемещения (элементы с адресами P и Q меняются местами).

Перемножаемые числа размещаются по относительным адресам 0 и 2n, произведение размещается по относительному адресу 0, замещая множители.

Программа для вычисления в системе счисления по основанию 2s произведения [a;b]4 по формуле (4) имеет следующий вид.

Программа 1:

equ(4, 0, 1)

sub(4, 1, 1)

equ(5, 3, 1)

sub(5, 2, 1)

xchg(1, 2, 1)

mul(0, 1, 1)

mul(2, 3, 1)

mul(4, 5, 1)

add(4, 0, 2)

add(4, 2, 2)

add(1, 4, 2)

Нетрудно видеть, что эта программа соответтвует схеме из табл.1.1 при значениях адресов a=c=0. По этой программе выполняется три умножения, и произведения последовательно накапливаются в блоке из четырех единиц с относительным адресом c =0.

Над программами рассматриваемого вида можно выполнять операции удвоения, удваивая все встречающееся в программе адреса и длины операндов. Например, удвоением программы 1 получим сдедующую программу.

Программа 2:

equ(8, 0, 2)

sub(8, 2, 2)

equ(10, 6, 2)

sub(10, 4, 2)

xchg(2, 4, 2)

mul(0, 2, 2)

mul(4, 6, 2)

mul(8, 10, 2)

add(8, 0, 4)

add(8, 4, 4)

add(2, 8, 4)
Удвоенная программа соответствует применению формулы (4) к сомножителям вдвое большей размерности, а также схеме из табл. 1.4.

Операция рекурсивной детализации в глубину программы 2 заключается в том, что строки, в которых определяются произведения слов длины 2 заменяются последовательностями строк, в соответствии с программой 1.

При этом адреса определяются в зависимости от номера k шага удвоения и первого адреса c команды умножения в соответствии с таблицей

^ Таблица 2.1. Правило детализации строки mul(с,с+2, 2) удвоенной программы, d=2k+1+4.


mul(с,с+2, 2)


equ(d,c,1)

sub(d,c+1,1)

equ(d+1,c+3,1)

sub(d+1,c+2,1)

xchg(c+1,c+2,1)

mul(c+0,c+1,1)

mul(c+2,c+3,1)

mul(d,d+1,1)

add(d,c,2)

add(d,c+2,2)

add(c+1,d,2)



Так, рекурсивной детализацией в глубину программы 2 получим программу 3 представленную в табл. 2.2, в первом столбце которой даны строки программ 2 замененные в программе 3 группами строк.

Таблица 2.2. Детализация программы 2


Программа 2

Программа 3

equ(8, 0, 2) }

equ(8, 0, 2) }

sub(8, 2, 2)

sub(8, 2, 2)

equ(10, 6, 2)

equ(10, 6, 2)

sub(10, 4, 2)

sub(10, 4, 2)

xchg(2, 4, 2)

xchg(2, 4, 2)

mul(0, 2, 2)


equ(12, 0, 1)

sub(12, 1, 1)

equ(13, 3, 1)

sub(13, 2, 1)

xchg(1, 2, 1)

mul(0, 1, 1)

mul(2, 3, 1)

mul(12, 13, 1)

add(12, 0, 2)

add(12, 2, 2)

add(1, 12, 2)

mul(4, 6, 2)


equ(12, 4, 1)

sub(12, 5, 1)

equ(13, 7, 1)

sub(13, 6, 1)

xchg(5, 6, 1)

mul(4, 5, 1)

mul(6, 7, 1)

mul(12, 13, 1)

add(12, 4, 2)

add(12, 6, 2)

add(5, 12, 2)

mul(8, 10, 2)

equ(12, 8, 1)

sub(12, 9, 1)

equ(13, 11, 1)

sub(13, 10, 1)

xchg(9, 10, 1)

mul(8, 9, 1)

mul(10, 11, 1)

mul(12, 13, 1)

add(12, 8, 2)

add(12, 10, 2)

add(9, 12, 2)

add(8, 0, 4)

add(8, 0, 4)

add(8, 4, 4)

add(8, 4, 4)

add(2, 8, 4)

add(2, 8, 4)



Полученная программа функционально соответствует схеме из табл. 1.5.

Рекурсивная программа умножения методом Карацубы может быть получена на основе программы 1 также путем, возможно, многократного выполнеия двух преобразований – удвоения, описанного выше, и рекурсивной детализации в ширину.

В табл. 2.1 в правом столбце первые пять строк будем рассматривать как прямой ход рекурсии, а заключительные три строки как обратный ход рекурсии, шестая, седьмая и восьмая строки образуют раздел умножения.

Рекурсивная детализация в ширину заключается в том, что

а) непосредственно перед разделом умножений добавляется очередной уровень прямого кода рекурсии, образуемый несколько измененными сроками прямого хода рекурсии табл. 2.1.

equ(d+2i,c,1)

sub(d+2i,c+1,1)

equ(d+2i+1,c+3,1)

sub(d+2i+1,c+2,1)

xchg(c+1,c+2,1)

для каждой удвоенной строки умножения с порядковымномером i

mul(c, c+2, 2)

б) i-я строка умножения заменяется тройкой строк

mul(с, с+1, 1)

mul(с+2, с+3, 1)

mul(d+2i,d+2i+1, 1)

в) непосредственно после раздела умножений добавляется очередной уровень обратного хода рекурсии, образуемый несколько измененными строками обратного хода рекурсии табл. 2.1.

add(d+2i,c,2)

add(d+2i,c+2,2)

add(c+1,d+2i, 2)

для каждой удвоенной строки умножения с порядковым номером i

mul(c, c+2, 2)

Так, рекурсивной детализацией в глубину программы 2 получим программу 3 представленную в табл. 2.3, в первом столбце которой даны строки программы 2.

^ Таблица 2.3. Рекурсивная детализация программы 2

Программа 2

Программа 3

equ(8, 0, 2) }

equ(8, 0, 2) }

sub(8, 2, 2)

sub(8, 2, 2)

equ(10, 6, 2)

equ(10, 6, 2)

sub(10, 4, 2)

sub(10, 4, 2)

xchg(2, 4, 2)

xchg(2, 4, 2)

Прямой шаг рекурсии (уровень 2)

equ(12, 0, 1)

sub(12, 1, 1)

equ(13, 3, 1)

sub(13, 2, 1)

xchg(1, 2, 1)

equ(14, 4, 1)

sub(14, 5, 1)

equ(15, 7, 1)

sub(15, 6, 1)

xchg(5, 6, 1)

equ(16, 8, 1)

sub(16, 9, 1)

equ(17, 11, 1)

sub(17, 10, 1)

xchg(9, 10, 1)

Умножения

mul(0, 2, 2)

mul(4, 6, 2)

mul(8, 10, 2)


mul(0, 1, 1)

mul(2, 3, 1)

mul(12, 13, 1)

mul(4, 5, 1)

mul(6, 7, 1)

mul(14, 15, 1)

mul(8, 9, 1)

mul(10, 11, 1)

mul(16, 17, 1)

Обратный шаг рекурсии (уровень 2)

add(12, 0, 2)

add(12, 2, 2)

add(1, 12, 2)

add(14, 4, 2)

add(14, 6, 2)

add(5, 14, 2)

add(16, 8, 2)

add(16, 10, 2)

add(9, 16, 2)

add(8, 0, 4)

add(8, 0, 4)

add(8, 4, 4)

add(8, 4, 4)

add(2, 8, 4)

add(2, 8, 4)


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

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

При умножении многочленов над конечным полем проблема представления знака не возникает.

Два вида рекурсиной детализации удвоенной программы отличаются тем, что при детализации в глубину приоритетно выполняются операции, обеспечивающие необходимые данные для выполнения очередной операции умножения, а при детализации в ширину выполняются все операции, обеспечивающие необходимые данные для выполнения всех 3k умножений на k-м шаге прямого хода рекурсии. Этим объясняется увелиение требуемого для исполнения программы объема памяти (см. раздел 4). Число выполняемых операций не изменяется, то есть использование рекурсивной детализации в глубину имеет преимущество.

^ 3. Контролируемый машиный синтез программ умножения многоразрядных чисел

В разделе 2 рассмотрены два способа построения линейных программ умножения многочленов. Очевидно, что несложно написать программу синтеза таких программ, как и программу построения табличных схем из раждела 1 путем многократных повторений дублирования и детализации.

Программы, синтезированные описанными двумя способами, принадлежат одному классу, при этом отличаются только способами адресации элементов и методами распределения памяти для хранения промежуточных результатов.

Формальным анализом построенных программ и табличных схем также машинным путем, примененем соответствущих программ фиксируются цепочки действий, выполняемых с фрагментами области результата при добавлении в эти фрагменты результатов перемножения определенных базовых слов. Например, по схеме из табл. 1.5 получаются цепочки действий (5). Такие же цепочки получаются при формальном анализе программ из табл. 2.2 и 2.3. По построению, эквивалениность цепочек действий, определямых схемой и рекурсивоной программой, полученными в результате k шагов удвоения и детализаци влечет эквивалентность цепочек действий, определяемых схемой и программой, полученными в результате k+1 удвоения и детализации. Таким образом, функционально эквивалентные табличная схема и программа порождают одинаковые цепочки действий. Верно и обратное: совпадение цепочек действий свидетельствует о функциональной эквивалентности программы и схемы. Это обстоятельство позволяет осуществлять контроль правильности синтезированной рекурсивной программы сравнением извлекаемых из нее цепочек действий с цепочками, извлекаемыми из соответствующей табличной схемы. При этом следует заметить, что построение и анализ табличной схемы нагляднее и проще построения и анализа программы.

Отметим, что эти вычисленные программно цепочки соответствуют декомпозиционной схеме, полученной в [2,4] неформализованным путем.

Предлагаемый метод автоматического контролируемого синтеза программ умножения многочленов заключается в том, что при заданных максимально возможных разрядностях 2m автоматически синтезируются табличная схема и рекурсивная программа того или иного вида. Затем из описаний табличной схемы и текста программы извлекаются цепочки действий по формированию базовых слов результата умножения. Формальными преобразованиями цепочки автоматическое приводятся к единому виду. Равенство полученных цепочек свидетельствует о корректности обеих последовательных программ. Данная проверка отменяет необходимость тестирования программ при конкретных значениях исходных данных.
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
Главная страница