Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

imagine you have a function f() which receives n parameters and it produces one result.

imagine that you then want to compute f for the same n parameters and another one. if you had kept the previous result the operation would be straight forward and constant in terms of cost.

For example imagine you have the function sum() if I ask sum(1,2,5,4) the answer is 10.

I then ask sum(1,2,5,4 and 3) the answer is 13. but this could be achieved also by 10 + 3 (10 being the previous result)

I want to know if there is a scientific name for the class of functions whose value can be determined by previous input.

I have this problem where if we compute a result for a certain function and then we want to do the same thing and adding a new parameter we still have to recompute everything. That's because this function (differently from sum or average or many others would not belong to this class)

is there any name for this ?

hope I have made myself clear.

share|improve this question
    
You might check en.wikipedia.org/wiki/Iterated_binary_operation or en.wikipedia.org/wiki/Fold_(higher-order_function). Please edit the question, currently it's vague and may be closed. –  sdcvvc Mar 19 '10 at 12:24
    
There is a similar class of results called "parallel repetition theorems" in theoretical computer science which roughly say that under appropriate circumstances doing several computations in parallel is harder than doing one of them. Your question asks what these circumstances are, under restricted notion of parallelism (the computations are sequential, but there is an access to the result of previous calculation). –  Boris Bukh Mar 19 '10 at 15:04
3  
Ah, but why do you care what it's called? Presumably, this is so you can look up information about such functions in the published literature? Because presumably you have a project and such a function came up? Or is it that by asking "what is this called" you can really phrase "tell me everything you know about this" in the form of a question? –  Theo Johnson-Freyd Mar 19 '10 at 15:46
add comment

5 Answers

The name for the process you are describing is recursion. A function is defined by recursion when the value of it at f(n+1) can be easily computed from the value f(n), fixing the other input.

The class of functions arising are known as the primitive recursive functions. This class is the smallest class of functions defined on the natural numbers which contains various simple functions (successor function, constant zero function, projective functions) and is closed under composition and primitive recursion. This class was introduced by Kurt Goedel as an approximation to the class of all computable functions, but the class of computable functions strictly extends the class of primitive recursive functions. For example, the Ackermann function is computable, but not primitive recursive. This diagonal of the Ackermann function is mind-bogglingly fast growing, and this prevents it from being primitive recursive, for every primitive recursive function is bounded by some level of the Ackermann function, while the diagonal eventually dominates any given such level.

share|improve this answer
    
Thanks. But I am not sure that you are right - and maybe because I have explained the question badly. if you follow my example immagine the function gives you the shortest distance between n points. (i.e.: the closest two points) if you give in input 5 points you then work it out. if you give in input the same 5 points plus another point you can not use the first answer or any previous computation to help you answering the question. Yet you could resolve this problem in a recursive way. –  lorenz Mar 19 '10 at 14:19
3  
Well, in this case, I would ask that you formulate your question more precisely. –  Joel David Hamkins Mar 19 '10 at 15:26
add comment

It sounds to me like you are describing an algorithm to compute the value of a function, as opposed to an actual function. You are describing the steps of a recursion, a technique commonly used in computer science and dynamic programming.

share|improve this answer
add comment

yes its a recursive function, but its a recursive function with caching. This comes up a lot in functional programming, where you will have functions that do a computation on lists.

Eg: sum l = fold + 0 l

what happens in this case is that what you want to happen is you will take you list of numbers $\ell$ and do some sort of hashing, and see if the hash is in your set of lists where you already know the answer. This sort of action only really makes sense if your "+" operation is far more expensive to compute than the whole framework of code needed to make caching work. In fact, there might even be some code which says "if the size of the list $\ell$ is less than 2, don't cache it".

also, if you were say doing an associative and commutative computation on lists of numbers, and it was done often enough and takes enough time that caching is worth while, you might say want to sort your numbers and then do sum(numbers which we've not summed)+sum(numbers which we've summed before) or some such.

Umut Acar has done a lot of cool work on some more sophistication versions of this sort of technique, and one of the cooler consequences is that he's able to create asymptotically optimal algorithms for an online "you're getting the data as its coming in" problem just by writing using his framework the standard offline algorithm "you've got the data all ahead of time" for the problem.

share|improve this answer
add comment

The class of functions you are describing are known as recursive. For example, the $sum$ function has the following recursive definition:

$sum(x_1) = x_1$

$sum(x_1, x_2, \cdots x_{n-1}, x_n) = sum(x_1, x_2, \cdots, x_{n-1}) + x_n$.

In this particular situation it was sufficient to know what $sum(x_1, x_2, \cdots, x_{n-1})$ is to quickly compute $sum(x_1, x_2, \cdots, x_{n-1}, x_n)$. However, in many other situations to compute $f(x_1, \cdots x_n)$ you must know the solution to a large number of subproblems of $f$ to be able to compute $sum(x_1,\cdots, x_{n})$ quickly. For example, $f$ may be defined recursively as:

$f(x_1) = g(x_1)$

$f(x_1, \cdots, x_n) = f(x_1,x_2, \cdots x_{\frac{n}{2}}) + f(x_{\frac{n}{2}+1}, \cdots, x_n)$

A general technique from computer science that can be used to compute such functions is dynamic programming. Essentially a table is constructed that stores the solution to all subproblems (or perhaps just some subset of the subproblems which will be needed later) to the original. Since the solution to larger subproblems is constructed using the solutions to smaller subproblems you construct this table in order of increasing size.

EDIT: Dynamic programming is typically used when the solutions to the subproblems needed to compute $f(x_1, \cdots, x_n)$ overlap. If they do not overlap a simple recursive definition will usually be simpler.

share|improve this answer
add comment

The other possibile answer not mentioned so far is "associative binary function." For example, the binary operation of "taking a sum" is associative and so we can unambiguously write $a + b + c$ instead of having to write either $(a + b) + c$ or $a + (b + c)$ every time and thereby think of "summing" as applying to more than two objects at a time.

And just because I can't help myself: 1 + 2 + 5 + 4 = 12, not 10.

share|improve this answer
    
I think you might be right please see comment I wrote above for the other guy. I just attempted to make my question a bit more clear with an example. –  lorenz Mar 19 '10 at 14:20
add comment

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.