[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: