How many times can I perform $\left\lfloor\frac{n-f}{s} + 1\right\rfloor$ on $n$ before the result becomes negative or zero?

Question

How do I compute how many times can a mathematical operation be performed before the answer starts becoming negative or zero.

Specifically, I am looking for how many times can I perform $$\left\lfloor\frac{n-f}{s} + 1\right\rfloor$$ on $n$.

Where f,s,n are Whole Numbers and f<=n and s<=n This function is used to compute the output size of a convolution layer in Convolution Neural Networks used for Image Processing. So if I start with $n = 639$ and $f$ and $s$ as $3$ and $2$, respectively, I can go from $639$ to $319$ ($\lfloor(639-3)/2 + 1\rfloor$) to $159$ ($\lfloor(319-3)/2+1\rfloor$) to $79$ to $39$ to $19$ to $9$ to $4$ to $1$, after which I cannot perform $n-f$ anymore. So $f(639,3,2) = 8$ since I can perform this operation $8$ times.

Also curious to know if there is a mathematical term for how many times can I perform a particular operation?

Answer 1

You can figure this out inductively:

First, look at the case when you can only do it once, i.e. $\lfloor \frac{n - f}{s} + 1 \rfloor \leq 0$. That implies that $\frac{n - f}{s} + 1 < 1$, or in other words $n < f$.

Then consider the case when it takes two iterations. In that case, we know that $\lfloor \frac{n - f}{s} + 1 \rfloor < f$, since we need this iteration to return something that will satisfy the restriction above. This then becomes $\frac{n - f}{s} + 1 < f$, since $f$ is an integer, and we can reduce that to $n < f + s(f - 1)$.

Going to three iterations, we now have $\lfloor \frac{n - f}{s} + 1 \rfloor < f + s(f - 1)$, which we can rearrange to $n < f + s(f - 1) + s^2(f - 1)$.

At this point there's a pretty clear pattern: for $k$ iterations, the range that gets sent below zero is $n < f + s(f - 1) + s^2(f - 1) + \ldots + s^{k-1}(f - 1)$. We can simplify that using the formula for a geometric series, giving $n < f + s(f-1)\frac{s^k - 1}{s - 1}$.

Finally, we can take that and solve for $k$ if $f>1$:

$\begin{eqnarray} n & < & f + s(f - 1) \frac{s^k - 1}{f - 1} \\ \frac{s^k - 1}{s - 1} & > & \frac{n - f}{s(f - 1)} \\ s^k - 1 & > & \frac{(n - f)(s - 1)}{s(f - 1)} \\ k & > & \log_s \left( 1 + \frac{(n - f)(s - 1)}{s(f - 1)} \right) \end{eqnarray}$

and taking the ceiling of the right-hand side should give the correct value of $k$. Checking on your corner cases, we have:

$\begin{eqnarray} k(26, 5, 3) & = & \left\lceil \log_3 \left(1 + \frac{(26 - 5)(3 - 1)}{3(5-1)}\right) \right\rceil \\ & = & \left\lceil \log_3 (4.5) \right\rceil \\ & = & 2 \\ k(4, 4, 2) & = & \left\lceil \log_2 \left(1 + \frac{(4 - 4)(2 - 1)}{2(2 - 1)} \right) \right\rceil \\ & = & \lceil \log_2 (1.5) \rceil \\ & = & 1 \end{eqnarray}$

so at least on those values we're getting your expected answer.

Answer 2

Let

$$F(n) = \left\lfloor \frac{n-f}{s}+1 \right\rfloor, G(n)=\frac{n-f}{s}+1$$

and let $F(F(F(x))) = F_3(n)$, and in general $F_m(n)$, with the same notation for $G$. Now the question becomes: "What is the largest $m$ for which $F_m(n) > 0$?"

Note that $G_m(n) \ge F_m(n)$ for all $n$. Since $F_m(n)$ is integer-valued, if $G_m(n)<1$, then $F_m(n) \le 0$. We can now instead ask "What is the largest $m$ for which $G_m(n) \ge 1$?" and use a more well-behaved function.

Assuming $s>1$, and letting $t = \frac1s$, if we iterate $G(n)$, we find the following:

$$G_m(n) = nt^m - ft \sum_{i = 0}^{m-1} t^{i} + \sum_{j=0}^{m-1} t^j = nt^m - ft \left(\frac{1-t^m}{1-t} \right) + \frac{1-t^m}{1-t}$$

With some rearrangement we can get:

$$t^m = \frac{(1-t)G_m(n) + ft - 1}{n - nt + ft - 1}$$

Since we want $G_m(n) \ge 1$, we have:

$$t^m \ge \frac{1 - t + ft - 1}{n - nt + ft - 1} \implies m \log t \ge \log \left( \frac{ft - t}{n - nt + ft - 1} \right) \\ \implies m \le \frac{\log (ft - t) - \log (n - nt + ft - 1)}{\log t} = \frac{\log \left( \frac f s - \frac1s \right) - \log \left(n- \frac n s + \frac f s - 1 \right)}{\log \frac1s}$$

We know that $\log \frac1s$ is negative because $s>1$, hence the change of direction of the inequality. So your maximum $m$ is the floor of the expression on the right.

Note that if $s=1$, the terms involving $s$ completely disappear, and we have a simple arithmetic progression. In that case, we find our maximum $m$ at $n/(f-1)$, thanks to adding $1$ each round.