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




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

Фролов А.Б., д.т.н., профессор, Московский энергетический институт (технический университет)

Жебет С.Ю., к.т.н., ведущий инженер-тестировщик, ЗАО «КРОК»

Винников А.М. студент, Московский энергетический институт (технический университет)

О машинном синтезе некоторых линейных программ1

Рассматриваются два способа автоматического синтеза программ умножения многоразрядных чисел по методу Карацубы  аналитический, имитирующий строение функциональной схемы умножения и способ, основанный на использовании рекурсивного описания этого метода. Функциональность программ, построенных первым способом очевидна. Программы, построенные по второму способу экономны по объему требуемой памяти. Описывается метод сравнения получаемых программ для доказательства их функциональной эквивалентности. Такой же подход возможен при синтезе программ умножения в кольце многочленов над конечным полем, программ дискретного преобразования Фурье и преобразования Уолша-Адамара.
Ключевые слова: автоматизация программирования, машинный синтез программ, линейная программа, декомпозиционная схема, метод Карацубы, функциональная эквивалентность программ, преобразование Фурье, преобразование Уолша-Адамара.

Введение

Изучение методов автоматического синтеза программ является важным разделом программной инженерии. Основной особенностью автоматически синтезированной компьютерной программы является ее надежность и отсутствие необходимости ее тестирования при конкретных значениях входных данных. Под автоматизацией синтеза программ будем понимать создание программного средства для формирования кода программы, реализующей алгоритмы заданного класса, по значениям глобальных параметров этих алгоритмов. Применением такого программного средства и осуществляется автоматический синтез программы. Алгоритмы, допускающие автоматический синтез программ можно найти, в частности, среди алгебраических алгоритмов компьютерной алгебры [1,2], описывающих операции в конечных алгебраических структурах и некоторые алгебраические преобразования. Так умножение многоразрядных чисел, умножение многочленов над конечным полем, быстрое преобразование Фурье и преобразование Уолша-Адамара используется во многих алгоритмах цифровой обработки сигналов, кодирования и криптографии. При этом получаются последовательные, или линейные программы, не содержащие циклов и условных переходов.

Впервые задача оптимизации умножения рассматривалась в работе [3]. Этой задаче посвящены работы [2,4]. В частности, в [4] обоснована т.н. декомпозиционная схема умножения многочленов, допускающая схемную и программную реализацию. Аналогичная схема может быть составлена для умножения многоразрядных целых чисел. В работах [5,6] сообщается о возможности автоматизации синтеза подобных схем и соответствующих компьютерных программ. Аргументы о корректности получаемых алгоритмов и программ, вопросы оптимизация распределения памяти для сокращения времени пересылок применительно к алгоритмам умножения впервые были рассмотрены в работе [7]. В работе [8] дано более полное их освещение. В настоящей работе эти идеи излагаются применительно к синтезу программы умножения многоразрядных неотрицательных целых чисел. Она состоит из настоящего введения и четырех разделов.

В первом разделе на основе известной формулы Карацубы применительно к умножению многоразрядных целых чисел описывается метод получения линейного (не содержащего циклов) алгоритма умножения. Коды сомножителей и вычисляемого произведения разбиваются на минимальные адресуемые единицы (элементарные числа). Линейный алгоритм представляется в виде последовательности действий, каждое из которых включает предварительные операции вычитания, присваивания или перестановки с некоторыми элементарными числами, попарное перемножение некоторых результатов предварительных вычислений и серию заключительных сложений полученных произведений. Из этой последовательности очевидным способом извлекаются цепочки действий по формированию каждой адресуемой единицы произведения.

Во втором разделе описывается рекурсивный алгоритм, оптимизирующий объем используемой памяти.

Третий раздел посвящен методу контролируемого автоматического синтеза оптимизированной программы умножения многоразрядных целых чисел.

В четвертом разделе предлагается подход к автоматическому синтезу программ преобразования Фурье и преобразования Уолша-Адамара бинарных векторов.
^ 1. Аналитический способ построения линейных программ умножения многоразрядных чисел

Как известно, целые числа A удобно представлять в позиционной системе счисления по некоторому основанию p в виде цепочки (an-1an-2a1a0p, совокупность элементов которой образует вектор

(1)

элементы таких цепочек и векторов это числа , или цифры позиционной системы счисления.

Так числу 126 в десятичной системе счисления соответствуют цепочка (126)10 и вектор

(6,2,1),

в двоичной системе счисления - цепочка (111110)2 и вектор

(0,1,1,1,1,1).

в восьмеричной системе счисления - цепочка (176)8 и вектор

(6,7,1)

По вектору (1) число A определяется как сумма

(2)

Например, 126=6´10^0+2´10^1+1´10^2=7+20+100 или

126=0´2^0+1´2^1+1´2^2+1´2^3+1´2^4+1´2^5+1´2^6=0+8+16+32+64.

Число n называется разрядностью представления числа в данной системе счисления. Если n=2m (т.е. четно), то сумма (2) разбивается на две части:



Вынесем за скобки piво второй сумме и получим



где числа A0 и A1 имеют разрядность не более m, а разрядность числа A не более 2m. Это ни что иное, как двухразрядное представление числа A в системе счисления по основанию pm.­

Пусть надо перемножить числа A и B, разрядность которых не превышает 2m. Представим каждое из них в этой системе счисления по основанию pm





Тогда по «школьному алгоритму» (или алгоритму сдвигов и сложений) мы можем получить произведение по формуле

A´B=A0´ B0+ ( A0´ B1+ A1´ B0 )pm + A1´ B1 p2m. (3)

При этом надо выполнить четыре операции умножения чисел вдвое меньшей размерности (одноразрядных чисел по основанию pm).

По формуле Карацубы [3] произведение тех же чисел получается следующим образом

A´B=A0´ B0(1+ pm)+( A1 - A0) ( B0 - B1) (pm) + A1´ B1(pm + p2m). (4)

При этом надо выполнить три операции умножения чисел вдвое меньшей размерности. Нетрудно проверить, что формулы (3) и (4) эквивалентны.

Для примера рассмотрим умножение по формуле Карацубы чисел

A=1234=34+12´102 и B=2314 =14+ 23´102 (n=4, m=2) в десятичной системе счисления, учитывая, что A0=34, A1=12, B0=14, B1=23:

34´14(1+102)+(12-34)(14-23) 102+12´23´(102+104)=

476´101+198´100+276´10100=48076 +19800+27600+2760000=2855476.

В данном случае мы использовали десятичную систему счисления для большей наглядности. Далее будем полагать, что числа представляются в двоичной системе и при размещении в памяти занимают n=2t (t1) машинных единиц (бит, байт или машинных слов)2. Мы используем здесь число n в виде степени двойки, чтобы была возможность применения формулы (4) при перемножении как самих чисел, так и их составных частей, образуемых при возможно многократном дроблении на две части. Тогда всегда сомножители рассматриваются как двухразрядные числа по основанию 2t1. При этом будем считать, что перемножение элементарных чисел осуществляется по известной подпрограмме (программной функции). Элементарные числа это одноразрядные числа по основанию 2s. Например, если используется программная функция перемножения байтов, то s=8, если это функция перемножения машинных слов, то s=32. Нашей задачей является получение программы умножения многоразрядных чисел по основанию 2s по методу Карацубы как последовательности действий с такими числами, содержащие операции умножения только элементарных чисел.

Будем использовать следующие обозначения:

[a]1 =[a]  одноразрядное число, размещенное по адресу a;

[aA]k k-разрядное число A, размещенное, начиная с адреса aA , k>1;

 младшая «половинка» числа [aA]k;

старшая «половинка» числа [aA]k.

При этом числа и наследуют знак числа [aA]k.

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

Если из контекста ясно, какое число представляется, будем использовать упрощенные обозначения и .

Полагая, что числа [aA] размещаются в памяти как последовательности элементарных чисел, с начальным адресом aA, будем использовать относительные адреса 0,1,…, n-1 для указания индексов элементов представляющих эти числа векторов (1), то есть элементарное число ai имеет адрес aA+i: ai=[aA+i]. При этом, используя описанный выше способ обозначения младших и старших «половинок», получаем, что элементарное число ai есть число 1 или, упрощенно 1, где (i) есть двоичный эквивалент числа i.

Будем обозначать

[a,b]k разность чисел [a]k и [b]k.

[a;b] 2k произведения чисел [a]k и [b]k.

[a1,a0;b0,b1]k произведение (A1A0)(B0B1) разностей [a1,a0]k/2 и [a1,a0]k/2 «половинок» k-разрядных чисел.

Тогда схема для вычисления с размещением результата по некоторому относительному адресу c может быть представлена табл. 1.1.

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



=













c c+1

c+1

c+1 c+2

В первой строке табл. 1.2. в квадратных скобках указаны относительные адреса множителей или слагаемых, образующих эти множители. При этом нижний индекс 0 означает, что используется младшая «половинка» числа, а нижний индекс 1 указывает на использование старшей половинки этого числа, имеющей адрес a+1. В третьей строке даны относительные адреса c, c+1 и c+2 блоков из двух машинных единиц, куда с учетом знака прибавляются произведения. Первое и третье произведения прибавляются дважды, по двум адресам каждое, множителями второго произведения являются две разности чисел. По данной схеме осуществляется три умножения, и произведения последовательно накапливаются в блоке из четырех единиц с относительным адресом c. Этой схеме соответствуют цепочки действий, изменяющих первоначально нулевые состояния блока из четырех единиц с относительным базисным адресом c (в квадратных скобках с индексом k указывается содержание блока из k базовых слов с базисным адресом c):






В случае, когда произведение накапливается по двум или более адресам, будем использовать совмещенные схемы (табл. 1.2), где a и b  относительные адреса сомножителей, c и d  относительные адреса накопления результата.

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



=













c c+1

c+1

c+1 c+2







d d+1

d+1

d+1 d+2


Схема для умножения разностей двух чисел дана в табл. 1.3.

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




=





[

]2







e e+1

e+1 e+2

e+1


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

Таблица 1.4. Удвоение схемы из табл. 1.1



=













c c+2

c+2

c+2 c+4

Удвоенная схема соответствует применению формулы (4) к сомножителям вдвое большей размерности. При этом относительный адрес второй «половинки» операнда удваивается.

Операция детализации схемы заключается в том, что используемые для описания схемы обозначения подсхем, определяющих произведения заменяются схемами, выражающими их через произведения Так, детализируя схему из табл. 1.4 с учетом табл. 1.1  1.3, получим схему в табл. 1.5.

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



=















[a00;b00]2

c c+2

c+1 c+3

[a 01; b01] 2

c+1 c+3

c+2 c+4

[a01, a00;

b00, b01]2

c+1 c+3






[(a1,a0)0;

(b0,b1) 0]2
c+2 c+3

[(a1,a0)1;

(b0,b1) 1]2
c+3 c+4

[(a1,a0)1,

(a1,a0)0;

(b0,b1)0,

(b0,b1)1]2

c+3






[a10;b10]2

c+2 c+4

c+3 c+5

[a11; b11]2

c+3 c+5

c+4 c+6

[a11,a10;

b10,b11]2

c+3 c+5

Как видим из табл. 1.5, произведение можно получить, выполнив 9 перемножений элементарных чисел и прибавив полученные произведения

11= [a00;b00]2,

12= [a 01; b01] 2,

13= [a01, a00; b00, b01]2,

21=[(a1,a0)0; (b0,b1) 0]2,

22=[(a1,a0)1; (b0,b1) 1]2,

23=[(a1,a0)1,(a1,a0)0;(b0,b1)0,(b0,b1)1]2,

31=[a10;b10]2,

32=[a11; b11]2,

33=[a11,a10;b10,b11]2

к содержимому определенных групп разрядов формируемого результата в указанной ниже последовательности:

[c]2 =[c] +11;

[c+1]3­=[c+1] +11+12+13;

[c+2]3=[c+2] +11+12+21+31;

[c+3]3 =[c+3] +11+12+13+21+22+31+32+23+33; (5)

[c+4]3 =[c+4]+12+22+31+32 ;

[c+5]3 =[c+5] +31+32+33;

[c+6]2 =[c+6] +32.

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

Выполняя последовательно операции удвоения и детализации, можно получить табличную схему для вычисления произведения при любом 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
контакты
www.vbibl.ru
Главная страница