less_retarded_wiki/function.md

Function

Function is a very basic term in mathematics and programming with a slightly different meanings in each, also depending on exact context: mathematical function basically maps numbers 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) 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 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 (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 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 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; 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 function that we write as sin(x). It can be defined in several ways, commonly e.g. as follows: considering a right triangle with one of its angles equal to x radians, sin(x) is equal to the ratio of the side opposing this angle to the triangle hypotenuse. 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 (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, also complex numbers, quaternions 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. 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 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).

Plotting functions of multiple parameters is more difficult because we need more axes and get to higher dimensions. For functions of 2 parameters we can draw e.g. a heightmap or create a 3D model 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 to lower dimensions.

Functions can have certain properties such as:

• being continuous: 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: 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: 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 that reverse the mapping (e.g. arcus sine is the inverse of a sin 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: 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 function.
• being an odd function: 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 function.
• being differentiable: Its derivative is defined everywhere.
• recursive: Referring to themselves in their own definition.
• ...

In context of functions we may encounter the term composition 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 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, i.e. something akin an "abstract computer": the field studying such functions is called computability theory. Here we may divide functions into classes 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, cosine, tangent, ...), factorial, logarithm, logistic sigmoid function, Gaussian function etc. Furthermore some more complex and/or interesting functions are (the term function may be applied liberally here):

• Ackermann function: Extremely fast growing function with some weird properties.
• busy beaver function: A famous, extremely quickly growing uncomputable function.
• Minkowski's questionmark function: Weird function with fractal properties.
• sin(1/x): Simple function that gets chaotic close to zero.
• Dirichlet function: Function that can't really be plotted properly.
• Weierstrass function: Continuous everywhere, differentiable nowhere.
• Drawing with function plots: there are many formulas whose plots create pictures, for example the Tupper's formula 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 or an equation that draws the symbol of a heart, which can be seen as functions too.
• Thomae's function: Function with a nice fractal plot.
• Cantor function
• Riemann zeta function: Function that's subject to Riemann hypothesis, one of the most important unsolved problems in mathematics.
• Blancmange curve
• space filling curves
• Dirac delta function: 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 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, 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:

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 or routines. Sometimes there was some distinction between them, e.g. in Pascal functions returned a value while procedures didn't.

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