Re: Ada function sqrt(x)

Re: Ada function sqrt(x)

[Pascal Obry]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 1499 bytes --]



"zeppelin" <zeppelin@access.mountain.net> wrote:

>I want to find the sqrt of a interger... how can I do this and what package
>do I need to declare

With Ada83 there is no standard package, but you should be able to
find one on the PAL (http://web.cnam.fr/Languages/Ada/PAL/ or
ftp://wuarchive.wustl.edu/languages/ada)

Informations/Pointers about Ada : http://lglwww.epfl.ch/Ada/

If you are using Ada95 then the package is

Ada.Numerics.Generic_Elementary_Functions or
Ada.Numerics.Elementary_Functions (for a float instanciation).


>I need to know before next Sunday the 22nd.. but the sooner the better..

Ouf I'am not too late :-)

>Thanks
>J Shriver

>zeppelin@access.mountain.net
>jshriver@cs.wvu.edu

Pascal.

--|------------------------------------------------------------
--| Pascal Obry                               Team-Ada Member |
--|                                                           |
--| EDF-DER-IPN-SID- Ing�nierie des Syst�mes d'Informations   |
--|                                                           |
--| Bureau G1-010           e-mail: pascal.obry@der.edfgdf.fr |
--| 1 Av G�n�ral de Gaulle  voice : +33-1-47.65.50.91         |
--| 92141 Clamart CEDEX     fax   : +33-1-47.65.50.07         |
--| FRANCE                                                    |
--|------------------------------------------------------------
--|
--|   http://ourworld.compuserve.com/homepages/pascal_obry
--|
--|   "The best way to travel is by means of imagination"

Re: Ada function sqrt(x)

[Keith Thompson]

In <51o7nh$5vl@cf01> pascal.obry@der.edfgdf.fr (Pascal Obry) writes:
> "zeppelin" <zeppelin@access.mountain.net> wrote:
> 
> >I want to find the sqrt of a interger... how can I do this and what package
> >do I need to declare
[...]
> If you are using Ada95 then the package is
> 
> Ada.Numerics.Generic_Elementary_Functions or
> Ada.Numerics.Elementary_Functions (for a float instanciation).

The original question was about finding the square root of an *integer*;
Generic_Elementary_Functions and its instantiations work on floating-point
types.

You can convert the argument to a floating-point type, take the square
root, and convert back to an integer type, but that may lose precision
in some cases.  Also, I think an integer square root operation typically
truncates rather than rounding (for example, sqrt(99) is 9, not 10).
Ada 95 provides a 'Truncation attribute (see RM95-A.5.3) -- but again,
watch out for loss of precision (sqrt(9.0) *might* return something like
2.9999999; also, many 32-bit integers cannot be represented exactly in
32-bit floating-point).

You might have better luck writing an integer sqrt function that only
uses integer arithmetic.  I'm sure this has been done before; perhaps
someone else knows where.

-- 
Keith Thompson (The_Other_Keith) kst@thomsoft.com <*>
TeleSoft^H^H^H^H^H^H^H^H Alsys^H^H^H^H^H Thomson Software Products
10251 Vista Sorrento Parkway, Suite 300, San Diego, CA, USA, 92121-2706
FIJAGDWOL

Re: Ada function sqrt(x)

[Roderick Chapman]

Keith Thompson wrote:
> 
> In <51o7nh$5vl@cf01> pascal.obry@der.edfgdf.fr (Pascal Obry) writes:
> > "zeppelin" <zeppelin@access.mountain.net> wrote:
> >
> > >I want to find the sqrt of a interger... how can I do this and what package
> > >do I need to declare
> [...]

A simple binary chop search is possible.  The algorihtm is not that complex, and can
even be proven correct with respect to a formal specification (yes...I've
actually done this just recently.)  Decide if you want a truncated or rounded
answer, and be careful when you want an answer for values near Integer'Last, since
it's easy to end up trying to square a number that will overflow.

Another algorihtm is detailed at:
   http://www.best.com/~mxmora/umpg/UMPG_II_Math&Algorithms.html

In the article Jamie McCarthy, a fast "bit twiddly" algorithm is given which 
we've found to be about twice as fast as the binary chop.  Interestingly, it
can be implemented efficiently in Ada (even in the SPARK subset) without
any implementation-dependent support for unsigned integers or bit-wise
operations.  I wouldn't fancy your chances of proving this algorihtm
correct, though.  I've run an exhausitve test over our the domain of
inetegers we have, and it gives the same result as the binary chop algorithm,
so that's good enough for me!

 - Rod Chapman, 
   Praxis Critical Systems rod@praxis.co.uk

Re: Ada function sqrt(x)

[Robert Dewar]

Reposting article removed by rogue canceller.

I assume the integer square root problem was an assignment anyway, so
I am not about to provide the obvious answer, but Keith said

"You can convert the argument to a floating-point type, take the square
root, and convert back to an integer type, but that may lose precision
in some cases.  Also, I think an integer square root operation typically
truncates rather than rounding (for example, sqrt(99) is 9, not 10).
Ada 95 provides a 'Truncation attribute (see RM95-A.5.3) -- but again,
watch out for loss of precision (sqrt(9.0) *might* return something like
2.9999999; also, many 32-bit integers cannot be represented exactly in
32-bit floating-point)."

In fact, the square root of 9 must be exactly 3.
\x1adp

Re: Ada function sqrt(x)

[Keith Thompson]

In <R.dewar.843335145@schonberg> dewar@cs.nyu.edu (Robert Dewar) writes:
[...]
> In fact, the square root of 9 must be exactly 3.

I can't find an RM reference for this requirement.

For implementations that don't support the optional Numerics Annex
(Annex G), the accuracy requirements on the mathematical functions
are nearly nonexistent.  Even Annex G only requires a relative error
bound of 2.0*EF.Float_Type'Model_Epsilon (where EF.Float_Type is the
floating-point type in question), which still allows Sqrt(9.0) to be
slightly above or below 3.0.

