I have these two sets of number, I also have a result. Is it possible to compute the relation between them so that I can figure out how the result is generated ?

for example I have :

Set A=4 6 12 25 39 41 Set B=3 7 14 26 47 48

And the result is : 2 24 29 31 32 49

Is it possible to figure out a formula for this ? An algorithm converts those two sets into one result set as I mentioned above. Basically I wanna break the algorithm.

  • $\begingroup$ Short answer: No. Long(er) answer: Not without a lot more information. This sounds like the Crypto.SE would be a better fit for this question. $\endgroup$ – Christian Clason Feb 5 '13 at 21:21

So if I understand you right then what you're asking for is this:

  • Given values $a_i,b_i$ as inputs and outputs $r_i=f(a_i,b_i)$, is there a way to identify $f(a,b)$?

The answer is of course "yes", and it's not even particularly difficult to do. In fact, there are infinitely many solutions. Think, for example if you had only a single input parameters and you were given a sequence of $N$ points $x_i$ and values $y_i=f(x_i)$. Then finding one $f$ can be done for example by looking among the polynomials of degree $N-1$, i.e. you are trying to find a polynomial $f(x)=\alpha_0 + \alpha_1 x + \alpha_2 x^2 + \cdots + \alpha_{N-1}x^{N-1}$ so that $y_i=f(x_i)$ for $i=1\ldots N$. These are $N$ equations for the $N$ alphas an you get them by solving a linear system.

Of course, if you are looking among the polynomials of degree $N$, then there will be infinitely many polynomials that satisfy these $N$ equations with their $N+1$ coefficients. This shows that the solution is not unique.

In 2d (with inputs $a,b$) the situation is not quite that simple because it's not quite clear how many coefficients you need to take in the $a$ and $b$ directions, respectively. But if, for example, you take $N$ coefficients in each direction, i.e. a function of the kind $f(a,b)=\sum_{i=0}^{N-1} \sum_{j=0}^{N-1} \alpha_{ij} a^i b^j$ then you are guaranteed to find coefficients that satisfy all data points. The problem is, of course, underdetermined, so there are infinitely many of these $N^2$ coefficients that yield a solution, but you can for example take the least squares solution of the linear system. Again, it's not particularly difficult to find some kind of solution.

Polynomial interpolation is not a stable approach if you have a lot of data points. There are better approaches for such cases, but the ideas above show that it's not terribly difficult to find any solution if you allow enough leeway in the class of functions you are looking in.

Of course it is an entirely different question whether the $f(a,b)$ so identified has anything to do with the function that originally created your data. That is not a question you can answer by just looking at the three sequences of numbers. You would need to have additional information, for example additional data points that you can use to determine whether what your $f(a,b)$ predicts matches the additional output. If it doesn't match then you know that you've got the wrong function and one of the infinitely many other possibilities must be it; if it matches, then all you know is that your function predicted this one point correctly, but it doesn't tell you anything about other potential points.


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