Square root of an integer number

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

By ARTRAG

Enlighted (6275)

ARTRAG's picture

15-12-2008, 19:51

The square root of an integer is equal to the number of times an increasing odd 
number can be subtracted from the original number and remain 
positive.  For example,
           
                   25
                 -  1         1
                   --
                   24
                 -  3         2
                   --
                   21
                 -  5         3
                   --
                   16
                 -  7         4
                   --
                    9
                 -  9         5 = square root of 25
                   --
                    0

Nice to keep in mind...
Wink

Login or register to post comments

By NYYRIKKI

Enlighted (5396)

NYYRIKKI's picture

15-12-2008, 20:05

If this is correct, then I really thank you!

I think this fact may cause plenty of really nice plasmas Wink

By Manuel

Ascended (15811)

Manuel's picture

15-12-2008, 21:20

It's shorter than what I programmed myself about 10 years ago (1996/1997, with the help of Alex Wulms):

; sqrt16b
; e = sqrt(hl)
; coded by M. Bilderbeek, thanks to Alex Wulms for the
; idea of the nice Newton-Raphson algorithm.
; changes a,bc,d

sqrt16b ld	e,255	; 1st approx., adapt for own sit.
	ld	b,8	; #iterations, 8 is necessary for all 8-bit possib.
sqrt2	push	bc	; save the step-counter
	push	hl	; (ld bc,hl)
	pop	bc	; make ready for division
	ld	d,0	; make sure de is 8-bit value
	push	hl	; save the argument of the sqrt
	call	div16b	; divide bc by e
	pop	hl	; restore the argument of the sqrt
	ld	a,c	; store result in a
	add	a,e	; add it to the prev. approx.
	push	af	; save the carry-flag
	ld	e,a	; put result back in e
	srl	e	; divide 8 bits by 2
	pop	af	; restore carry flag!
	jp	nc,sqrt3	; No carry? Then proceed...
	set	7,e	; carry->add 128 to result
sqrt3	pop	bc	; restore the step-counter
	djnz	sqrt2	; next iteration step
	ret

which depends on

; word-divide routine ripped from drive rom
; bc=bc\de
; hl=bc mod de
; hl=bc mod de
div16b	ld	hl,0
	ld	a,b
	ld	b,16
	rl	c
	rla
div1:	rl	l
	rl	h
	jr	c,div2
	sbc	hl,de
	jr	nc,div3
	add	hl,de
div3:	ccf
div4:	rl	c
	rla
	djnz	div1
	ld	b,a
	ret
div2:	or	a
	sbc	hl,de
	jr	div4

By ARTRAG

Enlighted (6275)

ARTRAG's picture

15-12-2008, 22:06

Manuel, any SQRT routine that relies on multiple divisions cannot compete with the algorithm I posted

By pitpan

Prophet (3131)

pitpan's picture

15-12-2008, 23:02

Worst case scenario: SQRT(127) requires 12 iterations. That's a bargain!

On the other side, a look-up table can be faster, but it lacks the elegance and compactness of this solution.

By ARTRAG

Enlighted (6275)

ARTRAG's picture

15-12-2008, 23:09

it can work also for 16 bit integers
sqrt(65536) is resolved in 256 iterations

By dvik

Prophet (2200)

dvik's picture

15-12-2008, 23:49

Yeah its a pretty cool algorithm. Its basically the same as the one to factorize numbers:

1 PRINTCHR$(-30*(D<>0OR(C-B)<>2))A:A=A-2*(D=0)-(A=0):B=(D=0)-(D<>0)*B:C=(D=0)-(D<>0)*C:D=D-A*(D=0):C=C-2*(D>0):B=B-2*(D<0):D=D+C*(D>0)-B*(D<0):GOTO1

Notice all the two -2*. Those are essentially the statements that adds two in each iteration step, described by artrag. The only difference is that the factorization uses two accumulators instead of one as for the square root.

By ARTRAG

Enlighted (6275)

ARTRAG's picture

15-12-2008, 23:59

ah, this line of basic opens new words to me Wink

By ARTRAG

Enlighted (6275)

ARTRAG's picture

16-12-2008, 00:12

this untested code should work (on 16 bit inputs)

; in hl
; out a

    ld  de,1
    ld  a,d
1:
    and a
    sbc hl,de
    ret m
    inc de
    inc de
    inc a
    jp  1b

manuel, do you want to compare with yours?
ehehe

By wolf_

Ambassador_ (9774)

wolf_'s picture

16-12-2008, 00:30

But his version prolly works tho.. Tongue

jp 1

Santa

*edit*

never mind Hannibal

By wolf_

Ambassador_ (9774)

wolf_'s picture

16-12-2008, 00:35

Funny, in a code box, the number 1 is identical to the letter l. May lead to confusing situations ^^

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