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$
5
  • $\begingroup$ Are you assuming anything about $a,b,c,d$ (e.g. that they are positive integers)? $\endgroup$ 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$
6
  • 1
    $\begingroup$ Did you mean to conclude $b=2$? $\endgroup$ 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.