6
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ What does "re-interpret" mean here? Symbolic computations may do what you want. Other than that, self-adusting computation is the only term that I know and seems related. $\endgroup$ – Raphael Sep 7 '15 at 17:38
  • $\begingroup$ I added an example to hopefully clear it up. $\endgroup$ – Alan Wolfe Sep 7 '15 at 17:49
  • 3
    $\begingroup$ Cross-posted on cs.se: cs.stackexchange.com/questions/46924/…. $\endgroup$ – Yuval Filmus Sep 8 '15 at 5:33
  • $\begingroup$ Like others, I'm not sure what you mean. Do you mean something like: you write an algorithm that takes in a binary string and returns the result of multiplying by 2 (it tacks a 0 on the right). Then you change your interpretation of what the input meant and no longer consider it to be the binary representation, but now think of it as a peculiar unary representation where you count the number of 1's to get the natural number it stands for. Now the algorithm computes the identity function. That satisfies having one computation with more than one interpretation, but is it what you meant? $\endgroup$ – Jim Hefferon Sep 8 '15 at 12:26
  • 5
    $\begingroup$ Please don't crosspost! That's impolite towards potential answerers which may waster their time producing redundant answers. $\endgroup$ – Raphael Sep 8 '15 at 16:46
17
$\begingroup$

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.

$\endgroup$
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ FYI, the concept of polynomial delay is still relevant in most places that combinatorial enumeration gets used. For example, listing all groups of a given order up to isomorphism, listing all instances of a given graph $H$ in a bigger graph $G$, etc. $\endgroup$ – Joshua Grochow Sep 8 '15 at 17:59
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Sorry to be so vague Gilles. Your middle paragraph is really interesting and i think is the most similar of anything I've heard about or come across in my search so far. The fact that there isn't a straight match to my question is an answer in it's own way. $\endgroup$ – Alan Wolfe Sep 8 '15 at 23:54
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Incremental computation looks like a near hit. The case I'm looking at has it such that "reinterpreting" the result to get another answer doesn't rely on the details of the function/algorithm/circuit at all. It does seem like there'd be some similar ideas reading up on it though. I'll check the other as well, thanks for the info! $\endgroup$ – Alan Wolfe Sep 7 '15 at 20:07
  • $\begingroup$ @AlanWolfe, cool, I hope it helps! If this doesn't match the needs of your particular case, you might want to ask a new question about your specific case and provide more details about your particular case. (Incidentally, the "re-interpreting" part has me puzzled; I'm not sure where that comes in, so if you ask a new question, you might need to explain that more carefully, or consider whether the "re-interpreting" language is adding anything.) $\endgroup$ – D.W. Sep 7 '15 at 20:09
  • $\begingroup$ I added some more about that to the question. It's hard cause I'm trying to find out if ive found anything remotely novel, or if it's already known, so I don't want to give it all away just to get scooped hehe. $\endgroup$ – Alan Wolfe Sep 7 '15 at 20:12
  • 3
    $\begingroup$ @AlanWolfe, I understand, but I'm afraid that kind of question might not be a good fit here. Playing 'hide the ball' or 'guess what Alan is thinking' is not a good fit for this site format. If your situation is such that you can't provide information that's relevant or necessary to understand what exactly you're asking, it's possible you might need to figure it out on your own or hire a consultant who will sign a NDA, rather than asking here. Just my personal opinion; others might differ. $\endgroup$ – D.W. Sep 7 '15 at 20:19
  • $\begingroup$ For sure. I've gotten great info on some related topics. That nothing is an exact match seems to point in the right direction and I have more to read about now. $\endgroup$ – Alan Wolfe Sep 7 '15 at 20:20
4
$\begingroup$

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

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

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ By "strange concept" I mean the literal interpretation of what I've said. You evaluate some logic circuit of XORs and ANDs in a special way and get back a bit string as an answer. You do an operation (say, XOR for example) using a constant that is based on the inputs to get the right answer. You can then change the inputs, which changes the constant, and by decoding the answer you already have using the new constant, you get the right answer for the changed inputs, without having to reevaluate the logic. $\endgroup$ – Alan Wolfe Sep 8 '15 at 4:42
  • $\begingroup$ Oh but FYI this isn't iterative computation. I also wanted to say thank you for the response, it has some good interesting info (: $\endgroup$ – Alan Wolfe Sep 8 '15 at 4:43
2
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.