Update

[less_retarded_wiki.git] / function.md

# Function

Function is a very basic term in [mathematics](math.md) and [programming](programming.md) with a slightly different meanings in each, also depending on exact context: mathematical function basically maps [numbers](number.md) to other numbers, a function in programming is similar but is rather seen as a subprogram to which we divide a bigger program. Well, that's pretty simplified but those are the very rough ideas. A more detailed explanation will follow.

Yet another attempt at quick summary: imagine function as a tiny box. In mathematics you throw numbers (or similar object, for example [sets](set.md)) to the box and it spits out other numbers (or "objects"); the number that falls out always only depends on the number you throw in. So the box basically just transforms numbers into other numbers. In programming a function is similar, it is also a box to which you throw numbers and can behave like the mathematical function, but the limitations are relaxed so the box can also do additional things when you throw a number in it, it may for example light up a light bulb; it may also remember things and sometimes spit out a different number when you throw in the same number twice.

## Mathematical Functions

In mathematics functions can be defined and viewed from different angles, but it is essentially anything that assigns each member of some [set](set.md) *A* (so called *domain*) exactly one member of a potentially different set *B* (so called *codomain*). A typical example of a function is an equation that from one "input number" computes another number, for example:

*f(x) = x / 2*

Here we call the function *f* and say it takes one [parameter](parameter.md) (the "input number") called *x*. The "output number" is defined by the right side of the equation, *x / 2*, i.e. the number output by the function will be half of the parameter (*x*). The domain of this function (the set of all possible numbers that can be taken as input) is the set of [real numbers](real_number.md) and the codomain is also the set of real numbers. This equation assigns each real number *x* another real number *x / 2*, therefore it is a function. (In the [C](c.md) programming language this function could be written as `float f(float x) { return x / 2.0; }`.)

We can naturally write input and output values of a function into a table, here is one for the function we just examined:

| x       | f(x)    |
| ------- | ------- |
| ...     | ...     |
| -2      | -1      |
| -1      | -0.5    |
| 0       | 0       |
| 1       | 0.5     |
| 2       | 1       |
| 3       | 1.5     |
| ...     | ...     |

And alongside this table we can also draw a plot to get a "graphical view" of our function -- we'll see this further below.

Now consider a function *f2(x) = 1 - 1 / x*. Note that in this case the domain is the set of real numbers minus [zero](zero.md); the function can't take zero as an input because we can't divide by zero. The codomain is the set of real numbers minus one because we can't ever get one as a result. Here is a table:

| x       | f2(x)     |
| ------- | --------- |
| ...     | ...       |
| -2      | 1.5       |
| -1      | 2         |
| 0       | undefined |
| 1       | 0         |
| 2       | 0.5       |
| 3       | 0.666...  |
| ...     | ...       |

Another common example of a function is the [sine](sin.md) function that we write as *sin(x)*. It can be defined in several ways, commonly e.g. as follows: considering a [right triangle](right_triangle.md) with one of its angles equal to *x* [radians](radian.md), *sin(x)* is equal to the ratio of the side opposing this angle to the triangle [hypotenuse](hypotenuse.md). For example *sin(pi / 4) = sin(45 degrees) = 1 / sqrt(2) ~= 0.71*. The domain of sine function is again the set of real number but its codomain is only the set of real numbers between -1 and 1 because the ratio of said triangle sides can never be negative or greater than 1, i.e. sine function will never yield a number outside the interval <-1,1>.

Note that these functions have to satisfy a few conditions to really be functions. Firstly each number from the domain must be assigned exactly one number (although this can be "cheated" by e.g. using a set of couples as a codomain), even though multiple input numbers can give the same result number. Also importantly **the function result must only depend on the function's parameter**, i.e. the function mustn't have any memory or inside state and it mustn't depend on any external factors (such as current time) or use any randomness (such as a dice roll) in its calculation. For a certain [argument](argument.md) (input number) a function must give the same result every time. For this reason not everything that transforms numbers to other numbers can be considered a function.

Functions can have multiple parameters, for example:

*g(x,y) = (x + y) / 2*

