// HACKER NEWS — CYBERSECURITY
Moving integer division to floating-point is trivial
Integer division q=(x/y) and remainder (of Euclidean division) r=(x%y) hardware operations are very sad
on current hardware. Typically very long latency and poor throughput. In contrast floating-point division
is pretty happy: shorter latency, higher throughput and often more execution units to perform the
operation. So there are cases it could be interesting to move some integer div/mod operations to floating point.
But it’s PITA right? Actually I think it’s easy. The math is pretty straightforward so if I’ve made a mistake
I expect to find out rather soon.
My claim is: for two integers x & y (signed or unsigned) that fit in 53/24 bits for double/single
precision respectively, with both promoted to floating point then:
From here on I will only consider unsigned integers since it’s the harder case (signed have a smaller max magnitude) but recall
that floating point effective stores a signed magnitude quantity.
Note that there are proven methods (SEE: Formally verified 32- and 64-bit integer division using double-precision floating-point arithmetic)
The standard rounding mode is: round-to-nearest (ties to even) and the first important observation is the ties
part. A tie happens when the exact result of an operation is exactly at the midpoint between two
floating point numbers. Floating point division (in our case of base-2 and same working precision) has zero
midpoints (SEE: Midpoints and exact points of some algebraic functions in floating-point arithmetic section 6.1, corollary 1).
Therefore there’s never a tie and only round-to-nearest portion applies.
Let’s look an example using a 4-bit precision floating point format with all possible configurations where the exact
result is less than one but as close as possible to rounding up:
Prior to rounding the hardware computes three extra digits: guard bit (G), round bit (R) and sticky bit (S) but since
the tie case is impossible we only need to know G. Therefore in any format where the exact result has $r$ bits for the
fractional part then for rounding to the next integer to occur requires the fractional part to have at least $r+1$ leading ones.
I’m claiming that this is impossible with legal inputs.
Since we only need to consider what happens with the fractional part let’s breakdown the exact result of $x/y$ into its integer $n$ and fractional parts:
(where $b=y$ just to be less of an eyesore) so obviously:
Given a $p$ precision binary floating point format the division produces a $d$-bit integer leaving $r$-bits for the remainder: