Unsigned Integer Restraint Errors

Unsigned Integer Restraint Errors

[frikk]

Hello Everyone!

I'm having a trivial difficulty with Ada. I am working with a 64 bit
unsigned integer, and of course I would like to know if the input to
this unsigned integer is out of range. I am having two issues.  The
first is that I cannot get ada to raise a constraint error unless I
make a subtype and state the range of being a finite number (but only
in some circumstances, I'll explain in a second).  The second thing is
that when I do get it to raise a constraint error with the finite
range, the exception isn't handled correctly. I think it may have
something to do with me using 64 bit unsigned integers.

Here is my unmodified code which I would expect to work. Note that I
set the value of 'test' twice to what I wouuld expect to be an invalid
value:

with Ada.Text_IO;
use Ada.Text_IO;

procedure Prime_Bits is
   -- Declare a 64 bit unsigned integer
   type UNSIGNED_LONG_INT is mod 2**64;
   test : UNSIGNED_LONG_INT := -5;

   package LONG_IO is new Modular_IO(UNSIGNED_LONG_INT);
   use LONG_IO;

begin
   Put("Minimum Value(uint64_t): ");
   Put(UNSIGNED_LONG_INT'FIRST);
   New_Line;
   Put("Maximum Value(uint64_t): ");
   Put(UNSIGNED_LONG_INT'LAST);
   New_Line;

   test := -5;
   Put(test);

exception
      when Constraint_Error => Put("Constraint Error!!!!");
      when others => Put("Unknown Error");

end Prime_Bits;
##############
Output:
M:\work\ada\prime_bits>prime_bits
Minimum Value(uint64_t):                     0
Maximum Value(uint64_t):  18446744073709551615
 18446744073709551611

Here is the code for which I *can* generate a constraint error,
however the error is not handled at all even though I have the
handling in the right area (I think):

with Ada.Text_IO;
use Ada.Text_IO;

procedure Prime_Bits is
   -- Declare a 64 bit unsigned integer
   type UNSIGNED_LONG_INT is mod 2**64;
   subtype SUB_UNSIGNED_LONG_INT is UNSIGNED_LONG_INT range 0 .. 5;
   test : SUB_UNSIGNED_LONG_INT := -5;

   package LONG_IO is new Modular_IO(SUB_UNSIGNED_LONG_INT);
   use LONG_IO;

begin
   Put("Minimum Value(uint64_t): ");
   Put(SUB_UNSIGNED_LONG_INT'FIRST);
   New_Line;
   Put("Maximum Value(uint64_t): ");
   Put(SUB_UNSIGNED_LONG_INT'LAST);
   New_Line;

   test := -5;
   Put(test);

exception
      when Constraint_Error => Put("Constraint Error!!!!");
      when others => Put("Unknown Error");

end Prime_Bits;

################
Output:
M:\work\ada\prime_bits>prime_bits
raised CONSTRAINT_ERROR : prime_bits.adb:8


LASTLY:
Please note that when I change the range value from 0 .. 5 to 0 ..
2**64-1, or 0 .. UNSIGNED_LONG_INT'Last, there is no constraint error
raised. This is the same behavior as the first example.

Thank you!
Blaine

Re: Unsigned Integer Restraint Errors

[Georg Bauhaus]

On Mon, 2007-03-12 at 08:07 -0700, frikk wrote:
> Hello Everyone!
> 
> I'm having a trivial difficulty with Ada. I am working with a 64 bit
> unsigned integer, and of course I would like to know if the input to
> this unsigned integer is out of range. I am having two issues.  The
> first is that I cannot get ada to raise a constraint error unless I
> make a subtype and state the range of being a finite number (but only
> in some circumstances, I'll explain in a second). 
> 
> procedure Prime_Bits is
>    -- Declare a 64 bit unsigned integer
>    type UNSIGNED_LONG_INT is mod 2**64;

> 
>    test := -5;

This first question is probably answered by LRM 3.4.5,
 19. For a modular type, if the result of the execution of a predefined
     operator is outside the base range of the type, the
     result is reduced modulo the modulus of the type to a value that
     is within the base range of the type.

HTH

Re: Unsigned Integer Restraint Errors

[Adam Beneschan]

On Mar 12, 8:07 am, "frikk" <frik...@gmail.com> wrote:
> Hello Everyone!
>
> I'm having a trivial difficulty with Ada. I am working with a 64 bit
> unsigned integer, and of course I would like to know if the input to
> this unsigned integer is out of range. I am having two issues.  The
> first is that I cannot get ada to raise a constraint error unless I
> make a subtype and state the range of being a finite number (but only
> in some circumstances, I'll explain in a second).  The second thing is
> that when I do get it to raise a constraint error with the finite
> range, the exception isn't handled correctly. I think it may have
> something to do with me using 64 bit unsigned integers.
>
> Here is my unmodified code which I would expect to work. Note that I
> set the value of 'test' twice to what I wouuld expect to be an invalid
> value:
>
> with Ada.Text_IO;
> use Ada.Text_IO;
>
> procedure Prime_Bits is
>    -- Declare a 64 bit unsigned integer
>    type UNSIGNED_LONG_INT is mod 2**64;
>    test : UNSIGNED_LONG_INT := -5;

I think your error comes from seeing "-5" and thinking this is the
number -5.  It's not.  -5 in Ada is not a numeric literal that
represents the number "negative five"; rather, it's the result of
applying the unary function "-" to the number 5.  And the way this is
written, the function that gets applied is the one that operates on
the modular type:

   function "-" (Left : UNSIGNED_LONG_INT) return UNSIGNED_LONG_INT;

and, as Georg has already pointed out, the predefined functions for
modular types always compute the result modulo the modulus.  See the
note in RM 4.5.4(3), which makes this more explicit.

This would give you a Constraint_Error, if it compiled:

    test: UNSIGNED_LONG_INT := UNSIGNED_LONG_INT (Integer' (-5));

because now the "-" that gets applied is the "-" that's defined for
the type Integer, and the result of the "-" operator is the Integer
-5, and the type conversion *does* raise Constraint_Error because -5
isn't in range.  In reality, this won't even compile, because the
compiler can determine that this evaluating this static expression
will raise Constraint_Error, and this makes the program illegal by RM
4.9(34).

This should raise Constraint_Error:

    X : integer := 5;
    Test : UNSIGNED_LONG_INT := UNSIGNED_LONG_INT (-X);

and this should not:

    X : integer := 5;
    Test : UNSIGNED_LONG_INT := - UNSIGNED_LONG_INT (X);

One more point: In the example that does raise Constraint_Error, your
exception handler that outputs the string "Constraint_Error!!!!" would
*not* be executed.  When an exception occurs in a declaraton, the
exception handler that gets executed, if any, must be in a scope that
*encloses* the scope with the declaration.  So to get your own
exception handler to work on an exception raised by a declaration,
you'd need to do something like this:

    procedure Prime_Bits is
    begin
       declare
           X : Integer := 5;
           Test : UNSIGNED_LONG_INT := UNSIGNED_LONG_INT (-X);
       begin
           null;
       end;
    exception
        when Constraint_Error => Put_Line("Constraint Error!!!");
    end;

Hope this helps clear things up,

                                 -- Adam

P.S. If you really want a good demonstration of what I mean about the
unary "-" operator, try this:

with Ada.Text_IO;
procedure Test1 is
    package Int_IO is new Ada.Text_IO.Integer_IO (Integer);
    type New_Int is new Integer;
    function "-" (Left : New_Int) return New_Int is
    begin
       return Left * 2;
    end "-";
    A : New_Int := -6;
    B : Integer := Integer (A);
begin
    Int_IO.Put (B);
end Test1;

Re: Unsigned Integer Restraint Errors

[Adam Beneschan]

On Mar 12, 8:07 am, "frikk" <frik...@gmail.com> wrote:

> LASTLY:
> Please note that when I change the range value from 0 .. 5 to 0 ..
> 2**64-1, or 0 .. UNSIGNED_LONG_INT'Last, there is no constraint error
> raised. This is the same behavior as the first example.

I missed this question the first time.

The reason for this is probably that special things are needed to do
this sort of check.  When you declare a subtype in the range 0 .. 5,
the code generated by the compiler can do its normal arithmetic
operations, and then check to see if the result is less than 0 or
greater than 5.  But when you declare a subtype in the range
0..2**64-1, the code can't do this, because *all* 64-bit integers are
going to appear to be in this range.  In order to do the check, either
the compiler will need to generate additional special code, or it will
need to do something to enable the processor's hardware overflow
mechanism.  On GNAT and some other compilers, this requires that you
use a special flag when compiling.  This might be -gnato, but I don't
remember offhand, and I'm hoping someone else will tell us what it is
so that I don't have to look it up myself.

                                  -- Adam

Re: Unsigned Integer Restraint Errors

[frikk]

On Mar 12, 1:23 pm, "Adam Beneschan" <a...@irvine.com> wrote:
> On Mar 12, 8:07 am, "frikk" <frik...@gmail.com> wrote:
>
> > LASTLY:
> > Please note that when I change the range value from 0 .. 5 to 0 ..
> > 2**64-1, or 0 .. UNSIGNED_LONG_INT'Last, there is no constraint error
> > raised. This is the same behavior as the first example.
>
> I missed this question the first time.
> [...]
>
>                                   -- Adam


Thanks for the answers Adam.  What you've said about the '-' makes
sense. I'll look into this.

The deal about how the constraint error being raised is outside the
scope of the procedure makes sense as well. I'll update my code to
reflect this.

So if I compile with gnato - should this fix my constraint error
raising? Basically I just need to be able to detect if the input is
outside the range - without using something like "if x < 0 or x >
2**64 then" ...

Thank you everyone!
Blaine

Re: Unsigned Integer Restraint Errors

[frikk]

On Mar 12, 2:11 pm, "frikk" <frik...@gmail.com> wrote:
> On Mar 12, 1:23 pm, "Adam Beneschan" <a...@irvine.com> wrote:
>
> > On Mar 12, 8:07 am, "frikk" <frik...@gmail.com> wrote:
>
> > > LASTLY:
> > > Please note that when I change the range value from 0 .. 5 to 0 ..
> > > 2**64-1, or 0 .. UNSIGNED_LONG_INT'Last, there is no constraint error
> > > raised. This is the same behavior as the first example.
>
> > I missed this question the first time.
> > [...]
>
> >                                   -- Adam
>
> Thanks for the answers Adam.  What you've said about the '-' makes
> sense. I'll look into this.
>
> The deal about how the constraint error being raised is outside the
> scope of the procedure makes sense as well. I'll update my code to
> reflect this.
>
> So if I compile with gnato - should this fix my constraint error
> raising? Basically I just need to be able to detect if the input is
> outside the range - without using something like "if x < 0 or x >
> 2**64 then" ...
>
> Thank you everyone!
> Blaine

As it turns out, the example that I've posted works just fine when I
use command line arguments:

b := UNSIGNED_LONG_INT'VALUE(Argument(2));

The constraint is thrown perfectly. I do this inside the procedure, of
course, not in the declarations.
Interesting eh?
Blaine

Re: Unsigned Integer Restraint Errors

[Adam Beneschan]

On Mar 12, 1:00 pm, "frikk" <frik...@gmail.com> wrote:
> On Mar 12, 2:11 pm, "frikk" <frik...@gmail.com> wrote:
>
>
>
> > On Mar 12, 1:23 pm, "Adam Beneschan" <a...@irvine.com> wrote:
>
> > > On Mar 12, 8:07 am, "frikk" <frik...@gmail.com> wrote:
>
> > > > LASTLY:
> > > > Please note that when I change the range value from 0 .. 5 to 0 ..
> > > > 2**64-1, or 0 .. UNSIGNED_LONG_INT'Last, there is no constraint error
> > > > raised. This is the same behavior as the first example.
>
> > > I missed this question the first time.
> > > [...]
>
> > >                                   -- Adam
>
> > Thanks for the answers Adam.  What you've said about the '-' makes
> > sense. I'll look into this.
>
> > The deal about how the constraint error being raised is outside the
> > scope of the procedure makes sense as well. I'll update my code to
> > reflect this.
>
> > So if I compile with gnato - should this fix my constraint error
> > raising? Basically I just need to be able to detect if the input is
> > outside the range - without using something like "if x < 0 or x >
> > 2**64 then" ...
>
> > Thank you everyone!
> > Blaine
>
> As it turns out, the example that I've posted works just fine when I
> use command line arguments:
>
> b := UNSIGNED_LONG_INT'VALUE(Argument(2));
>
> The constraint is thrown perfectly. I do this inside the procedure, of
> course, not in the declarations.
> Interesting eh?

Not unexpected, though.  As I said, something like -5 in an Ada
program is not a single number, but rather a unary operator "-"
applied to a numeric literal.  But in other cases, such as the
argument to a 'Value operation or when reading a number from a text
file with an instance of Text_IO.Integer_IO, "-" *is* considered part
of the number, and does not denote the unary "-" operator.  What I
said about "-" applies only in Ada source code.

                                 -- Adam

Re: Unsigned Integer Restraint Errors

[Dmitry A. Kazakov]

On 12 Mar 2007 08:07:12 -0700, frikk wrote:

> I'm having a trivial difficulty with Ada. I am working with a 64 bit
> unsigned integer, and of course I would like to know if the input to
> this unsigned integer is out of range. I am having two issues.  The
> first is that I cannot get ada to raise a constraint error unless I
> make a subtype and state the range of being a finite number (but only
> in some circumstances, I'll explain in a second).  The second thing is
> that when I do get it to raise a constraint error with the finite
> range, the exception isn't handled correctly. I think it may have
> something to do with me using 64 bit unsigned integers.

OK, this requires some clarification

1. Modular types cannot overflow per mathematical definition of. They form
a ring closed for +,-,*,/ (except zero divide).

2. When you input a modular type you cannot get an out of range number for
the reason 1. You can have it only when you convert a number from some
*different* type back to the modular type or else when you constrain the
modular type to a subtype of lesser range.

3. Unary "-" is an operation in Ada. See below.

> Here is my unmodified code which I would expect to work. Note that I
> set the value of 'test' twice to what I wouuld expect to be an invalid
> value:
> 
> with Ada.Text_IO;
> use Ada.Text_IO;
> 
> procedure Prime_Bits is
>    -- Declare a 64 bit unsigned integer
>    type UNSIGNED_LONG_INT is mod 2**64;
>    test : UNSIGNED_LONG_INT := -5;

Here you don't get overflow because it has the semantics: -(5). The unary
minus here has the meaning of the ring mod 2**64 which is different from
unary minus of integer, see RM 4.5.4.

The semantics you probably have implied is:

    test : UNSIGNED_LONG_INT := UNSIGNED_LONG_INT (Integer'(-5));

i.e. make *integer* -5 and convert it to test. This would indeed cause an
error, as expected.

>    package LONG_IO is new Modular_IO(UNSIGNED_LONG_INT);
>    use LONG_IO;
> 
> begin
>    Put("Minimum Value(uint64_t): ");
>    Put(UNSIGNED_LONG_INT'FIRST);
>    New_Line;
>    Put("Maximum Value(uint64_t): ");
>    Put(UNSIGNED_LONG_INT'LAST);
>    New_Line;
> 
>    test := -5;

This shall not raise Constraint_Error. The result should be 2**64 - 5, see
RM 4.5.4.

It seems that Windows GCC 3.4.6 for GNAT GPL 2006 (20060522) has a bug here
for 2**64 modulus. With lesser modulus it works correct.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Unsigned Integer Restraint Errors

[Martin Krischik]

Dmitry A. Kazakov wrote:

> 1. Modular types cannot overflow per mathematical definition of. They form
> a ring closed for +,-,*,/ (except zero divide).

type Byte is mod 256;
subtype Half_Byte is Byte range 0 .. 127;

Martin
-- 
mailto://krischik@users.sourceforge.net
Ada programming at: http://ada.krischik.com

Re: Unsigned Integer Restraint Errors

[Dmitry A. Kazakov]

On Mon, 12 Mar 2007 20:00:51 +0100, Martin Krischik wrote:

> Dmitry A. Kazakov wrote:
> 
>> 1. Modular types cannot overflow per mathematical definition of. They form
>> a ring closed for +,-,*,/ (except zero divide).
> 
> type Byte is mod 256;
> subtype Half_Byte is Byte range 0 .. 127;

OK, to be pedantic, a subtype of a modular type is not necessary a
"modular" type, because it may lose some properties of. Similarly a subtype
of an integer might be not an "integer" because it might lack the null
element, negative inverses etc. These are classical examples of LSP
problematic.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Unsigned Integer Restraint Errors

[frikk]

> The semantics you probably have implied is:
>
>     test : UNSIGNED_LONG_INT := UNSIGNED_LONG_INT (Integer'(-5));
>
> i.e. make *integer* -5 and convert it to test. This would indeed cause an
> error, as expected.
>
> >    package LONG_IO is new Modular_IO(UNSIGNED_LONG_INT);
> >    use LONG_IO;
>
> > begin
> >    Put("Minimum Value(uint64_t): ");
> >    Put(UNSIGNED_LONG_INT'FIRST);
> >    New_Line;
> >    Put("Maximum Value(uint64_t): ");
> >    Put(UNSIGNED_LONG_INT'LAST);
> >    New_Line;
>
> >    test := -5;
>
> This shall not raise Constraint_Error. The result should be 2**64 - 5, see
> RM 4.5.4.
>
> It seems that Windows GCC 3.4.6 for GNAT GPL 2006 (20060522) has a bug here
> for 2**64 modulus. With lesser modulus it works correct.
>
> --
> Regards,
> Dmitry A. Kazakovhttp://www.dmitry-kazakov.de

Thank you for the input. This leaves me with 2 questions:
1.  If my input is 2**35, wouldn't this still render the Integer type
inaccurate? The goal is to be able to use 64 bit integers... I'm
referring to your example of UNSIGNED_LONG_INT := UNSIGNED_LONG_INT
(Integer'(X));
2.  If this is a bug, then what kind of maximum input should I ask for
as a work around? I can try this on my mac when I get home...

Thanks
Blaine

Re: Unsigned Integer Restraint Errors

[Randy Brukardt]

"frikk" <frikker@gmail.com> wrote in message
news:1173726806.656979.305660@8g2000cwh.googlegroups.com...
> Thank you for the input. This leaves me with 2 questions:
> 1.  If my input is 2**35, wouldn't this still render the Integer type
> inaccurate? The goal is to be able to use 64 bit integers... I'm
> referring to your example of UNSIGNED_LONG_INT := UNSIGNED_LONG_INT
> (Integer'(X));

The real problem here is that you are trying to use modular types in a
checked way. As others have noted, they're not really intended for that.
It's best to avoid using modular types such that they'll raise an exception.

Ada has signed, checked integers, and unsigned, unchecked integers. It
doesn't have unsigned, checked integers. That omission is only a problem if
you need checked, maximum range unsigned integers; usually, you should just
use an appropriate signed integer type:

type Really_Big_Unsigned_Int is range 0 .. 2**63-1;

This type will have the overflow and range checking you've looking for. Even
better is to replace the upper bound by something that is appropriate for
your application:

   Max_Widgets : constant := 2**40;
   type Widget_Count is range 0 .. Max_Widgets;

The only problem here is that your upper bound has to be somewhat smaller
than the maximum allowed. Given the immense range of 64-bit integers, I have
a hard time imagining a case where that would be a problem (it's rarely a
problem even for 32-bit integers).

Note that this sort of declaration will work on any Ada compiler that
supports 64-bit numbers, and if it doesn't, you'll get a convenient error
message.

                         Randy.

Re: Unsigned Integer Restraint Errors

[Jeffrey R. Carter]

Randy Brukardt wrote:
> 
> Ada has signed, checked integers, and unsigned, unchecked integers. It
> doesn't have unsigned, checked integers. That omission is only a problem if
> you need checked, maximum range unsigned integers; usually, you should just
> use an appropriate signed integer type:

 From one point of view, Ada has signed, checked integers:

type Signed_Checked_Byte is range -128 .. 127;

unsigned, checked integers:

type Unsigned_Checked_Byte is range 0 .. 255;
for Unsigned_Checked_Byte'Size use 8;

(with the limitation that the upper bound can't exceed System.Max_Int, 
which is generally < System.Max_Binary_Modulus - 1);

signed, unchecked integers:

type Signed_Unchecked_Byte is range -128 .. 127;
pragma Suppress (Overflow_Check, On => Signed_Unchecked_Byte);

and unsigned, unchecked integers:

type Unsigned_Unchecked_Byte is mod 256;

It seems odd that we use a different syntax for 1 of the 4 (yes, I 
understand that the implications of modular types go beyond the lack of 
overflow checks).

-- 
Jeff Carter
"That was the most fun I've ever had without laughing."
Annie Hall
43

Re: Unsigned Integer Restraint Errors

[Randy Brukardt]

"Jeffrey R. Carter" <jrcarter@acm.org> wrote in message
news:BFoJh.14542$PF.8157@attbi_s21...
> Randy Brukardt wrote:
> >
> > Ada has signed, checked integers, and unsigned, unchecked integers. It
> > doesn't have unsigned, checked integers. That omission is only a problem
if
> > you need checked, maximum range unsigned integers; usually, you should
just
> > use an appropriate signed integer type:
>
>  From one point of view, Ada has signed, checked integers:
>
> type Signed_Checked_Byte is range -128 .. 127;

Yes.

> unsigned, checked integers:
>
> type Unsigned_Checked_Byte is range 0 .. 255;
> for Unsigned_Checked_Byte'Size use 8;
>
> (with the limitation that the upper bound can't exceed System.Max_Int,
> which is generally < System.Max_Binary_Modulus - 1);

Yes; I explained this. System.Max_Int is usually approximately
System.Max_Binary_Modulus/2, which means that there may be some programs
that can't use this technique. (Doesn't seem that likely, though.)

> signed, unchecked integers:
>
> type Signed_Unchecked_Byte is range -128 .. 127;
> pragma Suppress (Overflow_Check, On => Signed_Unchecked_Byte);

These aren't unchecked in any useful sense:

(1) The On parameter to Suppress is an obsolescent feature in Ada (*);
it was so poorly defined that we gave up on it.
(2) In any case, Suppress is a suggestion to the compiler; there is no
requirement that checks are actually suppressed. A lot of compilers ignore
some or all "On" parameters.
(3) A violation of a suppressed check makes a program erroneous; whereas a
modular type has defined behavior. Thus any program that has correctness
concerns can't really use this technique (you can't verify a program that
includes erroneous execution, because *anything* can happen). The only time
this is legitimate is if there are known (or proved) to be no checking
failures in the program: but then there is by definition no difference
between checked and unchecked numbers.

> and unsigned, unchecked integers:
>
> type Unsigned_Unchecked_Byte is mod 256;
>
> It seems odd that we use a different syntax for 1 of the 4 (yes, I
> understand that the implications of modular types go beyond the lack of
> overflow checks).

And the supposedly unchecked signed type is not unchecked in any useful
way...the only difference might be to remove code generated to make checks,
and that isn't even guaranteed.

              Randy.

(*) ISO published the Amendment on March 9th. So Ada 95 is now
obsolete...and "Ada" includes the Amendment.

Re: Unsigned Integer Restraint Errors

[frikk]

On Mar 12, 11:00 pm, "Randy Brukardt" <r...@rrsoftware.com> wrote:
> "Jeffrey R. Carter" <jrcar...@acm.org> wrote in messagenews:BFoJh.14542$PF.8157@attbi_s21...
>
[...]
> (*) ISO published the Amendment on March 9th. So Ada 95 is now
> obsolete...and "Ada" includes the Amendment.

Thank you everyone for the responses. To clear things up - I am really
only using the 64 bit unsigned integers since it is defined in my
project spec as a requirement. This is more of an acedemic program,
not so much for practical use. I'm counting the number of 'on' bits in
any 64 bit unsigned integer and returning if there is a prime number
of them or not, as part of the requirement.

I've used the suggestions you guys have had and now have it working
the way I'd like.  Thanks again, you guys are always very helpful!

Thanks,
Blaine

Re: Unsigned Integer Restraint Errors

[frikk]

I have a bit of an unrelated (but kind of related) question:

Are there any builtin square root functions? I thought this was
working, but I don't think it is anymore:
m := Integer(100**(0.5)+1);

This always coming out to 2. I;m using this to computer a maximum loop
value for finding primes. I'd like to loop from 2 to sqrt(n)/2 + 1.

Any suggestions?

Re: Unsigned Integer Restraint Errors

[frikk]

On Mar 13, 10:58 am, "frikk" <frik...@gmail.com> wrote:
> I have a bit of an unrelated (but kind of related) question:
>
> Are there any builtin square root functions? I thought this was
> working, but I don't think it is anymore:
> m := Integer(100**(0.5)+1);
>
> This always coming out to 2. I;m using this to computer a maximum loop
> value for finding primes. I'd like to loop from 2 to sqrt(n)/2 + 1.
>
> Any suggestions?

Actually I need to specify - I really used (1/2), not (0.5). I'm not
sure how that got in the code I posted...

But this would mean that the (1/2) is being converted to an Int -
which would be 0.  anything ^ 0 = 1, and 1+1 = 2.  So there, I know
why it is happening.

But how else can I compute a square root?

Blaine

Re: Unsigned Integer Restraint Errors

[Robert A Duff]

"frikk" <frikker@gmail.com> writes:

> But how else can I compute a square root?

Look up Generic_Elementary_Functions and Elementary_Functions in the Ada
RM.  There is a sqrt function, a "**" function, and various other maths stuff.

- Bob

Re: Unsigned Integer Restraint Errors

[Dmitry A. Kazakov]

On 13 Mar 2007 08:31:33 -0700, frikk wrote:

> On Mar 13, 10:58 am, "frikk" <frik...@gmail.com> wrote:
>> I have a bit of an unrelated (but kind of related) question:
>>
>> Are there any builtin square root functions? I thought this was
>> working, but I don't think it is anymore:
>> m := Integer(100**(0.5)+1);

See A.5.1 Ada.Numerics.Elementary_Functions it has sqrt and ** with the
right argument of Float.

>> This always coming out to 2. I;m using this to computer a maximum loop
>> value for finding primes. I'd like to loop from 2 to sqrt(n)/2 + 1.

Actually, you don't need sqrt for this, and alternative could be do loop
until the loop index I is such that

   I <= sqrt(n)/2+1

which is equivalent to

   I := 2;
   while 4*(I-1)*(I-1) <= n loop
      ...
      I := I + 1;
   end loop;

> Actually I need to specify - I really used (1/2), not (0.5). I'm not
> sure how that got in the code I posted...

The code you provided is illegal. In Ada you cannot mix types.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Unsigned Integer Restraint Errors

[Jeffrey R. Carter]

frikk wrote:
> On Mar 13, 10:58 am, "frikk" <frik...@gmail.com> wrote:
>>
>> m := Integer(100**(0.5)+1);
>>
> Actually I need to specify - I really used (1/2), not (0.5). I'm not
> sure how that got in the code I posted...
> 
> But this would mean that the (1/2) is being converted to an Int -
> which would be 0.  anything ^ 0 = 1, and 1+1 = 2.  So there, I know
> why it is happening.

1/2 is an integer expression, and unless you've redefined "/", it 
truncates towards zero. So you're correct; 1/2 = 0.

> But how else can I compute a square root?

Take a look at the standard library in Annex A, especially Ada.Numerics 
(A.5) and its children. You might find A.5.1, "Elementary Functions", 
helpful.

-- 
Jeff Carter
"If you don't get the President of the United States on that
phone, ... you're going to have to answer to the Coca-Cola
Company."
Dr. Strangelove
32

Re: Unsigned Integer Restraint Errors

[Adam Beneschan]

On Mar 13, 7:58 am, "frikk" <frik...@gmail.com> wrote:
> I have a bit of an unrelated (but kind of related) question:
>
> Are there any builtin square root functions? I thought this was
> working, but I don't think it is anymore:
> m := Integer(100**(0.5)+1);

This couldn't have worked as written, since there is no predefined
"**" that accepts a floating-point number on the right side.

> This always coming out to 2. I;m using this to computer a maximum loop
> value for finding primes. I'd like to loop from 2 to sqrt(n)/2 + 1.
>
> Any suggestions?

See Section A.5.1.  Ada.Numerics.Elementary_Functions (A.5.1(9))
defines Sqrt as well as a "**" that accepts floating-point exponents.

By the way, if I were going to write a loop that goes from 2 to
sqrt(n)/2 + 1, I wouldn't use Sqrt like this:

    for I in 2 .. Integer(Float'Floor(Sqrt(Float(N))/2.0)) + 1 loop...

but rather, I'd just write it something like this:

    I := 2;
    while (2 * I - 1) * (2 * I - 1) <= N loop -- I think I got this
right
        ...
        I := I + 1;
    end loop;

on the theory that using Sqrt is just a waste of cycles when you can
just use integer arithmetic.  But I've been programming for way too
long---long enough that I remember what a Hollerith card is---and I'm
sure that doing a square-root doesn't take nearly as long as it used
to, so there are probably some reasonable values of N for which
computing the square-root first makes things more efficient than the
repeated integer multiplications.  I don't know.  Use Sqrt if you want
to.

                                 -- Adam

Re: Unsigned Integer Restraint Errors

[Adam Beneschan]

On Mar 13, 9:04 am, "Adam Beneschan" <a...@irvine.com> wrote:

> By the way, if I were going to write a loop that goes from 2 to
> sqrt(n)/2 + 1, I wouldn't use Sqrt like this:
>
>     for I in 2 .. Integer(Float'Floor(Sqrt(Float(N))/2.0)) + 1 loop...
>
> but rather, I'd just write it something like this:
>
>     I := 2;
>     while (2 * I - 1) * (2 * I - 1) <= N loop -- I think I got this
> right

No, I didn't.  Jeff did.  I must have read (sqrt(n)+1)/2 or
something.  Oops.

                                 -- Adam

Re: Unsigned Integer Restraint Errors

[Adam Beneschan]

On Mar 13, 9:41 am, "Adam Beneschan" <a...@irvine.com> wrote:
> On Mar 13, 9:04 am, "Adam Beneschan" <a...@irvine.com> wrote:
>
> > By the way, if I were going to write a loop that goes from 2 to
> > sqrt(n)/2 + 1, I wouldn't use Sqrt like this:
>
> >     for I in 2 .. Integer(Float'Floor(Sqrt(Float(N))/2.0)) + 1 loop...
>
> > but rather, I'd just write it something like this:
>
> >     I := 2;
> >     while (2 * I - 1) * (2 * I - 1) <= N loop -- I think I got this
> > right
>
> No, I didn't.  Jeff did.  I must have read (sqrt(n)+1)/2 or
> something.  Oops.

Ooops again---I meant Dmitry, not Jeff.  Wow, I'm off to a really good
start today.

                             -- Adam

Re: Unsigned Integer Restraint Errors

[frikk]

On Mar 13, 12:42 pm, "Adam Beneschan" <a...@irvine.com> wrote:
> On Mar 13, 9:41 am, "Adam Beneschan" <a...@irvine.com> wrote:
>
> > On Mar 13, 9:04 am, "Adam Beneschan" <a...@irvine.com> wrote:
>
> > > By the way, if I were going to write a loop that goes from 2 to
> > > sqrt(n)/2 + 1, I wouldn't use Sqrt like this:
>
> > >     for I in 2 .. Integer(Float'Floor(Sqrt(Float(N))/2.0)) + 1 loop...
>
> > > but rather, I'd just write it something like this:
>
> > >     I := 2;
> > >     while (2 * I - 1) * (2 * I - 1) <= N loop -- I think I got this
> > > right
>
> > No, I didn't.  Jeff did.  I must have read (sqrt(n)+1)/2 or
> > something.  Oops.
>
> Ooops again---I meant Dmitry, not Jeff.  Wow, I'm off to a really good
> start today.
>
>                              -- Adam

It seems we're all a little bit fuzzy - I actually mean sqrt(n)+1 ...
why I put sqrt(n)/2+1 is beyond me.

Thank you for the great information everyone.  I like the idea of
doing the integer arithmetic better than the square root anyway.

I ended up doing this:

I = 2;
while (I)*(I) <= N loop
 ... I = I+1;

Thanks!
Blaine

Re: Unsigned Integer Restraint Errors

[Dmitry A. Kazakov]

On 13 Mar 2007 09:04:14 -0700, Adam Beneschan wrote:

> on the theory that using Sqrt is just a waste of cycles when you can
> just use integer arithmetic.  But I've been programming for way too
> long---long enough that I remember what a Hollerith card is

... and what was the Hollerith format of strings? (:-))

>---and I'm
> sure that doing a square-root doesn't take nearly as long as it used
> to, so there are probably some reasonable values of N for which
> computing the square-root first makes things more efficient than the
> repeated integer multiplications.  I don't know.  Use Sqrt if you want
> to.

(for very large number like in infinite arithmetic it could become an
issue)

BTW, the arithmetic complexity can be further "reduced" by removing
multiplication and computing k**2 using binomial decomposition
(k+1)*(k+1)=k*k+2*k+1. So it could be:

quadratic := 1; -- k*k, k=1
linear := 2; -- 2*k+1, k=1

loop
   linear := linear + 2; -- 2*k+1
   quadratic := quadratic + linear; -- k*k
   exit when k>=n;
   ...
end loop;

Whether this really would be any faster than multiplication or square root
computed once, God knows...

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Unsigned Integer Restraint Errors

[Adam Beneschan]

On Mar 13, 10:23 am, "Dmitry A. Kazakov" <mail...@dmitry-kazakov.de>
wrote:

>
> BTW, the arithmetic complexity can be further "reduced" by removing
> multiplication and computing k**2 using binomial decomposition
> (k+1)*(k+1)=k*k+2*k+1. So it could be:
>
> quadratic := 1; -- k*k, k=1
> linear := 2; -- 2*k+1, k=1
>
> loop
>    linear := linear + 2; -- 2*k+1
>    quadratic := quadratic + linear; -- k*k
>    exit when k>=n;
>    ...
> end loop;

Yep, that's certainly the way I'd do it on some of the *really* bare-
bones computers I occasionally had to work with---like the 6502 (used
in the Apple II).  Some of those chips, including the 6502, didn't
come with integer multiplication or division.

                                 -- Adam

Re: Unsigned Integer Restraint Errors

[Jeffrey R. Carter]

Dmitry A. Kazakov wrote:
> 
> ... and what was the Hollerith format of strings? (:-))

9HLIKE THIS

Those were the good old days! Why anyone would want to use a convenient 
notation such as "Like this" is beyond me.

-- 
Jeff Carter
"If you don't get the President of the United States on that
phone, ... you're going to have to answer to the Coca-Cola
Company."
Dr. Strangelove
32

Re: Unsigned Integer Restraint Errors

[frikk]

On Mar 13, 1:23 pm, "Dmitry A. Kazakov" <mail...@dmitry-kazakov.de>
wrote:
> On 13 Mar 2007 09:04:14 -0700, Adam Beneschan wrote:
>
> > on the theory that using Sqrt is just a waste of cycles when you can
> > just use integer arithmetic.  But I've been programming for way too
> > long---long enough that I remember what a Hollerith card is
>
> ... and what was the Hollerith format of strings? (:-))
>
> >---and I'm
> > sure that doing a square-root doesn't take nearly as long as it used
> > to, so there are probably some reasonable values of N for which
> > computing the square-root first makes things more efficient than the
> > repeated integer multiplications.  I don't know.  Use Sqrt if you want
> > to.
>
> (for very large number like in infinite arithmetic it could become an
> issue)
>
> BTW, the arithmetic complexity can be further "reduced" by removing
> multiplication and computing k**2 using binomial decomposition
> (k+1)*(k+1)=k*k+2*k+1. So it could be:
>
> quadratic := 1; -- k*k, k=1
> linear := 2; -- 2*k+1, k=1
>
> loop
>    linear := linear + 2; -- 2*k+1
>    quadratic := quadratic + linear; -- k*k
>    exit when k>=n;
>    ...
> end loop;
>
> Whether this really would be any faster than multiplication or square root
> computed once, God knows...
>
> --
> Regards,
> Dmitry A. Kazakovhttp://www.dmitry-kazakov.de

That's very cool. I've had the opportunity to work with algorithms
like that.  You guys have definitely made me think about what it takes
to break down an algorithm into more simple parts.

Thanks!
Blaine

Re: Unsigned Integer Restraint Errors

[Jeffrey R. Carter]

Randy Brukardt wrote:
> 
> And the supposedly unchecked signed type is not unchecked in any useful
> way...the only difference might be to remove code generated to make checks,
> and that isn't even guaranteed.
> 
>               Randy.
> 
> (*) ISO published the Amendment on March 9th. So Ada 95 is now
> obsolete...and "Ada" includes the Amendment.

Yes, I should have said "Ada 95", since I haven't looked at everything 
in the new standard yet, specifically suppressing checks. Now that I 
have looked at that section, I see that Ada (used properly this time) no 
longer has a way to specify a desire for unchecked, signed integer types 
(except Annex J). Suppressing overflow checks in general is not the same 
thing.

It may take me time to get used to the name change; at least I'm not 
writing 2006 for the date anymore ...

Perhaps if we were starting from scratch we could do something like

type T is range Min .. Max;

If Min is negative, T'Base is a signed type; otherwise, T'Base is an 
unsigned type.

There would be a pragma, something like

pragma Unchecked_Integer (T);

which would give T'Base the semantics of an Ada modular type if T'Base 
is unsigned. It would have a similar effect if T'Base is signed, which 
could be defined in Ada terms as unchecked converting the value to a 
modular type of the same size, performing operations with that modular 
type, and unchecked converting back to T'Base.

I just made this up, so I'm sure there are things I haven't considered. 
I'm assuming 2s-complement signed integers, for one thing.

-- 
Jeff Carter
"If you don't get the President of the United States on that
phone, ... you're going to have to answer to the Coca-Cola
Company."
Dr. Strangelove
32

Re: Unsigned Integer Restraint Errors

[Dmitry A. Kazakov]

On 12 Mar 2007 12:13:26 -0700, frikk wrote:

> Thank you for the input. This leaves me with 2 questions:
> 1.  If my input is 2**35, wouldn't this still render the Integer type
> inaccurate? The goal is to be able to use 64 bit integers... I'm
> referring to your example of UNSIGNED_LONG_INT := UNSIGNED_LONG_INT
> (Integer'(X));

I don't understand what are you trying to achieve. Where the input comes
from, and what type it has. I see only two possibilities:

1. The input type is UNSIGNED_LONG_INT, where is the problem? It is in the
range. -5 in your example is not a number, it is an expression of
UNSIGNED_LONG_INT and its result is in the range of. If the semantics of
"-" bothers you, redefine it:

   function "-" (Left : UNSIGNED_LONG_INT) return UNSIGNED_LONG_INT is
   begin
      if Left = 0 then
         return Left;
      else
         raise Constraint_Error; -- No wrapping
      end if;
   end "-";

or else disallow it altogether:

   function "-" (Left : UNSIGNED_LONG_INT) return UNSIGNED_LONG_INT
       is abstract;

2. The type is some different type. You have to convert it to
UNSIGNED_LONG_INT and if its value is outside UNSIGNED_LONG_INT'Range you
will get Constraint_Error. Again, no problem in sight.

It is safe in all cases.

-------
When you use Integer, it is to expect that on most machines
Integer'Last<System.Max_Binary_Modulus. But, again, I probably don't
understand your problem, because I don't see in the first place why you
wanted to convert signed integers to modular integers. As Randy has already
suggested, declare it signed natural and enjoy range checks.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de