Modular integers

Modular integers

[Lars]

Hi,

I was able to create an unsigned 64-bit integer using

    type unsigned_64_bit_integer is mod 2**64;

Then I defined a subtype:

    subtype safe_unsigned_64_bit_integer is unsigned_64_bit_integer range 0
.. 2**64-1;

When a variable of type unsigned_64_bit_integer contains 2**64-1 and you add
1, it is "reset" to 0, as expected.
When a variable of type safe_unsigned_64_bit_integer contains 2**64-1 and
you add 1, no exception is raised and it is "reset" to 0.

Why is that? Shouldn't the compiler be able to insert a check that throws an
exception if an overflow occurs?

-Lars

Re: Modular integers

[David C. Hoos]

"Lars" <lars-remove_me-m@gmx.net> wrote in message
news:bnlmg1$kqv$04$1@news.t-online.com...
> Hi,
>
> I was able to create an unsigned 64-bit integer using
>
>     type unsigned_64_bit_integer is mod 2**64;
>
> Then I defined a subtype:
>
>     subtype safe_unsigned_64_bit_integer is unsigned_64_bit_integer range
0
> .. 2**64-1;
>
> When a variable of type unsigned_64_bit_integer contains 2**64-1 and you
add
> 1, it is "reset" to 0, as expected.
> When a variable of type safe_unsigned_64_bit_integer contains 2**64-1 and
> you add 1, no exception is raised and it is "reset" to 0.
>
> Why is that? Shouldn't the compiler be able to insert a check that throws
an
> exception if an overflow occurs?

No.  By definition modular numbers cannot "overflow."  In fact, to say the
value
is "reset" to 0 is incorrect.  0 simply follows 2**64 - 1.

You can declare a _signed_ 64-bit integer type which will overflow when
adding
1 to 2**63-1, or underflow when subtracting 1 from -(2**63).

>
> -Lars
>
>
> _______________________________________________
> comp.lang.ada mailing list
> comp.lang.ada@ada-france.org
> http://www.ada-france.org/mailman/listinfo/comp.lang.ada
>
>

Re: Modular integers

[Lars]

Yes, it is not "reset".  I don't know a better word to describe it ...

Why couldn't the compiler insert code that checks what the upper limit of
the type is, then substracts the current value of the variable from the
upper limit to see if the difference is bigger or equal to the number you
want to add? If it is not, it could throw an exception ...


> No.  By definition modular numbers cannot "overflow."  In fact, to say the
> value
> is "reset" to 0 is incorrect.  0 simply follows 2**64 - 1.
>
> You can declare a _signed_ 64-bit integer type which will overflow when
> adding
> 1 to 2**63-1, or underflow when subtracting 1 from -(2**63).

Re: Modular integers

[Vinzent 'Gadget' Hoefler]

Lars wrote:

>Why couldn't the compiler insert code that checks what the upper limit of
>the type is,

It does, if necessary. AFAICS in your case it isn't: The upper limit
of your subtype is the same as that of the base type which is a
modular type.

So where would you expect the overflow? You don't get rid of the
modulo-operation just by defining a sub type.

>then substracts the current value of the variable from the
>upper limit to see if the difference is bigger or equal to the number you
>want to add? If it is not, it could throw an exception ...

Why should it? No thinkable result of the modulo 2**64 operation would
overflow your new range constraint for the subtype:

IOW: "(A + 1) mod 2**64 in 0 .. 2**64 - 1" is always true.

But try this with a subtype with a range only up to 2**64 - 2, this
*will* give you the expected overflow:

|with Ada.Text_IO;
|
|procedure t is
|   type    X_Base is mod 2**64;
|   subtype X_1    is X_Base range 0 .. 2**64 - 1;
|   subtype X_2    is X_Base range 0 .. 2**64 - 2;
|
|   A : X_Base;
|   B : X_1;
|   C : X_2;
|
|begin
|   A := X_Base'Last;
|   Ada.Text_IO.Put (X_Base'Image (A));
|   A := A + 1;
|   Ada.Text_IO.Put (X_Base'Image (A));
|   
|   B := X_1'Last;
|   Ada.Text_IO.Put (X_Base'Image (B));
|   B := B + 1;
|   Ada.Text_IO.Put (X_Base'Image (B));
|   
|   C := X_2'Last;
|   Ada.Text_IO.Put (X_Base'Image (C));
|   C := C + 1;
|   Ada.Text_IO.Put (X_Base'Image (C));
|end t;

compiled with GNAT3.15p gives:

| 18446744073709551615 0 18446744073709551615 0 18446744073709551614
|
|raised CONSTRAINT_ERROR : t.adb:25 range check failed

Isn't that the expected result?


Vinzent.

Re: Modular integers

[Lars]

>> Isn't that the expected result?

Thank you Vinzent! Oddly enough it seems totally self-explanatory now ...
I have totally forgotten which misconception had bothered me.

And yes, I agree, "Ada rocks!"

Re: Modular integers

[David C. Hoos]

"Lars" <lars-remove_me-m@gmx.net> wrote in message
news:bnloh2$q3d$03$1@news.t-online.com...
> Yes, it is not "reset".  I don't know a better word to describe it ...

How about "wraps" or "wraps around"?

>
> Why couldn't the compiler insert code that checks what the upper limit of
> the type is, then substracts the current value of the variable from the
> upper limit to see if the difference is bigger or equal to the number you
> want to add? If it is not, it could throw an exception ...
It cannot raise an exception because the langeage definition (RM95 3.5.4)
defines
a modular type as one in which all arithmetic is _modulo_ the specified
modulus --
i.e. with "wrap-around" semantics.

>
>
> > No.  By definition modular numbers cannot "overflow."  In fact, to say
the
> > value
> > is "reset" to 0 is incorrect.  0 simply follows 2**64 - 1.
> >
> > You can declare a _signed_ 64-bit integer type which will overflow when
> > adding
> > 1 to 2**63-1, or underflow when subtracting 1 from -(2**63).
>
>
> _______________________________________________
> comp.lang.ada mailing list
> comp.lang.ada@ada-france.org
> http://www.ada-france.org/mailman/listinfo/comp.lang.ada
>

Re: Modular integers

[Lars]

> How about "wraps" or "wraps around"?

Roger that.

Raising exceptions (was: Modular integers)

[Jeffrey Carter]

Lars wrote:

> Why is that? Shouldn't the compiler be able to insert a check that throws an
> exception if an overflow occurs?

This is Ada. Exceptions are raised, and then, we hope, handled. 
Throw/catch is used in inferior languages, which also require an extra 
construct (try/catch) that Ada does not.

-- 
Jeff Carter
"We burst our pimples at you."
Monty Python & the Holy Grail
16

Re: Raising exceptions

[Hyman Rosen]

Jeffrey Carter wrote:
> Throw/catch is used in inferior languages

I agree with this. Common Lisp always seemed like a
poor alternative to Scheme.

Re: Modular integers

[Vinzent 'Gadget' Hoefler]

Lars wrote:

>>> Isn't that the expected result?
>
>Thank you Vinzent! Oddly enough it seems totally self-explanatory now ...
>I have totally forgotten which misconception had bothered me.

Well, I thought about what I wrote and became unsure about it. ;)

So to  prove my point I enhanced the little test program:

|with Ada.Text_IO;
|
|procedure t is
|   type    X_Base is mod 2**64;
|   subtype X_1    is X_Base range 0 .. 2**64 - 1;
|   subtype X_2    is X_Base range 0 .. 2**64 - 2;
|
|   A : X_Base;
|   B : X_1;
|   C : X_2;
|
|begin
|   begin
|      Ada.Text_IO.Put ("A'Last + 1: ");
|      A := X_Base'Last;
|      Ada.Text_IO.Put (X_Base'Image (A));
|      A := A + 1;
|      Ada.Text_IO.Put (X_Base'Image (A));
|   exception
|      when Constraint_Error =>
|         Ada.Text_IO.Put (" Constraint_Error");
|   end;
|
|   Ada.Text_IO.New_Line;
|
|   begin
|      Ada.Text_IO.Put ("B'Last + 1: ");
|      B := X_1'Last;
|      Ada.Text_IO.Put (X_Base'Image (B));
|      B := B + 1;
|      Ada.Text_IO.Put (X_Base'Image (B));
|   exception
|      when Constraint_Error =>
|         Ada.Text_IO.Put (" Constraint_Error");
|   end;
|
|   Ada.Text_IO.New_Line;
|
|   begin
|      Ada.Text_IO.Put ("C'Last + 1: ");
|      C := X_2'Last;
|      Ada.Text_IO.Put (X_Base'Image (C));
|      C := C + 1;
|      Ada.Text_IO.Put (X_Base'Image (C));
|   exception
|      when Constraint_Error =>
|         Ada.Text_IO.Put (" Constraint_Error");
|   end;
|
|   Ada.Text_IO.New_Line;
|
|   begin
|      Ada.Text_IO.Put ("C'Last + 2: ");
|      C := X_2'Last;
|      Ada.Text_IO.Put (X_Base'Image (C));
|      C := C + 2;
|      Ada.Text_IO.Put (X_Base'Image (C));
|   exception
|      when Constraint_Error =>
|         Ada.Text_IO.Put (" Constraint_Error");
|   end;
|end t;

The output is as I hoped, if not to say "as I expected", but IMO quite
interesting:

|A'Last + 1:  18446744073709551615 0
|B'Last + 1:  18446744073709551615 0
|C'Last + 1:  18446744073709551614 Constraint_Error
|C'Last + 2:  18446744073709551614 0

As you can see, the behaviour of the subtype is absolutely correct,
although it might not be intuitive. I mean, adding 1 raises a
constraint error while adding 2 (or even more, try it) doesn't.

So what we get here is a modular type with range constraints. *That's*
interesting... :-)


Vinzent.

Re: Modular integers

[Jean-Pierre Rosen]

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


>"Vinzent 'Gadget' Hoefler" <ada.rocks@jlfencey.com> a �crit dans le message de
news:bnntu1$13vcju$1@ID->175126.news.uni-berlin.de...
>As you can see, the behaviour of the subtype is absolutely correct,
>although it might not be intuitive. I mean, adding 1 raises a
>constraint error while adding 2 (or even more, try it) doesn't.
>
>So what we get here is a modular type with range constraints. *That's*
>interesting... :-)

The key to understanding this behaviour is that an expression is computed in its base type (not the expected subtype), and then
converted to the expected subtype (which can raise Constraint_Error).

Therefore, Constraint_Error is raised if the final value of the expression is incompatible with the constraint,
but not during intermediate computations.

-- 
---------------------------------------------------------
           J-P. Rosen (rosen@adalog.fr)
Visit Adalog's web site at http://www.adalog.fr

Re: Modular integers

[Vinzent 'Gadget' Hoefler]

Jean-Pierre Rosen wrote:

>>"Vinzent 'Gadget' Hoefler" <ada.rocks@jlfencey.com> a écrit dans le message de
>news:bnntu1$13vcju$1@ID->175126.news.uni-berlin.de...
>
>>So what we get here is a modular type with range constraints. *That's*
>>interesting... :-)
>
>The key to understanding this behaviour is that an expression is
>computed in its base type (not the expected subtype), and then
>converted to the expected subtype (which can raise Constraint_Error).

Yes. That is what I was thinking of last night before I fell asleep. I
just wanted to verify that.

And as always, Ada didn't disappoint me. Good girl. :-)


Vinzent.