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

-

юз -

Здесь ЧЬ-ЧГ

реализуется поеледав ат ельностью (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

имеем