Unicode.Internal.Division

Fast division by known constants.

Division by a constant can be replaced by a double-word multiplication. Roughly speaking, instead of dividing by x, multiply by 2^64/x, obtaining 128-bit-long product, and take upper 64 bits. The peculiar details can be found in Hacker's Delight, Ch. 10.

Even GHC 8.10 does not provide a primitive for a signed double-word multiplication, but since our applications does not involve negative integers, we convert Int to Word and use timesWord#.

Textbook unsigned division by 21 or 28 becomes involved, when an argument is allowed to take the full range of Word up to 2^64. Luckily, in our case the argument was casted from Int, so we can guarantee that it is below 2^63.

Documentation

quotRem21 :: Int -> (Int, Int)

Input must be non-negative.

Instead of division by 21, we compute floor(floor((2^68+17)21 * n) 2^68) = floor((2^68+17)21 * n2^68) = floor(n21 + (n2^63 * 1732)21) = floor(n/21), because n2^63 * 1732 < 1.

quotRem28 :: Int -> (Int, Int)

Input must be non-negative.

Instead of division by 28, we compute floor(floor((2^65+3)7 * n) 2^67) = floor((2^65+3)7 * n2^67) = floor(n28 + (n2^63 * 34)28) = floor(n/28), because n2^63 * 34 < 1.