Signed integers are asymmetrical
borretti.me
borretti.me
This gets you an extra bit of precision when multiplying two signed numbers, because you no longer need to leave room for two sign bits in the product.
Tetrahedra almost tessellate but don't quite do it: https://www.pnas.org/content/pnas/103/28/10612/F1.large.jpg
In music, the frequency ratio of a semitone is ideally 2^(1/12), but without some tiny fudging (called tuning), you can't make harmonies as the frequencies almost but don't quite line up right. I forget exactly how this one works so I may have something off.
Other coincidences that drive me wild: speed of light is almost but not quite 3.0E8m/s And the fine structure constant being almost but not exactly 1/137.
On that subject, if you decided to make your base unit of length the distance light travels in a nanosecond it'd almost be a foot but not quite.
Similarly the earth-sun distance is 8 light-minutes.These feel right, like measuring mass in stone for people, kilos for sugar, carat for diamonds, electron-volts for particles etc.
IIRC correctly, it's not just harmonies; the range of a piano is big enough that if you tune each octave exactly based on that ratio, you'll end up with the first and last octaves sounding off from each other.
Hypothetically, or on an electronic instrument, you could. But if you did all 2^(1/12) ratios, your octaves wouldn't be in tune. Strings on a piano do not behave like an ideal string. Their overtones are not 2X, 3X, 4X, 5X, etc. times the fundamental frequency. Instead, the actual overtones are higher than the ideal frequencies. This is called inharmonicity (https://en.wikipedia.org/wiki/Inharmonicity).
So when tuning a piano, you have to tailor the way you tune it to each different piano if you want that piano's lower strings to be in tune with its higher strings.
I think I've been hearing this for a long time but didn't realize it was real so questioned my perceptual system.
Thank you for the info!
Some of it, of course, sounds like cats screeching but some of it is genuinely astonishing.
Now that you mention it, that convention does make me mad. Not because I have to write an extra character, but due to operations getting mixed-up based on implied context. For example:
Unary + is implicit: 3 = +3
Addition is written as juxtaposition: +2+5 = add(+2, +5) = +7. The first number can have an implicit sign, e.g. 2+5 = +2+5
"Subtraction" is a redundant operation; it's just addition involving a negative number: 8-3 = +8-3 = add(+8, -3) = +5.
The nice thing about this perspective is that subtraction commutes: +8-3 = -3+8.
What's annoying is that we also take juxtaposition to mean multiplication, and this flip-flops depending on implicit characters like unary '+'. For example:
-8-3 = add(-8, -3)
-8+3 = add(-8, +3)
ab = multiply(a, b)
2a = multiply(2, a)
a2 = multiply(2, a) (non-idiomatic)
-2a = multiply(-2, a)
a-2 = add(a, -2)
(1)(3) = multiply(1, 3)
(-1)(-3) = multiply(-1, -3)
-1-3 = add(-1, -3)
-1(-3) = multiply(-1, -3)
(-1)-3 = add(-1, -3)
This seems weirder than the case of addition/subtraction, probably because we already have the horizontal-bar notation for division, which seems even nicer. Note that the "÷" character itself is simply an inline approximation of the horizontal-bar notation (with placeholders above and below); the "foo/bar" notation is a more direct inline approximation (no placeholders, just 'tipping' the bar). Interestingly we don't use "bar\foo" to mean the same thing.
Thank you.
Also, it still has no total order, so keeps another messy part of IEEE floats
This is not true. It is defined to have the exact same ordering, bitwise, as two's complement integers. That means it has total order: the NaN is the most negative, then comes the negative numbers, then zero, and then positive numbers.
There is no a real number called "negative zero". For extremely small-magnitude negative values, posits have more to offer than IEEE floats without the abomination that is known as denormal numbers. And for limits approaching zero, using a datatype that is supposed to represent a subset of rational numbers is the wrong tool for the job.
https://people.freebsd.org/~das/kahan86branch.pdf
(he gives an example regarding complex branch cuts and fluid dynamics applications.)
But negative zero is not a redundant value. It behaves very differently from positive zero.
(Note also that -0 is an additive identity, and +0 isn't.)
Wait what
That's really confused me. Is this purely with reference to addition operations as defined in IEEE-754, or is there an underlying mathematical reasoning that makes it make sense?
I assume the reasoning was that they would prefer values to be +0 when possible. Assigning the sum of -0 and +0 to be +0 instead of -0 means that -0 is the identity and +0 isn't.
#include <limits.h>
#include <stdio.h>
int main(int argc, char const *argv[])
{
printf("%d", INT_MIN/(-1) == INT_MIN);
return 0;
} int Div(int a, int b) { return a / b; }
int (*pDiv)(int, int) = Div;
int main(int argc, char *argv[]) {
printf("%d\n", pDiv(INT_MIN, -1));
return 0;
}My first guess is that it involved some kind of architectural peculiarity of the PDP11.
One's Complement arithmetic wasn't uncommon on computers of the era and is fully symmetric. And, I believe that a PDP-7 uses one's complement.
2) "unsigned" didn't get implemented until about 5 years after C was initially implemented.
Why? Because it's quite likely the result will be used in arithmetic expressions involving other signed ints and/or subtraction. That goes with the kinds of things you'd use normally abs() for.
There will be some cases where abs() is being used by someone on a value that could be INT_MIN. But when your code might have to handle the full range of possible integers (signed or unsigned), there are probably many other things to get right as well. In such code, abs() is the least of your worries.
I think most uses of abs() are in arithmetic expressions of "numbers whose values we don't expect to overflow", and I'm fairly confident if abs() returned unsigned int, there would be more bugs that nobody spotted in the world than with it returning signed int. Not many more, because abs() is rarely used, but a few.
I used to be one of those people who felt it made sense to use unsigned types in C for values that can never be negative. That was tidier and clearer. It stated my intent.
After a few years of coding in C like this, I changed my mind: I spotted occasional little hidden bugs here and there, undetected by the compiler or the programmer, from overzealously using unsigned types just for "showing intent" where signed would have been fine.
It's not like using unsigned types prevents arithmetic bugs in C in practice (unless you really have values exercising most of the unsigned range). The "use unsigned because types should reflect intended range" argument is muddier than it first looks: The range [0..2^B-1] is no more "correct" than [-2^(B-1)..2^(B-1)-1] for almost all quantites, as people often aren't paying attention to correct handling of numbers in the upper end of the unsigned range either. They rely on "practical numbers are small enough that it doesn't matter", same as with signed ints.
If unsigned acted as a range-constrained arithmetic type in C, meaning "this variable can only hold a subset of the default integer type" and "arithmetic with other types is consistent", that would be different.
But it doesn't. It acts more like an unsignedness virus in C arithmetic, adding unnecessary boundary conditions into innocent-looking expressions.
Of course you can be aware of these issues and avoid them. I'm pretty experienced and can avoid such issues easily. But having to be careful for no added benefit, especially with multiple people, just raises risks. So now I default to, and advocate, sticking with signed integer types for values representing arithmetic quantities. If I were designing a language, I'd probably advocate for ranged types instead. That means limited to ranges like [0..2^(B-1)-1] (the upper half of the signed range), and have consistent arithmetic. But C is not like that.
Unsigned types in C are of course completely appropriate for bitwise and modular arithmetic uses, and for holding raw data. I'm a big fan of using them for relative timestamps using modular arithmetic comparisons, as done in Linux. If you're writing compression routines or a database engine they will be very useful.
But for general arithmetic quantities, nowadays my view is similar to this answer: https://stackoverflow.com/questions/51677855/is-using-an-uns.... I'm sympathetic to the "unnecessary discontinuity near common values" and "arithmetic closure is more useful" view. People won't agree on this. They don't agree in answers to that SO question. All I can say is, I used to be zealously "use unsigned for non-negative quantities", and then after some experience it seemed more pragmatic and safe-by-default to stop doing that, and the type-as-intent was misguided anyway when the upper range of unsigned wasn't being used. You still have to be unsigned-aware in C due to size_t especially. So I still use unsigned-by-default for arithmetic dancing around object sizes, memory and offsets in C.
One reason I picked this route is because Rust only lets you index arrays by usize and not isize, so I chose to extend this "unsigned for non-negative quantities" philosophy to C++. Additionally, std::vector::size() is size_t and unsigned, so I decided to follow. Because of the mixture of unsigned and signed indexing (and 32 vs. 64 bit values) across different libraries, I decided to turn on warnings so I know where incompatibilities lie. Rust outdoes C++ because it makes incompatible integer widths hard errors, comes with the equivalent of `-Wtautological-unsigned-zero-compare` out of the box, and has runtime checking (in debug mode) which panics if you decrement an unsigned value past 0.
I can understand "signed by default" even though I disagree and prefer not to use it for my own code. And I think 31-bit integers are a good idea if you don't need the range of an unsigned integer. I wish Rust had a type for "31-bit integer with negative values serving as a niche for enum cases" (though my concern is that a zero-overhead mutation API without runtime checks, combined with niche filling, would be UB since you can decrement 0 to -1 and effectively transmute an enum holding a u31).
Also signed integers aren't fully trouble-free, and can still overflow for very large differences (though that's less likely than 2 - 3). The Stack Overflow post mentions:
> Want to find the "delta" between two unsigned indexes into a file? Well you better do the subtraction in the right order, or else you'll get the wrong answer.
Well naive signed integer subtraction can be UB as well.
constexpr int f() {
return 0x7fffffff - -0x7fffffff;
}
constexpr int x = f();
<source>: In function 'constexpr int f()':
<source>:4:23: warning: integer overflow in expression of type 'int' results in '-2' [-Woverflow]
4 | return 0x7fffffff - -0x7fffffff;
| ~~~~~~~~~~~^~~~~~~~~~~~~
<source>: At global scope:
<source>:7:20: in 'constexpr' expansion of 'f()'
<source>:7:21: error: overflow in constant expression [-fpermissive]
7 | constexpr int x = f();
| ^
Compiler returned: 1
I guess this case (large numbers) is very rare compared to accidentally subtracting 3 from 2, and addition also risks overflow. And if you're using subtraction for deltas, then restricting file sizes to 2^31 - 1 or 2^63 - 1 makes differences fit in int32_t or int64_t (64-bit ptrdiff_t).
Sure, but the point is that you have to get overflow due to high magnitude of the involved integers. So yeah INT_MAX - -INT_MAX is UB, but you have to have quantities up around INT_MAX for this to be a problem. For the unsigned case you just have to have quantities around 0.
Now, having quantities around INT_MAX isn't necessarily that unusual, but what seals the deal for me (I wrote that SO answer) is that 64-bit values are becoming more ubiquitous, and there we can guarantee in some sense that many quantities won't reach their 2^63 limits any time soon. So I definitely thing "signed by default" is much more of a slam dunk if it is paired with "64-bit by default".
Note that though I'm a proponent of signed by default, in practice I find it hard to write this way in C and C++ because you are constantly fighting the impedance mismatch between the language, size_t, size(), etc and your own rule. So signed by default is definitely more palatable in languages which made that same decision for their builtins and standard library.
Yes yes and yes. There is nothing that would make me happier than if GCC and Clang gave us the freedom to choose an ILP64 data model. In that case, we wouldn't need prototypes anymore and we could restore much of the original intent behind the design of C.
The only issue with negative indices is that it is no longer possible to have containers-of-bytes as large as the address space, but except for that tiny time window when an usable 4GB address space was actually available on 32 bits systems, it is in practice not a big restriction.
std::string::find is size_t and unsigned too, now guess what it returns in corner cases.
>"showing intent"
I think intent of a signed integer is "it's a number, don't think weird things here".
If you absolutely have to, there are escape hatches like Uint8Array/Buffer/etc which allow you to deal with bytes. There are also ways to force JIT to treat your numbers as integers with tricks like `i = i|0`, but that's barely used.
Obviously compiled languages are different, but to me you could rename `signed integer` to `integer` and `unsigned integer` to `rawdata32` or `byte4`
https://github.com/OrchidTechnologies/orchid/blob/be5cc32a16...
I think it is the other way around, and that's why high level languages (under some definition of HLL) tend to have arbitrary precision integers. Python, Ruby, Lisp, and now Javascript (bigint) all have them. Finite fields are almost never used except in some special applications like cryptography or error correcting codes. Multiplication in the field with 2**32 elements doesn't look anything like integer multiplication. Normal computer arithmetic is not finite field arithmetic.
We really should be using trap-on-overflow in C most of the time. Making that difficult on RISC-V seems to me like a poor design decision.
That said, I certainly agree that if you are working with an actual unbounded numerical value you should be using a data structure that at least attempts to simulate an unbounded numerical value; but, what people always insist on instead is to continue using their fixed integer types which they want to magically have compatible semantics with unbounded integers... a fiction they insist the compilers and even CPUs join them in crafting, with things like the "trap-on-overflow" feature you are advocating for :/.
The result of this is that, rather than accepting types like "uint64" are finite fields that should have perfectly regular overflow, and inverse semantics that under no circumstances, should be "messed with" by the environment, and that they should be using "BigInt" for any actual numbers that occasionally come up, people keep ruining the finite field types by trying and, in the end, failing to add a bunch of weird optimizations and overflow trap semantics to their operation... mitigations that only cause further errors later: these types should have the most brutal possible interpretation of finite field math, and anyone who wants an actual number--maybe to represent a physical or monetary quantity should be forced to not consider them an option.
Meanwhile, languages should do anything and everything possible to not pessimize the syntax of types like BigInt by providing a short name for a good implementation of the type along with operator overloading that prevents anyone from ever considering the usage of a type like C's "int" to represent a number merely because it is easier or looks better or feels natural: you fix this issue, and "trap on overflow"--a ridiculous semantic that makes software look like it works until you push it a bit, and in a way that fails to be fungible with (and accepting the same solutions as) running out of memory--becomes a feature that has no legitimate usage.
We do in fact normally use integer datatypes to represent integers rather than elements of a cyclic group. For example, we expect n+1 to always be greater than n unless we are doing something not-so-common. In (say) Python, the int type is bigint, sometimes informally called "infinite precision" though their size is actually bounded by the size of the computer's memory. If your integers get too big, your program runs out of memory and weird things can happen, such as crashing, the OOM killer clobbering the process, or whatever. Basically undefined behaviour. In C it is the same thing, an int64 is infinite precision except bounded by the size of the machine word instead of by the memory size. If your program experiences uint64 overflow it's likely to be a genuine error condition unless the program is doing bit twiddling rather than arithmetic. In the case where it is an error condition, of course I'd want to trap it.
Haskell makes the distinction between the Int type (an integer expected to fit in the size of a machine word) and the Word type (a bit pattern that supports some arithmetic operations). That is really what C should have done from the beginning. I've been wanting to check how Rust handles it.
* i8::MIN.checked_abs() is None
* i8::MIN.overflowing_abs() is (i8::MIN,true)
* i8::MIN.saturating_abs() is i8::MAX
* i8::MIN.wrapping_abs() is i8::MIN
[edited to add]
* i8::MIN.unsigned_abs() is the 8-bit unsigned value 128
and finally
* i8::MIN.abs() will panic in debug builds or give i8::MIN in non-debug builds.
You should obviously not choose this last option if you in fact will call this function on i8::MIN (or any similar minimum values) which is why it panics if that happens. You should have instead chosen which behaviour you wanted (checked, overflowing, saturating or wrapping) up front.
Oh, ugh: I actually usually say "modular ring", but I'm not even sure that's a technical term, so for this comment I tried to get all fancy (as I thought I remembered that all rings are fields but not all fields are rings) and failed :(.
> We do in fact normally use integer datatypes to represent integers rather than elements of a cyclic group.
I assume our core disagreement comes because I believe that fundamentally everything representable on a Von Neumann computer is cyclic due to how memory works. I continue to 100% appreciate that this is an incredibly controversial opinion and that very few people are going to agree with me on this.
> If your program experiences uint64 overflow it's likely to be a genuine error condition unless the program is doing bit twiddling rather than arithmetic. In the case where it is an error condition, of course I'd want to trap it.
However, here I want to claim you are just wrong: you simply shouldn't be using that type for this... you should be using a big integer type; and the core solution here should NOT be to make overflow of this type trap, but to figure out why you are using this type in the first place and fix the language until you stop.
> In (say) Python, the int type is bigint, sometimes informally called "infinite precision" though their size is actually bounded by the size of the computer's memory. If your integers get too big, your program runs out of memory and weird things can happen, such as crashing, the OOM killer clobbering the process, or whatever.
This is fundamentally different, though: this isn't your program being wrong, but the system executing your program being wrong. Your program should strive to be correct, and insisting that "no one is ever going to need more than X-bits worth of Y" as an assertion in your program--as opposed to it merely being a limitation of the machine running your program--is a mistake.
For my own personal vanity, is someone who hasn't studied high enough level math enough to have a formal sense of what "finite field" means necessarily non-fluent in practical computation, or is it possible to have sufficient intuition about computational versus "real-world" integers without being able to express it?
If they are not aware of this property, bugs will certainly be caused by this, sooner or later.
In a set of modular numbers where the modulus is not a prime number, e.g. in C/C++ "unsigned char", "unsigned short" "unsigned", "unsigned long" and "unsigned long long", where the modulus is a power of two, multiplication is invertible only if the multiplicator is relatively prime with the modulus.
In the C/C++ modular numbers that means that only multiplication with odd numbers is invertible.
A consequence of this fact, which should be familiar to most programmers, even if they might not be aware of the cause, is that we have only one kind of shift to the left (i.e. multiplication by 2), but 2 kinds of shift to the right (division by 2).
In the set of integers modulo 2^n there are 2 numbers that multiplied by 2, i.e. shifted 1 position to the left, give the same number, and they correspond to the so-called logical shift to the right a.k.a. unsigned shift to the right and to the so-called arithmetical shift to the right a.k.a. signed shift to the right.
The names of the 2 shifts to the right are misleading, because both are well-defined meaningful operations for what in C/C++ are named "unsigned" numbers, but which are defined in the standards as modular integers, not unsigned integers (which would give exceptions or saturation on overflow).
The fact that in C/C++ you get for ">>" one of the 2 shifts depending on whether the operand is "signed" or "unsigned" is just a convention. However this convention is useful in most cases, because in C/C++ smaller numbers are typically considered as being truncated from larger numbers that correspond to either their zero-extended or their sign-extended equivalent, and not as really being modular numbers as they are defined and as they behave.
In languages that impose more constraints on the programmers, e.g. Ada, the programmer need not be so aware about how numbers are represented and which is the meaning and properties of the operations applied to numbers.
On the other hand, in C/C++, which besides some implicit safe conversions also have a large number of unsafe unchecked implicit or explicit number conversions, programmers will very likely cause some bugs eventually, unless they understand well the differences between modular numbers, signed integer numbers, unsigned integer numbers (really unsigned numbers, not those named so in C), how these numbers are compared by the hardware, depending on whether they are signed or not, how and when overflow is signaled by the hardware, also depending on whether the numbers are signed or not, which operations are invertible and which not, and so on.
Sometimes, especially when programming for embedded computers, the freedom of C/C++ is convenient, but nonetheless a lot of care is needed to not be surprised by undesired implicit conversions and truncations, like in the example that started this thread.
A nitpick: 32 or 64 bit integers are not finite fields. One of the finite field axioms is that any non-zero number must have a multiplicative inverse, which 2 does not have.
They are, however, commutative rings.
There are finite fields of of order 2^k for each k, but they work quite differently from the integers modulo 2^k.
I think the best short term for describing how machine integers work is to just say "modular arithmetic".
Sure, but also the important part of OP's argument seems to be that numbers be treated as members of the appropriate algebraic structure. Simply subbing in the correct terminology should fix the issue.
> I think the best short term for describing how machine integers work is to just say "modular arithmetic".
For addition this is correct, I don't believe it's correct for multiplication because of the negative integers. That is, the ring described by signed n-bit signed integers under multiplication and addition is not isomorphic to (Z_{2^n}, +, *).
No, it is. It is in fact just Z modulo 2^n, just with the choice of representatives being { -2^(n-1), ..., 2^(n-1)-1 } instead of { 0, ..., 2^n-1 }. This is pretty easy to check... do you have an example to the contrary?
So, to try to be absolutely explicit about what I was saying:
I was not saying anything about the C programming language. I was talking about the more general notion of fixed-length integers; more specifically, ones that are either unsigned or two's-complement. Obviously, that is frequently applicable to the C programming language, but they are not identical, as, e.g., technically C doesn't require two's-complement for signed integers (and what I said would be false for other sorts of signed integers such as one's-complement). So I'm not talking about C, and the C standard is not relevant to what I was saying.
I am not saying anything about the % operator, in C or any other programming language. I am talking about modular arithmetic, where you fix a modulus m -- which in this case is 2^k, where k is the length of the integers in question -- and you form a ring by taking congruence classes modulo m, and you add and multiply congruence classes by picking representatives, applying the appropriate operation, and then taking the congruence class of the result. The particular choice of representatives is irrelevant.
As I already said, I am only talking about addition, negation/subtraction, and multiplication (and the constants 0 and 1, if you want to be really nitpicky). Other operations are not relevant to what I'm talking about.
Now obviously, to represent congruence classes in a computer, you need to pick representatives; and so the modulo operator % (which, again, is not relevant to my point, but I think I need to address this anyway) returns a number rather than some sort of notional congruence class object, because, well, what else is it going to do. So, it returns a representative of the congruence class rather than the congruence class itself, because there's no way for it to do the latter.
As you point out, in C (as of C99 anyway), as well as several other programming languages, the % operator, when evaluating n % m, returns a representative from { -|m|+1, ..., 0 } if n is negative, instead of { 0, ..., |m|-1 } like might be expected. This is a quirk of the % operator, for sure, but it doesn't have anything to do with what I'm talking about. Also note that the ways that programming languages handle negative n or negative m vary quite a bit; some do what C does, some use the sign of m rather than n, and some always return a nonnegative result.
The distinction you are drawing between "modulus" and "Euclidean remainder" is, at least in mathematics, not a standard one; as such, if you want to make use of it, you are going to have to explain what you are talking about, rather than just assuming I know it. (I mean, to be clear, there is a distinction between the two, but it's not the one you seem to be drawing. Rather it's that Euclidean remainder is a number rather than a congruence class; is only defined in Euclidean domains; and isn't actually required to be unique. But that's tangential, we're just talking about integers, I'm going to assume you mean the obvious thing by "Euclidean remainder".) In math, at least, the result of modding out is a usually a congruence class, rather than a specific representative, unless you specify otherwise or the context makes it's clear that that really is what you mean (e.g. using "mod" as an operator). When "mod" is used as an operator, and n is negative, I'd assume that the author intended { 0, ..., |m|-1 } as their set of representatives, rather than mimicking C's % operator, unless they specified otherwise.
As best I can tell, you seem to be using "modulus", as opposed to "Euclidean remainder", to indicate the specific behavior of C's % operator. I would suggest that this terminology is not as standard as you seem to think it is and will confuse people; this is both not how it is used in mathematics, and not how it is used in lots of other programming languages. If you are trying to refer to that particular behavior, you should use a more unambiguous description.
But -- I say this again -- none of this is really on the point I was making. The point I was making was this: Addition, subtraction, and multiplication on fixed-width unsigned integers of length k, with all overflow ignored, consists exactly of operating on the numbers in Z/(2^k), and then taking the representative that can be expressed in k bits unsigned. Moreover, the same is true for fixed-with two's-complement integers of length k; you operate in Z/(2^k), and then take the representative that can be expressed in k bits 2's-complement. That is to say, you're just doing modular arithmetic. The numbers add, subtract, and multiply exactly like their corresponding congruence classes in Z/(2^k). That's all I'm claiming. Again, none of this is about the particular behavior of any C operators.
Now that I have utterly belabored this point, is there anything, on that main point, that you disagree with?
In C/C++, when -x is computed, x is promoted to int, so "-" does not overflow and "-ftrapv" does not matter.
This would be harmless, except that "return -x" truncates the result to 8 bits, which overflows, but this truncation is not checked so it does not signal an overflow exception, as it should in a decent programming language.
Had x been an "int", instead of an "int8_t", the error would have been caught in C/C++ with -ftrapv (when "-" is applied to INT_MIN), but "int16_t" would have also resulted in an error that is not caught, due to implicit unchecked truncation.
While forbidding all implicit conversions is a serious mistake in the opposite direction, many of the implicit conversions that exist in C/C++ for historical reasons are extremely harmful and they should be avoided like the plague, i.e. the truncation of larger integers into smaller integers and also the implicit conversions of signed integers into unsigned integers.
In C++ std::abs(std::numeric_limits<int>::min()) is undefined behavior (not even implementation-defined: nasal flying simian warning!). Most importantly, the optimizer is allowed to make optimizations that are only safe if abs() only returns non-negative values, but abs(INT_MIN) can also return a negative value (or trap to the kernel/SIGFPE/SIGBUS/etc. on some exotic architecture).
So, in C++ one might be tempted to get around this issue by writing:
static inline int my_abs(int x) {
const int result = abs(x);
if (result < 0 /* WRONG! UB! */ ) {return numeric_limits<int>::max();}
return result;
}
More crazily, if the C/C++ optimizer discovers that some conditional branch is always conditioned on undefined behavior, it can just optimize away the branch, or even both sides of an if-else.
static const int x = std::numeric_limits<int>::min();
void f() {
puts("Before\n");
if (abs(x) >= 0) {
puts("Expected\n");
} else {
puts("Unexpected\n");
}
puts("After\n");
}
When I was at Google, Michael Chastain was telling me about one of the oddest bugs he helped debug (super helpful and knowledgeable guy, btw, one of the few people trusted with code ownership of the root of the monorepo). It was basically the above, but the UB was related to static initialization order of floating point variables.
static double y = 22.0;
static double x = y / 7.0; // Uh-oh... depends on floating point static init order
void f() {
if (x > M_PI) {
...
} else {
...
}
}
fn absolute(n: i8) -> i8 {
if n >= 0 { n } else { -n }
}
fn main() {
let nums = [i8::MIN, i8::MIN + 1, 0, i8::MAX - 1, i8::MAX];
for num in nums {
println!("{}", absolute(num));
}
}
Compiling playground v0.0.1 (/playground)
Finished dev [unoptimized + debuginfo] target(s) in 3.57s
Running `target/debug/playground`
thread 'main' panicked at 'attempt to negate with overflow', src/main.rs:2:27
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
* Checked where you get Some(answer) or None
* Overflowing where you get (answer,false) or (overflowed_answer,true)
* Saturating where you get answer or the closest of type:::MIN and type::MAX to the correct answer
* Wrapping where the number line wraps around at the end
If you don't pick which you wanted, but then you do something that's poorly defined a debug build will panic, whereas a production build wraps.
The panic in debug is to encourage you to actually decide which of the four operations you meant and write that.
abs(-128) = 128
abs(-127) = 127
abs( 0) = 0
abs( 126) = 126
abs( 127) = 127 abs(-9223372036854775808) = -9223372036854775808
abs(-9223372036854775807) = 9223372036854775807
abs( 0) = 0
abs( 9223372036854775806) = 9223372036854775806
abs( 9223372036854775807) = 9223372036854775807In the first example, the branch is `>= 0` but then in the "examples" second, the second part, it's `> 0`. Which is it?
Either way, neat point to be made here. I'm surprised -ftrapv doesn't catch it.
If this seems strange to anyone, it comes from the fact that all numbers in JS [1] are represented as double-precision floating point values. The bit format for doubles is a sign bit, 11 bits for the exponent, and 52 bits for the fraction.
When storing integers in floats, you use an exponent of 1, and then stuff the integer into the fraction and sign bits.
[1] I think bigint is a thing now?
Is this correct? I would have just guessed that JS stores integers as their equivalent float values, which is why above 53 bits, you stop being able to represent all whole numbers (but you can represent some whole numbers), unless JS-land has changed since I last checked in almost a decade ago.
Edit: Ignore this, I'm wrong.
const std=@import("std");
test "IEEE fp representation" {
std.debug.print("\n{x}\n", .{@bitCast(u64, @as(f64, 1.0))});
std.debug.print("\n{x}\n", .{@bitCast(u64, @as(f64, 2.0))});
}
3ff0000000000000
4000000000000000
The "hidden bit", while tricky and hard to understand, is probably one of the few truly good decisions that IEEE-754 comittee made out of a lot of kludgey compromises. Note that if they had done it the way you suggest, there would be degenerate representations for the same number, leading to a much smaller total possible representations for the same bitspace (this is a minor problem for most object-based "Decimal" number systems used for financial Txs -- you often need to use a specialized equality function instead of the language builtin), the "hidden one" ensures that every binary form has a uniquely represented value, not counting craziness with NaNs, and plus/minus zero, sigh.
My brain fart was forgetting how floats work, seeing that the integer-resolution range for both single and double precision floats was exactly the number of bits in the fraction + the sign bit and then pattern matching.
Set the exponent to 0 and stuff in bits for the significand. This gets you a random float in the range [1,2). Now subtract 1.0.
Note that this misses many floating point values that should be selectable if you wanted all floats between 1 and 2, but it was good enough for video games.
It's worth pointing out that IEEE 754-2008 has decimal numbers like you describe without the hidden bit. But for decimals this can be really useful because numbers "remember" their exponent. So if you're doing addition of dollar values, for example, .84 + .12 = 1.00 rather than 1 (i.e. it remembers its significant digits).
Yeah, pretty decently supported as well: https://caniuse.com/bigint
I ran into it with WASM u64/i64 values, which are also apparently decently supported at this point: https://webassembly.org/roadmap/
There are, of course, edge cases. For example, despite the fact that numbers are floats, you can still perform bit operations on them. For these operations, the numbers are implicitly converted to 32-bit ints.
JavaScript also has Typed Arrays, so you can have an array of 32-bit unsigned ints. But not a u32 itself.
2's complement is negative biassed. 1's complement (unmentioned in the article) is zero biassed.
Neither surprise me.
Seriously, who cares? Very few of us. I'm one but this isn't a problem for almost everyone else.
if constexpr( std::is_unsigned_v<Number> ) { return x; } else { if( x >= 0 ) { return x; } if( x <= -std::numeric_limits<Number>::max( ) ) { // What do we return?? } return -x; }
This comes up in parsing too. One often will harden against signed overflow by using an unsigned type and then multiplying the sign at the end. One needs to check for these kinds of things when the type is the biggest, like intmax_t(generally int64_t)
Trying to take the absolute value of the most negative integer is not defined.Be honest, it is not an obvious gotcha. Don't get defensive if you didn't realize the implications of abs(-128) = -128 @int8.
Edit: what idiot downvotes this?
Also, the commonly used Common Era system for dates does not include a year zero, so it is symmetric.
A year zero does not exist in the Anno Domini (AD) calendar year system commonly used to number years in the Gregorian calendar (nor in its predecessor, the Julian calendar); in this system, the year 1 BC is followed directly by year AD 1. However, there is a year zero in both the astronomical year numbering system (where it coincides with the Julian year 1 BC), and the ISO 8601:2004 system, the interchange standard for all calendar numbering systems, (where year zero coincides with the Gregorian year 1 BC; see conversion table). And there is a year zero in most Buddhist and Hindu calendars.