ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 24.10.2024
Просмотров: 97
Скачиваний: 1
- 114 -
разрядов в память машины, а содержимое |
- знаковых равря-j |
|
дев пврешюыв&в* в младше разряды сумматора. Операционная |
! |
|
часть прадотавхена на рио.4.3, а микропрограмма команды <Х ^ |
I |
|
- на рис^ 4 .4 . |
г |
|
Алгоритм сложения Щ чисел о |
к —значиой точностью |
|
будет» для l« k |
|
! |
<£ > © ^ к (J - 2,3,..,»»!)
*< 1 > Я г = Н £ « ^ ) к ,
длл U k - f , * 4 5,2. |
|
|
|
F ‘ 4 |
' |
|
|
<иЕ .>© Ф |С |
( 1 , 2 , ! . . , |
m ) |
|
||||
|
|
|
|
; |
|
|
( . . и ) |
для i » 1 |
|
|
% |
|
|
|
. |
< I > ® |
|
|
|
||||
< I > + |
Y i * |
|
|
|
|
||
|
|
|
r< |
4 |
|
|
|
Время сложения |
W |
чиоел о |
к -аначной точностью оа- |
||||
раделится ив выражения |
|
|
|
|
|
|
|
I * |
|
( m + i ) k ' t o . |
|
|
|
||
"Ьшн ~ |
|
|
(4.35) |
||||
Абсолютный выигрыш во времени |
|
|
|
||||
|
|
|
|
||||
д £ т |
|
|
= ( m- f ) З |
Н |
о |
„ |
|
* 2 k |
Cm-2) t o . |
|
|
|
i |
||
Относительный выигрыш |
|
|
|
|
|
|
|
|
- |
|
2 k ( m - 2 ) t o _ |
|
|
|
|
i * |
|
|
3K(m-<)to “ |
I V a m / - |
|||
График зависимости |
o tm |
|
от m |
предотавлен иа рио* 4.5, где |
|||
|
|
||||||
- П5 -
PrS п т
* 4 * |
1 2 * * * |
п- |
* 4 « М |
п |
( Ц ~ { ) |
||||
-----ТУ |
|
|
|
|
"ZT
У2 |
УО |
У4 |
Рио. |
4.3 |
|
Ряс. 4.4
1
- 116
k m j t m - U n i |
( l |
- |
£ - 0,,6)6 ( e-) . |
1 |
Покажем относительныйвыигрышв объеме программы. П ре-' |
|
|||
водя вооледевательное сложениечисел, получйы |
|
|||
dwi — 3 k ( / И - 0 * |
|
команд,1 |
|
|
Используя метод накопления суш , |
|
|
|
|
Относительный выигрыш в объеме памяти соотавия
5 d « « Д * О М - к ( м + о |
|
|
||
Отевда |
а к С т - 0 |
Aiс |
|
|
|
|
|
||
t i m $ c U |
=» tim |
2 К ~ |
т = l |
s 0, 66. |
м -*<* |
|
З к |
т |
|
|
|
ж |
|
|
Таким образом, при W —т 00 |
относительный выигрши в |
|||
•бьеме памяти составляет 66$. |
|
|
|
|
Если частичные суши членов ряда могут превышать едини |
||||
цу, то алгоритм (4.34) |
даот верный результат при условии, что |
|||
общий результат ве переполняет разрядную оетку, |
т.е. |
|||
- 117 -
(4.36)
Это обеспечивается введением специальной команды олокеаня, по
которой блокируется оигнал |
| |
о переполнения разрядной |
||||
ветки. Например, сложим 4 числа о удвоенной точностью. |
||||||
ф < * + |
0,1101 |
ип |
Ф<4= |
OO.IIOI |
в 00.1Щ |
|
фд.« + 0,1110 |
0101 |
Ф»4* |
OO.IIIO |
Ф и * |
00.0101 |
|
ф| ж + |
0,0001 |
оно |
% ,» |
00.0001 |
Ф и * |
00.0110 |
%• - |
ОДНО 0101 |
|
I I .0001 |
ф * - ОО.ЮИ |
||
г - + |
0,11100101 ( |
£ = 0 ). |
|
|
||
Алгоритм |
|
0 |
|
|
|
|
Ф и -+ Z |
|
|
|
|||
|
|
|
|
|
||
|
|
< £ > © |
Фи. |
|
|
|
|
|
< £ > © «Ям |
|
|
|
|
< £ > «= > ( Г Ч ^ а < £ > © ф / < Х > ф Ф м
< £ > © Ф * < £ > + ¥ * 4 < £ > - » ■ (
Проведен олокенио чисел ооглаоно алгоритму; 'fit ~ 0 0 ‘. 4 Ш
ФVax « О О. OtCI
©0 1 . 0 1 0 0
Ф»з * 0 0 . 0 1 1 0
Фо Г Ш 0
юн
ш
Lb
<X>*oo*ooli
<f44»0 0 . n 0 1
- |
118 - |
|
|
© |
O O . I I H |
|
|
Mil = oo. m o |
o |
t |
|
© |
о j . h |
||
o o . o o o i
oififO
=1 1 . 0001
oo:-H н
= oo.un.
В приведенном примере при сложении старших частей во
2-й и 3-й частичной сумме налицо переполнение, |
однако сигнал |
||
| = 1 |
блокируется, т .к , сложение осуществляется по специа |
||
льной команде. Четвертая частичная сумма есть |
старшая часть |
||
результата. |
Она не имеет переполнения и по команде обычного |
||
сложения машиной будет отработан сигнал |
| |
= О. |
|
Если в (4.30) условие (4.36) не всегда выполняется, то для олучая
сигнал |
jj |
о переполи един разрядной сетки |
аудет равен нулю. |
||||
|
Отсвда |
следует, что для правильного контроля переполне |
|||||
ния разрядной |
сетки, |
если может быть (4 .37), |
необходимо накап |
||||
ливать сумму ( |
W - |
I) |
чисел. При атом Р< |
т - 2 |
, а ^ |
||
выбирается из условия |
(4 .33). |
|
|
||||
|
Данный метод накопления суммы можно применить и для чи- |
||||||
оел *fj |
( j |
= |
1 , 2 , . . . , |
m ), где необходимо провести |
ряд сло |
||
жений и вычитаний. Введение специальных команд вычитания позволит свести время реализации к (4 .3 5 ).
Для прямых и обратных кодов представления чисел алгоритм накопления суммы будет сложнее, т .к . потребует учета сушарного циклического переноса и операции присвоения знака младшим чаотям.
- 119 -
4 . 4 , |
Алгоритмы вы числения линейных Функций |
||||
На практике часто приходится решать задачи, в состав ко |
|||||
торых входит линейная функция типа |
Л * Q &+ 6 |
. Такими |
|||
задачами могут быть задачи вычисления элементарных функций, |
|||||
представленных полиномами степени |
р |
, |
или различные многочле |
||
ны. Как правило, |
при вычислении на машине полиномы приводятся |
||||
к схеме Горнера, где линейная функция |
Л |
есть отдельный |
|||
участок, к которому обращается |
Р |
|
раз. |
|
|
Повышенная точность вычисления линейной функции может быть реализована алгоритмами умножения в отдельности. При этом время реализации линейной функции из (4.24) и (4.27) бу дет
га-£КуцН+-Ьсл ■■ k m ^ o t k t i o * k ( k m + E ) t o ^
Для уменьшения времени Ь я воспользуемся методом на копления суммы однозначных слов частичных произведений и соот
ветствующих олов коэффициента |
|
6 |
й |
, |
|
|
||
Перемножение длинных чисел |
и ofr даст |
к |
чао- |
|||||
тичных произведений . |
|
|
|
|
|
|
||
( с и г - ‘" Щ 2 ' ,н) - ( < » * W o г - <“ * -0 "+ |
(4.39) |
|
||||||
|
|
|
|
|
|
|
|
|
+ ( а з £ ) ( ^ ) Г |
^ > и | |
|
|
|
j* 1,2,...,к ) , |
|
||
при вложении которых получим произведение |
|
|
||||||
|
|
м |
|
|
|
|
|
|
|
|
П - 1 П |
. 2 |
- |
' " |
|
|
|
Для 'Р * |
1 , 2 , . . . , к |
аз |
(4.39) |
можно найти |
241-i |
|
||
олов частичных произведений. Отбрасывав олова, меньше, чем |
|
|||||||
2 Ч J |
, |
сложим однозначные олова частичных произ |
||||||
ведений я олова коэффициента |
6 |
|
Но методу накопления оуммы: |
|||||
для |
шеей |
|
|
|
|
|
|
|
+0-10... 0 0 =* Р(к+0+П(к+0 •4.40)