Integer overflow

[Izaak_Beekman]

Please note I have corrected the typo in the thread title. 10:20 AM EST 6-11-2010

Simple question: Does anyone know if the standard specifies what happens when integers overflow? Through some experimentation with intel 11.1.046 it looks like the value of the integer seems to wrap around. i.e

[fortran]PROGRAM int_explode
IMPLICIT NONE
INTEGER :: my_int

my_int = HUGE(my_int)
PRINT*, my_int
my_int = my_int + 1
PRINT*, my_int
PRINT*, -HUGE(my_int) - 1
IF ( my_int == -HUGE(my_int - 1) PRINT*, 'Integer overflow wraps around.'
END PROGRAM[/fortran]

Is thisbehaviorspecified by the standard, or will relying on it result in non-portable code?

Many thanks,

-Z

[Steven_L_Intel1 · Accepted solution]

The standard does not specify the behavior of such a thing. The standard does descirbe the "model" for integer data types, but that only holds as long as your computations are within the model range. You cannot depend on the behavior of code such as you show. In particular, the standard's model of integers is that the model range is symmetric around zero, which typical twos-complement binary is not. You have undoubtedly noticed that -HUGE(my_int) is not the most negative integer value.

Intel Fortran does not have integer overflow detection.

[Izaak_Beekman]

Thank you so much for your reply Steve, I really appreciate it. I guess I will have to think carefully about how to implement the hash function I am working on.

-Z

[jimdempseyatthecove]

To expand on Steves reply:

Two's compliment arithmitic yields

my_int = HUGE(my_int)
if(my_int .ne. 0) print "this will print"
my_int = my_int + 1
if(my_int .ne. 0) print "this will print"
if(my_int .lt. 0) print "this will print (integer overflow)"
if(my_int .eq. -my_int) print "this will print"

The integer overflow wraps to the largest negative number.
Depending on your deffinition of 0, this may also be -0.

Jim

[Izaak_Beekman]

Thanks Jim,
I know what two's complement arithmatic is ;-)
-Z

[Steven_L_Intel1]

Compliments are always welcome, but note that we're discussing two's complement arithmetic. :D

[Izaak_Beekman]

Spelling errors? Me!? Never!

[TimP]

If you require standard defined behavior with wrap, you must use C unsigned int, preferably C99 uint64_t . As ifort (like most Fortran compilers) has no unsigned integer, you must take care in accordance with these data types being reinterpreted as signed when seen from Fortran.

[jimdempseyatthecove]

Quoting zbeekman

Thank you so much for your reply Steve, I really appreciate it. I guess I will have to think carefully about how to implement the hash function I am working on.

-Z

Implement your hash functions in C

Or stay in Fortran but implement as user defined type with "member functions" for generation, manipulation, comparisons etc... (forcing you to use module routines as opposed to integer functions/expressions)

Jim

[Steven_L_Intel1]

Or compute in INTEGER(8) and mask off the upper bits? I don't know if that helps.

[Izaak_Beekman]

It seems to me that hash functions are just a deterministic bit scrambling. The goal is to take objects which might be similar or related (i.e. have a nearly matching machine representation) and to scater in a uniform distribution, avoiding collisions. In this regard they seem to be akin to random number generators. After some quick research it looks like perhaps I can use the transfer function to transfer strings (in chunks of 4 characters) to integers (4 Byte integers). From this array of integers, I could use bit manipulations to mix the bits up and reduce the arry of integers to a single integer, then perform the modular division. This is akin to the "Marsaglia shift register" random number generation technique. The bit manipulation functions should be fast, and efficient and mixing in all the information in the string. If anyone has doubts about this approach please let me know. I am going to do some testing and report back on what I find.

[msbriggs]

Several possibilities:

For portability, as already suggested, implement in C.

Or, Michel Olagnon has a Fortran module to provide a 32-bit unsigned type: look for unsi32.f90.Z at http://www.ifremer.fr/ditigo/molagnon/fortran90/engfaq.html or ftp://ftp.ifremer.fr/ifremer/ditigo/fortran90/. I haven't tested it, can't say anything about the speed, etc.

While integer overflow goes beyond the standard, the overflow behavior of unsigned integers will be extremely common, approaching universal, though not guaranteed. Once you have done your calculation, you can assign the result to a larger integer type. Then either mask off the bits (suggested above), or if the value is negative, add a correcting offset. Depending on your needs re guaranteed portability, this method might work.

I wish that Fortran had unsigned integers.... in my work I have several uses. Apparently the standard's committee has declined to add them despite numerous requests. One compiler has them as an extension.

[fortran]
program IntTest

   implicit none
   
   integer, parameter :: Int32 = selected_int_kind (8)
   integer, parameter :: Int64 = selected_int_kind (18)
   
   integer (Int32) :: RegularInt
   integer (Int64) :: BigInt1, BigInt2
   
   write (*, *) huge (RegularInt), huge (BigInt1)
   
   RegularInt = 2147483645
   RegularInt = RegularInt + 10;
   BigInt1 = RegularInt
   BigInt2 = RegularInt
   if (BigInt1 < 0) BigInt1 = BigInt1 + 4294967296_Int64
   BigInt2 = iand ( BigInt2, int (Z'FFFFFFFF', Int64) )
   write (*, *) RegularInt, BigInt1, BigInt2
   
   
   RegularInt = 2147483645
   RegularInt = 2 * RegularInt + 10;
   BigInt1 = RegularInt
   BigInt2 = RegularInt
   if (BigInt1 < 0) BigInt1 = BigInt1 + 4294967296_Int64
   BigInt2 = iand ( BigInt2, int (Z'FFFFFFFF', Int64) )
   write (*, *) RegularInt, BigInt1, BigInt2
   

   stop

end program IntTest[/fortran]
 

Compare the results to:

[cpp]#include 
#include 

int main (void) {

   uint32_t  RegularInt1, RegularInt2;

   RegularInt1 = 2147483645;
   RegularInt2 = RegularInt1 + 10;
   printf ( "%un", RegularInt2 );
   
   
   RegularInt1 = 2147483645;
   RegularInt2 = 2 * RegularInt1 + 10;
   printf ( "%un", RegularInt2 );
   
   return 0;

}[/cpp]

[Izaak_Beekman]

I agree, it would be a nice addition. I have decided to approach hashing using bit manipulation rather than the linear congruential generator approach. This way I can ensure a thorough mixing of bits without worrying about holes in the standard and integer overflow. But thanks for your post!

[msbriggs]

With the extension, the Fortran code for unsigned integers becomes as simple as the C:

program SunIntTest

   implicit none
   
   integer, parameter :: Int32 = selected_int_kind (8)
   
   integer (Int32) :: RegularInt
   unsigned (kind=4) :: UnsignedInt32
   
   write (*, *) huge (RegularInt), huge (UnsignedInt32)
   
   UnsignedInt32 = 2147483645U_4
   UnsignedInt32 = UnsignedInt32 + 10U_4;
   write (*, *) UnsignedInt32
   
   UnsignedInt32 = 2147483645U_4
   UnsignedInt32 = 2U_4 * UnsignedInt32 + 10U_4;
   write (*, *) UnsignedInt32
   
   stop

end program SunIntTest


The output is:

 2147483647 4294967295
2147483655
4


Intel, any interest in also adding this extension?   Maybe if enough vendors did, it would get added to the standard. 
Unsigned integers would make it easier to write certain algorithms and data handlers.

[Steven_L_Intel1]

At this time we are not interested in adding this extension. The standards committee has debated this one quite a bit and rejected it. I don't see that changing anytime soon. We have our hands quite full just finishing the standard.