SQR & LOG Algorithms

Thursday 29 Mar 2001, at 15:54:09,
Pawel Kislyak -> All:

PK> Looking for quick subjects (algorithms for calculating the square root
PK> and the decimal logarithm) in assembler, you can also use the algorithm
PK> for exponentiation of a number and the normal algorithm generation
PK> random numbers.

╒═══< Begin file: mat .asm >══════════
*area : CODE.ZX
*from : Aleksey Malov
*to : All
*subj : Mathematical procedures.
*date : 04-04-00
*time : 01:03:19

Greetings, All!

So, procedure number 1: rapid division 16/16. Anyone who can
accelerate it
can have a monument erected during his lifetime (at his expense). Acceleration by
replacing
jr with jp is not considered, because gain/loss in speed depends
on the size of the arguments.

At the input:
de-dividend
bc-divisor
At the output:
de-quotient
hl-remainder

divide ld a,b ;change
cpl ;
ld b,a ;sign
ld a,c ;
cpl ;у
ld c,a ;
inc bc ;divisor t=30

ld hl,0 ;reset new dividend
ld a,d ;move first
rla ;high byte of dividend
;t=18
rl l ;┐
add hl,bc ;│
jr c,$+4 ;│8 times
sbc hl,bc ;│
rla ;┘ t=8*45=360

ldd,a ;st. result byte
ld a,e ;now move
rla ;low byte t=12

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

ld e,a ;ml. result byte
;hl-remainder of division
;t=4

Total:
30+18+360+12+416+4=840 cycles.

If the remainder is not needed, then the end of the procedure should look like this:

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

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

Total:
30+18+360+12+364+34=818 cycles.

P.S. If you divide by zero, then, as you would expect, the quotient will be equal to zero, and the remainder will be equal to the dividend, i.e. in this regard, the procedure
has no glitches.
;********************************

Procedure number 2: extracting the square root of a register pair. Here
here
we really need to erect a monument to someone who will speed up the procedure at least
by 1 clock cycle. Acceleration by replacing jr with jp is not considered, because
gain/loss
in speed depends on the value of the argument.

At the input:
hl-number from which you need to extract
square root
output:
a-square root of hl

sqrhl xor a ;zeroed a;-)
ld de,64 ;this is required by the algorithm
; t=14

sla h ;take the two leftmost
adc a,a ;argument bits
sla h ;
adc a,a ;
jr z,$+4 ;if they are not equal
dec a ;then increase
inc d ;result
; t=39

sla h ;┐next we follow
adc a,a ;│the algorithm for extracting
sla h ;│square root
adc a,a ;│ "column", only
sla d ;│
ld c,d ;│3 times
sli c ;│
cp c ;│
jr c,$+4 ;│
sub c ;│
inc d ;┘ t=63*3=189

sla l ;┐do a similar
adc a,a ;│operation with
sla l ;│low byte
adc a,a ;│argument
sla d ;│
ld c,d ;│2 times
sli c ;│
cp c ;│
jr c,$+4 ;│
sub c ;│
inc d ;┘ t=63*2=126

ld h,a ;
or a ;reset the carry flag
; t=8

sbc hl,de ;now we are missing
jr nc,$+3 ;one register d for
add hl,de ;performing the last
ccf ;two cycles, we will have
rl d ;use more
add hl,hl ;slow operations
add hl,hl ;with register pairs
; t=67

sbc hl,de ;and last time
ccf ;perform calculations without
ld a,d ;restoring hl
adc a,a ;in a-result
; t=27

Total:
14+39+189+126+8+67+27=470 clock cycles.

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

Procedure number 3: extracting the square root of a three-byte number.
Acceleration
by replacing jr with jp is not considered, because gain/loss in speed
depends
on the value of the argument.

At the input:
dhl=d*65536+hl - the number itself
At the output:
hl - the same square root

sqrdhl xor a ;beginning of the procedure
ld bc,64 ;almost similar
;previous
; 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 times
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 times
sli e ;│
cp e ;│
jr c,$+4 ;│
sub e;│
inc b ;┘ t=63*2=126

ld d,l ;
ld l,h ;
ld h,a ;change registers
or a ; t=16

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

ld l,h ;there is a suspicion that
ld h,0 ;this block and the previous one
ld c,b ;you can speed it up a little
ld b,h ;
rl h ;
ld a,d ; t=31

rla ;┐and I
adc hl,hl;│don’t like this block.
rla ;│it is very likely that
adc hl,hl;│it can be well
sla c ;│accelerated. But how?
rl b ;│
ld d,b ;│
ld e c ;│3 times
sli e ;│
rl d ;│
sbc hl,de;│
jr nc,$+4;│
add hl,de;│
dec c ;│
inc c ;┘ t=3*119=357 (!)
;horror! Think about how to
;speed up!

rla ;this block is similar
adc hl,hl;to the previous one with
rla ;a small difference
adc hl,hl;at the end. This was done
ld d,b ;for the sake of increasing
ld e,c ;computation speed
sla e ;
rl d ;
sli e ;
rl d ;
sbc hl,de;
ccf ; t=97

ld h,b ;
ld l,c ;
adc hl,hl;v hl - result
; t=23

The result:
14+39+189+126+16+134+31+357+97+23=1026.

I wish you health, happiness and creative Uzbeks. Croft 4.50.
* * Source: (c) Vivid/BW^XPJ. (500:8362/1.3)
╘═══< End file: mat .a >════════════

Nice connections Pawel...