Started by Jun 30 2001 12:58 PM

,
25 replies to this topic

Posted 30 June 2001 - 12:58 PM

I have a small problem and I was wondering if anyone can help. it''s a little difficult, So hopefully you like math.
I have five known variables: A1, A2, A3, A4, and A5.
I have four unkown variables: a,b,c, and d.
A1 = (a+b+c+d)/4
so it is the average of all of them
A2 = (a+b)/2
A3 = (b+d)/2
A4 = (a+c)/2
A5 = (c+d)/2
So, how can I find a,b,c, and/or d?

Posted 30 June 2001 - 01:20 PM

You will need to know all of the other unknown variables in the equation. for example...

A2 = (a+b)/2

TO FIND a

a = 2(A2)-b

TO FIND b

b = 2(A2)-a

I might be wrong, but it looks right (to me!)

I dont think there is any way to do this without knowing the other other variable in the equation.

for A1 = (a+b+c+d)/4, you would have to do something like this

a = 4(A1)-b-c-d

I hope this is corect, and helps. It is possible that i just answered a question that you did not ask, so if I missunderstood the question, let me know.

A2 = (a+b)/2

TO FIND a

a = 2(A2)-b

TO FIND b

b = 2(A2)-a

I might be wrong, but it looks right (to me!)

I dont think there is any way to do this without knowing the other other variable in the equation.

for A1 = (a+b+c+d)/4, you would have to do something like this

a = 4(A1)-b-c-d

I hope this is corect, and helps. It is possible that i just answered a question that you did not ask, so if I missunderstood the question, let me know.

Posted 30 June 2001 - 02:03 PM

Ive figured out that much, which is why i posted here.

I am thinking that I would have to use the A''s in pairs or trios. Like to find a maybe do something with A2 and A4?

Or i am thinking maybe since i have A2 and A5 I could use those and then A4 to get it somehow? This should get a and c both if its possible.

I am thinking that I would have to use the A''s in pairs or trios. Like to find a maybe do something with A2 and A4?

Or i am thinking maybe since i have A2 and A5 I could use those and then A4 to get it somehow? This should get a and c both if its possible.

Posted 30 June 2001 - 02:46 PM

Use matrices and L-U decomposition.

Say we have a resultant vector y = |A2 A3 A4 A5|, an original vector x = |a b c d| and a coefficient matrix

such that y = Ax, then A can be decomposed into lower and upper matrices L and U:

such that A = LU. A can be shown to be given as

A(i,j) = S(k=1,j){L(i,k)U(k,j)}. Solving for the important terms (A(1,1), A(1,2), A(2,2), A(2,4), A(3,1), A(3,3), A(4,3), A(4,4)), we obtain the matrices

(I may have made an error, so please validate this result by multiplication). We now obtain

or |y| = |L| * |U| * |x|

The solution can now be achieved using y = L(Ux) by letting Ux = z, y = Lz and solving for z. Then solve for x in Ux = z.

Edited by - Oluseyi on June 30, 2001 9:51:21 PM

Say we have a resultant vector y = |A2 A3 A4 A5|, an original vector x = |a b c d| and a coefficient matrix

|1 1 0 0|

A = |0 1 0 1|

|1 0 1 0|

|0 0 1 1|

such that y = Ax, then A can be decomposed into lower and upper matrices L and U:

|1 0 0 0 | |U11 U12 U13 U14|

L = |L21 1 0 0 | , U = |0 U22 U23 U24|

|L31 L32 1 0 | |0 0 U33 U34|

|L41 L42 L43 1 | |0 0 0 U44|

such that A = LU. A can be shown to be given as

A(i,j) = S(k=1,j){L(i,k)U(k,j)}. Solving for the important terms (A(1,1), A(1,2), A(2,2), A(2,4), A(3,1), A(3,3), A(4,3), A(4,4)), we obtain the matrices

|1 0 0 0| |1 1 0 0|

L = |0 1 0 0| , U = |0 1 0 1|

|1 0 1 0| |0 0 1 0|

|0 0 0 1| |0 0 0 1|

(I may have made an error, so please validate this result by multiplication). We now obtain

|A2| |1 0 0 0| |1 1 0 0| |a|

|A3| = |0 1 0 0| * |0 1 0 1| * |b|

|A4| |1 0 1 0| |0 0 1 0| |c|

|A5| |0 0 0 1| |0 0 0 1| |d|

or |y| = |L| * |U| * |x|

The solution can now be achieved using y = L(Ux) by letting Ux = z, y = Lz and solving for z. Then solve for x in Ux = z.

Edited by - Oluseyi on June 30, 2001 9:51:21 PM

Posted 30 June 2001 - 02:57 PM

okay, everyone watch me try to work this out :^)

If there is a way to reverse the calculations and find out what the source vector was from the transformed vector, T has to be inverted, which means it must be square. We'll just drop the first row (A1) and use that as the new matrix T.

Calculating det(t), we find that it is = 0. This is because the rows can be added such that they become multiples of each other, even if we left the first row in... and you can't invert a matrix whose determinate is zero.

What you ask cannot be done without knowing at least one of the variables. End of story. End of Linear Algebra proof.

...and I'm moderately sure that the above post is wrong... at any rate, one of us has to be, and I'd love a third opinion stating who it is... anyone a math prof?

