The post NaNs, Infinities, and Negative Numbers In Loan Calculators first appeared on Exploring Binary.
]]>I found many more errors — NaNs, but also infinites, negative numbers, and one called “incomplete data”, whatever that means — all on websites within the top Google search results for “loan calculator”. All I had to do to elicit these errors was to enter large numbers. (And in one case, simply including a dollar sign.) All of the errors arise from the use of floating-point arithmetic combined with unconstrained input values. Some sites even let me enter numbers in scientific notation, like 1e308, or even displayed them as results.
Here are screenshots of seven sites:
The post NaNs, Infinities, and Negative Numbers In Loan Calculators first appeared on Exploring Binary.
]]>The post Incorrect Hexadecimal to Floating-Point Conversions in David Gay’s strtod() first appeared on Exploring Binary.
]]>I have emailed Dave Gay to report the problem; I will update this post when he responds.
The post Incorrect Hexadecimal to Floating-Point Conversions in David Gay’s strtod() first appeared on Exploring Binary.
]]>The post Incorrect Hexadecimal to Floating-Point Conversions in Visual C++ first appeared on Exploring Binary.
]]>
The following table shows examples of incorrect conversions by Visual C++ strtod() on Visual Studio 2022 Community Edition, running on Windows 11. Some of the examples are taken from the problem report, and some are additional ones I tried. All are supposed to convert to 0x1.0000000000000p-1022 (or 0x1p-1022 if you omit trailing 0s); that is, 2^{-1022}, the smallest (positive) normal value of a double, also known as DBL_MIN.
Ex # | Hex input | Visual C++ strtod() |
---|---|---|
1 | 0x1.fffffffffffffp-1023 | 0x0.0000000000000p+0 |
2 | 0x1.fffffffffffff0p-1023 | 0x0.0000000000000p+0 |
3 | 0x1.fffffffffffff000000000p-1023 | 0x0.0000000000000p+0 |
4 | 0x1.fffffffffffff1p-1023 | 0x1.0000000000000p-1019 |
5 | 0x1.fffffffffffff2p-1023 | 0x1.0000000000000p-1019 |
6 | 0x1.fffffffffffff3p-1023 | 0x1.0000000000000p-1019 |
7 | 0x1.fffffffffffff4p-1023 | 0x1.0000000000000p-1019 |
8 | 0x1.fffffffffffff5p-1023 | 0x1.0000000000000p-1019 |
9 | 0x1.fffffffffffff6p-1023 | 0x1.0000000000000p-1019 |
10 | 0x1.fffffffffffff7p-1023 | 0x1.0000000000000p-1019 |
11 | 0x1.fffffffffffff8p-1023 | 0x1.0000000000000p-1019 |
12 | 0x1.fffffffffffff9p-1023 | 0x1.0000000000000p-1019 |
13 | 0x1.fffffffffffffap-1023 | 0x1.0000000000000p-1019 |
14 | 0x1.fffffffffffffbp-1023 | 0x1.0000000000000p-1019 |
15 | 0x1.fffffffffffffcp-1023 | 0x1.0000000000000p-1019 |
16 | 0x1.fffffffffffffdp-1023 | 0x1.0000000000000p-1019 |
17 | 0x1.fffffffffffffep-1023 | 0x1.0000000000000p-1019 |
18 | 0x1.ffffffffffffffp-1023 | 0x1.0000000000000p-1019 |
19 | 0x1.ffffffffffffffffffffffp-1023 | 0x1.0000000000000p-1019 |
20 | 0x1.fffffffffffff0000000001p-1023 | 0x1.0000000000000p-1019 |
21 | 0x1.fffffffffffff0000000000011p-1023 | 0x1.0000000000000p-1019 |
22 | 0x0.fffffffffffff8p-1022 | 0x1.0000000000000p-1020 |
23 | 0x7.ffffffffffffcp-1025 | 0x1.0000000000000p-1021 |
24 | 0xf.ffffffffffff8p-1026 | 0x1.0000000000000p-1020 |
Three of those conversions underflowed to 0, and inexplicably, the remaining conversions — even though they got the correct bits — were off in their exponents.
0x1.fffffffffffffp-1023 (Example 1, and its equivalents Examples 2 and 3) converted incorrectly to 0. That input specifies 53 bits of 1s — 1 bit before the radix point and 13 x 4 = 52 after. However, at exponent -1023, which is where the subnormal numbers start, there are only 52 bits of precision. That makes this number a halfway case. (When reading hexadecimal format, it is key to think about it in binary to understand exactly where the rounding bits are.) The result must be rounded, according to round-half-to-even rounding. That rounding propagates all the way up to the first bit. After normalizing (from a binary point of view, that is, making the hex digit before the point a 1), it becomes 0x1p-1022, the correct result.
Examples 4 through 21 are Example 1 with extra bits appended to make them greater than halfway cases. They convert to the correct bits — except with an exponent of -1019!
Examples 22 through 24, which when normalized are the same as Example 1, also convert to the correct bits but with the wrong exponent.
Additionally, I hand tested a few dozen normal and subnormal numbers not at the boundary and found no errors. (If I have time I will try to do automated testing comparing Visual C++ with David Gay’s strtod(). Update 1/27/24: I ran millions of random tests and found no additional errors.)
I also tested the decimal equivalent of 0x1.fffffffffffffp-1023, a 768 significant decimal digit, exactly representable number. Visual C++ converted that correctly, hinting that this bug is isolated to converting from hexadecimal notation. (That 768-digit number rounded to 17 digits is 2.2250738585072011e-308, the input that sent PHP into an infinite loop.)
I verified that Apple Clang C++ , Java, and Python converted the examples correctly (with some formatting differences). Here are examples of how a I tested the hex to floating-point to hex round-trip conversions in each language:
printf("0x1.fffffffffffffp-1023 converts to %a\n", strtod("0x1.fffffffffffffp-1023", NULL));
(I know, that is really the C way of doing it.) Don’t forget to add the line #include <stdlib.h> if you try this.
Output:
0x1.fffffffffffffp-1023 converts to 0x1p-1022
System.out.printf("0x1.fffffffffffffp-1023 converts to %a\n", Double.parseDouble("0x1.fffffffffffffp-1023"));
Output:
0x1.fffffffffffffp-1023 converts to 0x1.0p-1022
print('0x1.fffffffffffffp-1023 converts to', float.hex(float.fromhex('0x1.fffffffffffffp-1023')))
Output:
0x1.fffffffffffffp-1023 converts to 0x1.0000000000000p-1022
Interestingly, Visual Studio converts these examples correctly at compile time, meaning when they appear as literals (and not strings in a call to strtod()); for example, when coded as:
double d = 0x1.fffffffffffffp-1023;
instead of
double d = strtod("0x1.fffffffffffffp-1023", NULL);
(This was noted in the problem report and I verified it.)
It might come as a surprise that you can get different conversions at compile time vs. run time, and this is in fact the first time I observed it in Visual Studio. However, this was an issue in GCC vs. GLIBC.
I have discovered and/or reported on many incorrect conversions over the years — around the normal/subnormal boundary and otherwise — but all have been from decimal inputs, not hexadecimal. I viewed hexadecimal constants as direct mappings to floating point — text representations to recover specific floating-point numbers, and thus a way to bypass potentially incorrect decimal to floating point conversion. I don’t think I ever considered that one would specify a hexadecimal input with more precision than IEEE floating-point allows, thus requiring rounding, and thus potential for incorrect conversion.
So much for assuming that incorrect rounding was a decimal-only issue.
The post Incorrect Hexadecimal to Floating-Point Conversions in Visual C++ first appeared on Exploring Binary.
]]>The post ChatGPT Will Never Write For Exploring Binary first appeared on Exploring Binary.
]]>Mastering Decimal, Binary, & Two’s Complement Conversion
In the digital world, understanding numerical notations like decimal, binary, and two’s complement can provide a substantial advantage and presents opportunities for improved problem-solving. The journey starts with the basic foundation of decimal …
I did not click through the tracking link to get the rest of the article but it looks like the generic fluff ChatGPT wrote when I asked it about Exploring Binary. It’s worse than fluff actually; I don’t see how knowing numerical notations helps with problem solving.
If you’ve read anything on this site you’d know immediately that I didn’t write that. Will AI ever be able to write an article indistinguishable from one of my own? I don’t think so.
The post ChatGPT Will Never Write For Exploring Binary first appeared on Exploring Binary.
]]>The post ChatGPT Writes Decent Code For Binary to Decimal Conversion first appeared on Exploring Binary.
]]>
(The line that got cut off in the screenshot of the second solution is
decimal += (binaryArray[i] - '0') * Math.pow(2.0, (binaryArray.size - 1 - i).toDouble()).toInt()
)
My first observation is that it was smart enough to know that by base 10 I meant decimal, and even named the function binaryToDecimal() as I would have.
The first solution is more clever then I was expecting; it uses the built-in function parseInt() to do the conversion directly. It compiles and runs successfully.
The second solution is along the lines of what I was expecting, although it computes the nonnegative powers of two instead of the more efficient “nested” multiplication by two as I do in function bin2dec_i(). It compiles and runs successfully, although it did have one warning from the IDE about the Math.pow() function: “Should be replaced with Kotlin function. Replace with ‘pow’ function”. I replaced “Math.pow(2.0,…” with “2.0.pow(…” and it got rid of the warning.
I was hoping that it might have generated code to handle arbitrary length integers, like my converters and calculators. I guess I’ll have to be more specific.
(The line that got cut off in the screenshot of the second solution is
decimal = decimal.add(bit.multiply(BigInteger.valueOf(2).pow(binaryArray.size - 1 - i)))
)
It decided to use BigInteger, which is what I would have done.
The first solution compiles and runs successfully. It takes the “shortcut” of using BigInteger itself to convert integers to different bases directly.
The second solution does not compile. The compiler complains about valueOf(): “None of the following functions can be called with the arguments supplied.”. But a simple fix — appending .toLong() to (binaryArray[i] – ‘0’) — allowed it to compile and run successfully. It still has the same inefficiencies as the limited-precision solution above though.
Stylistically, it did not use operators for the BigInteger functions to make the code easier to read, like this:
decimal += bit * BigInteger.valueOf(2).pow(binaryArray.size - 1 - i)
When I set out with my query I was really hoping that it would generate code to handle any arbitrary length number, integer or floating-point; let’s add that to the request.
This solution does not compile. (And also has the same warning as above about Math.pow().) Even after fixing the small compiler error (changing “val decimal” to “var decimal”) the code works incorrectly. For the sample test code, it prints 1101.625. It incorrectly converts the integer part, treating it as decimal.
A simple additional fix that gets the sample test running correctly is to add import java.math.BigInteger and to replace
var decimal = BigDecimal(parts[0], MathContext.UNLIMITED)
with
var decimal = BigInteger(parts[0], 2).toBigDecimal()
which is a trick it used in another solution.
But the code still has an error, when the input has no integer part; for example, “.101”. This causes the runtime exception “Zero length BigInteger”. (With the original line that has BigDecimal, the runtime exception is “Index 0 out of bounds for length 0”.)
A simple fix for this is to replace the modified line with this further modified line:
var decimal = (if (parts[0].isEmpty()) BigInteger.ZERO else BigInteger(parts[0], 2)).toBigDecimal()
I tested the new version on this number:
11101011100010101001000110101111010101011111101111111101011010111011.1110101011010001001001101010101010101010101010101010101011111010101010001011101010101
which gave this correct output, as confirmed by my binary to decimal converter:
271560613247152281275.9172538916269938194405650664083933868757033715246596017323099658824503421783447265625
The final fix is to use the BigInteger pow() function. In keeping with the original style of ChatGPT’s solution, and making the minimum change possible, I replaced
fraction += BigDecimal(bit * Math.pow(0.5, i + 1.0))
with
fraction += bit.toBigDecimal() * BigDecimal.ONE.divide(BigInteger.TWO.pow(i + 1).toBigDecimal())
I tested this with fractional values longer than 1074 bits.
Finally, I was expecting it to use BigIntegers with scaling, not BigDecimal, which is overkill. And it computes the negative powers of two instead of the more efficient “nested” division by two as I do in function bin2dec_f().
I’m not sure what to make of ChatGPT’s coding ability since I only asked it to code a short, well-known algorithm. But for this case I’d say its results are a great starting point, and is easier than searching the Web. On the other hand, searching could open your eyes to other solutions, and to the errors I pointed out.
It’s interesting that ChatGPT wrote decent Kotlin, given that it’s a relatively new language, and considering ChatGPT’s training data is only through 2021. I was also impressed that it printed the code in dark mode, which seems to be what developers prefer.
I wonder: if ChatGPT learned to code by reading others’ code, what happens when it learns from its own code? This sounds like one giant feedback loop converging to incorrect answers. (This is a bigger issue, applying to everything it learns, not just code.)
I published this article yesterday and asked ChatGPT about it today:
I’m really starting to question what it thinks it knows.
Except for a few individual lines, the code is in screenshots. Is it reading images?
A few things in its response that stick out:
The post ChatGPT Writes Decent Code For Binary to Decimal Conversion first appeared on Exploring Binary.
]]>The post Binary Numbers Haiku (by ChatGPT) first appeared on Exploring Binary.
]]>Nice, but I was looking for the 5/7/5 syllable format (this is 6/8/5), so I asked for that specifically:
Oddly, that was worse in terms of format (5/9/5). I tried again with the original, shorter prompt, and then for some reason it was able to crank out four in a row of the desired format:
Pretty impressive! The first of the four is my favorite (plus it is number-centric, like I asked).
The post Binary Numbers Haiku (by ChatGPT) first appeared on Exploring Binary.
]]>The post What ChatGPT Knows About Exploring Binary (Spoiler: Not Much) first appeared on Exploring Binary.
]]>
It can “write a biblical verse in the style of the King James Bible explaining how to remove a peanut butter sandwich from a VCR” but it’s never heard of my site.
(“Useful resource” is flattering, especially after first hearing it did not know about my site.)
A bit generic but not bad. I do cover the basics of binary numbers, but what makes this blog unique is the discussion of the intricacies of decimal to binary floating-point and binary floating-point to decimal conversions, including the related bugs I’ve found in commercial and open-source software.
Again, pretty generic, and not the specifics I was looking for. My converters and calculators are my most popular pages, followed by the articles Number of Bits in a Decimal Integer, Binary Multiplication, Binary Division, Ten Ways to Check if an Integer Is a Power Of Two in C, and Binary Subtraction. (The “intricacies” articles have a much smaller potential audience.)
(“Clear explanations”. Wait – does it know or is it just continuing to try to flatter me?)
Some of the links I see in my stats from US colleges and universities are from Drexel University, Emory University, New York University, Stanford University, Stony Brook University, University of Texas, University of Washington, Villanova University, and Virginia Tech.
“Bicimal” was a term I found in the bowels of the internet when I was looking years ago for a way to describe fractional binary numbers. I wrote a few articles using it, and the top search results on the term lead to this site.
Another generic answer, although I certainly agree with “make it fun”. I prefer my method though, using tape flags (analogous to base ten blocks) and describing another non-decimal base (base 5) before getting to base 2 (which in its simplicity almost hides the place value pattern).
That’s basically the same answer as for third graders. I found that a different method might be more suited to adults, approaching it by showing that any number can be written as a sum of powers of two (and not calling them “powers”).
“Why does 0.3 + 0.6 = 0.89999999999999991?” was a sentence in my article Why 0.1 Does Not Exist In Floating-Point. It got the answer right at a high level (and with some extra fluff). But I was looking for a more concise answer like “because most decimals have infinite representations in binary, and binary-floating point has finite precision”.
Pretty close, but wrong. It’s actually the largest subnormal number, not the smallest normal number.
I was looking for PHP Hangs On Numeric Value 2.2250738585072011e-308, or even its offshoot, Java Hangs When Converting 2.2250738585072012e-308. (Those two articles went viral, inasmuch as these kinds of articles do.)
That one hurt. It knows about specific websites, just not mine. It said earlier that my site dealt with two’s complement (a generic guess?), yet it missed my Decimal/Two’s Complement Converter, which has been the top Google search result for many years. To boot, none of those sites listed has a two’s complement converter (as far as I can tell).
I really had no expectations for this one, especially at this point. Overly generic, and bullet 5 is wrong.
I would have bet it would have at least picked one of the many Rick Regans that aren’t me.
“Clear and concise”. That’s three times now; I’ll accept the compliments.
The post What ChatGPT Knows About Exploring Binary (Spoiler: Not Much) first appeared on Exploring Binary.
]]>The post Jetpack Compose Byte Converter App: 2022 Version first appeared on Exploring Binary.
]]>
The impetus for updating the app was to change how I represented and handled state. In the original code, the observable state is a mutableState byte value and an array of mutableState, one element for each of the eight bits in a byte. I passed the array as a parameter of type Array<MutableState<Boolean>>. Google, however, recommends passing the State’s value and a lambda to set it instead.
Also, as it turns out, as conceptually clean as I found the bit-to-mutable-state mapping, it was overkill; one mutableState for the whole byte does not impact performance (of a tiny app like this one at least). And it lends itself to a better solution, one based on an immutable state object containing an array of bits (Booleans) and an integer value representing them.
All the code needed for the app, except for the imports, is listed in segments below. (If you copy and paste all the segments into an Android Studio Compose project, the IDE will suggest the required imports.) The essential structure and purpose of the composable functions is unchanged, so you can refer to the original article for details I don’t describe here.
I created an additional, app-level state object, acting kind of like a “view model”. It holds the newly-defined byte object (type UiByte) as mutableState, so recomposition is triggered whenever the mutableState is set to a new object. A new object is created with each bit flip, from a copy of the bit array, but with the changed bit.
When constructing UiByte, the byte’s value is calculated with the specified bit values. This has the vibe of Compose’s “declarative” philosophy, which feels more appropriate than mutating a separate state value with each bit flip. (I also made the calculation more efficient, although that was for aesthetics and not observed performance.)
/** Rick Regan, https://www.exploringbinary.com/ */ class AppState { var byte by mutableStateOf(UiByte()) fun bitFlip(bitPosition: Int) { byte = byte.bitFlip(bitPosition) } } val appState = AppState() class UiByte( private val bits: Array<Boolean> = Array(8) { false } // MSB is index 0 (bit 7); LSB is index 7 (bit 0) ) { val size = bits.size val value = bits.fold(0) { value, bit -> value * 2 + (if (bit) 1 else 0) } // Horner's method fun getBit(bitPosition: Int) = bits[bits.size - 1 - bitPosition] fun getBitPlaceValue(bitPosition: Int) = bitPlaceValues[bitPosition] private companion object { val bitPlaceValues = intArrayOf(1, 2, 4, 8, 16, 32, 64, 128) } fun bitFlip( bitPosition: Int ): UiByte { val newBits = bits.copyOf() val bitIndex = bits.size - 1 - bitPosition newBits[bitIndex] = !newBits[bitIndex] return UiByte(bits = newBits) } }
App() is the new top-level composable function that I added to access the global app state and “launch” the app’s screen:
@Composable fun App() { ByteToDecimal( appState.byte, appState::bitFlip ) }
ByteToDecimal() is the top composable of the app proper; I changed it to pass in the state and lambda, rather than access them globally.
@Composable fun ByteToDecimal( byte: UiByte, bitFlip: (bitPosition: Int) -> Unit ) { Column( horizontalAlignment = Alignment.CenterHorizontally, modifier = Modifier.fillMaxWidth() ) { Byte( byte, bitFlip ) Spacer(modifier = Modifier.padding(top = 20.dp)) Decimal("${byte.value}") } }
I changed Byte() to pass in parameter byte as type UiByte instead of type Array<MutableState<Boolean>> (the motivation for updating the app).
@Composable fun Byte( byte: UiByte, bitFlip: (bitPosition: Int) -> Unit ) { Row { for (bitPosition in byte.size - 1 downTo 0) { Bit( bitPosition = bitPosition, bit = byte.getBit(bitPosition), bitPlaceValue = byte.getBitPlaceValue(bitPosition), bitFlip = bitFlip ) } } }
I made an incidental change to Bit(), passing in bitPlaceValue instead of computing it.
@Composable fun Bit( bitPosition: Int, bit: Boolean, bitPlaceValue: Int, bitFlip: (bitPosition: Int) -> Unit ) { Column( horizontalAlignment = Alignment.CenterHorizontally ) { Text( text = bitPlaceValue.toString() ) val colors = if (bit) { ButtonDefaults.buttonColors( backgroundColor = Color.White, contentColor = Color.Blue ) } else { ButtonDefaults.buttonColors( backgroundColor = Color(240, 240, 240), contentColor = Color.Blue ) } Button( onClick = { bitFlip(bitPosition) }, modifier = Modifier .padding(2.dp) .size(45.dp), colors = colors, border = BorderStroke(1.dp, color = Color.Blue) ) { Text( text = if (bit) "1" else "0", modifier = if (!bit) Modifier.alpha(0.4f) else Modifier ) } Text( text = bitPosition.toString(), color = Color.Gray ) } }
Decimal() is unchanged from the original code.
@Composable fun Decimal( decimal: String ) { Text( text = decimal, Modifier .width(70.dp) .border(BorderStroke(1.dp, color = Color.Black)) .padding(4.dp), textAlign = TextAlign.Center, color = Color(0, 180, 0), fontSize = 5.em ) }
I wrote an alternative implementation for UiByte, using Kotlin’s unsigned byte type (UByte). In this case, the bits and the value are one and the same; the value is the integer value of the UByte, and the bits within it are accessed with masks and bitwise operations. (It felt a little too low-level to use as the primary implementation, at least for the purposes of this article.)
class UiByte( val value: UByte = 0u ) { val size = 8 fun getBit(bitPosition: Int) = (value and bitPlaceValues[bitPosition].toUByte()) != (0u.toUByte()) fun getBitPlaceValue(bitPosition: Int) = bitPlaceValues[bitPosition] private companion object { val bitPlaceValues = intArrayOf(1, 2, 4, 8, 16, 32, 64, 128) } fun bitFlip( bitPosition: Int ): UiByte { val newValue = value xor bitPlaceValues[bitPosition].toUByte() return UiByte(value = newValue) } }
The app worked perfectly fine as coded. And even though I wrote it to a pre 1.0 release alpha, it compiles and runs unchanged on the latest version of Compose/Material2 (Compose UI 1.3.0-alpha03, Compose compiler 1.3.0).
I updated the app because I did not want to pass a State type to my composable functions; I wanted to follow Google’s recommendations. In the process, I consolidated the app’s state into one immutable object.
As newly coded, the app still recomposes efficiently; only the changed bits are recomposed. This either reflects that I didn’t fully understand back then how recomposition worked, or Compose has since added optimizations (or both).
I have learned much more about how to code Compose apps, and how to code better in Kotlin itself. A lot of that can’t be demonstrated with this little demo app though (and getting into those things would be beyond the scope of this blog in any case).
The post Jetpack Compose Byte Converter App: 2022 Version first appeared on Exploring Binary.
]]>The post Anomalies In IntelliJ Kotlin Floating-Point Literal Inspection first appeared on Exploring Binary.
]]>For Doubles for example, every literal over 17-digits should be flagged, since it never takes more than 17 digits to specify any double-precision binary floating-point value. Literals with 16 or 17 digits should be flagged if there is a replacement that is shorter or closer. And no literal with 15 digits or fewer should ever be flagged, since doubles have of 15-digits of precision.
But IntelliJ doesn’t always adhere to that, like when it suggests an 18-digit replacement for a 13-digit literal!
You can enable the inspection in IntelliJ IDEA by going to Preferences -> Editor -> Inspections -> Kotlin -> Other Problems and checking Floating-point literal exceeds the available precision. (The inspection was enabled by default for me.)
Kotlin uses Java’s floating-point to decimal conversion routine, the dtoa() method of Java’s FloatingDecimal class. It has a 20-year old bug against it that is the source of the issue. I learned about this bug over six years ago, when writing “Java Doesn’t Print The Shortest Strings That Round-Trip”. When I recently encountered the Kotlin inspection I went back to that bug report and tried out some of its examples; here are eight literals that the inspection flagged, along with their suggested replacements:
Ex. # | Literal | Digits | Replacement | Digits |
---|---|---|---|---|
1 | 4.8726570057E288 | 11 | 4.8726570056999995E288 | 17 |
2 | 7.68905065813E17 | 12 | 7.6890506581299994E17 | 17 |
3 | 1.790086667993E18 | 13 | 1.79008666799299994E18 | 18 |
4 | 2.273317134858E18 | 13 | 2.27331713485799987E18 | 18 |
5 | 2.82879384806159E17 | 15 | 2.82879384806159008E17 | 18 |
6 | 1.45800632428665E17 | 15 | 1.45800632428664992E17 | 18 |
7 | 1.9400994884341945E25 | 17 | 1.9400994884341944E25 | 17 |
8 | 5.684341886080801486968994140625E-14 | 31 | 5.6843418860808015E-14 | 17 |
Examples 1-6 should not have been flagged, since they have 15 digits or fewer. Moreover, the replacements all have more digits.
Example 7 should not have been flagged either, because the replacement is another 17-digit number which is further than the original from the floating-point number. Written as integers, the original is 19400994884341945000000000, and the replacement is 19400994884341944000000000. Both convert to floating-point as 19400994884341944949932032 (the floating-point value written exactly in decimal). The original is closer to the floating-point value, with an absolute difference of 50,067,968 vs. 949,932,032.
In Example 8, the replacement is shorter than the original, but a one digit shorter replacement, 5.684341886080802E-14, would work as well, even though it’s further than the replacement from the floating-point number. This happens because the literal is a power of two (2^{-44}). The gap size above a power of two is double the gap size below it, which in this case leads to a shorter replacement candidate that is not nearer.
Replacements could change format with respect to the original. For example, 123456789012345678E-16 becomes 12.345678901234567 (the “E” notation is removed), and 1234.56789012345678E-16 becomes 1.234567890123457E-13 (the number is normalized). This is not an error; it’s just a byproduct of FloatingDecimal’s dtoa() method’s rules for formatting, which are what they are.
It was easy enough to determine how the inspection was implemented; the source code is on github. The code is simple, but I simplified it further for the purposes of this article, keeping only the logic for Doubles.
fun intellijFloatingPointLiteralPrecisionInspection( literal: String ): String { var replacement = literal.toDouble().toString() val literalBD = BigDecimal(literal) val replacementBD = BigDecimal(replacement) if (literalBD == replacementBD) replacement = "" return replacement }
The inspection relies entirely on the conversions done under the covers by the Java code, the decimal to floating-point conversion done by toDouble(), and the floating-point to decimal conversion done by toString(). The assumption is that the literal round-trips back from double-precision in its shortest or nearest form.
BigDecimal is used to factor out formatting differences between the literal and the replacement string that toString() returns. For example, if the literal is 5.198135943396802E6, the replacement is 5198135.943396802. Those are numerically equivalent, so there is no need to suggest a replacement.
The implementation of the inspection demonstrates the principle I described in my article “17 Digits Gets You There, Once You’ve Found Your Way”. Literals greater than 17 digits can’t simply be rounded or truncated to 17 digits directly. Depending on how close the literal is to halfway between two binary floating point numbers, all of its digits may be needed to decide the correct Double to round to. The conversion done with toDouble() takes this into account. Once the floating point number is identified, its shortened “stand in” is generated by the return trip conversion, the toString() call.
Subnormal numbers change the rules in that they aren’t subject to the 15/16/17 digit boundaries described above; they have lower, variable effective precision. For example, 8.3616842E-322 has a suggested replacement of 8.35E-322, which is expected because the floating-point number has only 8 bits of precision.
(I did not look for anomalous replacements for subnormal numbers.)
These examples would be addressed by a fix for the FloatingDecimal bug: return the shortest replacement or, if there isn’t a shorter one, return an equal-length replacement that is nearer to the floating-point value. (Coincidentally, this bug has been marked “resolved” as of June 2022, which I noticed as I was writing this article. I will look into it when it is released and incorporated into IntelliJ.)
Short of that proper fix, a workaround in the inspection itself could be to filter out most of the bad replacements. It could filter any replacement returned by toString() that has more digits than the original, and it could use BigDecimal to check whether an equal-length replacement is closer. Adding an else to the code above should take care of those two cases, addressing literals like Examples 1-7:
fun intellijFloatingPointLiteralPrecisionInspectionWorkAround( literal: String ): String { var replacement = literal.toDouble().toString() val literalBD = BigDecimal(literal) val replacementBD = BigDecimal(replacement) if (literalBD == replacementBD) replacement = "" else { // Filter out false positives when { literalBD.precision() < replacementBD.precision() -> replacement = "" literalBD.precision() == replacementBD.precision() -> { val doubleBD = BigDecimal(literal.toDouble()) val literalDeltaBD = (literalBD - doubleBD).abs() val replacementDeltaBD = (replacementBD - doubleBD).abs() if (literalDeltaBD <= replacementDeltaBD) replacement = "" } } } return replacement }
Coding a workaround for “shortest not nearest” cases like Example 8 would be harder. And it may not be worth the effort, since there are only 54 powers of two for which this comes into play.
I submitted issue KTIJ-22245 against the IntelliJ IDEA Kotlin plugin.
If this inspection worked perfectly, I still don’t think I would find it useful. I encountered it while coding floating point literals to approximate logarithms. The originals can be more visually faithful to the actual decimal value. For example, log_{2}(15) = 3.9068905956085185293…, which I coded (rounded to 17 digits) as 3.9068905956085185, had a suggested replacement of 3.9068905956085187. While both map to the same double-precision binary floating-point value (0x1.f414fdb498226p1), the original literal is closer in decimal, and is a correct decimal rounding of the logarithm; the replacement is not.
Also, Doubles don’t have 17 digits of precision (nor do they have 16 digits across the whole range of floating-point numbers). When the suggested replacement has 17 digits, it’s not really solving the “cannot be represented with the required precision” problem; it’s only giving what I have dubbed coincidental precision. This makes the name of the inspection itself questionable.
Perhaps a more generic name would be better: “Another literal can represent the same floating-point number”. That name would also have these benefits:
There probably is no perfect name, because to describe it exactly would take too many words: “A shorter or closer decimal literal can represent the same binary floating-point number”.
These are not accompanied by suggested replacements, but it would seem reasonable to suggest 0 for the “conforms to 0” case and either Double.MAX_VALUE or Double.POSITIVE_INFINITY (for positive numbers for example) for the “conforms to infinity” case.
Also, I would suggest a new inspection for subnormal numbers, warning of their lower precision (there would be no replacement to make).
The post Anomalies In IntelliJ Kotlin Floating-Point Literal Inspection first appeared on Exploring Binary.
]]>The post Showing n! > 2^{n} When n Is A Power of Two first appeared on Exploring Binary.
]]>When I saw this problem though I wondered if I could solve it in another way: Could the factors of two alone in 64! be greater than 2^{64}? As it turns out, almost.
64! has a factor of 2^{63}; 16! has a factor of 2^{15}; 512! has a factor of 2^{511}. That’s what Wolfram Alpha told me, after I worked out similar but smaller examples on paper. The pattern was clear: the factorial of any positive power of two p, p!, had a factor of 2^{p-1}. (p = 2^{k}, for any integer k ≥ 1.)
It’s not hard to see why. The factors of 2 come from the even numbers, and from the 64 factors in 64! (1, 2, 3, …, 64) there are 32 even numbers: 2, 4, 6, …, 64. If you pull out a factor of two from each number in that list you get a new list: 1, 2, 3, …, 32. In that list there are 16 even numbers (2, 4, 6, …, 32) from which you can pull out another 16 factors of 2. Repeating this process until the list reduces to no even numbers (a list of just 1), you have a total number of factors of two of 32 + 16 + 8 + 4 + 2 + 1 = 63.
To generalize, we are repeatedly halving a power of two with each new list of even numbers, and repeatedly halving a power of two 2^{k} gives a sequence of nonnegative powers of two from 2^{k-1} down to 1. If we sum that sequence of powers of two — 2^{0} + 2^{1} + 2^{2} + … + 2^{k-1} — we get 2^{k} – 1.
(I haven’t thought much about how to do this with an inductive proof, or whether it would be necessary — it certainly isn’t for my purposes. But you’d do it in “reverse”, starting with smaller powers of two and proving the property holds for bigger ones.)
Although there aren’t more than p factors of two in p! like I had wondered, the proof that p! > 2^{p} is still trivial just using the powers of two that are present. For our example, the factors 2^{63} and 3 of 64! make it greater than 2^{64}. Because 3 will always be a factor of p! for any p ≥ 4, this result applies generally to show p! > 2^{p}.
The post Showing n! > 2^{n} When n Is A Power of Two first appeared on Exploring Binary.
]]>The post Hexadecimal Numbers: Uppercase or Lowercase? first appeared on Exploring Binary.
]]>For example, do you prefer the integer 3102965292 written as B8F37E2C or b8f37e2c? Do you prefer the floating-point number 126.976 written as 0x1.fbe76cp6 or 0x1.FBE76Cp6?
I ran this poll on my sidebar, and after 96 responses, about 70% are “prefer uppercase” and about 9% are “prefer lowercase”. What do you think? (For the “depends on context” answer I meant things other than numeric values, like the memory representation of strings. However, for the purposes of this article, please answer with just numeric values in mind.)
I had always used uppercase but switched to lowercase when I started this blog. (I don’t remember why, but I think I was under the impression that the wider programming community preferred lowercase.) My article examples are in lowercase (I use “%a” rather than “%A” for hexadecimal floating-point constants), as are the outputs of my floating-point converter (the Hexadecimal floating-point constant and Raw hexadecimal output formats) and base converter (with the default digit characters). Since I’m writing an app that displays hexadecimal numbers, I figured this would be a good time to check my assumptions.
(I think lowercase is easier to read, but uppercase fits better with numeral fonts, making it look more uniformly numeric.)
The post Hexadecimal Numbers: Uppercase or Lowercase? first appeared on Exploring Binary.
]]>The post Another NaN In the Wild first appeared on Exploring Binary.
]]>(According to Castbox, this is an error in the ad and is out of their control.)
The post Another NaN In the Wild first appeared on Exploring Binary.
]]>