5
$\begingroup$

I already got tired trying to think of a function $f:\{1,2,3,4\}\rightarrow \{0,1,1,0\}$ in other words:

$f(1)=0\\f(2)=1\\f(3)=1\\f(4)=0$

Don't suggest division in integers; it will not pass for me. Are there ways to implement it with modulo, absolute value, and so on, without conditions?

  • 1
    This is one of my favorite Math.SE questions.2012-11-20

10 Answers 10

1

Look the example for Lagrange Interpolation, then it is easy to construct any function from any sequence to any sequence.

In this case :

$L(x)=\frac{1}{2}(x-1)(x-3)(x-4) + \frac{-1}{2}(x-1)(x-2)(x-4)$ wich simplifies to: $L(x)=\frac{-1}{2}(x-1)(x-4)$ which could possibly explain Jasper's answer, but since the method for derivation was not mentioned can not say for sure.

  • 0
    @YongHaoNg: I mean that on the given domain, $\{1,2,3,4\}$, all of the various representations give the same function:$\begin{align}1\to0\\2\to1\\3\to1\\4\to0\end{align}$2012-10-31
17

Seeing the zeroes of the function and its symmetry, one tries to fit a quadratic curve to get $f(x)=-0.5(x-1)(x-4)$.

  • 0
    Very ingenious, and quick!2012-11-29
11

Another one (a bit more complicated than the parabola) is: $f(x)=\frac{2}{\sqrt{3}}\sin\bigg(\frac{\pi}{3}(x-1)\bigg)$

This one generates: $0,1,1,0,-1,-1,0,...$


And another simple one:

$f(x)=1.5-\left | 2.5-x\right|$

9

Here's a simple one using only mods and a square

$f(x)=(x-1)^2 \mod 3$

  • 0
    Interesting. So under mod 7 it would be $(-1/2)(x-1)(x-4)$ which since $-1/2=6/2=3$ would give $3(x^2-5x+4)$ or $3x^2-x-2$. And that works. I guess as long as 2 is invertible mod$n$we have the example. I wonder about when $n$ is even...2012-11-28
8

If you have bit operations, just return the two's bit of the input. So $y=x \gt \gt 1 ;\ \ f(x)=y\%2$

  • 0
    I see, thanks for the info.2012-12-08
5

Since you tagged "binary" in your question, you might also want to recall that Karnaugh map is a standard way to map inputs to outputs with just complement, AND and OR gates. (Or "~", "$\&$" and "|" bit-wise operators in C)

For example, you can define $a,b,c$ to be bits at position 2,1,0 here to use the map.
If you draw out the map, this is what it looks like:

$\begin{array}{c|c|c|c|c|c|} & &bc &bc &bc &bc\\ \hline & & 00 & 01 & 11 & 10\\ \hline a& 0 & \text{X} & 0 & 1 & 1 \\ \hline a& 1 & 0 & \text{X} & \text{X} & \text{X} \\ \hline \end{array}$ Explanation: X denotes values that cannot occur (normally called "Don't care" I think). We want to focus on representing the "1"s, which is represented by the entries $\bar abc$ and $\bar a b\bar c$. (Notice that you only get "1" for one of the variables, they cannot occur together.)
They can be combined: $\bar a bc + \bar a b \bar c=\bar a b (c+\bar c)=\bar a b$.
Getting rid of the $\bar a$ is possible when you noticed that its alternative row has no entries. (i.e. the 2 entries below are "X"s)

Using this idea you can construct any function for any bigger variable.
It is probably not going to be the most efficient implementation, but you can get the solution fast. From there, you may do some reduction using logical operations and the final result should be decent.

  • 0
    Okay let me try to figure out how to draw a table. :)2012-10-21
4

Heaviside functions (using the appropriate convention) should work too. Use

$f(x) = U(x-1) - U(x-2)$

where $U$ is the Heaviside step function.

2

From a mathematical point of view, describing such a function is trivial: $ f(x)=\begin{cases} 0 & \text{if } x \in \{1,4\} \\ 1 & \text{if } x \in \{2,3\} \\ \end{cases}.$ It's not a particularly slick formula for the function, but it's certainly straightforward. An alternative is to search for "magic numbers". For example: $f(x)=2x^2+3 \mod 5.$ To find this function, I just let my computer search until the numbers happened to match.

If you're looking for an efficient implementation of this function, in C say, any one of these would compute the function:

char f=(x&2)>>1; char f=(x>>1)%2;  // this is Ross Millikan's suggestion char f=(x>>1)&1; 

Here & is bitwise and, >> is right bit-shift by one, and % is the mod operation.

If you only need an if(f!=0) { ... } statement (i.e., "if $f(x)\neq 0$"), then this would suffice:

if(x&2) { ... } 

An alternative to the above is simply storing the values in memory. E.g. via:

char f[5]={0,0,1,1,0}; 

whenceforth, if you want to compute $f(x)$, you can just recall f[x] from memory.

2

Something more complex maybe? $f(x)=\max(0, \text{Im}\, i^{x-1}-\text{Re}\, i^{x-1})$

Or something simpler:

$f(x) = 1 - \max(0, 2-x, x-3)$

Similarly (in the vein of the $|x-2.5|$ answers):

$f(x) = 3-\max(2, |2x-5|)$

  • 0
    Or $f(x)=4-max(x,5-x)$ in the same vein as your "simpler". But I liked the powers of $i$ version, since they cycle around the circle, and since one needs two in a row, using the line $y=x$ etc...2012-10-21
1

Given any set of $n$ points and values, you can always construct a polynomial of degree less than or equal to $n-1$ that goes through all the points. See http://en.wikipedia.org/wiki/Polynomial_interpolation.

Using the method from there, we get

$\left[\begin{smallmatrix}1 & 1 & 1 & 1\\8 & 4 & 2 & 1\\27 & 9 & 3 & 1\\64 & 16 & 4 & 1\end{smallmatrix}\right] \left[\begin{smallmatrix}a_{3}\\a_{2}\\a_{1}\\a_{0}\end{smallmatrix}\right] = \left[\begin{smallmatrix}0\\1\\1\\0\end{smallmatrix}\right]$

Multiplying by the inverse matrix on the left on both sides gives

$\left[\begin{smallmatrix}a_{3}\\a_{2}\\a_{1}\\a_{0}\end{smallmatrix}\right] = \left[\begin{smallmatrix}0\\- \frac{1}{2}\\\frac{5}{2}\\-2\end{smallmatrix}\right]$

meaning that the resulting polynomial is $- \frac{1}{2} x^{2} + \frac{5}{2} x -2$ (indeed, if you factor this, you get the same thing as Jasper Loy). You can easily check that this polynomial works. Note that in this case, the polynomial had degree one less than we were expecting.

  • 0
    Perhaps for equally spaced inputs and symmetric outputs one would expect degree 2.2012-10-21