Программирование вычислительных алгоритмов

Кто подскажет как написать программу на АС-ме для воспроизведения, например, полинома 5-й степени используя фиксированную запятую (8, 16, 32 разряда)?

 

используя поразрядное суммирование и умножение.

 

Спасибо!
Как применить Ваш совет к примеру: y= ax^5 - b*x^3 + x при следующих значениях
a= 120,
b= 6,
c=1
{x} = -2...+2 ?

 

для 4 можно на SSE

Код (Text):

1. movaps  xmm0,dqword[xxxx]    ;x,1,1,1
2. movaps  xmm1,xmm0
3. shufps  xmm1,xmm1,11110000b
4. mulps   xmm0,xmm1            ;x^2,x,1,1
5. shufps  xmm1,xmm1,11111100b
6. mulps   xmm0,xmm1            ;x^3,x^2,x,1
7. shufps  xmm1,xmm1,11111111b
8. mulps   xmm0,xmm1            ;x^4,x^3,x^2,x
9. mulps   xmm0,dqword[abcd]    ;dx^4,cx^3,bx^2,ax
10. movhlps xmm1,xmm0
11. addps   xmm0,xmm1            ;dx^4+bx^2,cx^3+ax
12. movaps  xmm1,xmm0
13. shufps  xmm0,xmm0,1
14. addss   xmm0,xmm1            ;dx^4+bx^2+cx^3+ax
15. -//-
16. align 16
17. abcd dd 0.7,0.9,0.4,0.1      ;коэффиценты
18. xxxx dd 1.0,1.0,1.0,2.0      ;x=2

Добавлено:
C фиксированой запятой не знаю может MMX или SSE2. Но в любом случае для 5 степени нужна высокая точность желательно поболее 32 (если x не целое в диапазоне [-2;2]).

 

Весь фокус в том, чтобы с фиксированной запятой!
Нет сложности на FPU, но не тот "коленкор"!

 

Еще более сложнее и интереснее если:
a=1/120,
b=1/6,
c=1!

 

Господа!
Дайте ваши комментарии на мое решение мною же поставленной задачи.
Исходное уравнение
у= 120*х^5 - 6*х^3 + x
при изменении аргумента от -2 до +2.
Решение.
Исходное уравнение преобразовал по схеме Горнера:
у=х*((6*х^2)*((20*х^2)-1)+1)
Арифметический алгоритм:
у1=х*х
у2=20*у1
у3=у2-1
у4=6*у1
у5=у3*у4
у6=у5+1
у7=у=у6*х.
Умножение на 20 и 6 выполнял не с помощью команды imul, а методом
сдвига и сложения. Шаг изменения аргумента взял равным 0,125.
Основное тело программы:
mov ax,x
imul ax
mov cx,dx ;cx->(x^2)*(2^-)2
shld dx,ax,2
mov bx,dx ;dx->x^2=y1
;----------------------------
add cx,dx ;cx->20*x^2=y2
;-----------------------------
sub cx,100h ;cx->(20*x^2-1)=y3
;---------------------------------
mov ax,bx
sar bx,1
add ax,bx ;ax->(6*x^2)=y4
;--------------------------------
imul cx
shld dx,ax,2 ;dx->y5=y4*y3
;-------------------------------
add dx,10h ;dx->y6=y5+1
;--------------------------------
mov ax,x
imul dx
shld dx,ax,2 ;dx->y6*x=y
mov y,dx
Программа написана для MS DOS (для ускорения ускорения отладки).
Наибольшая абсолютная ошибка вычисления составила 0,1640625, при наибольшем значении полинома 3794, математиическое ожидание погрешности - 0,041666667, дисперсия - 0,003430752
Готов ответить на любые вопросы по программе и методу реализации вычислений.
Нетрудно подсчитать объем ОЗУ, который требует эта программа, и число тактав
на ее исполнение. Согласен,что есть недостатки в стилистике, алгоритмизации,
в программипрвании. Вся работа над программой заняла 2 часа.
Жду ваши комментарии и вопросы, господа!

 

Насчёт мат. части х.з.

Если хочешь увеличить быстродействие замени shld на

Код (Text):

1. SHR REG2, 30
2. LEA REG1, [REG1*4 + REG2]

Можно и на MMX (SSE2) переписать

 

По мат. части :

Это НЕ схема Горнера. =) Это схема имени тебя.

 

чтото я не пойму, то 8,16,32 разряда, то ограничиваемся шагом 0,125 изменения значения аргумента, почему не 1e-32?

насколько отладчик под ДОС ускоряет ускоряет процесс отладки? и как он это делает?

 

Уважаемый murder!
Спасибо за ответ!.
1. Теоретически, судя по описаниям процессоров, команды SHR и SHLD выполняются одинаково и за одно и тоже время, практически - я специально не проверял.
2. Бесусловно представляет интерес написать программу, реализующую этот алгоритм с
использованием технологии ММХ!
3. Я не силен в сленге Асс-щиков, но что означает Х.З.! Надеюсь не совсем плохое?!
Жду еще вопросов, с уважением, 1212.

Уважаемый Forever!
Вы наверное математик! Очень приятно, ведь не часто встречаются на подобных форумах профессионалы в нескольких областях! Прошу простить, это действительно не схема Горнера, а лишь только начальная стадия преобразования полинома, которую предложил Горнер для нахождения корней полинома!
Желаю Вам успехов на избранном поприще!
Жду еще вопросов, с уважением, 1212.

Уважаемый Freeman!
Спасибо за вопросы. Если есть вопросы, следовательно я не был понят. Все беды на Земле не от того, что люди злы и вредные, а от того, что мы друг-друга не понимаем!(Это я цитировал кого-то)/
1. Программа специально написана для 16-ти разрядной машины с представлением данных в форме с фиксированной запятой. (См. начало диалога по теме). Предложения о FPU менее интересны. Дело в том, что иногда приходится применять для реализации вычислительных алгоритмов процессоры, не имеющие формат плавающей запятой (например процессоры Blacfin фирмы Analog Devices). Нет смысла стрелять по
воробьям ракетами типа земля-земля. Можно проектировать программы для вычислительных алгоритмов использую фиксированную запятую. Такие программы обеспечат требуюмую точность, но будут исполняться быстрее, при этом занимая в ОЗУ гораздо меньше объема!
2. Если в предложенной программе заменить во всех регистрах Х на h или l, (разумеется поменяв определения для переменных), то программа будет работоспособна для байтовых переменных. точность будет хуже. По моей оценке наибольшая ошибка будет 70-100, при том же наибольшем значении полинома. Если ко всем РОНам в программе приписать букву Е, то программа будет обрабатывать данные 32-х разрядные. Точность повысится примерно в 5000 раз. Шаг изменения аргумента взят 0,125, Вы совершенно правы, с потолка. При этом шаге число точек вычислений полинома будет 33, что достаточно для
построения графика в EXEL. Вы совершенно правильно заметели, что шаг кратен целой степени двойки. Это резко повышает точность!
3. Говоря о повышении производительности при написании программы для MS DOS, я имел в виду себя лично и мое конкретное рабочее место с моим лично инструментарием. Не более!
Жду еще вопросов, с уважением, 1212.

 

не ожтдал от вас столь развернутого ответа

дык это всемирно извесное выражение.. х. знает

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

для реализации применяецо мозг и компилятор. процессор лишь выполняет прогу.

довольно серъезный проц. можно под него и земля-земля накодеть

нудык мы не экстрасенсы

 

1212
На процессорах AMD инструкция shld декодируется программно (т.н. VectorPath) и за такт может быть декодирована только одна такая инструкция. Аппаратно декодируемые инструкции (т.н. DirectPath) могут быть декодированы в количестве 3 штук за такт. Кроме того shr и lea выполняются в разных модулях обработки т.е. параллельно.

В AMD Athlon Processor x86 Code Optimization Guide есть оддельная тема про shld.

Тогда MMX, а также 32-битный lea и инфа о shld не актуальны.

 

Вот.. сделали бесплатно лабу человеку ))

 

deLight вы не правы

 

ну так скучно когда кто-то всегда прав... =)

1212
>Дело в том, что иногда приходится применять для реализации вычислительных алгоритмов процессоры, не имеющие формат плавающей запятой (например процессоры Blacfin фирмы Analog Devices)

а где это используется, если не секрет?

 

Видимо для автоматизации производственных процессов.

 

Уважаемые Ассемблерщики!
Для того, чтобы проблема была более понятной, (а все беды на Земле из-за непонимания друг друга) приведу конкретные цифры.
Если приведенный арифметический алгоритм реализовать «в лоб», без команды SHLD после каждой операции умножения, то будем иметь следующий результат:
наш полином пятого порядка имеет наибольшие значения (3794) на краях интервала изменения аргумента, т.е. при Х=+2 или – 2. Наибольший машинный Х -> 4000h, т.е. полностью использует разрядную сетку ЦВМ. При таком машинном аргументе программа написанная «в лоб» дает машинное значение полинома 0007H. Заметьте, это наибольшее значение полинома. Программа, написанная с использованием команды SHLD после каждой операции умножения, дает машинное значение полинома 7690H. Т.е. наибольшее значение полинома полностью использует информационную часть разрядной сетки процессора (не имеет балластом 12 старших информационных битов). Вывод: применение SHLD в предложенном варианте реализации вычислительного алгоритма повышает точность в 4096 раз!
Я акцентирую ваше внимание на один из возможных СПОСООВ ПОЛУЧЕНИЯ НАИБОЛЬШЕЙ ТОЧНОСТИ при реализации вычислительных алгоритмов на ассемблере!
Когда разработчики промышленных систем не имели возможность использовать импортные процессоры, то очень часто использовались 1810ВМ86. Этот процессор не имеет команду SHLD. Тогда мы применяли такую конструкцию для повышения точности команды умножения
Mov ax,x
Mov bx,ax
Imul bx
Sar dx, 1 ; повышение точности при одном разряде запаса по точности,
Sar ax, 1 ; если запас по точности в два разряда, то конструкцию
Adc dx,0 ; повторяют еще раз
В этом смысле SHLD лишь механизм для улучшения качества выполнения операции умножения.
Уважаемый murder, спасибо за высокопрофессиональный совет! Я этого не знал. Учту на будущее. Вы совершенно правы показывая всем, что ассембреристы должны очень хорошо знать аппаратную часть процессора, для которого пишут программы на языке низкого уровня!
Более интересной и практически значимой будет вторая задача:
Y= X - X^3/6 + X^5/120 при том же диапазоне изменения аргумента. Наверное многие вспомнили, что этот полином – три первых члена разложения в ряд Маклорена SIN(X). Если пытаться новый полином реализовать «в лоб» путем применения операции деления получим У=Х (проверьте!)
Если 1/6 и 1/120 заменить на соответствующие вычисленные коэффициенты, то эти коэффициенты будут периодическими дробями, т.е неточными, да прибавится погрешность при переводе этих коэффициентов в двоичную систему. Конечная дробь в одной системе счисления не обязательно будет конечной дробью в двоичной системе. Так конечная в десятичной системе дробь 0,8 есть периодическая дробь 0,(110) в двоичной.
Кто знает как решить задачу вычисления синуса по вышеприведенной формуле для 16-ти разрядных ЦВМ? Оптимальное решение этой задачи должно давать погрешность не хуже 0,1 процента. Это очень высокая точность. Разумеется, 32-х разрядные ЦВМ дадут значительно лучшую точность.
Ответ на вопрос а где это применяется – практически вами дан. В системах автоматизации производственных процессов! При этом будем под «это» понимать умение реализовывать вычислительные алгоритмы с предельной для используемой разрядности точностью. Стрельба из «земля-земля» (см. выше) – то же производственный процесс. Более конкретнее – системы управления подвижными объектами, роботами. Системы обработки радиолокационных сигналов.
Уважаемый delight если эта маленькая программка поможет Вам в лабораторных работах, то это очень прекрасно! Разберитесь в поставленных проблемах и методах их решения досконально и Вы сможете самостоятельно защитить лабораторку. Успехов Вам!
Жду ваших вопросов, коллеги!
С уважением, 1212

 

1212
Ну вот нашёл демку. Может пригодится.

Код (Text):

1. org 100h
2. mov al,13h
3. int 10h
4. push word 09000h
5. pop ds
6. xor si,si
7. mov di,395
8. Singen:mov [si],ch
9.        add cx,di
10.        mov ax,40
11.        imul cx
12.        sub di,dx
13.        inc si
14. jnz Singen
15. push word 0A000h
16. pop es
17. xchg ax,dx
18. aloop:xor di,di
19.       mov bl,200
20.       yloop:mov cx,320
21.             xloop:mov al,[bx]
22.                   mov si,cx
23.                   add al,[si]
24.                   add si,dx
25.                   add al,[si]
26.                   and al,dh
27.                   stosb
28.             loop xloop
29.             dec bl
30.       jnz yloop
31.       inc dx
32. jmp aloop