книги из ГПНТБ / Основы теории алгоритмов учеб. пособие

О,

+ 0 ,[^ l]o fP c =рi-i +0, (<£-¥)L,

( ь ~ к,

2 )

рк = 0 ) ;

(4Л 6)

< 5 ^ , ^

+

о + Pi -

S ( tf-4,)j., №

- ¥ ) 1 .

че£рз последовательности

О, ft + 0> [ % ] 0 -t-pL=*pi-i+0,(*£~'>ijl j

(4.1?)

< L ~ K k - i , , . . , 2 ;

=

$ 4 i ,

i+l[- 5t i ,4*Je + pi * S(jr-*j1;(if- 4 ? )I .

Система (4.17) может быть реализована, как (4 .1 2 ), ес-

#и олова

вычитаемого инвертировать и

рк

принять равным

2 К!1

.Вносимая ошибка такого алгоритма равна нулю. Если

принять,

что

рк= 0, то система (4.17)

будет

соответствовать

(4 .1 6 ),

ошибка которой ^ 2 ~**,

частичных произведений.

Для длинных чисел

•

^

i

i."l

y

-

Z

^

2-j" .

j

i=t

отдельных слов

\

представленных в прямых кодах,

произведение

( * * * ) ( % ?

*

)

-

(

m

^

2

Произведение отдельного

слова

на длинное Число

j

Y* можно найти из йгерационной

носледоватёльности

|

( % 2 ~ in)(4 'i

z *

) + Р а ч , 2 - <С+* " ’

-

i

-

П « . л

,

(4.18)

j

Q - k , k 4 , . . . , 2 , U

Р ( н к ) - 0 ) .

йлеоь

'<■ -

множитель,

a

T

-множимое.

Реализация данной последовательности даст

№ 2 -“ j T f - f U - ' V Z

2

илиИ

i " 1

( f

Z

П

«

*

Л

2 '

^

Для

j =50

t = К

имеем

2К

(

*

O

к

v

-

П

*

5

первое длинное частичное произведение.

f ’ *

Обозначим через

«Д1+1-=-

f i t

2'^*

сущу

длинных

частичных произведений

*

Тогда

% Y - >

«Лг- i T ,

«И

e

3u*t

г

*fiY .

(4.18)

-

юз -

Здесь ЧЬ-ЧГ

реализуется поеледав ат ельностью (4 .1 8 ).

После

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

числа

»ii L+i.

,

С учетом

сказанного

и принимая за

начальное

условие

L-+-f ■= (Кк+ч =>0

,

произведение длишшх чисел мо­

жет быть получено из системы

П

2 ‘

и^

) 2 ч”

'

" +

и 2 ^

"

-

(

,

зи

(Зля j=«k

имеем

irVo-K) = 0

>

(4.19)

флЯ с*к

и j - k ,

2 ,f

име«м

f l ( i 4(j)

*“О )

( Ъ 2 -* Х 'Ч 2 * )+ (> < Щ )2 - < Ъ )Н

+

+

П

2 Ч

( ^ (для^ J4

)Н

,

P -

(

iп

+

i

о -

o

,

В (4.19) для каждого фиксированного

i = к

,

к '( .........

2, I

параметр

j

принимает

значения

=

,

, . . . , 2 , 1 .

Реализация системы

(4.19) дает

,

3

КН

T

-

Z

n

s

2

-

S

" .

f

Sri,

—*■

S c ^ ) l

,

(4.20)

где | - k + f , k , . . . , 2 , 1 }

С * 7 0 # и - О

р к +ч - 2 “(к" * ° }

р о - О ,

;

получим

к

'

O f у ) -

Z .C fy2j j^ ” ■

Данное произведе!ие будет получено о абсолютной ошибкой

Л < 0,5 - 2"

к

н

.

- 104 -

Тогда в (4.19)

i =* к , к - Ь •«- > 2 , ( ;

I

В этом случае число обращений к итерациям системы

(4 .I9'1

к ц е т

равно

.

i

4

( к + 5 ) Н -

|

С.

5

Абсолютная погрешность такого произведения увеличится

счет' отброшенных частичных произведений на величину

! г - < ы ' ”[ 2 к - я ,

\

д 5 .<2 - ав , + 2 - с “ ‘ ” " 2[ к - з1 .

Ввиду малости второго слагаемого можно считать,

что

i

Л < 0 .5 - 2 ~ кп

Из системы (4.19) можно получить множество алгоритмов

|

Умножения с различными показателями

А

, Например,

отбрасы-f

вая

И -разрядные члены частичных произведший,меньшие,

чем

:

2 ~ кп , можно получить алгоритм с

абсолютной погрешностью

j

I

А < 2 - * и[ 2 М .

.

j

V

Если здесь частичные произведения

Ч,. 'f j

,

гд е ^ к -(И );

получать с

округлением, то ошибка такого

алгоритма

!

д

< 2 ~ * t1( i . s k - i ) .

А . л с

о-ки

i

Если

до

:

строить алгоритм о ошибками от Д < U . b d

2 “K"C2k -0

* Т0 МОЖНО получить

L - 2 ( 2 k - l )

алгоритмов

с различными показателями

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

Л .

Для чисел,

представленных в памяти машины в

обратных

i

или в

дополнительных кодах, Для получения

З ч

применяем так­

же систему итераций (4 .1 9 ). Однако при округлении

З ч

. по л у ­

ченного в дополнительных кодах, в системе

(4.20)

будет отсутст-

- 105

-

воватьоперация

Sfl<

SCVY)| ,т.к.младшие оловав ячейках

памятихранятояоположительнымзнаком.

Для* обратного

кода представления чисел

округление

Осуществляется по последовательности

A s

+ С + Р |

-

P |- i + W Y )'j-,

<4-21)

где

4,

+

к

2,

, < .

. .0; , , е

Цтус

д 0> ; и

к

Рк*4 “

2 ”^**^

|

С-*11,(4, • ••, Н,«сим ¥ ¥ < 0 ;

( « ■ * % . « - О . )

-ре - О ,

кодах представления чисел в ЗУ.

I

Для прямого кода представления чисел,

вводя специальные

- 107

для

t « M , k - 2 , . . . , 3 , 2

i

< r > ® V i

!

Сй8 П - *

для

U ]

l < P a > | ^ ( ^ + Y ) i ;

,

i

'

< I > + ^

< I > - * 0 * + 4 f ) lf

где

©

~ код операции оложения без переполнения;

j

-

код операции перенооаС а цифровыхв и разрядов в регистр

память машины,

I

Применяя специальный код записи < £ >

по модулю в па­

мять машины о последующим обнулением цифровых разрядов

X

и перенос значения

Р н в младший разряд

£

(код|<£>{

),

получим алгоритм для t = к

*Ри -* £

'

!

‘

(4,22)

для

3,2.1*

1

< I > @

для’

(,«= \

< 2 > - » W + y ) < .

Если ввести

специальные коды оложения младших и отар- 1

тих частей о одновременным сложением значения

Р(,ч

,

кото-f

рпй будем хранить в специальном разряде [48,

67] ,

то для

j

L=k, ы , . . . , 5 , 2

имеем

для с и

ч»*—» * ;

< £ > © i 4 /,

< Т > ~ * Q i+ Y h .

|ЭДеоь

© г -

код операции сложения младших частей о

р н

; |

:

© Г -

код операции сложения старших частей о

ра.

>

При составлении набора алгоритмов вычитания в повышен­

ной точностью можно ввести специальные команды вычитания

["67]

Ооновной показатель

(

i

) алгоритма УВС,

работающей

И реальном масштабе времени, можно определить в зависимости

от степени точности (

к )

следующим образом.

:

Для алгоритмов

сложения зависимость i от к

представля­

ется как

|

-

k

i t e

,

;

,

(4.24)

уде

х-о - время выполнения проотой операции о одинарной

)

точностью;

:

^ ~ число простых операций в одной итерации сложения.

- 109 -

Алгоритм вычитания имеет

I

й « . - k U o

,

:

где

& - число простых операций в

одной итерации вычитания*

!

I

Для прямого и обратного кодов представления чисел в па­

мяти машины величины t

и

S

содержат операции, учитывающие

циклический перенос и присвоение знаков младшим частям.

Длягалгоритмов умножения система итераций (4,19)

повто-

ряетоя

k

раз, тогда

-

ka m - f e o

+

C

M

'

а

j

■

Ьунн

)

- Ь о

где

время выполнения одной итерации системы

(4 .1 9 );

GL -

число простых операций в одной итерации округле­

ния (4,20) или (4,21).

Если

округление исключить, то

£ у МН

«

k w ■to •

(4.27)

Если оиотема

(4,19) повторяется -§•(к+з> -1

раз?

то

Й и н

.

(4.28)

Таким образом, возможность изменения структуры алторатг

ма и его сложности позволяет разработать наборы алгоритмов,

конкретное использование которых будет зависеть от класса ре­

шаемых задач и определится процессом оптимизации.

В общем случае следует различать рассмотренный метод

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

ращения задачи,

так как для каждогв численного метода можно

получить множество отрунтур

с различию»! погрешностями. В то

же время каждая структура в

зависимости от кодов операций по-

зволяетпоотроить прогршшы о разлившей оложноотыз.

Весь процесс разработки набора алгоритмов представляется

в виде 3-х

уровней: