Path: utzoo!utgpu!jarvis.csri.toronto.edu!clyde.concordia.ca!uunet!mcsun!hp4nl!kunivv1!ge
From: ge@kunivv1.sci.kun.nl (Ge' Weijers)
Newsgroups: comp.graphics
Subject: Re: Integral Square Root
Message-ID: <606@kunivv1.sci.kun.nl>
Date: 2 Jan 90 17:44:28 GMT
References: <9170@cbmvax.commodore.com> <21550@mimsy.umd.edu> <21561@mimsy.umd.edu> <21562@mimsy.umd.edu> <9182@cbmvax.commodore.com>
Organization: University of Nijmegen, The Netherlands.
Lines: 35

Another integer square root algorithm, from Mr. Otto Peter from Innsbruck,
Austria (published in C'T 1-90) copied verbatim:

#define	N_BITS	32
#define	MAX_BIT	((N_BITS+1)/2-1)

unsigned long int sqrt_5(x)
unsigned long int x;
{
	register unsigned long int xroot, m2, x2;

	xroot = 0; m2 = 1<< MAX_BIT * 2;

	do {
		x2 = xroot + m2;
		xroot >>= 1;
		if(x2 <= x) {
			x -= x2;
			xroot += m2;
		}
	} while(m2 >>= 2);
	if(xroot < x) return (xroot+1);
	return(xroot);
}

The algorithm does not use multiplication, which is a benefit on things like
a 68000.

Ge' Weijers


Ge' Weijers                                    Internet/UUCP: ge@cs.kun.nl
Faculty of Mathematics and Computer Science,   (uunet.uu.net!cs.kun.nl!ge)
University of Nijmegen, Toernooiveld 1         
6525 ED Nijmegen, the Netherlands              tel. +3180612483 (UTC-2)