For my recent search for short examples of double rounding errors in decimal to double to float conversions I wrote a Kotlin program to generate and test random decimal strings. While this was sufficient to find examples, I realized I could do a more direct search by generating only decimal strings with the underlying double rounding error bit patterns. I’ll show you the Java BigDecimal based Kotlin program I wrote for this purpose.

## Overview of The Code

For my initial exploration of double rounding errors in floating-point conversions I generated examples by hand, setting the required bit patterns indirectly to produce long decimal strings. It occurred to me that some of these long decimal strings could be rounded to much shorter ones — like 0.1000000000000000055511151231257827021181583404541015625 rounds to 0.1 — and map to the same double, in our case the double representation of a float midpoint. From there, it’s only a matter of checking if the double rounding error still occurs, since the decimal number could have shifted to the midpoint or to the other side of it.

Starting with a randomly selected double rounding error bit pattern (which I call a “template” in the code) I fill in the “don’t care” bits with a random value and then randomly shift those example bits left or right a random number of binary places to create a decimal number that will experience a double rounding error upon conversion from decimal to double to float. I do these calculations using BigDecimal operations on powers of two, meaning I create a decimal number indirectly by thinking of its construction in binary. Then, I successively round this long, exact decimal representation to 17 digits, 16 digits, 15 digits, etc., stopping when the double rounding error no longer occurs. (In many cases the 17-digit representation does not even cause an error.)

## Kotlin Program

Here is the Kotlin code I wrote:

/* Rick Regan, https://www.exploringbinary.com/ */ import java.math.BigDecimal import java.math.MathContext import java.math.RoundingMode import kotlin.random.Random funfindDoubleRoundingExamples(maxLength: Int) { val random = Random(1) for (i in 1..1_000_000) { val (decimal, numSigDigits) =generateDoubleRoundingExample(random) if (numSigDigits <= maxLength) { // Only interested in numbers this short or shorter println("$numSigDigits digits: $decimal") } } } fungenerateDoubleRoundingExample(random: Random): Pair<String, Int> { val decimalExact =generateExactDoubleRoundingExample(random) var numSigDigits = decimalExact.precision() // Try to make the exact number shorter (often will get at least a 17-digit number) var decimalPrev = decimalExact.toString() for (i in 17 downTo 1) { val decimal = decimalExact.round(MathContext(i,RoundingMode.HALF_UP)).toString() if (decimal.toFloat() == decimal.toDouble().toFloat()) break // No double rounding error at this length decimalPrev = decimal numSigDigits = i } return Pair(decimalPrev, numSigDigits) } fungenerateExactDoubleRoundingExample(random: Random): BigDecimal { /* Double rounding bit pattern templates (pick one randomly) 1 2-23 (any value) 24 25 26-53 54 up 1: 18014401730707455 : 1 0000000000000000000000 1 0 1111111111111111111111111111 1 1 up 2: 18014401730707454 : 1 0000000000000000000000 1 0 1111111111111111111111111111 1 0 down 1: 18014399583223809 : 1 0000000000000000000000 0 1 0000000000000000000000000000 0 1 down 2: 18014399583223810 : 1 0000000000000000000000 0 1 0000000000000000000000000000 1 0 */ val templateBits = when (random.nextInt(1, 5)) { 1 -> BigDecimal(18014401730707455) 2 -> BigDecimal(18014401730707454) 3 -> BigDecimal(18014399583223809) else -> BigDecimal(18014399583223810) } /* Generate a random 22-bit integer to fill out bits 2-23 (22-bit numbers lie between 2^21 = 2,097,152 and 2^22 - 1 = 4,194,304 - 1). Shift the number left 32 bits (2^32 = 4,294,967,296) so it will start at bit 2 when added in to the template */ val pow2To21 = 2_097_152 val pow2To22 = 4_194_304 val pow2To32 = BigDecimal(4_294_967_296) val exampleBits = templateBits + BigDecimal(random.nextInt(pow2To21, pow2To22)) * pow2To32 /* The max binary exponent for a float is 127, and the min (normal) exponent is -126. We have a 55-bit integer, so normalized its binary exponent starts out as 54. This means we can only shift the point to the right a max of 73 more bits: 127 - 54 (add 1 for non-inclusive endpoint to get 74), but we can shift the point to the left as much as 180 bits: 126 + 54 (add 1 for non-inclusive endpoint to get 181). */ return if (random.nextBoolean()) // Randomly pick a left or right shift exampleBits * BigDecimal(2).pow(random.nextInt(0, 74)) else exampleBits.divide(BigDecimal(2).pow(random.nextInt(1, 181))) // Kotlin quirk: Must use divide() since / operator does integer division } funmain() {findDoubleRoundingExamples(12) // Look for examples of 12 digits or fewer (change as desired) }

### Code notes

- I classify the bit patterns into four types (I describe them as three types and a subcase in my article):
*up pattern 1*,*up pattern 2*,*down pattern 1*, and*down pattern 2* - I start rounding at 17 digits because I view that as the start of the “short” examples.
- The rounding loop is overkill sometimes; a string of 0s that leads to short strings could be removed in one swoop. (I wanted to keep it simple.)
- I test for double rounding errors by doing the decimal to float and decimal to double to float conversions. In an alternative version of the code (not shown) I just checked the bit patterns of each rounded number to see if it matched an error pattern. I did this by scaling the BigDecimal representation of the string to an integer, converting that to a BigInteger, converting that to a binary string, and then testing the bits to see if they matched one of the patterns. That is more code, but it is independent of any particular language’s decimal to floating-point conversion routine (which may have errors).
- Only normal (not subnormal) numbers are generated and tested.
- Kotlin allows you to use operator symbols for BigDecimal operations; for example, ‘*’ instead of multiply(), and ‘/’ instead of divide(). However, oddly, the ‘/’ ends up doing integer arithmetic, so I had to use divide().

## Examples

Here are some examples the program found, from the initially generated decimal number to the shortest rounding:

**17 digits**: 16581582576129408000 => **1.6581582576129408E+19**

**17 digits**: 3929563.874999999767169356346130371093750 => **3929563.8749999998** (this looks like it could round up to 10 digits but it doesn’t)

**13 digits**: 585276137701600012475039744 => **5.852761377016E+26**

**13 digits**: 150821866599299996733401494192128 => ** 1.508218665993E+32**

**11 digits**: 6.058141011400000204336628621036399613317319814496643298255323900016867931117800261830346267299951534823776455596089363098144531250E-33 => **6.0581410114E-33**

**10 digits**: 5169850375000000058598302970544128 => **5.169850375E+33**

**10 digits**: 9347089477999999790045239508467712 => **9.347089478E+33**

## Observations

The initially generated decimal string is not guaranteed to round to a shorter string that causes a double rounding error. In my tests, on average, about 45% round to at least a 17 digit example. If you break it out by pattern type, about 38% of *up pattern 1*, about 62% of *up pattern 2*, about 28% of *down pattern 1*, and about 62% of *down pattern 2* round to at least a 17 digit example.

During the sequence of roundings, an initial *up pattern 1* can end with a shorter string that exhibits *up pattern 2* (and vice versa). Similarly, an initial *down pattern 1* can end up with a shorter string that exhibits *down pattern 2* (and vice versa).

I was surprised at first to see *up pattern 1*s converting to *up pattern 2*s and *down pattern 1*s converting to *down pattern 2*s. But after looking at examples I saw that this happened only for roundings to integers — integers with their last 1 bit at bit 54. For example, in an *up pattern 1* to *up pattern 2* scenario, 28808324560453631 rounded to 28808324560453630, the latter changing bit 55 from 1 to 0 (and keeping bit 54 1). In a *down pattern 1* to *down pattern 2* scenario, 16301684200308736.5 rounded to 16301684200308737, with the former having bit 54 = 0 and bit 55 = 1, and the latter having bit 54 = 1 (and no bit 55).

(Cookies must be enabled to leave a comment...it reduces spam.)