* Re: Ada function sqrt(x)
[not found] <01bba50c$7c1a2760$dc014dc6@MountainNet>
@ 1996-09-18 0:00 ` Pascal Obry
1996-09-20 0:00 ` Keith Thompson
0 siblings, 1 reply; 9+ messages in thread
From: Pascal Obry @ 1996-09-18 0:00 UTC (permalink / raw)
[-- 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"
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: Ada function sqrt(x)
1996-09-20 0:00 ` Keith Thompson
@ 1996-09-20 0:00 ` Roderick Chapman
1996-09-21 0:00 ` Robert Dewar
` (2 subsequent siblings)
3 siblings, 0 replies; 9+ messages in thread
From: Roderick Chapman @ 1996-09-20 0:00 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: Ada function sqrt(x)
1996-09-18 0:00 ` Ada function sqrt(x) Pascal Obry
@ 1996-09-20 0:00 ` Keith Thompson
1996-09-20 0:00 ` Roderick Chapman
` (3 more replies)
0 siblings, 4 replies; 9+ messages in thread
From: Keith Thompson @ 1996-09-20 0:00 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: Ada function sqrt(x)
1996-09-20 0:00 ` Keith Thompson
1996-09-20 0:00 ` Roderick Chapman
@ 1996-09-21 0:00 ` Robert Dewar
1996-09-21 0:00 ` Robert Dewar
1996-09-22 0:00 ` Matthew Heaney
3 siblings, 0 replies; 9+ messages in thread
From: Robert Dewar @ 1996-09-21 0:00 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: Ada function sqrt(x)
1996-09-20 0:00 ` Keith Thompson
1996-09-20 0:00 ` Roderick Chapman
1996-09-21 0:00 ` Robert Dewar
@ 1996-09-21 0:00 ` Robert Dewar
1996-09-26 0:00 ` Keith Thompson
1996-09-22 0:00 ` Matthew Heaney
3 siblings, 1 reply; 9+ messages in thread
From: Robert Dewar @ 1996-09-21 0:00 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: Ada function sqrt(x)
1996-09-20 0:00 ` Keith Thompson
` (2 preceding siblings ...)
1996-09-21 0:00 ` Robert Dewar
@ 1996-09-22 0:00 ` Matthew Heaney
1996-09-22 0:00 ` Matthew Heaney
3 siblings, 1 reply; 9+ messages in thread
From: Matthew Heaney @ 1996-09-22 0:00 UTC (permalink / raw)
> >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
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: Ada function sqrt(x)
1996-09-22 0:00 ` Matthew Heaney
@ 1996-09-22 0:00 ` Matthew Heaney
0 siblings, 0 replies; 9+ messages in thread
From: Matthew Heaney @ 1996-09-22 0:00 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: Ada function sqrt(x)
@ 1996-09-24 0:00 W. Wesley Groleau (Wes)
0 siblings, 0 replies; 9+ messages in thread
From: W. Wesley Groleau (Wes) @ 1996-09-24 0:00 UTC (permalink / raw)
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
---------------------------------------------------------------------------
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: Ada function sqrt(x)
1996-09-21 0:00 ` Robert Dewar
@ 1996-09-26 0:00 ` Keith Thompson
0 siblings, 0 replies; 9+ messages in thread
From: Keith Thompson @ 1996-09-26 0:00 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 9+ messages in thread
end of thread, other threads:[~1996-09-26 0:00 UTC | newest]
Thread overview: 9+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
[not found] <01bba50c$7c1a2760$dc014dc6@MountainNet>
1996-09-18 0:00 ` Ada function sqrt(x) Pascal Obry
1996-09-20 0:00 ` Keith Thompson
1996-09-20 0:00 ` Roderick Chapman
1996-09-21 0:00 ` Robert Dewar
1996-09-21 0:00 ` Robert Dewar
1996-09-26 0:00 ` Keith Thompson
1996-09-22 0:00 ` Matthew Heaney
1996-09-22 0:00 ` Matthew Heaney
1996-09-24 0:00 W. Wesley Groleau (Wes)
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox