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.

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?

share|improve this question
1  
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

3 Answers 3

up vote 2 down vote accepted

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.

share|improve this answer
    
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.

share|improve this answer

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.

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.