www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Is there a formula for overflow?

reply thebluepandabear <therealbluepandabear protonmail.com> writes:
I am reading through Ali's book about D, and he gives the 
following examples for an overflow:

```D
import std.stdio;
void main() {
// 3 billion each
uint number_1 = 3000000000;
uint number_2 = 3000000000;
}
writeln("maximum value of uint: ", uint.max);
writeln("
  number_1: ", number_1);
writeln("
  number_2: ", number_2);
writeln("
  sum: ", number_1 + number_2);
writeln("OVERFLOW! The result is not 6 billion!");
```

The result overflows and is 1705032704.

Also for the second example, it overflows and comes up with the 
value of 4294967286:

```D
void main() {
uint number_1 = 10;
uint number_2 = 20;
writeln("PROBLEM! uint cannot have negative values:");
writeln(number_1 - number_2);
writeln(number_2 - number_1);
}
```

Also a fun one, the following produces 4294967295:

```D
uint number = 1;
writeln("negation: ", -number);
```

But the book doesn't talk about why the D compiler came up with 
these results (and it also goes for division/multiplication) for 
the overflow (or maybe it did further down ?), as in it didn't 
talk about the formula it used for calculating this value.

I am curious as to what formula the D compiler uses for 
calculating 'overflowed' values, if such thing exists? :)

Regards,
thebluepandabear
Nov 29 2022
next sibling parent reply Basile B. <b2.temp gmx.com> writes:
On Wednesday, 30 November 2022 at 03:07:44 UTC, thebluepandabear 
wrote:

 I am reading through Ali's book about D, and he gives the 
 following examples for an overflow:

 ```D
 import std.stdio;
 void main() {
 // 3 billion each
 uint number_1 = 3000000000;
 uint number_2 = 3000000000;
 }
 writeln("maximum value of uint: ", uint.max);
 writeln("
  number_1: ", number_1);
 writeln("
  number_2: ", number_2);
 writeln("
  sum: ", number_1 + number_2);
 writeln("OVERFLOW! The result is not 6 billion!");
 ```


writeln((3000000000LU + 3000000000LU) % uint.max);


 The result overflows and is 1705032704.

 Also for the second example, it overflows and comes up with the 
 value of 4294967286:

 ```D
 void main() {
 uint number_1 = 10;
 uint number_2 = 20;
 writeln("PROBLEM! uint cannot have negative values:");
 writeln(number_1 - number_2);
 writeln(number_2 - number_1);
 }
 ```

 Also a fun one, the following produces 4294967295:

 ```D
 uint number = 1;
 writeln("negation: ", -number);
 ```


writeln( cast(uint) -(cast(int)1) );


 But the book doesn't talk about why the D compiler came up with 
 these results (and it also goes for division/multiplication) 
 for the overflow (or maybe it did further down ?), as in it 
 didn't talk about the formula it used for calculating this 
 value.

 I am curious as to what formula the D compiler uses for 
 calculating 'overflowed' values, if such thing exists? :)

 Regards,
 thebluepandabear


It's always a wraparound (think modulo) but your examples with 
negative number can be explained because there are hidden 
unsigned to signed implicit convertions.
That the only special things D does.
Nov 29 2022
next sibling parent Basile B. <b2.temp gmx.com> writes:
On Wednesday, 30 November 2022 at 03:19:49 UTC, Basile B. wrote:

 [...]
 It's always a wraparound (think modulo) but your examples with 
 negative number can be explained because there are hidden 
 unsigned to signed implicit convertions.
 That the only special things D does.


forgot to say, you can use the dmd flag -vcg-ast to see the 
hidden rewrites
Nov 29 2022
prev sibling parent Siarhei Siamashka <siarhei.siamashka gmail.com> writes:
On Wednesday, 30 November 2022 at 03:19:49 UTC, Basile B. wrote:

 writeln((3000000000LU + 3000000000LU) % uint.max);


It's actually

     writeln((3000000000LU + 3000000000LU) % (uint.max.to!ulong + 
1));

or

     writeln((3000000000LU + 3000000000LU) & uint.max);
Nov 29 2022
prev sibling next sibling parent reply Salih Dincer <salihdb hotmail.com> writes:
On Wednesday, 30 November 2022 at 03:07:44 UTC, thebluepandabear 
wrote:

 I am curious as to what formula the D compiler uses for 
 calculating 'overflowed' values, if such thing exists? :)

 Regards,
 thebluepandabear


**Source:** 
http://ddili.org/ders/d.en/cast.html?#ix_cast.arithmetic%20conversion

1. If one of the values is real, then the other value is 
converted to **real**
2. Else, if one of the values is **double**, then the other value 
is converted to **double**
3. Else, if one of the values is **float**, then the other value 
is converted to **float**
4. Else, first integer promotions are applied according to the 
table above, and then the following rules are followed:
**A.** If both types are the same, then no more steps needed
**B.** If both types are signed or both types are unsigned, then 
the narrower value is converted to the wider type
**C.** If the signed type is wider than the unsigned type, then 
the unsigned value is converted to the signed type
**D.** Otherwise the signed type is converted to the unsigned type

