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

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 24.10.2024

Просмотров: 99

Скачиваний: 1

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

-» 108 -

<£>®ьчг

(4.23)

для с и

ч»*—» * ;

 

 

 

 

< £ > © i 4 /,

 

 

 

 

< Т > ~ * Q i+ Y h .

 

 

|ЭДеоь

© г -

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

р н

; |

:

© Г -

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

ра.

 

>

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

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

["67]

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

тивным кодом, улучшающим параметры d mi. , есть код, реализу­ ющий в оистеые (4.19) операции умножения и сложения (умножение

снакоплением).

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

Изменение структуры в зависимости от требуемой степени точнос­ ти значительно влияет на показатели объема программ и быстро­ действия алгоритма,

 

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

(

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-х

уровней:

 

 

 

 

 

 

 

 

 

— но -

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

4.3. Алгоритмы типа накопления

В данном параграфе рассматривается вопрос проектиро­ вания эффективных алгоритмов для случая многократного сложе­ ния нескольких чисел или образована i оушы отдельных одно­ значных слов слагаемых для' дополнительных чодов представле­ ния чисел в памяти машины. Однако общие принципы проектиро­ вания могут быть распространены и яа алгоритмы накопления оумыу для прямого и обратного кодов представления чисел.

Сложение 2-х чисел с повышенной точностью требует про­ граммной реализации итерационной последовательности (4.12). 1При этом число команд, реализующих одну итерацию, может быть 1различно я зависит от выбранной структуры команд. Условимся,;

'что действие одной команды програшы связано о однтм обраще­ нием к памяти машины. Тогда минимальная програша сложения 2-х однозначных слов не может быть меньше 3-х команд. Приме­ рами таких щюграиы явяяютоя (4.22) и (4.23), где, соглас­

но (4.24)* Ь * 3 и

 

 

 

 

t

c 3A k

t

o “

•

Для сложения трех чисел с к -значной точностью н е - ’ обходимо два рава обратиться к программе сложения 2-х чи-

 

 

 

 

-

Ill -

 

 

 

 

 

сел,

тогда

 

 

 

 

 

 

 

 

 

 

 

 

-Ьса -

2 '3

к to

•

 

 

 

 

 

Очевидно, что при сложении

Ш

чисел

 

 

 

 

 

 

ir a = ( m - i ) 3 k i o .

(4.29)

 

 

 

 

 

 

 

 

 

 

 

 

Преобразуй алгоритм

(4 .12),

последовательно

примененный

(

пЫ

) раз для сложения

 

m

чисел, к виду-

 

 

 

 

 

 

 

 

 

 

 

(4.30)

 

 

 

(

t - k , k - i , ... , 2 ,

i

)

 

 

 

 

 

где

P i и p i-и -

значение переноса от сложения ( t+I)

и

ь - х

слов

соответственно, при атом

(U * M - i

,

 

 

для

Рассмотрим возможную реализацию такого вида алгоритма

 

 

 

 

 

 

 

 

 

 

 

 

Пусть

Ш s 4 . Для реализации

(4.S3)

введем команда

 

следующего содержания:

 

 

 

 

 

 

 

 

 

I.

Специальное оложение (уоловное обозначение

 

По этой команде происходит сложение 2-х чисел по всем прави­

лам сложения чиоел в модифицированном дополнительном коде.

 

Сигнал о переполнении разрядной сетки блокируется.

 

 

 

2 . специальная запись

(условное обозначение

©

),

Операционное устройство и микропрограмма специальной запиои

 

приведены соответственно на рис.

4 .1 . и рио.

4 .2 .

 

 

 

Пооледоаательнс сложим однозначные слова 4-х

слагаемых,

используя команду опециального' оложешя. Как показано ниве, на

примере q o .I

I I .

« . X I

I I

О 0 .1

I1 . . . I I

I t

О 0,1

I I

. * . I I

I I

0 0 .1

II . . . I I

I I

1 I. II I . . . I I

о о . ’ ,

сложение 4-х макоимальинх по величине слов дает 3 единицы пе­ реноса, которые зафиксируются в знаковых разрядах.

- 112 -

 

а

Рио* 4,2

 

Применяя к полученной сумме команд;,

специальной записи

( \\—

), перепишем единицы перенооа из

знаковых разрядов

в младшие разряды сумматора. Очевидно, что последующее сложе­

ние данного переноса со словами (

Ь-х) 4.-х слагаемых может

 

также дать не больше, чем 3 единицы переноса, которые также

 

зафиксируются в

знаковых разрядах.

Продолжая таким образом

 

последовательное

сложение однозначных слов от l * k до

,

запишем алгоритм получения

%

:

 

для

о - к

имеем

i*

 

 

 

 

 

< £ > © % к

 

 

 

L - K - i

 

< £ > К = Ф <.*•+#*+¥,♦¥«■)* ;

 

ДЛЯ

,

К -2

з , 2

 

 

< 1 > © * Р Н

< 1 > |* = м « е ,+ < г г + & 4 * 4) .

 

 

 

 

 

 

 

 

 

 

 

 

 

(4.31)

для

L ж I

 

 

< т у © ч > «

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

< 5 > © < Р м

 

 

 

 

 

 

 

 

 

 

 

< £ > Ф ¥ и

 

 

 

 

 

 

 

 

 

 

 

< S > © V * i

 

 

 

 

 

 

 

 

 

 

 

< 1 > - К « |+ & + < Ь + * 4 ) < .

 

 

 

Сравним показатели -fc

для алгоритмов (4.22),

(4.23)

и алгоритма

(4 .31).

Йз

(4.31) следует,

что для олокения 4-х

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

сложения 4-х чноел о

 

к -значной точностью при использования,

метода накопления суммы

 

 

 

 

 

 

 

 

 

 

 

 

^ 4« - 5 k 4 e .

 

 

 

 

(4. 32)

Для

 

б*

согласно

(4 .29),

получим

 

 

 

 

 

 

 

 

 

 

 

«

4-

5( (‘ 6i

)

o

54t

o =

 

.

 

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

(4.31)

из (4.32)

 

 

 

 

 

 

 

 

 

 

 

 

 

= 3 0 1с

 

 

 

 

Абсолютный выигрыш во времени

Д t

ж2 А Ьо f что при­

мерно составляет

44,4$.

 

 

 

 

 

 

 

т >А

 

В общем случае,

если требуется накопить сумму

чисел,

необходимо ввести Ц знаковых разрядов для фиксиро­

вания

(

ж - I )

возможных переносов»

При этом

CJ.

внбираетоя

из условия

 

 

 

 

2 %.

 

 

 

 

 

 

 

 

 

 

iV < <

№ 4

 

 

 

 

(4.33)

 

 

 

 

 

 

 

 

 

 

 

 

Здесь вводятся специальная команда засылки по

 

-знаковым"

разрядам

(

==>

),

которая ооущеотвляет'запиоь цифровнх

Смотрите также файлы