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