Re: Integer Square Root

[okellogg@cube.net (Oliver Kellogg)]

-- 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;