Square root of an integer number

Page 1/5
| 2 | 3 | 4 | 5
```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...

If this is correct, then I really thank you!

I think this fact may cause plenty of really nice plasmas

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
div3:	ccf
div4:	rl	c
rla
djnz	div1
ld	b,a
ret
div2:	or	a
sbc	hl,de
jr	div4
```

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

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.

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

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.

ah, this line of basic opens new words to me

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

But his version prolly works tho..

`jp 1`

*edit*

never mind

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