1
$\begingroup$

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?

$\endgroup$
0

2 Answers 2

1
$\begingroup$

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 !

$\endgroup$
3
  • $\begingroup$ Great, I went through the proof myself, and agree that it does proof the equation, which is very helpful. Do you know if this way of accurately calculating floor integer division by multiplication with the reciprocal is a well know method? I am a professional in electronics development, doing algorithms on FPGA/ASIC, and being able to do fast integer division with a fixed number is sometimes very useful, so the method is very valuable, but I was not aware of this previously. $\endgroup$
    – EquipDev
    Sep 28, 2017 at 9:12
  • $\begingroup$ I'm afraid I don't know, I would look in popular libraries such as gmp to see what kind of tricks they use. $\endgroup$
    – mercio
    Sep 28, 2017 at 9:30
  • $\begingroup$ OK, thanks for the answer; and for helping out with this :-D $\endgroup$
    – EquipDev
    Oct 1, 2017 at 13:29
1
$\begingroup$

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$.

$\endgroup$
2
  • $\begingroup$ I appreciate your answer, and it gave me some good inspiration; however, I accepted the other answer, since it was more tight, thus actually proving the equation. $\endgroup$
    – EquipDev
    Sep 28, 2017 at 9:07
  • $\begingroup$ @EquipDev: thanks for caring to explain. $\endgroup$
    – user65203
    Sep 28, 2017 at 9:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .