Dwayne Crooks

Posted on

# 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" +
}

> 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.

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.

## 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
``````