6
$\begingroup$

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?

$\endgroup$

migrated from math.stackexchange.com May 31 '13 at 10:17

This question came from our site for people studying math at any level and professionals in related fields.

3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Note that this is the case regardless of whether truncation or round-to-nearest is used. $\endgroup$ – Sneftel Jun 5 '13 at 14:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.