From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-1.3 required=5.0 tests=BAYES_00,INVALID_MSGID
	autolearn=no autolearn_force=no version=3.4.4
X-Google-Language: ENGLISH,ASCII-7-bit
X-Google-Thread: 103376,5b88cd8e97eaef79
X-Google-Attributes: gid103376,public
From: okellogg@cube.net (Oliver Kellogg)
Subject: Re: Integer Square Root
Date: 1996/10/22
Message-ID: <54jk3f$k8o@salyko.cube.net>#1/1
X-Deja-AN: 191399549
references: <mheaney-ya023180001510962133390001@news.ni.net>
 <DzEEq3.9tI@thomsoft.com> <mheaney-ya023180001710962222450001@news.ni.net>
content-type: text/plain; charset=ISO-8859-1
organization: CUBENet Munich
mime-version: 1.0
newsgroups: comp.lang.ada
Date: 1996-10-22T00:00:00+00:00
List-Id: <comp.lang.ada>


-- This is a square root algorithm for unsigned 32 bit integers that
-- uses addition, subtraction, and shifts only.
-- Result is *truncated*, i.e. Sqrt(62) = 7.
-- For a description of the algorithm, see the German computer magazine
-- c't, January 1990, page 300 ff. (Otto Peter, "Prozessor zieht Wurzeln")

with Interfaces;
use  Interfaces;
function Sqrt (X : Unsigned_32) return Unsigned_32 is
   Root : Unsigned_32 := 0;
   M    : Unsigned_32 := 16#4000_0000#;
   X1   : Unsigned_32 := X;
   X2   : Unsigned_32;
begin
   loop
      X2 := Root + M;
      Root := Shift_Right (Root, 1);
      if X2 <= X1 then
         X1 := X1 - X2;
         Root := Root + M;
      end if;
      M := Shift_Right (M, 2);
      exit when M = 0;
   end loop;
   return Root;
end Sqrt;