# Is it possible to simplify these iterated functions?

I'll apologise in advance, as I'm a programmer and my math is a bit rusty, so please bear with me.

Let's say I have a linear function:

$$f(x) = mx + c$$

But the result of the function is clamped between $0$ and $1$. I'm not sure of the mathematical term for this, but basically it's setting a minimum and maximum on the result. If it's less than $0$ it becomes $0$, and if it's greater than $1$ it becomes $1$.

$$f(x) = clamp(mx + c)$$

I have a certain number ($n$) of these functions, each with different values for $m$ and $c$, and I apply them in order like so:

$$f_n(f_\ldots(f_2(f_1(x))))$$

Is it possible to simplify these $n$ functions into a single function that will give the same result? For instance (this is obviously wrong, but it gives you an idea of what I'm after):

$$g(x) = clamp \left( \left( \sum m \right)x + \sum c \right)$$

If it's not possible due to the clamping, would it be possible if each function was just a simple linear function?

-
Without the "clamping" the composite of a linear function is another linear function, so is doable in that case. –  Peter Grill Mar 17 '12 at 3:29
Your function maps integers to integers? –  Patrick Da Silva Mar 17 '12 at 3:48
They will be real numbers. The value of x will range from 0.0 to 1.0, if that helps. –  Tom Dalling Mar 17 '12 at 3:53
Well, $f_n(\ldots f_1(x)\ldots)$ will turn out to be another clamped linear function for sure, although it may be clamped between a smaller range than 0 and 1 (e.g., it might be clamped between 0.2 and 0.9). –  JohnJamesSmith Mar 17 '12 at 4:09

It seems to make this work, we should first generalize the “clamping” to ranges other than $$[0, 1]$$. Let $C_{[a,b]}(x)$ denote the clamping of x into the range $[a, b]$, $a \le b$, i.e.

$$C_{[a,b]}(x) = \begin{cases}a, &\mbox{iff } x \le a \\ b, &\mbox{iff } x \ge b\\ x, &\mbox{otherwise} \end{cases}$$

Then, you are asking about the composition of a number of functions $f_i(x)$ of the form

$f_i(x) = C_{[0,1]}(m_i x + c_i)$.

If we take the composite of two such functions, $f_i$ and $f_j$, we get

$f_i(f_j(x)) = C_{[0,1]}(m_i C_{[0,1]}(m_j x + c_j) + c_i)$.

To proceed further, we need to work out some properties of the “clamp” operation. Consider, first, the composition of clamps: what is $C_{[a,b]}(C_{[c,d]}(x))$? The result from the inner clamp will be in the range $[c, d]$, then the outer, in the range $[a, b]$. Now, consider the following (note that “within” and “inside” also includes lying just on an endpoint, e.g. $[1, 2]$ lies “entirely within” $[1, 3]$ here):

$[c, d]$ lies entirely within $[a, b]$: Then, the result of the composite of clamps is just $[c, d]$. $[a, b]$ lies entirely within $[c, d]$: The result of the composite of clamps is just $[a, b]$. $[a, b]$ overlaps $[c, d]$ such that $b$ is inside $[c, d]$ but a is outside: This implies $a < c$ and $d > b$. Then, the result is to clip the upper part of $[c, d]$ off to get $[c, b]$. $[a, b]$ overlaps $[c, d]$ such that $a$ is inside $[c, d]$ but $b$ is outside: This implies $a > c$ and $d < b$. Then, the result is to clip the lower part of $[c, d]$ off to get $[a, d]$. $a < b \le c < d$: $x$ will be clamped to $[c, d]$, but that will always be $\ge b$, so will be clamped to $b$. $c < d \le a < b$: $x$ will be clamped to $[c, d]$, but that will always be $\le a$, so will be clamped to $a$.

Thus, we can see that the result of composited clamps is to clamp to an “intersection” of the two ranges $[a, b]$ and $[c, d]$ that is slightly different from a normal intersection in that if the ranges are disjoint, the result of $[a, b] \cap [c, d]$ is not a null but rather a or b, depending on which side of $[a, b]$ $[c, d]$ lies on. We'll just denote this operation by $[a, b] \cap^{*} [c, d]$ to distinguish it from ordinary intersection. Note that it is not commutative!

So we can say,

$$C_{[a,b]}(C_{[c,d]}(x)) = C_{[a, b] \cap^{*} [c, d]}(x)$$.

Now consider $y C_{[a, b]}(x)$. For $x < a$, this is $ya$. For $a \le x \le b$, this is $yx$. For $x > b$, this is $yb$. We recongize this easily as $C_{[ya, yb]}(yx)$. So we have

$$y C_{[a, b]}(x) = C_{[ya, yb]}(yx)$$.

Now, finally, consider $C_{[a, b]}(x) + y$. For $x < a$, this is $a + y$. For $a \le x \le b$, this is $x + y$. For $x > b$, this is $b + y$. We recognize this easily as $C_{[a + y, b + y]}(x + y)$. So we have

$$C_{[a, b]}(x) + y = C_{[a + y, b + y]}(x + y)$$.

Now, with these properties in hand, we can do the composition just mentioned. It gives

\begin{align}f_i(f_j(x)) &= C_{[0,1]}(m_i C_{[0,1]}(m_j x + c_j) + c_i) \\ &= C_{[0,1]}(C_{[0, m_i]}(m_i m_j x + m_i c_j) + c_i) \\ &= C_{[0,1]}(C_{[c_i, m_i + c_i]}(m_i m_j x + m_i c_j + c_i)) \\ &= C_{[0,1] \cap^{*} [c_i, m_i + c_i]}(m_i m_j x + m_i c_j + c_i)\end{align}.

It is then straightforward to generalize to more than 2 functions. Note the result is just another clamped linear function, though it may be that the clamp interval is different from $[0, 1]$.

EDIT: I just noticed that I forgot take into account a negative multiplier $y$. If the multiplier is negative then the clamp interval in the identities above for multiplying a clamped value needs to have its parameters reversed since in that case $ya$ will now be the top of the range and $yb$ will be the bottom. Or we could just make it understood that in the notation that $[a, b]$ for $a > b$ should be interpreted as $[b, a]$. This keeps things compact.

-
I think all the answers are correct, but this one was the easiest to understand and translate into code. –  Tom Dalling Mar 18 '12 at 3:11

Yes, this is possible. Let the quadruple $(a,b,r,s)$ with $a\le b$ describe the function

$$g(x)=\begin{cases} ra+s&x\le a\;,\\ rx+s&a\lt x\lt b\;,\\ rb+s&b\le x\;,\end{cases}$$

where $a$ may be $-\infty$ and $b$ may be $\infty$. Start out with the identity function, represented by $(-\infty,\infty,0,1)$. Applying one of your functions $f(x)=\max(0,\min(1,mx+c))$ to the function $g(x)$ represented by $(a,b,r,s)$ yields the function $f(g(x))$ represented by $(a',b',r',s')$, where

$$\begin{eqnarray} a'&=&d(a)\;,\\ b'&=&d(b)\;,\\ r'&=&mr\;,\\ s'&=&ms+c\;, \end{eqnarray}$$

where

$$d(x)=\begin{cases} -s'/r'&r'x+s'\le0\;,\\ x&0\lt r'x+s'\lt 1\;,\\ (1-s')/r'&1\le r'x+s'\;. \end{cases}$$

This assumes $r'\ne0$; in case $r'=0$, use $(0,0,0,\max(0,\min(1,ms+c)))$ instead.

-

This answer is essentially the same as mike4ty4's.

Let $f_i(x) = \text{clamp}(m_i x + b_i)$. If all of the $m_i$ are positive then $f_i(x) = 0$ if $x \leq -b_i/m_i$ and $f_i(x) = 1$ if $x \geq (1-b_i)/m_i$. It follows then that $f_2(f_1(x)) = 0$ if $$x \leq -\frac{b_1}{m_1 m_2} - \frac{b_2}{m_2}$$ and $f_2(f_1(x)) = 1$ if $$x \geq \frac{1-b_1}{m_1 m_2} - \frac{b_2}{m_2}.$$ Otherwise, $f_2(f_1(x)) = m_2 m_1 x + m_2 b_1 + b_2.$ Iterating, we see that

$$(f_n \circ f_{n-1} \circ \cdots \circ f_1)(x) = \begin{cases} 0, &\text{if } x \leq - \sum_{i=1}^{n} b_{i} \prod_{j=1}^{n-i+1} m_{n-j+1}^{-1},\\ 1, &\text{if } x \geq \prod_{k=1}^{n}m_k^{-1} - \sum_{i=1}^{n} b_{i} \prod_{j=1}^{n-i+1} m_{n-j+1}^{-1}, \\ x \prod_{k=1}^n m_k + \sum_{i=1}^{n}b_i \prod_{j=i+1}^{n} m_j, &\text{otherwise.} \end{cases}$$

This formula can be applied to the case when the $m_i$ are allowed to be negative by simply noting that the values $0$ and $1$ are switched when an odd number of the $m_i$ are negative and remain unchanged otherwise.

-