2 ms·
NaNs are an incredibly good idea, but it turns out we really need only one. Also, two's complement signed integers have an asymmetry that INT_MIN < -INT_MAX.
by Someone 12y ago
NaNs are an incredibly good idea, but it turns out we really need only one.
Also, two's complement signed integers have an asymmetry that INT_MIN < -INT_MAX.
Therefore, I were to design a CPU today, I would add arithmetic instructions that treated INT_MIN as a NaN, thus removing the asymmetry, and giving us an integer NaN.
16 bit int values would range from -32767 to +32767, with the bit pattern now used for -32768 being NaN. You would use it for everything that isn't representable as an int (overflow, underflow, 3/2 (as opposed to 3 mod 2), etc)
Yes, that CPU would also would have instructions for doing the regular modulo 2^16 arithmetic, but 'sane ints' would help not penalize programming languages that want to do sane integer arithmetic.
- keeperofdakeys 12y ago2's complement (the binary representation of numbers in a cpu) has one awesome feature, if you add two signed numbers, even if one or both are negative, you get the right answer. This means that you can add two numbers without checking if one is negative, saving time and scarce circuit space. In order to add a NaN, you'd need a check for NaN. This would basically double the amount of time an add would take, and add more circuit paths to the core of the cpu. If we use a single bit dedicated to signalling NaN, the overhead might be worth it. Of course, we lose half of our range in doing so.
- cesarb 12y agoIt wouldn't double the amount of time for an add (or any other operation), if it's implemented in hardware the comparison can be done in parallel with the addition, and the result of the addition ignored at the end if the compare returned true. It would increase the use of space by the circuit, but not by much. And we already have circuitry doing similar things to set the flags (zero, carry, overflow, parity...). If you want a real-world system with a single extra bit for every value (on registers at least), see the Itanium and its NaT bit (used for speculative loads).
- keeperofdakeys 12y agoAfter writing it, I realised that you could just do both in parallel, but it soon makes things much more complicated since nearly everything is based on adds.
- Someone 12y agoYou get the right answer _modulo_2^N_. In many cases, that is not the right answer. Also, most CPUs will set an overflow bit if addition overflows or underflows. I don't see how it would be that hard to also force the result to 0b100....000 if that happens. And 'scarce circuit space'? There are areas where that is still true, but they are getting rarer and rarer. Certainly, for desktop CPUs, x86 shows that one can waste circuit space by keeping around the classical x87 FPU logic, a few variants of SSE that one should not use anymore, a few attempts at vector units, instructions for branching hints that the CPU ignores, etc, and yet be successful. I think the price paid for the detection of logic errors would be worth it.
- Someone 12y ago"If we use a single bit dedicated to signalling NaN, the overhead might be worth it. Of course, we lose half of our range in doing so." You don't need to lose half your range; you can also add a bit. You only need to add a sticky overflow bit to each register, keep the arithmetic hardware as-is, and modify loads to set the sticky overflow when reading the NaN pattern, and modify writes to write 0b1000...000 when writing a register whose sticky overflow bit is set. Hardware cost would, I think, be very small, as you would only need a bit per register, and keep memory as-is. Given that Apple has non-wrap around ints in Swift and designs its own CPUs, it wouldn't surprise me if they added something similar or their CPUs, just as I expect them to add instructions for loading from tagged pointers (https://www.mikeash.com/pyblog/friday-qa-2012-07-27-lets-build-tagged-pointers.html https://www.mikeash.com/pyblog/friday-qa-2012-07-27-lets-bui...)
- lifthrasiir 12y agoSee also: http://blog.regehr.org/archives/642 http://blog.regehr.org/archives/642