Suppose I have a function which divides an $m$-bit unsigned integer $a$ by an $n$-bit unsigned integer $b$ and returns the quotient as a fixed-point number with $t$ fractional bits, truncating towards zero. So I have $f(a,b)= 2^{-t}\lfloor 2^t\cdot(a/b)\rfloor$, with $0 \leq a < 2^m$ and $0 < b < 2^n$.
What is the smallest $t$ which will guarantee that $f(a_1,b_1)=f(a_2,b_2)$ only if $a_1/b_1=a_2/b_2$? That is, how many fractional bits do I need to preserve the ordering?
Assume $m \ge n$. Consider the function $$ \begin{aligned}g(k) &= \frac{2^n-k-1}{2^n-k} \\ &= \frac{1-(k+1)2^{-n}}{1-k2^{-n}} \\ &= \left(1-(k+1)2^{-n} \right)\left(1 + k2^{-n} + k^2 2^{-2n} + O(2^{-3n})\right) \\ &= 1-2^{-n}-k 2^{-2n} + O(2^{-3n}) \end{aligned}$$ For large enough $n$, $g(1)$ and $g(2)$ differ by essentially $2^{-2n}$, and therefore require $2n$ bits to distinguish. Conversely, we have $$\left|\frac{a_1}{b_1}-\frac{a_2}{b_2}\right| = \left|\frac{a_1 b_2 - a_2 b_1}{b_1 b_2} \right| \ge \frac{1}{(2^n-1)(2^n-1)} > 2^{-2n}$$ for all distinct fractions, so $2n$ bits is also sufficient.
I don't have a theoretical backing for this, I'm afraid, but based on brute-force testing I've found that $t = 2n$ never produces collisions (for $n$ up to $20$), whereas $t = 2n-1$ always does.
