Файл: Основы теории алгоритмов учеб. пособие.pdf

рацию сложения

(как, например, в дискретно-разностных алго­

ритмах), т .е .

только

операции умножения являются порождающи­

ми [5 l]

.

'

В

этом случае

одна из форм записи программы реализации

такого алгоритма может быть следующей:

с =•

1т К ,

где

fit

-

операция вызова числа из

t -ой ячейки;

•

-

операция вызова числа из

j -ой ячейки;

+

С

-

операция умножения;

Oft -

операция пересылки результата операции С в ячей­

И -

ку

с адресом

Ь ;

количество слагаемых в алгоритме;

S - операция слижения.

Фигурные скоски с индексами означают, что оператор

О л =* Oi'Sj C Cft'

является выполненным только в

случае,

когда ] ,

L

,

t

пробегают значения от I до

К .

После это­

го

раоотает

оператор

G U * {(&toi+i S X & m S j - - 3

Вели в

каком-лиоо

операторе отсутствует

операция Oft ,

то будем подразумевать, что результат действия этого

оператора

остаетоя в арифметическом устройстве (АУ). Например,

после вы­

полнения оператора Q.J *=■о* St+i 5 его результат

остается в аУ;

после этого вызывается содержимое ячейки

и складывает­

вести исходный алгоритм к такому виду,

чтобы операции сложе­

ния и умножения порождали друг друга.

Это обстоятельство

по­

зволит исключить в выражении (3.9) операцию

.

Можно доказать, что всякий алгоритм,

состоящий из

опе­

раций сложения и умножения, в котором одна операция умноже­

ния порождает одну операцию сложения,

можно привести к виду

Q _ f(6c6j c)(fiw SJCbj-iCj - j ,

t - l - s K , j - J - i - K .

(3.10)

Рассмотрим алгоритм в

общем виде

У e X l Vi +ЭС-х % + - - + # К $ С -

(3 .II)

Для случая, когда # 1

, ¥ t , З&ь . V* . . . . . # К ,^ п р и ­

нимают все вещественные значения,

можно всегда найти такие чис­

ла, что

v

ry

v

—

OCk

7

_ w l

iVj

** s — »

>* ' • * C k-i

OCk-l

Подобное представление переменных позволяет записать

исходный алгоритм (3 .II) в виде

у « ( • • • ( V * г * л +

( 3Л2)

Разместив в ячейках

6 i

величины ¥ь

и в

ячейках

величины

, нетрудно убедиться, что запись

програшы

(3.10)

соответствует

реализации алгоритма (3 .12). Но алгоритм

(3.12)

является эквивалентным алгоритму ( З . П ) .

Точно так же можно найти

Jft

m i -

%

m

-

3 .

fflr-l

т г ~

Ук-i

v t

В этом случае в ячейках

размещаются величины

d6i

,

а в

ячейках

-

величины

.

Запись программы (3.10) алгоритма, состоящего из опера-

ояения и умножения,

является более экономичной, так как

-

76 -

здесь

исключается

операция

CLt .

На практике чаще всего встречаются алгоритмы, в кото­

рых

X i или

являются постоянными коэффициентами, В

ht «=С/(<п , &г = Q К42,

. . . ,

&к « Озк

то будем иметь

+-Q<X [h-K]~

U

* ЯоЭйМ +

+••

3

(3.13) ’ |

- O k h ^[H-i] ---------Cl2KLj[n-К].

~ y t n - i ] Z * - X [ n - K ] Z K - i +

<ЗЛ4>

+

гк- 2+■ *+ х [м -о 2о + л) Гн]) Оо,

где

си

k

Zi

cti

’

Clm-i

Количество

операций в

алгоритмах

(3.13) и (3,14) одно

Пусть необходимо производить вычисления функции у=^(ас) ,

причем аргумент

X

есть

некоторая случайная величина. В та­

ких случаях, очевидно, масштабировать надо по максимальному

значению промежуточного результата

2

,

получаемого в процес­

се вычисления для данного X

,

Один из способов для определения

~ f ( X )

состоит

в исследовании функционального преобразования

у = £ (об)

и выражения

2 1

как функции не

только

от X

, но и от у ..

Рассмотрим эффективные приемы масштабирования алгорит­

мов типа (3.7) в олучае реализации их на УВС о фиксированной

запятой. Выберем масштабные коэффициенты в ввде (71 = 2 * ^

(

t

= 0 , 1 , 2 , . . . )

и.определим

H ( n T b J z ( ^ ( « ' 0 T ,

где

Z («T ). максимальное

значение суммы ( з . 7 ; .

Предположим,

что для

Qi

и

&L введены

постоянные мас­

штабы для всего

процесса вычислений от

( 1 = 1

до

И = N

•

Для входных переменных ОС

О ТJ

масштаб Щх (иТ)

будет

равен

^

и является постоянным для всех X [ ( n - L ) T ]

при вычислении

только одного

значения

y f n T ]

.

to входных пере­

Для нахождения коэффициента

сдвига

менных достаточно 2 ( п Т )

представить в

нормализованном виде

Z ( n T ) ^ c ( 2 C ,

тогда

порядок

t

и будет

искомым коэффици­

ентом сдвига. При этом,

если

t < 0

, осуществляем одвиг всех

# [ ( > Г - с ) Т ]

, (

I

=

0 , 1 , 2 , » . . , К

)

на

t

разрядов вле­

во,

в против;

ом случае -

на

t разрядjb вправо.

Исследуем алгоритм

(3 .?),

золи

Х ( ч -

ступенчатая функ­

ция,

и запишем аго в ваде

к

Ц п **

£=0

" £

S t ^ w -ь •

У 5jcm =*■X < Е » ^ У

$c«t 2 ^ ^^

х £

о с

(3,15)

Sк+i— Sк— $1

«“I,

“ S k« “ б г ^ и - а ,

$ к + г * S k+i - I -

= н .

Промежуточная сумма S j ( j

i, 2 , . ••, K+ О

изменя­

ется

с изменением

j

и в некоторой точке принимает максималь­

ное

значение

, причем этот максимум будет либо при'

Q 4. J £: К

,

либо при

j 4 К 4 5

У уст <

ЗС

О £

ИЛИ

*Ч I4 Tj

> i •

l + Z & i

Если же

У ^ 1

, то промежуточная сумма достигает

максимального значения

при K+

+

,

При выполнении алгоритма

(3.15)

S c

образуются сумми­

рованием коэффициентов. Обозначим максимальную промежуточную

сумму при сложении коэффициента

Cf через

S a

,

а при сложе­

нии коэффициентов

S

- через

S s

. Тогда

при

2 я 1

'*• ОС S

a ,

(3.16)

а при й* * 1

к.

^

*

(3.17)

Если X

£-о

- медленно изменяющийся процеоо,

то

И Mi

'*

ОС Mia* S o ,

(3.18)

=

OCn X

^ ~ < / у сЖ

,

(3.19)

i*o

где OC*m<jx_ максимальное по модулю из

значений Х п

,Х>м, . . . ,

ОС и-к J

У так - максимальное по модулю значение ^ и- i , . . . , ^ н - г .

Полученные таким образом величины 2 н

отражают только

поэтому для

того, чтобы не получить 2 и

меньше входных пере­

менных, необходимо n p a S a < l(u/,u S l * i )

вместо S a ( UJIUS bJ

в фррмулы (3.16, 3 .18), (3.17, 3.19) подставить единицу,

Еоли

ЭС (Ч) изменяется достаточно медленно, то

и