SDB 79
Nov 29 2022
parent reply thebluepandabear <therealbluepandabear protonmail.com> writes:
 then the narrower value is converted to the wider type
 **C.** If the signed type is wider than the unsigned type, then 
 the unsigned value is converted to the signed type
 **D.** Otherwise the signed type is converted to the unsigned 
 type

 SDB 79


I didn't  ask about casting...
Nov 30 2022
parent Salih Dincer <salihdb hotmail.com> writes:
On Wednesday, 30 November 2022 at 11:40:36 UTC, thebluepandabear 
wrote:

 then the narrower value is converted to the wider type
 **C.** If the signed type is wider than the unsigned type, 
 then the unsigned value is converted to the signed type
 **D.** Otherwise the signed type is converted to the unsigned 
 type

 SDB 79


 I didn't  ask about casting...


You cannot fully grasp the topics without fully knowing the above 
items.

SDB 79
Nov 30 2022
prev sibling next sibling parent =?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> writes:
On 11/29/22 19:07, thebluepandabear wrote:


 But the book doesn't talk about why the D compiler came up with these
 results


The compiler doesn't do anything special. It's all about the lack of 
bits to store the value. If the result needs 33 bits but the type has 
only 32 bits, the contribution of the highest bit is simply lost.

Ali
Nov 30 2022
prev sibling parent "H. S. Teoh" <hsteoh qfbox.info> writes:
On Wed, Nov 30, 2022 at 03:07:44AM +0000, thebluepandabear via
Digitalmars-d-learn wrote:

 I am reading through Ali's book about D, and he gives the following
 examples for an overflow:


[...]

 The result overflows and is 1705032704.
 
 Also for the second example, it overflows and comes up with the value
 of 4294967286:


[...]

 Also a fun one, the following produces 4294967295:


[...]

 But the book doesn't talk about why the D compiler came up with these
 results (and it also goes for division/multiplication) for the
 overflow (or maybe it did further down ?), as in it didn't talk about
 the formula it used for calculating this value.
 
 I am curious as to what formula the D compiler uses for calculating
 'overflowed' values, if such thing exists? :)


[...]

First, you have to understand that it's not the D compiler that imposes
some arbitrary maximum after which an integer value will overflow. To
overflow rules are more-or-less a description of how the hardware
behaves under the hood, rather than something the compiler deliberately
imposes.

The value 4294967296 is actually 2^32. Why 2^32? Because that's the
number of distinct values a 32-bit machine register can hold. In fact,
the maximum value that a 32-bit register can hold is (2^32 - 1), i.e.,
4294967295, because 0 is one of the values represented.  Now, (2^32 - 1)
is the maximum for uint, but for int, one bit is reserved for indicating
the sign of the value, so the actual maximum is (2^31 - 1), i.e.,
2147483647, which, incidentally, is the value of int.max.

As for the actual overflow behaviour, it's a simple consequence of the
2's complement representation of integers. I.e., -1 is represented not
as:
	0b1000_0000_0000_0000__0000_0000_0000_0001

but rather as:

	0b1111_1111_1111_1111__1111_1111_1111_1111 (i.e. 0xFFFF_FFFF)

The most negative value that can be represented in 32-bit 2's complement
is:

	0b1000_0000_0000_0000__0000_0000_0000_0000 (0x8000_0000)

which is -2^31 == -2147483648, which, incidentally, is int.min.

Why 2's complement?  Well, because that's what the machine implements...
but why did the engineers choose to implement it that way?  Because 2's
complement representation has the interesting property that addition and
subtraction can be done exactly as if the values were unsigned, and
you'd get the correct results back when you reinterpret them as 2's
complement.  I.e., if you add 1 to 0xFFFF_FFFF, interpreted as an
unsigned integer, you get 0x0000_0000 (there's a leading 1 on the far
left but it's in the 33rd bit, which doesn't fit in the machine
register, so it gets discarded).  If you reinterpret 0xFFFF_FFFF in 2's
complement as -1, then you have the nice result that (-1) + 1 == 0 (the
+ here is unsigned addition).

One consequence of this is that negation is implemented as:

	-x == ~(x-1)

As a consequence of the 2's-complement representation of integers, and
the way arithmetic operations are implemented, the overflow rules that
you read about just fall out of the rules as natural consequences:

	0x7FFF_FFFF + 1 == 0x8000_0000

i.e., interpreted as 2's complement:

	2147483647 + 1 == -2147483648

Negating an unsigned number is equivalent to doing ~(x-1), so:

	cast(uint) -1 == 0xFFFF_FFFF == 2^32 - 1 == 4294967295

Adding 3_000_000_000 to 3_000_000_000 (in hexadecimal, that's
0xB2D05E00) gives you:

	0xB2D05E00 + 0xB2D05E00 == 1_65A0BC00

But that leading 1 is in the 33rd bit, which doesn't fit into a 32-bit
register (i.e., it overflows). If you discard it, you get 0x65A0BC00,
which in decimal is 1705032704.

So you see, none of this is D's own idiosyncratic rules; it's merely a
reflection of how the machine implements 32-bit integer values.
(Analogous results can be said for 64-bit values.)


T

-- 
If you want to solve a problem, you need to address its root cause, not just
its symptoms. Otherwise it's like treating cancer with Tylenol...
Nov 30 2022