Article View: comp.arch
Article #11030Re: integer distance or sqrt
From: Bjoern Reese
Date: Tue, 17 Nov 1992 11:30
Date: Tue, 17 Nov 1992 11:30
48 lines
1581 bytes
1581 bytes
In article <1992Nov16.172604.4947@sei.cmu.edu> firth@sei.cmu.edu (Robert Firth)
writes:
> In article <1992Nov16.110102.17077@imada.ou.dk> breese@monet.imada.ou.dk
(Bjoern Reese) writes:
>
> >Heron(x) {Fast integer squareroot routine}
> > IF x <= 64 THEN
> > y = 2 + (x >> 3) {shift right 3 times}
> > ELSE
> ...
> > ENDIF
> > root := (y + x DIV y) >> 1
> >
> >This algorithm is faster than Newton's Method...
>
> Maybe so, but Newton's method doesn't tell you that the square
> root of 0 is 1.
:( Sorry about that :(
Let's fix it.
Heron(x)
IF x = 0 THEN
y = 1
ELSE
IF x <= 64 THEN
...
ENDIF
ENDIF
root := (y + x DIV y) >> 1
or
Heron(x)
IF x = 0 THEN
root := 0
ELSE
IF x <= 64 THEN
...
ENDIF
root := (y + x DIV y) >> 1
ENDIF
--
Bjoern Reese | Email: breese@imada.ou.dk
Odense University, Denmark | Voice: +45 65 932 182 (private)
Technical Details
Message-ID:
<1992Nov17.113057.11993@imada.ou.dk>Path:
arc1-ca.pugleaf.net!sparky!uunet!zaphod.mps.ohio-state.edu!darwin.sura.net!spool.mu.edu!sol.ctr.columbia.edu!ira.uka.de!math.fu-berlin.de!news.netmbx.de!Germany.EU.net!mcsun!sunic!dkuug!imada!newsReferences:
<1992Nov16.172604.4947@sei.cmu.edu>Show Full Headers
Complete Article Headers
Newsgroups: comp.arch Path: arc1-ca.pugleaf.net!sparky!uunet!zaphod.mps.ohio-state.edu!darwin.sura.net!spool.mu.edu!sol.ctr.columbia.edu!ira.uka.de!math.fu-berlin.de!news.netmbx.de!Germany.EU.net!mcsun!sunic!dkuug!imada!news From: breese@monet.imada.ou.dk (Bjoern Reese) Subject: Re: integer distance or sqrt Message-ID: <1992Nov17.113057.11993@imada.ou.dk> Sender: news@imada.ou.dk (USENET News System) Organization: Dept. of Math. & Computer Science, Odense University, Denmark References: <1992Nov16.172604.4947@sei.cmu.edu> Date: Tue, 17 Nov 1992 11:30:57 GMT Lines: 48