Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Especially when you have more than 2 variables and those terms are divided by an integer n within the ceiling/floor functions.

share|improve this question

1 Answer 1

up vote 2 down vote accepted

A partial answer to get an upper bound for individual floor/ceiling function.
There may be better solutions.

Due to the property of the floor function, you can always take out integers.
$\lfloor x+n\rfloor=\lfloor x\rfloor +n$, if $x$ is a real number and $n$ any integer.

This means for $\lfloor \dfrac{v_1+\dots+v_k}{n}\rfloor$, an upper bound is to check all $0\leq v_i < n$ combinations.
Any time $v_i=an+b$, you may take out $a$ and leave $b$ inside as a fraction.

Edit: added multiplication case:
Suppose you have $\lfloor\dfrac{v_1v_2\dots v_k}{n}\rfloor$.
Then you can write it as:
$\lfloor\dfrac{(an+b)v_2\dots v_k}{n}\rfloor$
$=\lfloor (av_2\dots v_k)+\dfrac{bv_2\dots v_k}{n}\rfloor$
$=(av_2\dots v_k)+\lfloor \dfrac{bv_2\dots v_k}{n}\rfloor$

and once again you may assume all the variables $0\leq v_i< n$.
This gives a maximum of $n^k$ combinations to be checked within each ceiling/floor function.

But in actual situation/working you can usually do better:
1) Some $v_i$ might not have the full range.
2) After setting some $v_i$, the remaining $v_i$ might not matter.
3) Due to interaction of different floor functions, some cases may be combined/simplified.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.