[A83] Yet another integer square root routine (was: Pythagorean's theor
[Prev][Next][Index][Thread]
[A83] Yet another integer square root routine (was: Pythagorean's theorem)
This routine one is pretty much the same size as the one I
posted previously, but the maximum execution time has been
reduced from about 980 Tstates to about 780 Tstates.
-- Norbert
;; in: HL = x, 0 <= x < 65536
;; out: HL = isqrt(x) = trunc(sqrt(x))
isqrt:
EX DE, HL
LD BC, 0 ; xroot = 0
;; DE = x
;; BC = xroot
LD HL, 16384 ; 1 << 14
ADD HL, BC ; x2 = xroot + (1 << 14)
SRL B
RR C ; xroot >>= 1
EX HL, DE ; HL = x, DE = x2
SBC HL, DE ; x -= x2
JR C, dontSet7 ; if x < x2, don't set bit 7
LD A, 64 ;
ADD A, B ;
LD B, A ; xroot += (1 << 14)
JR bit7Done
dontSet7:
ADD HL, DE ; x += x2
bit7Done:
EX HL, DE ; DE = x
LD HL, 4096 ; (1 << 12)
ADD HL, BC ; x2 = xroot + (1 << 12)
SRL B
RR C ; xroot >>= 1
EX HL, DE ; HL = x, DE = x2
SBC HL, DE ; x -= x2
JR C, dontSet6 ; if x < x2, don't set bit 6
LD A, 16 ;
ADD A, B ;
LD B, A ; xroot += (1 << 12)
JR bit6Done
dontSet6:
ADD HL, DE ; x += x2
bit6Done:
EX HL, DE ; DE = x
LD HL, 1024 ; 1 << 10
ADD HL, BC ; x2 = xroot + (1 << 10)
SRL B
RR C ; xroot >>= 1
EX HL, DE ; HL = x, DE = x2
SBC HL, DE ; x -= x2
JR C, dontSet5 ; if x < x2, don't set bit 5
LD A, 4 ;
ADD A, B ;
LD B, A ; xroot += (1 << 10)
JR bit5Done
dontSet5:
ADD HL, DE ; x += x2
bit5Done:
EX HL, DE ; DE = x
LD HL, 256 ; 1 << 8
ADD HL, BC ; x2 = xroot + (1 << 8)
SRL B
RR C ; xroot >>= 1
EX HL, DE ; HL = x, DE = x2
SBC HL, DE ; x -= x2
JR C, dontSet4 ; if x < x2, don't set bit 4
INC B ; xroot += (1 << 8)
JR bit4Done
dontSet4:
ADD HL, DE ; x += x2
bit4Done:
EX HL, DE ; DE = x
LD HL, 64 ; 1 << 6
ADD HL, BC ; x2 = xroot + (1 << 6)
SRL B
RR C ; xroot >>= 1
EX HL, DE ; HL = x, DE = x2
SBC HL, DE ; x -= x2
JR C, dontSet3 ; if x < x2, don't set bit 3
EX HL, DE ; DE = x
LD HL, 64 ; 64
ADD HL, BC ; xroot + 64
LD B, H
LD C, L ; xroot += 64
JR bit3Done
dontSet3:
ADD HL, DE ; x += x2
EX HL, DE ; DE = x
bit3Done:
LD HL, 16 ; 1 << 4
ADD HL, BC ; x2 = xroot + (1 << 4)
SRL B
RR C ; xroot >>= 1
EX HL, DE ; HL = x, DE = x2
SBC HL, DE ; x -= x2
JR C, dontSet2 ; if x < x2, don't set bit 2
EX HL, DE ; DE = x
LD HL, 16 ; 16
ADD HL, BC ; xroot + 16
LD B, H
LD C, L ; xroot += 16
JR bit2Done
dontSet2:
ADD HL, DE ; x += x2
EX HL, DE ; DE = x
bit2Done:
LD HL, 4 ; 1 << 2
ADD HL, BC ; x2 = xroot + (1 << 2)
SRL B
RR C ; xroot >>= 1
EX HL, DE ; HL = x, DE = x2
SBC HL, DE ; x -= x2
JR C, dontSet1 ; if x < x2, don't set bit 1
INC BC
INC BC
INC BC
INC BC ; xroot += 4
JR bit1Done
dontSet1:
ADD HL, DE ; x += x2
bit1Done:
EX HL, DE ; DE = x
LD HL, 1 ; 1 << 0
ADD HL, BC ; x2 = xroot + (1 << 0)
SRL B
RR C ; xroot >>= 1
EX HL, DE ; HL = x, DE = x2
SBC HL, DE ; x -= x2
JR C, bit0Done ; if x < x2, don't set bit 1
INC BC ; xroot + (1 << 0)
bit0Done:
LD H, B
LD L, C ; HL = isqrt(x)
References: