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?

$\endgroup$
12
  • 1
    $\begingroup$ Sorry, what is it all about? For instance, what is $a$ and $b$, isn't it a one variable function you would like to see? $\endgroup$
    – Berci
    Oct 17, 2012 at 7:41
  • 3
    $\begingroup$ You can use the Iverson bracket and simply write it as $f(a)=[a=2]+[a=3]$. :-) $\endgroup$ Oct 17, 2012 at 7:55
  • 12
    $\begingroup$ f == isPrime ;) $\endgroup$
    – wim
    Oct 17, 2012 at 11:14
  • 4
    $\begingroup$ Have you considered the function $f : \{1,2,3,4\} \to \{0,1\}$ such that $f(1)=0$, $f(2)=1$, $f(3)=1$, and $f(4)=0$? :) $\endgroup$
    – Snowball
    Oct 17, 2012 at 21:51
  • 4
    $\begingroup$ @starovoitovs: You really should clearly state the intended purpose. Honestly, for most mathematical purposes, definition you've given in your question is probably what you really should be wanting to use. If your purpose is for fast implementation on a computer, then you really should say that, to let people who know about such things make good suggestions (and you should probably include how it's going to be used, as well). If your purpose is something else, then if you state it, people can give you answers to suit your needs rather than just having fun. $\endgroup$
    – user14972
    Oct 18, 2012 at 0:03

10 Answers 10

17
$\begingroup$

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)$.

$\endgroup$
5
  • 5
    $\begingroup$ It has division by integers. $\endgroup$
    – Asaf Karagila
    Oct 17, 2012 at 15:13
  • 4
    $\begingroup$ Write $1/2$ as $0.5$ ... $\endgroup$
    – lhf
    Oct 17, 2012 at 23:56
  • $\begingroup$ I think the OP meant integer division, like 1/2 = 0. $\endgroup$
    – asmeurer
    Oct 21, 2012 at 1:36
  • $\begingroup$ How does one arrive at this result? $\endgroup$
    – jimjim
    Oct 21, 2012 at 6:25
  • $\begingroup$ Very ingenious, and quick! $\endgroup$
    – amWhy
    Nov 29, 2012 at 0:14
11
$\begingroup$

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|$$

$\endgroup$
9
$\begingroup$

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

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

$\endgroup$
3
  • $\begingroup$ To all: I had not seen Doug Stone's similar $f(x)=2x^2+3 \mod 5$ $\endgroup$
    – coffeemath
    Oct 21, 2012 at 6:20
  • 1
    $\begingroup$ @coffeemath I recently realized that all the modulo solutions can be obtained from the initial Lagrange Interpolation $-\frac{1}{2}(x-1)(x-4)$. Under modulo 5 you get $2x^3+3$ and under modulo 3 you get $x^2+x+1$, which is what you have here. $\endgroup$ Oct 31, 2012 at 10:41
  • $\begingroup$ 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... $\endgroup$
    – coffeemath
    Nov 28, 2012 at 13:08
8
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Or similarly, $(x>>1)\&1$. Is the $\&$ operation cheaper than $\%$? $\endgroup$ Oct 21, 2012 at 5:46
  • $\begingroup$ @YongHaoNg It can be. It depends on the underlying hardware and, especially, how efficient the compiler is. $\endgroup$ Dec 7, 2012 at 1:16
  • $\begingroup$ I see, thanks for the info. $\endgroup$ Dec 8, 2012 at 9:35
4
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ +1 for Karnaugh map, now an example of it to fit this instance. $\endgroup$
    – jimjim
    Oct 21, 2012 at 6:09
  • $\begingroup$ Okay let me try to figure out how to draw a table. :) $\endgroup$ Oct 21, 2012 at 6:12
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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|)$$

$\endgroup$
1
  • $\begingroup$ 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... $\endgroup$
    – coffeemath
    Oct 21, 2012 at 4:08
1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ If someone knows how to make the elements of those vectors line up, please edit and fix. I just used SymPy's $\LaTeX$ generation to get that. $\endgroup$
    – asmeurer
    Oct 21, 2012 at 1:49
  • $\begingroup$ Perhaps for equally spaced inputs and symmetric outputs one would expect degree 2. $\endgroup$
    – coffeemath
    Oct 21, 2012 at 3:34
1
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ ...which is Jasper's answer. $\endgroup$
    – lhf
    Oct 21, 2012 at 1:53
  • 1
    $\begingroup$ @lhf: on the specified domain, all of these functions are the same. This is a nice derivation of the answer Jasper Loy gave. $\endgroup$
    – robjohn
    Oct 21, 2012 at 8:02
  • $\begingroup$ @robjohn You mean that $L(x)=2x^3+3$ under modulo 5 and $L(x)=x^2+x+1=(x-1)^2$ under modulo 3 right? I found out about this while answering a similar question elsewhere. Are the polynomials unique in the chosen domain? $\endgroup$ Oct 31, 2012 at 10:47
  • $\begingroup$ @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}$$ $\endgroup$
    – robjohn
    Oct 31, 2012 at 13:28

You must log in to answer this question.

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