Best way to find a set of numbers

Started by
3 comments, last by LilBudyWizer 19 years, 6 months ago
Im trying to find a decent algorithim to find the coefficents of a scaled array of 8 numbers ranging from 0 - 255 to an array of 4 numbers via this formula : (a sub n - 1 + a sub n) / 2 such that the 4 element array is an average of the 8 element array and the coefficents are the difference between the element in the 4 size array and its matching 2 elements in the 8 element. for example:::::: 127 30 89 17 255 54 109 233 as the 8 element array 78 53 154 171 as the 4 element array and the coefficents being 48, 36, 101, and 62. i need a method to generate a key that can be sent to a function which outputs the coefficents. currently all i can think of is to enumerate all of the possiblities which results in 256^4th differnt combinations to search through and linear search time. is there some better way to find the coefficents than searching 256 ^th combinations?
Advertisement
Why would you want to do this? You certainly don't save on any information by splitting your original 8 element array into two 4 element arrays! If you're looking to split your data into approximation and detail... this doesn't seem like a good way to go about it.

Anyway... let's assume there is a valid reason to do this...

Without both the averaged array and the coefficients, there is no way to obtain the original array. It's fairly trivial to see that you need either the original array to generate the coefficients, or, the average array and the 1st element of each averaged pair in order to generate the coefficients.

Timkin
Is this homework?
one: no it isnt homework and
two: a single 4 element array would be stored, and a key as well that would be passed to a function that generates the coefficents.

the 4 element array is an scaled array, element 0 is the average of elements 0 and 1 in the 8 element array, element 1 is the average of 2 and 3 etc.

the issue is how to generate the coefficents.

the only method i can think of is a linear search through all the possibilites of coefficents using the key as the number of irreations into the linear search, such as assuming coefficent 1 is 0 then moving to all the possilibites of the other 3 coefficents until all possilibites with coefficent 1 being = to are searched then increment coefficent 1 to 1 and try all other possibilites with that.
Assuming you are using this as a means of encryption you have a few problems. The biggest one being that integers are not closed under division. Overall you are just mapping vectors to vectors. So basically (x,y) maps to ((x+y)/2,(y-x)/2). I don't believe there is any general rounding rule that will cause (1,1), (1,2), (2,1) and (2,2) to map to four distinct pairs. The problem is that division and the rounding it requires. You could map (x,y) to (x+y,x-y) instead and not have that problem. Your inverse function is then (x',y') maps to ((x'+y')/2,(x'-y')/2). There you don't have rounding because x' and y' are either always both even or both odd. Specifically if x and y are both odd or both even then x+y is even and x-y is even. If one is odd and one is even then x+y is odd and x-y is odd. Another problem in your example is that you are actually using (x,y) maps to ((x+y)/2,|x-y|/2). That makes (x,y) and (y,x) map to the same pair because of the absolute value taken, i.e. x+y=y+x and |x-y|=|y-x|.

I don't understand at all why you are having trouble finding the coefficents. The only thing I can think is that because you don't have a bijection and thus no inverse you are having trouble reconstructing the original stream when you test. The problem isn't how you calculate your coefficients, but rather the definition of the coefficients itself.
Keys to success: Ability, ambition and opportunity.

This topic is closed to new replies.

Advertisement