Anyone good at math? - Reverse engineer an algorithm

[chopin1810]

davebardsley, thanks, i'll look into that.
chopin1810, as I have already stated this is not a homework question

If you need it immediatly, then it's probably for your job, and in that case I still consider it homework.

[daacosta]

If you need it immediatly, then it's probably for your job, and in that case I still consider it homework.

f(xi, yi, zi) = Ai

From the given data set and the extra conditions of xi, yi and zi >= 0 and a subset of Z [integers] and Ai >= 0

Dude... Are you sure this is not homework?

My first trial would be with a garden variety:

f(xi, yi, zi) = K xi + L yi + M zi

I would not even try to solve it by hand but I would use Solver from MS Excel with K, L and M as the adjustable parameters and force R^2 to be 1.0... Or you could use a SAS program...

data jason;
input xi yi zi Ai;
cards;
6 847 3,240 12,851
6 1,360 4,590 17,787
5 313 1,000 5,034

<Data goes here...>
;
proc corr;
proc reg;
model Ai=xi yi zi;
output out=resids p=yhat r=resid;
proc plot;
plot resid*&#40;yhat&#41;;
proc univariate plot;
var resid;
run;

btw, have you plotted that animal using Octave or Matlab?

[smolloy]

Go easy on me here -- I'm thinking while I'm typing and I had a couple of beers with dinner

If the three input numbers are x, y, and z, and the output is sigma, then you can imagine an infinite function which could cover all possible solutions, like this (all captial letters in this represent constants),
(A)+(Bx+Cy+Dz)+(Ex.x+Fx.y+Gx.z+Hy.y+Iy.z+Jz.z)+(Kx .x.x+Lx.x.y+Mx.x.z+...) = Sigma

I've put brackets around certain sets of components of the function to indicate the different orders -- constant, linear, 2nd order terms, etc. As you can see this leads to an inifinite series of terms, which is not good, so we need to start cutting terms. To do this you could use the context of the problem (which you don't want to tell us!) -- for example, perhaps you can see from the context that the constant (A) can be eliminated. From whatever terms remain, you are limited by the data. If you have n data examples, then you can only solve this for n terms. You gave us three examples, which means that it would be possible for us to solve this equation for three terms -- for example, A, B, and C -- however you allude to the fact that there are more examples, so you will be able to solve this equation to a higher degree of accuracy than us.

The problem that I'm not smart enough to get around is that there will always be a certain amount of ambiguity due to the fact that you have to eliminate terms relatively randomly (if the inputs were less than zero then you could start eliminating the higher order terms that would tend towards zero, but this isn't the case). This ambiguity means that being given a new data set could result in you "reverse engineering" a completely different solution. And I can't figure out a way around this.

I haven't used the facts that x, y, and z are all greater than zero and are integers, and this may provide the key. I dunno.

I hope my ramblings were able to provide some insight

[daacosta]

Absolutely interesting... I suggested starting with a regular old linear function because I am lazy. However, the SAS code I shared can be altered to fit any function you wish to use...

I don't know what the problem posted here originally is about but given a set of data one can fit it to a function one wishes to...

One possibility:

Fix two of the parameters and let the third one blow up to see what the result is...

Fix the other two parameters and repeat...

We are just trying to see if the function produces values that are bounded...

It is 2:22 am here and more data is required... What is this thing for anyway?

[psic]

It is 2:22 am here and more data is required... What is this thing for anyway?

He 'can't disclose it'.

Probably black helicopter type stuff, very hush-hush. Need-to-know basis, the works.

As daacosta already said, have you tried plotting it? Hopefully, you'll see a nice function emerge.

[TomX]

It is 2:22 am here and more data is required... What is this thing for anyway?

He 'can't disclose it'.

Probably black helicopter type stuff, very hush-hush. Need-to-know basis, the works.

As daacosta already said, have you tried plotting it? Hopefully, you'll see a nice function emerge.

If it was something especially important they hire cryptanalysts I think.

Plotting it will not work, there is an infinite number of functions to give the output to the inputs given, though most of them will be extremely complex.

I emailed him asking for the output to certain inputs, ones which would be useful in trying to figure out what the function does:
0,0,0 <-- always useful
1,1,1 <-- ditto
10,21,143 <-- all co-prime to each other
5,7,11 <-- all prime

others too (though less useful I think).

He replied saying how the inputs cannot be chosen, they're input from elsewhere (maybe it's a sensor of some sort? the input would be whatever the sensor senses, say, temperature) so if we was to be given any more data points, we wouldn't be able to choose the input.

I believe, unless someone is really lucky, that it's impossible to find the function (and therefore inverse function).

[jasonlambert]

I tried plotting it in a some charts in openoffice calc... I don't think when people said "try plotting it" that was what they intended I could'nt get it to accept all the columns properly either in OO. Matlab i've never heard of and wasn't in apt-cache, and I have no idea how to use octave2.

I was talking to someone who is a math guru about using neural networks (really interesting stuff actually) to solve it, I would need to get a lot more data than I currently have in order to do it with any sort of accuracy.

Anyway, I think this is as far as i can go without more data; thanks to everyone for their help.

[daacosta]

Try this:

Fix (x, y) = (0, 0) and let z be the independent variable

Caculate F(0,0,z) vs. z to see what is it that we are dealing with...

Repeat the above with F(0,1,z) then with F(0,2,z) then... You get the picture...

This will give you a set of parametric curves that will indicate you what the partial derivative with respect to z will look like... Now...

Thus far you have worked on a bidimensional plane and it is time to go to a tri-dimensional space.

Calculate F(1,0,z), F(2,0,z) and so on... Repeat with F(1,1,z) F(2,1,z) etc. These are going to be your contours and we will be able to run a SAS program to fit the 'rugs'

[davebardsley]

Very nice solution daacosta! Wish I thought of it.