0
$\begingroup$

First of all, I am not a mathematician so forgive me for the errors.

I am dealing with a processing pipeline that applies a reduction function, $r(x)$, $n$ times at its core, where:

$$r(x) = \lceil x/2 \rceil$$

If I am applying this function $n = 3$ times then, the processing pipeline function $R_n(x)$ would be:

$$R_3(x) = r(r(r(x)))$$

How could I generalize this expression for an arbitrary $n$ number of times? I am looking for:

$$R_n(x) = ¿?$$

I know this must be very simple, but I just can not generalize it. I have search over recursive functions like the Fibonacci which gave me some clues but still can not generalize it. Thanks in advance community!

$\endgroup$
2
  • $\begingroup$ What is your goal? To obtain an explicit expression for $R_n(x)$ in terms of $x$? $\endgroup$ Commented Oct 14, 2020 at 11:43
  • $\begingroup$ Yes! thank you for your interest $\endgroup$
    – JVGD
    Commented Oct 14, 2020 at 14:19

1 Answer 1

1
$\begingroup$

The answer is simple: $$R_n(x) = \lceil \frac{x}{2^n} \rceil$$ Applying $r$ will halve the value, so applying it $n$ times will divide by $2^n$. The repeated roundings upwards turn out not to matter, and can just be done once at the end.

$\endgroup$
3
  • $\begingroup$ Really appreciated man, upvoted. However I don't really see how the rounding upwards does not matter, is it distributive? $\endgroup$
    – JVGD
    Commented Oct 14, 2020 at 14:18
  • $\begingroup$ OK, tested, it really works! Thank you! $\endgroup$
    – JVGD
    Commented Oct 14, 2020 at 14:25
  • 1
    $\begingroup$ Those upward roundings get halved by any subsequent applications of $r$, so all together the roundings never add up to more than one in the final answer, and can then be handled by just a single rounding in $R_n$. $\endgroup$ Commented Oct 14, 2020 at 14:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .