[A83] Re: Pythagorean's theorem
[Prev][Next][Index][Thread]
[A83] Re: Pythagorean's theorem
----- Original Message -----
From: "Matthew Marshall" <mmarshall@myrealbox.com>
To: <assembly-83@lists.ticalc.org>
Sent: Saturday, August 09, 2003 9:17 PM
Subject: [A83] Re: Pythagorean's theorem
> Thanks! However, right now speed is my utmost priority. I need to find the
> length of a line several hundred times per second. I currently have the
> code working great for 8-bit numbers, but I am still debugging the 16-bit
> stuff. I think that it will have to wait until tomorrow, unfortunately. I
> am not used to staying up this late. (10 o'clock is my normal bedtime... it
> is past eleven and I still have to shower.) Maybe I will post the code
> tomorrow and see what everyone thinks about it.
>
> MWM
Here is fast isqrt code producing one bit of result per iteration,
based on the binary version of longhand square-rooting. I had to
unroll the loop in order to fit into registers. After every step,
A contains the current square-root approximation, and BC contains
the square of A. A approaches the desired result from below.
I have to increment the original input by one and handle an input
of 65535 as a special case in order to get simple branching. There
is probably room for improvement, but I am tired and will stop here.
I have performed a reasonable amount of testing and the code seems
to be working fine.
-- Norbert
;; in: HL = x, x <= x < 65535
;; out: HL = isqrt(x) = trunc(sqrt(x))
isqrt:
LD A, H
AND A, L
CP A, 255 ; x = 65535 ?
JR Z, sqrtDone ; yup, result is 256
EX HL, DE ; DE = x
;; HL = newVal
;; DE = x
;; BC = oldVal
;; A = root
INC DE ; x + 1 (simplifies branching)
SUB A, A ; root = 0, clear CF
LD BC, 0 ; oldValue = 0
LD HL, 16384 ; newval = oldVal + ((2*root + 128) << 7)
SBC HL, DE ; newVal > x ?
JR NC, dontSet7; yup, don't set bit 7 of result
ADD HL, DE ; newVal
LD B, H ; oldVal = newVal
LD C, L ;
ADD A, 128 ; root += 128
dontSet7:
ADD A, 32 ; root + 32
LD H, 0
LD L, A ; HL = root + 32
SUB A, 32 ; root
ADD HL, HL ; 2*root + 64
ADD HL, HL ; (2*root+64) << 1
ADD HL, HL ; (2*root+64) << 2
ADD HL, HL ; (2*root+64) << 3
ADD HL, HL ; (2*root+64) << 4
ADD HL, HL ; (2*root+64) << 5
ADD HL, HL ; (2*root+64) << 6
ADD HL, BC ; newVal = oldVal + ((2*root + 64) << 6)
SBC HL, DE ; newVal > x ?
JR NC, dontSet6; yup, don't set bit 6 of result
ADD HL, DE ; newVal
LD B, H ; oldVal = newVal
LD C, L
ADD A, 64 ; root += 64
dontSet6:
ADD A, 16 ; root + 16
LD H, 0
LD L, A ; HL = root + 16
SUB A, 16 ; root
ADD HL, HL ; 2*root + 32
ADD HL, HL ; (2*root+32) << 1
ADD HL, HL ; (2*root+32) << 2
ADD HL, HL ; (2*root+32) << 3
ADD HL, HL ; (2*root+32) << 4
ADD HL, HL ; (2*root+32) << 5
ADD HL, BC ; newVal = oldVal + ((2*root+32) << 5)
SBC HL, DE ; newVal > x ?
JR NC, dontSet5; yup, don't set bit 5 of result
ADD HL, DE ; newVal
LD B, H ; oldVal = newVal
LD C, L
ADD A, 32 ; root += 32
dontSet5:
ADD A, 8 ; root + 8
LD H, 0
LD L, A ; HL = root + 8
SUB A, 8 ; root
ADD HL, HL ; 2*root+16
ADD HL, HL ; (2*root+16) << 1
ADD HL, HL ; (2*root+16) << 2
ADD HL, HL ; (2*root+16) << 3
ADD HL, HL ; (2*root+16) << 4
ADD HL, BC ; newVal = oldVal + ((2*root+16) << 4)
SBC HL, DE ; newVal > x ?
JR NC, dontSet4; yup, don't set bit 4 of result
ADD HL, DE ; newVal
LD B, H ; oldVal = newVal
LD C, L
ADD A, 16 ; root += 16
dontSet4:
ADD A, 4 ; root + 4
LD H, 0
LD L, A ; HL = root + 4
SUB A, 4 ; root
ADD HL, HL ; 2*root+8
ADD HL, HL ; (2*root+8) << 1
ADD HL, HL ; (2*root+8) << 2
ADD HL, HL ; (2*root+8) << 3
ADD HL, BC ; newVal = oldVal + ((2*root+8) << 3)
SBC HL, DE ; newVal > x ?
JR NC, dontSet3; yup, don't set bit 3 of result
ADD HL, DE ; newVal
LD B, H ; oldVal = newVal
LD C, L
ADD A, 8 ; root += 8
dontSet3:
ADD A, 2 ; root + 2
LD H, 0
LD L, A ; HL = root + 2
SUB A, 2 ; root
ADD HL, HL ; 2*root+4
ADD HL, HL ; (2*root+4) << 1
ADD HL, HL ; (2*root+4) << 2
ADD HL, BC ; newVal = oldVal + ((2*root+4) << 2)
SBC HL, DE ; newVal > x ?
JR NC, dontSet2; yup, don't set bit 2 of result
ADD HL, DE ; newVal
LD B, H ; oldVal = newVal
LD C, L
ADD A, 4 ; root += 4
dontSet2:
LD H, 0 ;
LD L, A ; HL = root
INC HL ; root+1
ADD HL, HL ; 2*root+2
ADD HL, HL ; (2*root+2) << 1
ADD HL, BC ; newVal = oldVal + ((2*root+2) << 1)
SBC HL, DE ; newVal > x ?
JR NC, dontSet1; yup, don't set bit 1 of result
ADD HL, DE ; newVal
LD B, H ; oldVal = newVal
LD C, L
ADD A, 2 ; root += 2
dontSet1:
LD H, 0 ;
LD L, A ; HL = root
ADD HL, HL ; 2*root
INC HL ; 2*root+1
ADD HL, BC ; newVal = oldVal + (2*root+1)
SBC HL, DE ; CF = newVal <= x
ADC A, 0 ; root += (newVal <= x)? 1 : 0
sqrtDone:
LD H, 0
LD L, A ; HL = A = isqrt(x)
References: