For $$q = \lfloor \frac{n}{d} \rfloor,$$ we can instead use $$q = nM \gg s.$$ By first thinking about it as $$q = \lfloor \frac{n}{d} \rfloor = \lfloor \frac{nM}{2^{p}} \rfloor,$$ This makes $$\lfloor \frac{1}{d} \rfloor = \lfloor \frac{M}{2^{p}} \rfloor,$$ and, in fact, $$M \approx \lceil \frac{2^{p}}{d} \rceil.$$ We can then make $$p = b + s,$$ where b is the size of the inputs of multipication. For example, on 64-bit hardware, b = 64, but for C's integers, b = 32. We can now solve for M using $$M = \lceil \frac{2^{64 + s}}{d} \rceil,$$ using the smallest non-zero natural for s, so the formula works for all n. Finding s is usually done on an incremental basis. Checking s can usually be done by applying many inputs and checking them all, but there is a systematic way of checking s. With $$0 \le r = n - qd \le d - 1,$$ r is the remainder, so $$n = qd + r.$$ Then, $$nM = qdM + rM.$$ Now, change $$dM \to 2^{p} - e,$$ (defining e) and then, using the distributive property and associativity property, $$nM = q2^{p} + (qe + rM).$$ If we floor divide by 2^p, and then subtract q on both sides, we get $$\lfloor \frac{nM}{2^{p}} \rfloor - q = \lfloor \frac{qe + rM}{2^{p}} \rfloor.$$ (q is not floored, since it is an integer.) Since we defined q as the minuend they are both the same. Thus, on the right-hand side, if s and M really are correct, should be $0$. With the largest quotient $$0 \le q \le Q = \frac{2^{b} - 1}{d},$$ We can substitute the maxima to get this inequality for checking s and M: $$Qe + (d - 1)M \le 2^{p} - 1.$$