Integer Square Root

[mheaney@ni.net (Matthew Heaney)]

W. Wesley Groleau <mailto:wwgrol@pseserv3.fw.hac.com> pointed out to me
some errors in an algorithm I posted for performing the square root of an
integer number without using floating point arithmetic.

That I did that off the top of my head, without any testing (neither static
nor dynamic), and the fact that that algorithm basically doesn't work,
should prove to everyone (especially me) that "off-the-cuff" programming
doesn't work!  Thank you, Wes, for pointing out to me the errors of my
ways.

So here, if I may be given a chance to right my wrongs, is a "correct" version:

   function Square_Root (N : Natural) return Natural is
      X0 : Natural := N / 2;
      X1 : Natural := 2;
   begin
      case N is 
         when 0 =>
            return 0;

         when 1 =>
           return 1;

         when others =>
             while abs (X0 - X1) > 1 loop
                  X0 := (X0 + X1) / 2;
                  X1 := N / X0;
            end loop;

            return X0;

      end case;
   end Square_Root;

This is similar to an algorithm for fixed point types that appears in
Section 5.4 of the Ada 83 Rationale.

If anyone is interested in a generic version that works for any integer
type, then let me know, and I'll post it.

matt

--------------------------------------------------------------------
Matthew Heaney
Software Development Consultant
mheaney@ni.net
(818) 985-1271