Beware of integer division in Elm 0.19.1

Recently, I was implementing a function, toHex, that converts a non-negative integer represented in base 10 to its base 16 representation. For e.g.

> toHex 0
Just [] -- the empty list works for my needs

> toHex 16
Just [0, 1]

> toHex 255
Just [15, 15]

> toHex (2^32)
Just [0, 0, 0, 0, 0, 0, 0, 0, 1]

I wanted the function to work for all integers in the range 0 to Number.MAX_SAFE_INTEGER (= 2^53 - 1). However, when I tried toHex (2^53 - 1) I got Just [15, 15] which, as you can see from the example, is the same as toHex 255.

My implementation of toHex makes use of divModBy which is implemented as follows:

divModBy : Int -> Int -> (Int, Int)
divModBy divisor dividend =
    ( dividend // divisor
    , modBy divisor dividend
    )

And one step of the base conversion calculation involves computing divModBy 16 (2^53 - 1), which turns out to be equal to (-1, 15).

To understand the previous result we have to understand how Elm implements integer division.

Integer division in Elm

In Basics.elm we have:

infix left 7 (//) = idiv

idiv : Int -> Int -> Int
idiv =
    Elm.Kernel.Basics.idiv

Then, in Elm.Kernel.Basics.js we have:

var _Basics_idiv = F2(function(a, b) { return (a / b) | 0; });

Interesting! It makes use of JavaScript's bitwise OR. According to the description of bitwise OR, the operands are converted to 32-bit integers and numbers with more than 32 bits get their most significant bits discarded.

Let's do the calculation by hand to see how the result unfolds.

> a = 2^53 - 1
> b = 16
> a / b
562949953421311.94

What's the hexadecimal representation of 562949953421311.94?

function float64ToHex(number) {
    const view = new DataView(new ArrayBuffer(8));
    view.setFloat64(0, number);

    return "0x" +
        view.getUint32(0).toString(16).padStart(8, '0') +
        view.getUint32(4).toString(16).padStart(8, '0');
}

> float64ToHex(562949953421311.94)
0x42FF_FFFF_FFFF_FFFF

So,

(a / b) | 0
= 0x42FF_FFFF_FFFF_FFFF | 0 // before converting the operands to 32-bit integers
= 0xFFFF_FFFF | 0           // after converting the operands to 32-bit integers
= 0xFFFF_FFFF
= -1                        // 32-bit two's complement

// Check for yourself

> int32View = new Int32Array(new ArrayBuffer(4))
> int32View[0] = 0xFFFF_FFFF
> int32View[0]
-1

To be fair the documentation for Int does indicate that Int math is only well-defined in the range -2^31 to 2^31 - 1.

A workaround

Now that we know the problem we can try to fix it so that we're able to compute the correct quotient. The main culprit is Elm's use of the bitwise OR which returns its result as a 32-bit integer. A slower but correct implementation that works with all integers in the safe range is the following:

divModBy : Int -> Int -> (Int, Int)
divModBy divisor dividend =
    ( floor (toFloat dividend / toFloat divisor)
    , modBy divisor dividend
    )

And,

> divModBy 16 (2^53 - 1)
(562949953421311, 15)

Key takeaways

1. The safe range for the Int data type is between -2^53 and 2^53 - 1 inclusive.
2. Int math is only well-defined between -2^31 and 2^31 - 1. As far as I can tell, addition, subtraction, and multiplication work well in the safe range but integer division isn't well-defined when the quotient is outside the well-defined range.
3. The bitwise operators convert their operands to 32-bit integers and return their results as a 32-bit integer. Thus, any use of these operators in the implementation means that you need stick within the well-defined range to get the results you'd expect.

Helpful Resources

Learn about JavaScript's bitwise operators and how they work.

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Guide/Expressions_and_Operators#bitwise_operators

Before exploring this problem I didn't know about JavaScript's typed arrays. These resources helped me to understand them alot better.

• https://developer.mozilla.org/en-US/docs/Web/JavaScript/Typed_arrays
• https://web.dev/webgl-typed-arrays/

Bonus

We can verify the hexadecimal representation of 562949953421311.94 as follows:

> buffer = new ArrayBuffer(8) // 8 bytes = 64 bits
> view = new DataView(buffer)
> view.setUint32(0, 0x42FFFFFF)
> view.setUint32(4, 0xFFFFFFFF)
> view.getFloat64(0)
562949953421311.94