Is it a Known Concept to Compute an Algorithm Once and Re-Interpret Answer for Different Inputs

Question

I recently came across a strange concept and was wondering if this was a known / named concept in the realm of CS.

The concept is that you evaluate some computation or logical circuit that takes in N number of binary inputs and gives an output. (and if doing multiple of these in parallel it could then be N inputs to M outputs)

You can then change your mind after the fact about the values of the binary inputs you want the algorithm to have evaluated and essentially re-interpret the result of the original equation to get the answer for those different inputs.

The benefit here would be that if there was some complex and lengthy computation, that you could do it once, and then just re-interpret the result to get the answer of that same algorithm for different inputs.

It sounds strange I know, but are there any existing methods for this, or terminology at least?

Example:

As an example let's say you calculated a function $f(x) = x * 8$ for $x=5$ in a specific way that gave you a resulting bit string. When an operation was done on the bit string, which was a function of the inputs (say, XOR against a number which was the function of the inputs for example), that the value came out to be 40.

But then, you say "OK but what would it be for $f(6)$?". Since 6 is different than 5, the XOR constant changes, but you can use that new XOR constant against the result you already got from the previous calculations, to get the new correct answer of 48.

The decoding process is the same regardless of the algorithm/function being evaluated. It is a function of the inputs, and has nothing to do with the details of the function itself (so isn't iterative computation).

it almost seems a little related to a karnaugh map, in that you get something boiled down to the results of the algorithm, no matter how complex the steps were to get to that result originally.

Answer 1

I'm not sure, but you might be talking about what has been termed incremental computation.

The key idea behind incremental computation is to program in a way such that the program responds to input changes by updating its output while only re-evaluating those portions of the program affected by the change. Incremental computing is feasible in situations where input changes lead to relatively small changes in the output. Clearly, in limiting cases one cannot avoid a complete re-computation of the output, but in many cases the results of the previous computation may be re-used to obtain the updated output more quickly than a complete re-evaluation. In many cases, taking advantage of incrementality therefore dramatically improves performance, especially as the input size increases.

Designing and developing applications that respond to incremental modifications, however, is challenging: it often involves developing highly specific, complex algorithms.

This has lead some people to investigate the idea of moving the responsibility to avoid reevaluation where possible to the language run-time: instead of expecting the programmer to develop software for a particular application and a particular class of incremental modifications, the language run-time is tracking the dynamic data dependences of the computation and incrementally updating their output as needed. This is called or self-adjusting computation, and the person most associated with this programming language approach is Umut Acar. I recommend visiting his website for further information.

Note that ideas like this go back to the 1950s. Ad-hoc forms of incremental computing are heavily used in modern web-browsers because you don't want to reprocess ("reflow") the full page when a mutatation (e.g. Javascript performs a DOM operation) is performed.

I also recommend to consider the related field of online algorithms.

Answer 2

Some of the very early work on complexity theory used a sequential time model -- that is, rather than studying the worst-case runtime of the TM that can produce the correct output on an arbitrary input, they studied machines that would run infinitely and enumerate the correct output for each input in lexicographic order. The complexity of the machine was then based on the worst-case time gap ("delay") between the enumeration of consecutive outputs. This model can be used to study the problem of taking an input $1^n$ and producing on output the $2^n$-sized truth table of a language on all inputs of length $n$ , while trying to minimize the average computation time required per input (so $2^n poly(n)$ is considered "efficient" in this model). This seems pretty similar to the question you're asking.

Here is a paper that uses that model. Here is a blog post that is only somewhat related, but includes some references that you might find interesting.

One note about this model is that for some NP problems, including SAT, you can print their truth table in polynomial time per bit by exploiting the self-reducibility of the problem. For example, with SAT, you can always efficiently find the next bit of the truth table by fixing one of the variables, computing the reduced version of the problem under this variable fix, and then looking up the solution to the reduced version of the problem in the truth table that you have computed so far.

Answer 3

It's difficult to know what you mean because you're staying at a level that's so high that there's nothing interesting. Specific cases could be very interesting, but the basic idea that having computed a function for one input can make it easier to compute it for other inputs is too general.

It may be that you have a function $f$ such that having computed $f(x)$, you gain some information about $f(g(x))$ for certain choices of functions $g$: there's an equation of the form $\forall x, f(g(x)) = h(f(x))$. The general term for such properties is a morphism: $f$ is a morphism from $(D,g)$ to $(R,h)$ where $D$ is the domain of $f$ and $R$ is its range. The interesting part is finding useful algebraic structures with such properties.

Sometimes the computation of $f(x)$ involves work that's the same for all possible inputs, or for a subset of possible inputs that are in some sense sufficiently similar. Splitting the computation into a common part and an input-specific part is known as partial evaluation. The interesting aspect is finding useful ways to partially evaluate a function, and useful ways to memorize and consult partial results without wasting more time consulting cached partial results than would have been spent recalculating the thing.

Answer 4

You seem to be asking about incremental computation.

In general, it takes the following form: we have a function $f$, which is expensive to compute. We have computed $f(x)$ for a single input $x$. Now we want to compute $f(x')$, for a second input $x'$ where $x'$ is somehow "similar" to $x$. It'd be nice if we could take advantage of the fact that we already know $f(x)$ to compute $f(x')$ more quickly than computing it from scratch. This is the sort of problem that incremental computation helps with.

There are many methods for incremental computation: too many to list here. The particular method to use will depend on the nature of the function $f$. The Wikipedia article I linked to has a few references to get you started. If you want more details, you'll probably need to pick a single function $f$ and ask about that one, or a narrowly-defined class of functions $f$.

You might also be interested in strength reduction from the compiler optimization literature.

Answer 5

This is basically what dynamic data structures and streaming algorithms are about. A few links, off the top of my Google:

• High performance data structure for streaming graphs
• Mihai Patrascu's thesis
• Dynamic Integer Sets with Optimal Rank, Select, and Predecessor Search
• Dynamic shortest paths and transitive closures

For example, a dynamic data structure for shortest paths in a graph computes all shortest paths in a graph, and then when you add or remove edges to the graph should do the least amount of work needed to update all of the shortest path information. (Actually, frequently it is a combination of running time and the space needed for the data structure that is considered, but for the purposes of this question that's just a detail.)

Answer 6

Many times, we can use Linearization of a function to approximate values near a point to reasonable accuracy. A single answer is generated with expensive algorithms (e.g., $\sqrt{2}\approx1.41421...$) then nearby answers are generated from that answer with a simple algorithm (e.g., $\sqrt{x}\approx0.35355x+0.70711, x\approx2$. Using expensive algorithms, $\sqrt{2.05}\approx1.43178$, while the cheap algorithm produces $\sqrt{2.05}\approx1.43189$. $\sqrt{1.95}\approx1.39642$ (expensive) and $\sqrt{1.95}\approx1.39653$ (cheap) are likewise quite close.

A really simplified version of the above is when we approximate a function as constant near a point, such as the surface gravity of a planet. $f={{m_om_nG}\over{r^2}},a={f\over{m_o}}$ becomes $a=c_n$ where $c_n$ is calculated once at planet $n$'s creation in a game or simulation.

To a large extent though, this "strange concept" is how basic computer science works. We save intermediate results then calculate many end results from that number, rather than re-doing expensive computations repeatedly. It's just that normal programming simplifies the concept further. $s=\sqrt{2}, x=s+4, y=s+9$ is more readable than $x=\sqrt{2}+4, y=x+5$ (especially if we're calculating hundreds of variables), and if we don't know the offsets ahead of time, $s=\sqrt{2}, x=s+O_x, y=s+O_y$ is faster than $x=\sqrt{2}+O_x, y=x+(O_y-O_x)$.

Another way to use previous data is the incremental results methods used in things like data backup and video streaming to save bandwidth and time. Each frame is re-calculated using multiple differential frames rather than being transmitted in its entirety.

A different class of this concept is calculations that require super-slow or real-money-expensive processes, like humans or sending satellites to space. We take these "algorithms" and re-interpret the results in a different context. For example, we can measure irradiance from the Sun near Earth at $1367 {W\over{m^2}}$ using expensive satellite equipment. Now we can calculate irradiance near other bodies quickly and cheaply. For example, $P_{Mars}=P_{Earth}{(1 AU)^2\over(1.52 AU)^2}\approx592{W\over{m^2}}$.

Addendum:
I don't think what you're asking for is possible in a direct sense. If getting $f(x+\Delta x)$ from $f(x)$ is somehow easier than plugging $x+\Delta x$ directly into $f()$ then you can probably simplify $f()$ somehow.

Let's use your example. $f(x_1)=8x_1=h$, so now we want to find $f(x_2)$$=f(x_1+\Delta x)$ as a function of $h$ and something else. $f(x_1+\Delta x)$$=8(x_1+\Delta x)$$=h+8\Delta x$$=h+8(x_2-x_1)$. We could try it as $f(x_2)=f(x_1*k_2)$, which gets $f(x_2)$$=8(x_1k_2)$$=h{{x_2}\over{x_1}}$. In either case, we do more work getting $x_2$ from $x_1$ than just calculating $f(x_2)=8x_2$ directly.

I don't have mathematical proof of this, but I would imagine this holds for any complex function, because a function is already a definition of how to relate inputs to outputs. If you could somehow re-define an extremely complex formula for all inputs relative to a known output, then nobody would bother with the complex formula anymore except to show how they got the fast formula.

Answer 7

This paper describes a new form of incremental computation: taking derivatives on data-type-valued functions (e.g. List-valued functions).

http://www.informatik.uni-marburg.de/~pgiarrusso/papers/pldi14-ilc-author-final.pdf

Answer 8

For what it's worth, it turns out that this is how quantum computing works. When it does it's computations, it does so on cubits which can be 1, 0, or a superposition of 1 and 0. If you use superpositional bits, it means that it does the computations on all possible bit value permutations. It's only when the result is "observed" that it collapses into an actual value. Unfortunately you can't (or they don't know how) to clone the result in the unobserved state, so you can't get access to all permutations, only one of them.