Of course a decent implementation of Sqrt *should* return exactly 3.0
for Sqrt(9.0).

-- 
Keith Thompson (The_Other_Keith) kst@thomsoft.com <*>
TeleSoft^H^H^H^H^H^H^H^H Alsys^H^H^H^H^H Thomson Software Products
10251 Vista Sorrento Parkway, Suite 300, San Diego, CA, USA, 92121-2706
FIJAGDWOL

Re: Ada function sqrt(x)

[Robert Dewar]

I assume the integer square root problem was an assignment anyway, so
I am not about to provide the obvious answer, but Keith said

"You can convert the argument to a floating-point type, take the square
root, and convert back to an integer type, but that may lose precision
in some cases.  Also, I think an integer square root operation typically
truncates rather than rounding (for example, sqrt(99) is 9, not 10).
Ada 95 provides a 'Truncation attribute (see RM95-A.5.3) -- but again,
watch out for loss of precision (sqrt(9.0) *might* return something like
2.9999999; also, many 32-bit integers cannot be represented exactly in
32-bit floating-point)."

In fact, the square root of 9 must be exactly 3.
\x1adp

Re: Ada function sqrt(x)

[Matthew Heaney]

> >I want to find the sqrt of a interger... how can I do this and what package
>> >do I need to declare
>[...]
>> If you are using Ada95 then the package is
>> 
>> Ada.Numerics.Generic_Elementary_Functions or
>> Ada.Numerics.Elementary_Functions (for a float instanciation).
>
>The original question was about finding the square root of an *integer*;
>Generic_Elementary_Functions and its instantiations work on floating-point
>types.

If you really want a function to do integer square roots, here it is (my
Ada 95 syntax may not be quite right):

   generic
      type T is range <>;
   function Generic_Square_Root (N : T) return T'Base;

   function Generic_Square_Root (N: T) return T'Base is
      The_Square_Root : T'Base := N/2;
   begin
      loop
         declare
            The_New_Value : constant T'Base := 
               (The_Square_Root + N / The_Square_Root) / 2;
         begin
            exit when The_New_Value = The_Square_Root;
         end;
      end loop;

      return The_Square_Root;
   end Generic_Square_Root; 

This will work in Ada 83, too, by removing the references to 'Base and
making sure type T has a large enough range to include the value of the
square root.

matt

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

Re: Ada function sqrt(x)

[Matthew Heaney]

Oops!  Of course I meant:


   generic
      type T is range <>;
   function Generic_Square_Root (N : T) return T'Base;

   function Generic_Square_Root (N: T) return T'Base is
      The_Square_Root : T'Base := N/2;
   begin
      loop
         declare
            The_New_Value : constant T'Base := 
               (The_Square_Root + N / The_Square_Root) / 2;
         begin
            exit when The_New_Value = The_Square_Root;
            The_Square_Root := The_New_Value;                  -- This
statement is important!
         end;
      end loop;

      return The_Square_Root;
   end Generic_Square_Root; 

matt

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

Re: Ada function sqrt(x)

[W. Wesley Groleau (Wes)]

Matthew Heaney <mheaney@NI.NET> suggests:

> If you really want a function to do integer square roots, here it is (my
> Ada 95 syntax may not be quite right):

Well, perhaps more than syntax.  Suppose I call an instance with a parameter
of 25......

                                                         Iteration

> generic                                                   1   2   3  ...
>   type T is range <>;
> function Generic_Square_Root (N : T) return T'Base;
>
> function Generic_Square_Root (N: T) return T'Base is
>   The_Square_Root : T'Base := N/2;                       12
> begin
>   loop
>     declare
>       The_New_Value : constant T'Base :=
>            (The_Square_Root + N / The_Square_Root) / 2;   1   1   1   ...
>     begin
>       exit when The_New_Value = The_Square_Root;         no  no  no   ...
>     end;
>   end loop;
>
>   return The_Square_Root;
> end Generic_Square_Root;

At the risk of being flamed for inefficency:

function Integer_Square_Root ( N : T ) is

  Temp : constant T'Base :=
         T'Base ( Ada.Numerics.Elementary_Functions.Sqrt ( Float (N) ) );

begin

  if Temp * Temp /= N then

     raise Some_Package.Input_Is_Not_An_Integer;

  else

    return Temp;

  end if;

end Integer_Square_Root;

---------------------------------------------------------------------------
W. Wesley Groleau (Wes)                                Office: 219-429-4923
Hughes Defense Communications (MS 10-40)                 Home: 219-471-7206
Fort Wayne,  IN   46808                  (Unix): wwgrol@pseserv3.fw.hac.com
---------------------------------------------------------------------------