The function *g* computes the average of its two parameters, *x* and *y*. Formally we can see this as a function that maps elements from a set of couples of real numbers to the set of real numbers.

Of course function may also work with just [whole numbers](whole_number.md), also [complex numbers](complex_number.md), [quaternions](quaternion.md) and theoretically just anything crazy like e.g. the set of animals :) However in these "weird" cases we generally no longer use the word *function* but rather something like a *[map](map.md)*. In mathematical terminology we may hear things such as a *real function of a complex parameter* which means a function that takes a complex number as an input and gives a real number result.

To get better overview of a certain function we may try to represent it graphically, most commonly we make function **[plots](plot.md)** also called **graphs**. For a function of a single parameter we draw graphs onto a grid where the horizontal axis represents number line of the parameter (input) and the vertical axis represents the result. Basically we make a table of the function input and output values, like we have seen above, and the pairs of numbers in each row give us coordinates of points we will plot. For example plotting a function *f(x) = ((x - 1) / 4)^2 + 0.8* may look like this:

```

         |f(x)
        2+
'.._     |
    ''--1+.____...--'
___,__,__|__,__,_____x
  -2 -1  |0 1  2
       -1+
         |
       -2+
         |


```

If the function is continuous (like here) we also connect the plotted [*x*,*f(x)*] points to create a continuous curve (see also [interpolation](interpolation.md)).

Plotting functions of multiple parameters is more difficult because we need more axes and get to higher [dimensions](dimension.md). For functions of 2 parameters we can draw e.g. a [heightmap](heightmap.md) or create a [3D model](3d_model.md) of the surface which the function defines. 3D functions may in theory be displayed like 2D functions with added time dimension (animated) or as 3D density clouds. For higher dimensions we usually resort to some kind of cross-section or [projection](projection.md) to lower dimensions.

Functions can have certain properties such as:

