Direct Generation of Double Rounding Error Conversions in Kotlin

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

fun findDoubleRoundingExamples(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")
        }
    }
}

fun generateDoubleRoundingExample(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)
}

fun generateExactDoubleRoundingExample(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
}

fun main() {
    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 1s converting to up pattern 2s and down pattern 1s converting to down pattern 2s. 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).