5
$\begingroup$

Consider a simple sum of floor functions: $$S = c\left\lfloor \frac{x}{a}\right\rfloor + d\left\lfloor \frac{x}{b} \right\rfloor$$

Can we combine these two terms into a single function? I am trying to simplify something like this to avoid successive divisions in a computer program.

My question, in general, is: can we combine the following $k$ terms to avoid performing $k$ divisions and multiplications of $x$: $$S(x,k)=\sum_{i=0}^{k}c_i\left\lfloor \frac{x}{a_i}\right\rfloor$$

$\endgroup$
  • $\begingroup$ Are you assuming anything about $a,b,c,d$ (e.g. that they are positive integers)? $\endgroup$ – Robert Israel Jun 8 '17 at 21:30
  • $\begingroup$ Yes, we can assume that every coefficient is a positive integer $\endgroup$ – Nisrak Jun 8 '17 at 21:35
  • 2
    $\begingroup$ No such combination formula in general. Computation-wise (assuming $x$ is a variable and $a_i$ are constants) you could save the divisions by pre-computing $1/a_i$ to reduce it to multiplications in the loop. $\endgroup$ – dxiv Jun 9 '17 at 5:19
  • $\begingroup$ Is there a way to prove that no such combination formula exists? I.e., can we prove that the summation given above must require k operations to find S(x,k) for a given x? $\endgroup$ – Nisrak Jun 9 '17 at 20:24
  • $\begingroup$ Are you trying to build the table of $S(x, k)$ ? $\endgroup$ – Mudream Jun 10 '17 at 2:07
3
$\begingroup$

A simple compute, this might not be a proof :

Assume $\exists a, b \in \Bbb N $ s.t. $\forall x$

$$\left[\frac{x}{2}\right] + \left[\frac{x}{3}\right] = a\left[\frac{x}{b}\right]$$

put x = 2 :

$$a\left[\frac{2}{b}\right] = 1$$

$$\Rightarrow a = 1, b = 2$$

But $\left[\frac{x}{2}\right] + \left[\frac{x}{3}\right] > \left[\frac{x}{2}\right]$ for large enough $x$.

This form might not be able to simplify if the denominators has no limitation.

$\endgroup$
  • 1
    $\begingroup$ Did you mean to conclude $b=2$? $\endgroup$ – Matthew Conroy Jun 9 '17 at 3:39
  • $\begingroup$ Oh thanks @Matthew Conroy $\endgroup$ – Mudream Jun 9 '17 at 4:09
  • $\begingroup$ I'm not sure I follow. Are you attempting to prove that such an a,b exist or are you showing that they do not exist? $\endgroup$ – Nisrak Jun 9 '17 at 20:29
  • $\begingroup$ @Nisrak, a, b do not exist. $\endgroup$ – Mudream Jun 10 '17 at 1:23
  • $\begingroup$ I see. Any ideas to develop a more complete proof? Maybe we can somehow equate this to combining terms of a polynomial, which you obviously can't do? $\endgroup$ – Nisrak Jun 10 '17 at 2:01

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.