Is this a known method for positive integer floor division through multiplication?

Question

For fast division, I would like to do positive integer floor division of $a \in \mathbb{N}$ and $b \in \mathbb{N+}$ through multiplication as:

$$\frac{a}{b} = a \cdot \frac{1}{b}$$

When $a$ and $b$ are of limited bit length, given by $len(a)$ and $len(b)$, an error is usually introduced by the truncation in the floor operation ($\lfloor x \rfloor$), even when scaling the reciprocal value of $b$ with $len(a) + len(b)$ as:

$$\left\lfloor \frac{a}{b} \right\rfloor = \left\lfloor\frac{a \cdot \left\lfloor\frac{2 ^ {len(a) + len(b)}}{b}\right\rfloor}{2 ^ {len(a) + len(b)}}\right\rfloor$$

The reason for doing as above, is that for repeated division with same value of $b$, $\left\lfloor\frac{2 ^ {len(a) + len(b)}}{b}\right\rfloor$ can then be calculated once and held as integer value with fixed length, and the final floor division by $2 ^ {len(a) + len(b)}$ is a simple truncation of bits, whereby the division is converted to a simple integer multiplication.

However, it appears for a number of specific cases that I have tried, that by adding $1$ to the multiplication constant, the multiplication actually gives the correct result, thus doing:

$$\left\lfloor \frac{a}{b} \right\rfloor = \left\lfloor\frac{a \cdot \left\lfloor\frac{2 ^ {len(a) + len(b)}}{b} + 1\right\rfloor}{2 ^ {len(a) + len(b)}}\right\rfloor$$

Is my conclusion correct, and is there a proof of this method for division?

Answer 1

Let $c = 2^{len(a)+len(b)}$ and let us write $a = kb+p$ and $c = lb+q$, where $k,p,l,q \ge 0$ and $p,q < b$.

Then you are asking if $k = \lfloor \frac {a(l+1)}c \rfloor$, or equivalently, if $ck \le a(l+1) < c(k+1)$.

Multiply it by $b$, so it is equivalent to $c(a-p) \le a(c-q)+ab < c(a-p)+bc$.
Then substract $ac$ from everywhere to get $-pc \le a(b-q) < c(b-p)$.

The first inequality is now obvious. For the second, we have to use that $c$ is very large, mainly that $c > ab$. Moreover, $b-p \ge 1$, and $b-q \le b$,
and then it is proven by

$a(b-q) \le ab < c \le c(b-p)$

Therefore your computation does give the correct result !

Answer 2

With an obvious notation, we have $a<2^\alpha,b<2^\beta$. Then we use the identity $\lfloor t\rfloor=t-\{t\}$. The formula is

$$\left\lfloor\frac a{2^{\alpha+\beta}}\left(\frac{2^{\alpha+\beta}}b-\left\{\frac{2^{\alpha+\beta}}b\right\}\right)\right\rfloor.$$

In the best case (no fractional part), this is exactly

$$\left\lfloor\frac ba\right\rfloor.$$ In the worst case (fractional part nearing $1$),

$$\left\lfloor\frac a{2^{\alpha+\beta}}\left(\frac{2^{\alpha+\beta}}b-1\right)\right\rfloor=\left\lfloor\frac ab-\frac a{2^{\alpha+\beta}}\right\rfloor$$ and you have a negative error term than can result in an error of $-1$.

---

Now with the modified formula,

$$\left\lfloor\frac ab+\frac a{2^{\alpha+\beta}}\left(1-\left\{\frac{2^{\alpha+\beta}}b+1\right\}\right)\right\rfloor,$$ the error term is always positive. But then it might be possible that in some cases it causes an error of $+1$.