Алгоритмы SQR & LOG

Привет, Pawel!

Четверг 29 Мар 2001, в 15:54:09,
Pawel Kislyak -> All:

PK> Ищутся быстрые сабж (алгоритмы вычисления квадратного корня
PK> и десятичного логарифма) в ассемблере, можно еще и алгоритм
PK> возведения в степень числа и нормальный алгоритм генерации
PK> случайных чисел.

╒═══< Begin file: mat .asm >══════════
*area : CODE.ZX
*from : Aleksey Malov
*to : All
*subj : Математические процедуры.
*date : 04-04-00
*time : 01:03:19

Приветствую тебя, All!

Итак, процедура номер 1: быстрое деление 16/16. Тому, кто сможет ее
ускорить,
можно будет памятник при жизни поставить (за его счет). Ускорение путем
замены
jr на jp не рассматривается, т.к. выигрыш/ проигрыш в скорости зависит
от величины аргументов.

Hа входе:
de-делимое
bc-делитель
Hа выходе:
de-частное
hl-остаток

divide ld a,b ;меняем
cpl ;
ld b,a ;знак
ld a,c ;
cpl ;у
ld c,a ;
inc bc ;делителя t=30

ld hl,0 ;обнулили новое делимое
ld a,d ;сначала двигаем
rla ;старший байт делимого
;t=18
rl l ;┐
add hl,bc ;│
jr c,$+4 ;│8 раз
sbc hl,bc ;│
rla ;┘ t=8*45=360

ld d,a ;ст. байт результата
ld a,e ;теперь двигаем
rla ;младший байт t=12

adc hl,hl ;┐
add hl,bc ;│
jr c,$+4 ;│8 раз
sbc hl,bc ;│
rla ;┘ t=8*52=416

ld e,a ;мл. байт результата
;hl-остаток от деления
;t=4

Итого:
30+18+360+12+416+4=840 тактов.

Если остаток не нужен, то конец проце-
дуры должен выглядеть так:

adc hl,hl ;┐
add hl,bc ;│
jr c,$+4 ;│7 раз
sbc hl,bc ;│
rla ;┘ t=7*52=364

adc hl,hl ;
add hl,bc ;
rla ;
ld e,a ; t=34

Итого:
30+18+360+12+364+34=818 тактов.

P.S. Если будете делить на ноль, то, как и следовало ожидать, частное
будет
равно нулю, а остаток - делимому, т.е. в этом плане у процедуры глюков
нет.
;***********************

Процедура номер 2: извлечение квадратного корня из регистровой пары. Вот
тут
уж действительно надо памятник поставить тому, кто ускорит процедуру хотя
бы на 1 такт. Ускорение путем замены jr на jp не рассматривается, т.к.
выигрыш/проиг
в скорости зависит от величины аргумента.

Hа входе:
hl-число из которого необходимо извлечь
квадратный корень
на выходе:
a-квадратный корень из hl

sqrhl xor a ;обнулили a ;-)
ld de,64 ;этого требует алгоритм
; t=14

sla h ;берем два самых левых
adc a,a ;бита аргумента
sla h ;
adc a,a ;
jr z,$+4 ;если они не равны
dec a ;нулю, то увеличиваем
inc d ;результат
; t=39

sla h ;┐далее следуем
adc a,a ;│алгоритму извлечения
sla h ;│квадратного корня
adc a,a ;│"столбиком", только
sla d ;│
ld c,d ;│3 раза
sli c ;│
cp c ;│
jr c,$+4 ;│
sub c ;│
inc d ;┘ t=63*3=189

sla l ;┐проделываем похожую
adc a,a ;│операцию с
sla l ;│младшим байтом
adc a,a ;│аргумента
sla d ;│
ld c,d ;│2 раза
sli c ;│
cp c ;│
jr c,$+4 ;│
sub c ;│
inc d ;┘ t=63*2=126

ld h,a ;
or a ;обнулили флаг переноса
; t=8

sbc hl,de ;теперь нам не хватает
jr nc,$+3 ;одного регистра d для
add hl,de ;выполнения последних
ccf ;двух циклов, придется
rl d ;использовать более
add hl,hl ;медленные операции
add hl,hl ;с регистровыми парами
; t=67

sbc hl,de ;и последний раз
ccf ;выполняем расчеты, не
ld a,d ;восстанавливая hl
adc a,a ;в a-результат
; t=27

Итого:
14+39+189+126+8+67+27=470 тактов.

------------------------------------------

Процедура номер 3: извлечение квадратного корня из трехбайтового числа.
Ускорение
путм замены jr на jp не рассматривается, т.к. выигрыш/проигрыш в скорости
зависит
от величины аргумента.

Hа входе:
dhl=d*65536+hl - само число
Hа выходе:
hl - тот самый квадратный корень

sqrdhl xor a ;начало процедуры
ld bc,64 ;практически аналогично
;предыдущей
; t=14

sla d ;
adc a,a ;
sla d ;
adc a,a ; t=39
jr z,$+4 ;
dec a ;
inc b ;

sla d ;┐
adc a,a ;│
sla d ;│
adc a,a ;│
sla b ;│
ld e,b ;│3 раза
sli e ;│
cp e ;│
jr c,$+4 ;│
sub e ;│
inc b ;┘ t=3*63=189

sla h ;┐
adc a,a ;│
sla h ;│
adc a,a ;│
sla b ;│
ld e,b ;│2 раза
sli e ;│
cp e ;│
jr c,$+4 ;│
sub e ;│
inc b ;┘ t=63*2=126

ld d,l ;
ld l,h ;
ld h,a ;меняем регистры
or a ; t=16

sbc hl,bc;┐
jr nc,$+3;│
add hl,bc;│
ccf ;│2 раза
rl b ;│
add hl,hl;│
add hl,hl;┘ t=67*2=134

ld l,h ;есть подозрение, что
ld h,0 ;этот блок и предыдущий
ld c,b ;можно немного ускорить
ld b,h ;
rl h ;
ld a,d ; t=31

rla ;┐да и этот блок мне
adc hl,hl;│не нравится.
rla ;│очень вероятно, что
adc hl,hl;│его можно неплохо
sla c ;│ускорить. Hо как?
rl b ;│
ld d,b ;│
ld e c ;│3 раза
sli e ;│
rl d ;│
sbc hl,de;│
jr nc,$+4;│
add hl,de;│
dec c ;│
inc c ;┘ t=3*119=357 (!)
;ужас! Думайте, как
;ускорить!

rla ;этот блок аналогичен
adc hl,hl;предыдущему с
rla ;небольшой разницей
adc hl,hl;в конце. Это сделано
ld d,b ;ради повышения
ld e,c ;скорости вычислений
sla e ;
rl d ;
sli e ;
rl d ;
sbc hl,de;
ccf ; t=97

ld h,b ;
ld l,c ;
adc hl,hl;в hl - результат
; t=23

Итого:
14+39+189+126+16+134+31+357+97+23=1026.

Желаю вам здоровья, счастья и творческих узбеков.
Aleksey Malov aka VIVID/Brainwave.

*--- Cuming soon Lara Croft 4.50.
* * Origin: (c) Vivid/BW^XPJ. (500:8362/1.3)
╘═══< End file: mat .a >════════════

Приятных коннектов Pawel...