Write a floored integer division in function of two divisions?

110 Views Asked by At

Is there any method to calculate the floored integer division for the sum of two numbers given the floored division of the summands, without splitting into cases?

I know that, with floored division, we have the two cases that if $a$%$b$ + $a$%$c$ $<c$ then $$\frac{a + b}{c} = \frac ac + \frac bc $$

and if $a$%$b$ + $a$%$c$ $\geq c$ then $$\frac{a + b}{c} = \frac ac + \frac bc + 1 $$

I wish to know if a non case-separated equation exists or not ?

1

There are 1 best solutions below

0
On

No, you have to separate into cases; in particular, if we let $$f(x)=\left\lfloor\frac{x}c\right\rfloor$$ then this question asks if we can determine $f(a+b)$ given $f(a)$ and $f(b)$. As your cases show, we know that one of the following holds: $$f(a+b)=f(a)+f(b)$$ $$f(a+b)=f(a)+f(b)+1$$ However, to know which is which, we'd have to know something about the "excess" that we rounded off - that is, are $a-cf(a)$ and $b-cf(b)$ large enough to contribute an extra $1$ to $f(a+b)$? To be very explicit, notice that $n_1=f(cn_1)=f(c(n_1+1)-1)$ and $n_2=f(cn_2)=f(c(n_2+1)-1)$. If we could determine the sum $f(a+b)$ given just $f(a)$ and $f(b)$, then it would have to be that $f(cn_1+cn_2)$ equalled $f(c(n_1+1)-1+c(n_2+1)-1)$, since their summands have the same integer part in division. However, the former has $f(cn_1+cn_2)=n_1+n_2$ whereas the latter has $f(cn_1+cn_2+2c-2)=n_1+n_2+1$. Thus, the sum cannot be further determined just from $f(a)$ and $f(b)$.

We can, however, see that the identity: $$\left\lfloor\frac{a+b}{2c}\right\rfloor=\left\lfloor\frac{\left\lfloor\frac{a}c\right\rfloor+\left\lfloor\frac{b}c\right\rfloor}{2}\right\rfloor$$ does hold, since it holds in either case.