- being **[continuous](continuous.md)**: A continuous function is, intuitively speaking, a function whose graph is a continuous curve without any holes, i.e. we can plot any part of it with a single stroke.
- being **[discrete](discrete.md)**: Non-continuous function that is defined only in some points, typically on whole number positions (e.g. the function that says how many divisors a whole number has).
- being **[bijective](bijection.md)**: Pairs exactly one element from the domain with one element from codomain and vice versa, i.e. for every result (element of codomain) of the function it is possible to unambiguously say which input created it. For bijective functions we can create **[inverse functions](inverse_function.md)** that reverse the mapping (e.g. [arcus sine](asin.md) is the inverse of a [sin](sin.md) function that's limited to the interval where it is bijective). For example *f(x) = 2 * x* is bijective with its inverse function being *f^(-1)(x) = x / 2*, but *f2(x) = x^2* is not bijective because e.g. both 1 and -1 give the result of 1. 
- being an **[even function](even_function.md)**: For this function it holds that *f(x) = f(-x)*, i.e. the plotted function is symmetric by the vertical axis. Example is the [cosine](cos.md) function.
- being an **[odd function](odd_function.md)**: For this function it holds that *-f(x) = f(-x)*, i.e. the plotted function is symmetric by the center point [0,0]. Example is the [sine](sin.md) function.
- being **[differentiable](differentiable.md)**: Its [derivative](derivative.md) is defined everywhere.
- **[recursive](recursion.md)**: Referring to themselves in their own definition.
- ...

In context of functions we may encounter the term [composition](composition.md) which simply means chaining the functions. E.g. the composition of functions *f(x)* and *g(x)* is written as *(f o g)(x)* which is the same as *f(g(x))*.

[Calculus](calculus.md) is an important mathematical field that studies changes of continuous functions. It can tell us how quickly functions grow, where they have maximum and minimum values, what's the area under the line in their plot and many other things.

Mathematical functions can be seen as [models of computation](model_of_computation.md), i.e. something akin an "abstract computer": the field studying such functions is called [computability](computability.md) theory. Here we may divide functions into [classes](class.md) depending on how "difficult" it is to compute their result.

### Notable Mathematical Functions

Functions commonly used in mathematics range from the trivial ones (such as the constant functions, *f(x) = constant*) to things like  trigonometric functions ([sine](sin.md), [cosine](cos.md), [tangent](tan.md), ...), [factorial](factorial.md), [logarithm](log.md), [logistic](logistic_function.md) sigmoid function, [Gaussian function](gaussian_function.md) etc. Furthermore some more complex and/or interesting functions are (the term function may be applied liberally here):

- **[Ackermann function](ackermann_function.md)**: Extremely fast growing function with some weird properties.
- **[busy beaver function](busy_beaver.md)**: A famous, extremely quickly growing [uncomputable](computability.md) function.
- **Minkowski's [questionmark function](questionmark_function.md)**: Weird function with [fractal](fractal.md) properties.
- **sin(1/x)**: Simple function that gets [chaotic](chaos.md) close to zero.
- **[Dirichlet function](dirichlet_function.md)**: Function that can't really be plotted properly.
- **[Weierstrass function](weierstrass_function.md)**: Continuous everywhere, [differentiable](derivative.md) nowhere.
- **Drawing with function plots**: there are many formulas whose plots create pictures, for example the **[Tupper's formula](tuppers_formula.md)** is a self-referential formula that can be seen as a function which when plotted draws the text of the formula itself. There are also equations such as the [Batman equation](batman_equation.md) or an equation that draws the symbol of a heart, which can be seen as functions too.
- **[Thomae's function](thomaes_function.md)**: Function with a nice [fractal](fractal.md) plot.
- **[Cantor function](cantor_function.md)**
- **[Riemann zeta function](riemann_zeta_function.md)**: Function that's subject to [Riemann hypothesis](riemann_hypothesis.md), one of the most important unsolved problems in mathematics.
- **[Blancmange curve](blancmange.md)**
- **[space filling curves](space_filling_curve.md)**
- **[Dirac delta function](unit_impulse.md)**: Function representing infinitely short impulse with unit energy.
- TODO

{ Playing around with plotting 2D functions (functions with 2 parameters) is very fun, you can create beautiful pictures with very simple formulas. I once created a tool for this (just some dirty page with JavaScript) and found quite nice functions, for example: `gaussian_curve((x^2) mod (abs(sin(x + y)) + 0.001) + (y^2) mod (abs(sin(x - y)) + 0.001))` plotted from [-3,-3] to [3,3] (plot with amplitude set to range from white to black by given minimum and maximum in the given area). ~drummyfish }

## Programming Functions

In programming the definition of a function is less strict, even though some languages, namely [functional](functional.md) ones, are built around purely mathematical functions -- for distinction we call these strictly mathematical functions **pure**. In traditional languages functions may or may not be pure, a function here normally means a **subprogram** which can take parameters and return a value, just as a mathematical function, but it can further break some of the rules of mathematical functions -- for example it may have so called **[side effects](side_effect.md)**, i.e. performing additional actions besides just returning a number (such as modifying data in memory which can be read by others, printing something to the screen etc.), or use randomness and internal states, i.e. potentially returning different numbers when invoked (called) multiple times with exactly the same arguments. These functions are called **impure**; in programming a *function* without an adjective is implicitly expected  to be impure. Thanks to allowing side effects these functions don't have to actually return any value, their purpose may be to just invoke some behavior such as writing something to the screen, initializing some hardware etc. The following piece of code demonstrates this in [C](c.md):

```
int max(int a, int b, int c) // pure function, returns the greatest of three numbers
{
  return (a > b) ? (a > c ? a : c) : (b > c ? b : c);
}

unsigned int lastPresudorandomValue = 0;

unsigned int pseudoRandom(unsigned int maxValue) // impure function
{
  lastPresudorandomValue = // side effect: working with global variable
    lastPresudorandomValue * 7907 + 7;

  return (lastPresudorandomValue >> 2) % (maxValue + 1);
}
```

In older languages functions were also called *[procedures](procedure.md)* or *[routines](routine.md)*. Sometimes there was some distinction between them, e.g. in [Pascal](pascal.md) functions returned a value while procedures didn't.

Just as in mathematics, a function in programming may be [recursive](recursion.md) -- here we define recursion as a function that calls itself.