Re: Is there a formula for overflow?
On Wed, Nov 30, 2022 at 03:07:44AM +, 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________0001 but rather as: 0b________ (i.e. 0x_) The most negative value that can be represented in 32-bit 2's complement is: 0b1000________ (0x8000_) 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 0x_, interpreted as an unsigned integer, you get 0x_ (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 0x_ 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_ + 1 == 0x8000_ i.e., interpreted as 2's complement: 2147483647 + 1 == -2147483648 Negating an unsigned number is equivalent to doing ~(x-1), so: cast(uint) -1 == 0x_ == 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...
Re: Is there a formula for overflow?
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
Re: Is there a formula for overflow?
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
Re: Is there a formula for overflow?
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...
Re: Is there a formula for overflow?
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
Re: Is there a formula for overflow?
On Wednesday, 30 November 2022 at 03:19:49 UTC, Basile B. wrote: writeln((30LU + 30LU) % uint.max); It's actually writeln((30LU + 30LU) % (uint.max.to!ulong + 1)); or writeln((30LU + 30LU) & uint.max);
Re: Is there a formula for overflow?
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
Re: Is there a formula for overflow?
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 = 30;
uint number_2 = 30;
}
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((30LU + 30LU) % 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.
Is there a formula for overflow?
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 = 30;
uint number_2 = 30;
}
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
