Square root of an integer number

Page 2/5
1 | | 3 | 4 | 5

By Arjan

Paladin (714)

Arjan's picture

16-12-2008, 00:54

The following routine (by Ricardo Bittencourt) takes 8 iterations for any 16 bit number

;Square root of 16-bit value
;In: HL = value
;Out: D = result (rounded down)
;
Sqr16: ld de,#0040
ld a,l
ld l,h
ld h,d
or a
ld b,8
Sqr16_Loop:
sbc hl,de
jr nc,Sqr16_Skip
add hl,de
Sqr16_Skip:
ccf
rl d
add a,a
adc hl,hl
add a,a
adc hl,hl
djnz Sqr16_Loop
ret

By ARTRAG

Enlighted (6323)

ARTRAG's picture

16-12-2008, 10:13

hehehe
I'm sure that the one I posted was not the best way, but it was so simple that I could not resist Smile
Ricardo's code seems an implementation of the Bombelli algorithm
Here a description (sorry, in Italian) and a C snippet implementing it:

http://it.wikipedia.org/wiki/Metodi_per_il_calcolo_della_radice_quadrata

By Arjan

Paladin (714)

Arjan's picture

16-12-2008, 10:59

Well, there is no "best" way, it all depends on the requirements. If you don't care about speed and need the smallest possible code, then your solution is the best (if you change jp to jr .Tongue).

By AuroraMSX

Paragon (1901)

AuroraMSX's picture

16-12-2008, 11:14

(sorry, in Italian)Well, there's a small box on hte left hand side of that page titled altre lingue and in that box you'll find a link to the english version of the page :P

By Manuel

Ascended (15968)

Manuel's picture

16-12-2008, 11:45

ARTRAG: of course the one I posted cannot compete with anything. It's just that I wanted to say that your algo sounds like a LOT more efficient than Newton Raphson! Smile Also my ASM implementation was a direct port from the algorithm, without trying to optimize anything. Ah well, pure educational purposes Smile

By ARTRAG

Enlighted (6323)

ARTRAG's picture

16-12-2008, 11:49

Smile

By sjoerd

Hero (593)

sjoerd's picture

16-12-2008, 11:57

This way ARTRAG's routine is probably always faster:

; in hl
; out a

    ld  de,1
    xor a
1:
    sbc hl,de
    ret c
    inc e
    inc e
    inc a
    jp  1b

By pitpan

Prophet (3131)

pitpan's picture

16-12-2008, 12:11

But it won't work after the 127th iteration, 'cause after DE=255 you'll have DE=1. I'm afraid that INC DE is required instead of INC E.

By sjoerd

Hero (593)

sjoerd's picture

16-12-2008, 12:20

It isn't always that much faster also. Ah well, I better go back to sleep now Tongue

By pitpan

Prophet (3131)

pitpan's picture

16-12-2008, 14:43

Well, your approach of avoiding the repetition of XOR A in every iteration produces a sensible overall improvement. We, anonymous assemblers (A.A.), do live for optimization ;D. I'm really high on size optimization. What's your dope? ;D

Page 2/5
1 | | 3 | 4 | 5