--Tr][aD--

Edited by - TrIaD on June 30, 2001 10:05:57 PM

the vector [[ a1 ] [ a2 ] [ a3 ] [ a4 ] [ a5 ]] = [T]* [[ a ] [ b ] [ c ] [ d ]]

...with T = [[1/4 1/4 1/4 1/4]

[1/2 1/2 0 0 ]

[ 0 1/2 0 1/2]

[1/2 0 1/2 0 ]

[ 0 0 1/2 1/2]

If there is a way to reverse the calculations and find out what the source vector was from the transformed vector, T has to be inverted, which means it must be square. We'll just drop the first row (A1) and use that as the new matrix T.

Calculating det(t), we find that it is = 0. This is because the rows can be added such that they become multiples of each other, even if we left the first row in... and you can't invert a matrix whose determinate is zero.

What you ask cannot be done without knowing at least one of the variables. End of story. End of Linear Algebra proof.

...and I'm moderately sure that the above post is wrong... at any rate, one of us has to be, and I'd love a third opinion stating who it is... anyone a math prof?

--Tr][aD--

Edited by - TrIaD on June 30, 2001 10:05:57 PM

Posted 30 June 2001 - 03:07 PM

I agree with TrIaD. Let me do it the long way...

Althought it -seems- like you have 5 equations and only 4 unknowns, since the equations are not linearly independent, there is no way to find a unique solution.

This is easily proved by guassian elimination: Take the matrix equation (forgive my crappy matrix drawing):

|1 1 1 1||a| = |2*A1|

|1 1 0 0||b| = |2*A2|

|1 0 1 0||c| = |2*A4|

|0 1 0 1||d| = |2*A3|

|0 0 1 1||-| = |2*A5|

To do guassian elimination we change that into the augmented matrix:

|1 1 1 1 || 2*A1|

|1 1 0 0 || 2*A2|

|1 0 1 0 || 2*A4|

|0 1 0 1 || 2*A3|

|0 0 1 1 || 2*A5|

Which reduces to:

|01 01 01 01 || 2*A1|

|00 00 -1 -1 || 2*A2 - 2*A1|

|00 -1 00 -1 || 2*A4 - 2*A1|

|00 01 00 01 || 2*A3|

|00 00 01 01 || 2*A5|

-->

|01 01 01 01 || 2*A1|

|00 00 -1 -1 || 2*A2 - 2*A1|

|00 -1 00 -1 || 2*A4 - 2*A1|

|00 00 00 00 || 2*A3 + 2*A4 - 2*A1|

|00 00 00 00 || 2*A5 + 2*A2 - 2*A1|

As you can see, this gives the l.i. equations:

a + b + c + d = A1

c + d = A1 - A2

b + d = A1 - A4

Which, since there are four unknowns and only three equations, has infinitely many solutions.

What you CAN say, however, is that unless (2*A3 + 2*A4 - 2A1 = 0), and (2*A5 + 2*A2 - 2*A1 = 0), the system is inconsistant and there are no solutions; but that's pretty obvious anyway.

If you want to find any particular solution, let's just say, let d be some arbitrary variable x. Then the solution for any particular x would be:

d = x

b = 2*A1 - 2*A4 - x

c = 2*A1 - 2*A2 - x

a = -2*A1 + 2*A2 + 2*A4 + x

Hope that helps.

Edited by - Shadow Mint on June 30, 2001 10:11:17 PM

Edited by - Shadow Mint on June 30, 2001 10:13:55 PM

Althought it -seems- like you have 5 equations and only 4 unknowns, since the equations are not linearly independent, there is no way to find a unique solution.

This is easily proved by guassian elimination: Take the matrix equation (forgive my crappy matrix drawing):

|1 1 1 1||a| = |2*A1|

|1 1 0 0||b| = |2*A2|

|1 0 1 0||c| = |2*A4|

|0 1 0 1||d| = |2*A3|

|0 0 1 1||-| = |2*A5|

To do guassian elimination we change that into the augmented matrix:

|1 1 1 1 || 2*A1|

|1 1 0 0 || 2*A2|

|1 0 1 0 || 2*A4|

|0 1 0 1 || 2*A3|

|0 0 1 1 || 2*A5|

Which reduces to:

|01 01 01 01 || 2*A1|

|00 00 -1 -1 || 2*A2 - 2*A1|

|00 -1 00 -1 || 2*A4 - 2*A1|

|00 01 00 01 || 2*A3|

|00 00 01 01 || 2*A5|

-->

|01 01 01 01 || 2*A1|

|00 00 -1 -1 || 2*A2 - 2*A1|

|00 -1 00 -1 || 2*A4 - 2*A1|

|00 00 00 00 || 2*A3 + 2*A4 - 2*A1|

|00 00 00 00 || 2*A5 + 2*A2 - 2*A1|

As you can see, this gives the l.i. equations:

a + b + c + d = A1

c + d = A1 - A2

b + d = A1 - A4

Which, since there are four unknowns and only three equations, has infinitely many solutions.

What you CAN say, however, is that unless (2*A3 + 2*A4 - 2A1 = 0), and (2*A5 + 2*A2 - 2*A1 = 0), the system is inconsistant and there are no solutions; but that's pretty obvious anyway.

If you want to find any particular solution, let's just say, let d be some arbitrary variable x. Then the solution for any particular x would be:

d = x

b = 2*A1 - 2*A4 - x

c = 2*A1 - 2*A2 - x

a = -2*A1 + 2*A2 + 2*A4 + x

Hope that helps.

Edited by - Shadow Mint on June 30, 2001 10:11:17 PM

Edited by - Shadow Mint on June 30, 2001 10:13:55 PM

Posted 30 June 2001 - 03:08 PM

quote:Original post by TrIaD

...and I''m moderately sure that the above post is wrong... at any rate, one of us has to be, and I''d love a third opinion stating who it is... anyone a math prof?

Actually, I''m moderately sure myself. Logic seems to dictate that you do need to know

Posted 30 June 2001 - 04:38 PM

Thanks for all the help you peoples, but sadly I have proved it impossible. A real shame too. If this would have worked, I could have compressed any data at a constant ratio based on data size. Larger the data, better compression is. But, it would only work if I could store just THREE of the averages and find the original values then. You can get the other two from them then easily. O well.

Posted 30 June 2001 - 05:14 PM

you can figure it out

and it isnt that hard

look here

A2 = (a+b)/2

can be rewritten as

a = (2*A2)-b

then you have

A4 = (a+c)/2

can be rewritten as

a = (2*A4)-c

so you can then set the two a equations equal to each other

so that

(2*A2)-b = (2*A4)-c

if you know A2 and A4 then you can get b and c

you can use the same method for the other variables

"I pity the fool, thug, or soul who tries to take over the world, then goes home crying to his momma."

- Mr. T

and it isnt that hard

look here

A2 = (a+b)/2

can be rewritten as

a = (2*A2)-b

then you have

A4 = (a+c)/2

can be rewritten as

a = (2*A4)-c

so you can then set the two a equations equal to each other

so that

(2*A2)-b = (2*A4)-c

if you know A2 and A4 then you can get b and c

you can use the same method for the other variables

"I pity the fool, thug, or soul who tries to take over the world, then goes home crying to his momma."

- Mr. T

Posted 30 June 2001 - 06:34 PM

quote:Original post by ncsu121978

so you can then set the two a equations equal to each other

so that

(2*A2)-b = (2*A4)-c

if you know A2 and A4 then you can get b and c

you can use the same method for the other variables

Substitute any two values you like for A2 and A4 and see what you get. (2*A2) and (2*A4) will be constants, so 10 and 8 are as good choices as any. Given

10 - b = 8 - c, what are b and c?

Not as easy as you thought, eh? There''s no answer.

quote:

"I pity the fool, thug, or soul who tries to take over the world, then goes home crying to his momma."

- Mr. T

Aye. Me too.

Posted 01 July 2001 - 03:59 PM

b = c - 18

There is too a solution, just not a definite one...

incidently, TI will fully back up my claim that the matrix I represented has no existing inverse... that, or their 86 calcs don''t work right

There is too a solution, just not a definite one...

incidently, TI will fully back up my claim that the matrix I represented has no existing inverse... that, or their 86 calcs don''t work right

Posted 01 July 2001 - 04:13 PM

Well, if we were seeking relatoionships between the variables, then b = c - 18 would be a solution. But as we''re seeking the values of the four variables a, b, c and d, we have no (definite) solution.

Why do I belabor these things? Oh, well...

Why do I belabor these things? Oh, well...

Posted 01 July 2001 - 05:08 PM

Don''t worry about this, it is IMPOSSIBLE as I now see.

If anyone ever does solve it, they have a way to compress ANY amount of data to only 4 bytes. Do that, and you are God.

If anyone ever does solve it, they have a way to compress ANY amount of data to only 4 bytes. Do that, and you are God.

Posted 02 July 2001 - 12:01 PM

We appear to have five equations and three unknowns, but watch what happens:

A2 = (a+b)/2

A3 = (b+d)/2

A4 = (a+c)/2

A5 = (c+d)/2

Without much effort:

a = d + 2*(A2-A3)

a = d + 2*(A4-A5)

b = c + 2*(A2-A4)

b = c + 2*(A3-A5)

All this means is that A2-A3 = A4-A5 and A2-A4 = A3-A5. Which means that in fact, you really only had three distinct equations to begin with.

Therefore, you have three equations and four unknowns, which makes solving it impossible. Simple.

For the record, there is no such thing as a compression algorithm which can compress everything - think about it.

Edited by - Beer Hunter on July 2, 2001 7:04:12 PM

A2 = (a+b)/2

A3 = (b+d)/2

A4 = (a+c)/2

A5 = (c+d)/2

Without much effort:

a = d + 2*(A2-A3)

a = d + 2*(A4-A5)

b = c + 2*(A2-A4)

b = c + 2*(A3-A5)

All this means is that A2-A3 = A4-A5 and A2-A4 = A3-A5. Which means that in fact, you really only had three distinct equations to begin with.

Therefore, you have three equations and four unknowns, which makes solving it impossible. Simple.

For the record, there is no such thing as a compression algorithm which can compress everything - think about it.

Edited by - Beer Hunter on July 2, 2001 7:04:12 PM

Posted 02 July 2001 - 03:47 PM

Yea I knew that, pretty much. But I was sure these unknowns could be found. So, I''ve been trying to find out why its impossible for sure. Too bad. Imagine if it COULD work.

// God.c

void main() {

WORLD Earth;

LIFE People = Earth.CreateLife(HUMAN);

GiveHope(&People);

delete Earth;

EvilCackle();

}

// God.c

void main() {

WORLD Earth;

LIFE People = Earth.CreateLife(HUMAN);

GiveHope(&People);

delete Earth;

EvilCackle();

}

Posted 03 July 2001 - 10:30 AM

as a random thought, if you write a bitwise compressor, it is possible to make a compressor that will never produce a ''compressed'' file significantly larger than the source... compress the file in ''blocks'' and put a bit in front of each block for ''compressed'' or ''uncompressed'', and at worst, it''ll be 1 bit bigger per block of the file

--Tr][aD--

--Tr][aD--

Posted 04 July 2001 - 01:16 AM

I used a method like that for the image format my game uses. It has some nice compression by interleaving RLE and RGB data, well, better that TGA anyhows

Posted 04 July 2001 - 03:44 AM

Actually, Triad, thats exactly what I am doing. Creating a Bitwise Compressor, as you call it. Its called BSZIP (check out sourceforge.net). The webpage isn''t up yet and no beta is finished yet either. I have a seperate library done tho, pretty much, for accessing data by bits. You can create sequences, copy them, reverse, read/write bits and sequences, etc. Soon I will add math to it. Anyone need to work with a 4 billion bit number? :o)

I have other methods of compression tho so this isn''t a big loss. Thats the big part of BSZIP, being able to use multiple methods of compression.

// God.c

void main() {

WORLD Earth;

LIFE People = Earth.CreateLife(HUMAN);

GiveHope(&People);

delete Earth;

EvilCackle();

}

I have other methods of compression tho so this isn''t a big loss. Thats the big part of BSZIP, being able to use multiple methods of compression.

// God.c

void main() {

WORLD Earth;

LIFE People = Earth.CreateLife(HUMAN);

GiveHope(&People);

delete Earth;

EvilCackle();

}

Posted 04 July 2001 - 10:28 AM

Actually, I was thinking about mentioning that "use several algorithms" part... it sounds like a good idea...

...and no, I don''t want to work with that number, thank you

--Tr][aD--

...and no, I don''t want to work with that number, thank you

--Tr][aD--

Posted 04 July 2001 - 11:57 AM

Interleaving RLE and RGB? Isn''t that what RLE is supposed to do anyway?

This...

222222 313346 2222222 44444 33333

should compress to this...

62 06313346 72 54 53

...according to the windows help. Check under BITMAPINFOHEADER, I think.

Huffman compression is good for using in conjunction with other algos. On its own, it averages out at about 30% compression, which is quite powerful. It works on a per character basis, replacing the most common characters with shorter bit strings than the less used ones. And it can generate the best bit strings to use, too.

And now, an explanation as to why there are no magic compressors.

Let''s say a compresser**could** compress every file of x bits in length. There are 2^x possible files of x bits in length. Each one of these has to compress to a file smaller than x bits. Since there are only 2^x - 1 possible files of less than x bits, at least two files of x bits in length must compress to the same output file. But these two identical files cannot decompress to two different files, and this is a contradiction.

Therefore, you cannot compress all files of x bits in length, where x = anything.

This...

222222 313346 2222222 44444 33333

should compress to this...

62 06313346 72 54 53

...according to the windows help. Check under BITMAPINFOHEADER, I think.

Huffman compression is good for using in conjunction with other algos. On its own, it averages out at about 30% compression, which is quite powerful. It works on a per character basis, replacing the most common characters with shorter bit strings than the less used ones. And it can generate the best bit strings to use, too.

And now, an explanation as to why there are no magic compressors.

Let''s say a compresser

Therefore, you cannot compress all files of x bits in length, where x = anything.