Hard MATH question no 1 answered YET!

[invitro]

Ok, ive posted this before, but many people got confused and dint know what i was talking about. Im going to try again, because this is extremly important to me.

Ok.

If u have a set of random numbers, lets say 5 of them.
Lets say their all tied together by their differences in numbers.

So # 1 & # 2 have a difference of 5.
#3 has a difference of 4 with 5 - ^
#4 has a difference of 6 with 4
#5 has a difference of 2 with 6
and so on.... so it would look like this.

X1,X2,X3,X4,11

Lets say i gave u the last number, and the difference between 11 and X4. And said it was 2.

X1 - X2 = A# ( - does not mean nagative, means difference)
X3 - A# = B#
X4 - B# = C#
11 - C# = 2

.....i lost most of ya dint i? ........ anyways, how can i reverse this equasion.
What i tried to do is

Lets say i have the #'s.
1, 2, 3, 6, 7 (their all random).

I tried doing this
2 - 1 = 1
3 - 1 = 2
6 - 2 = 4
7 - 4 = 3

and then, i tried making a third colum of the differences I got in the first one.
2 - 1 = 1
4 - 1 = 3
3 - 3 = 0

But there was no way of reversing this one either, even though i had the last numbers of all the colums.

1, 2, 3, 6, 7
-1 -2- 4- 3
-1 -3 -0

Is anyone following me? So if i give u 7, 3, 0
Could u reverse this? Is this even possible?

And to those that skimed this post, were working with RANDOM numbers, so read over it if your thinking you can solve this with a number sequence with differences or something.

If you have any more questions, ill answer them asap because i know this is probably confusing alot of you, its just hard to explain.

[fkauffman]

Yep, I'm confused...

You just want some random numbers (like 0,6,3,5) sorted the other way around (5,3,6,0) ?

[Dim]

=/ i'm also lost but i caught the word "reverse" several times so...how about using the "StrReverse" method to reverse what ever you need.

Hope that helps ,
D!m

[Ctrack]

Hello,

i don't know what kind of studies you have done or are doing, but I have learned something very similar to solve these kind of problems.

Its called matrices, it also works with columns and row
First you get 3 variables in your case 5

example (witch won't be correct of course), it's just an example.

3x+7y-3z=-10
4x-2y+3z=11
2x-3y-5z=5

then they remove the variables
+3 +7 -3 -10
+4 -2 +3 +11
+2 -3 -5 +5

then they do some calculations (witch I forgot at the moment)

and they get
1 0 0 6 x=6
0 1 0 4 y=4
0 0 1 3 z=3 for example

if I were you i'd consult a good mathematics book, and look for Gauss-Jourdon or Matrices, I think it might be helpfull to do that first, and then translate it into code, or try working with Excel (great for maths)...

Greetings...

[HarryW]

I don't thikn he wants to reverse the order of the numbers, he's talking about an inverse function. I don't really understand what you're doing from your description, but I guess you do, so first of all figure out whether your function is one-to-one or not. If it's not then I'm pretty sure you won't be able to reverse it without more data.

If you have a starting number, and then you have a series of numbers representing differences between the last number and the current number, then err.. what's the problem?

This was my rough interpretation of the problem, but I don't think it's right.

[Sam Finch]

OK, I think I get what you're trying to do. Is this it

you have 5 Random Numbers A,B,C,D and E

and you transform this into 4 numbers

|A - B|
|B - C|
|C - D|
|D - E|

were the straight brackets represent the Modulus of the number, eg |4 - 5| = |-1| = 1

and you want to find the original 5 numbers from these 4

the answer's no

imagine the numbers 1,2,3,4 and 5, this gives you

1,1,1,1

the numbers 3,4,5,6,7 also give you

1,1,1,1

as to the numbers 9,8,7,6,5

and the numbers 1,2,3,2,1
an 1,2,1,2,1


this is known as a crushing transfomation, which means when you do it, you can't go back

[invitro]

Thank u all for tackeling my problem, but its not as simple as reversing numbers.

Ill try 1 more time.

Think about this chart

1, 3, 4, 6, 9

U take the first 2 numbers and u find the difference.
3 - 1 = 2 (then u take the 2, and find the diff. in the next #4) 4 becase we already used 1, 3

so its 4 - 2 = 2 (then u do the same with the next #)
6 - 2 = 4 (and so on)
9 - 4 = 3

So what u get is
1, 3, 4, 6, 9 -as the original sequence
2 2 4 3 -represents the differences.

BUT lets say i only give u
9 and 3
the last numbers
Is there a way to reverse this sequance and obtain the previous numbers?

?, ?, ?, ?, 9

U see, if u have 9 and the difference of the previous number, u take 9 - 3 to get 4.

so what we got is
?, ?, ?, ?, 9
? ? 4 3

Now how would i get 6, the # before 9.

Do u see what i mean?
I tried making another colum to get 6, because if i got 6, i could keep going to get the next # and so on solving my whole equation.

I will look into Matrices, actually that example looked like polynomials to me, but ill search for it because i think it might help me solve my question.

This is actually a very important question, and if i get it solved ill tell u all what im doing.

I hope this isent a case of 'crushing transformation'... and if it is, does anyone have any ideas how to reverse this kind of equation? maybe instead of taking the difference of the numbers, adding them or multiplaying them or doing something to them, so i can work back in the equation.



Thanks again for the interest and any help!



[Edited by invitro on 08-02-2000 at 12:08 AM]

[cognito]

Originally posted by invitro
BUT lets say i only give u
9 and 3
the last numbers
Is there a way to reverse this sequance and obtain the previous numbers?

?, ?, ?, ?, 9

U see, if u have 9 and the difference of the previous number, u take 9 - 3 to get 4.

so what we got is
?, ?, ?, ?, 9
? ? 4 3

Now how would i get 6, the # before 9.

I don't think you can from just those last 2 numbers. Because, originally you're given the whole sequence of numbers, but what you're trying to do is get the original sequence with only knowing 2 numbers. So there are an infinite number of possible sequences.

For example, say you had this information:

a b c d 8
e f g 2

You know that g = 8 - 2 = 6:

a b c d 8
e f 6 2

But from there you can pick any d and f such that d - 6 = f, which would include an infinite number of values, like:
f = -1, d = 5
f = 0, d = 6
f = 1, d = 7
f = 2, d = 8
...etc...

So, in conclusion, I don't think it's possible without other information.

QED

[invitro]

Yeah that is what ive been straining my mind about. I tried adding extra 2 colums and traying to figure out other numbers to build up the sequence from the top.
Lets say I had

a b c d e 3
f g h i j 2
k l m n o 4

I found that u can get J and O, and then N, but I cant seem to be able to work up, the more colums I add dosent help me in solving this.

What other information would you need? I looked into getting other formulas. Maybe instead of getting the difference i was thinking of multiplaying the numbers so they would have some kind of relation.

Any suggestions of how I could build a formula for an equation such as this?

[Sam Finch]

The big difficulty is that when you take the differences of the numbers you ignore the sign, so for 2 numbers 2,6 you get a difference of 4, for the 2 Numbers 10,6 you also get a difference of 4, by not distinguishing between the 2 you are loosing that information, unfortunatley in a way in which it cannot be retrieved. if you included a sign, set 2,6 --> 4 and 10,6 --> -4 then you can do it.

[funkyd77]

'As Sam Finch said, it cant be done:

'look at this:

'Using the numbers you gave in one of your examples, and
'also variable (in the mathematical sense) names to
'generalise it:
a=1
b=3
c=4
d=6
e=9

w=?
x=?
y=?
z=?

'now:

a-b = w, so w = 2 .....(1)
c-w = x, so x = 2 .....(2)
d-x = y, so y = 4 .....(3)
e-y = z, so z = 5 .....(4)

'now, the information you are going to give us is that:

e = 9 and z = 5 ', all other variables are unknown, so:

a, b, c, d, w, x, y all = ?

'now using equation 4 above:, we can rearrange it to get:

y = e-z, so y = 9 - 5 = 4

'so now we know e, y and z. All others still remain unknown.
'from equation (3) above there are 3 variables but only
'1 known quantity (y) so it can't be solved from here on.

[cognito]

You'd have to have the whole sequence of differences. Like:

a b c d 8
5 4 6 2

for example. Once you know the bottom row, you can figure out the top row. But otherwise, it could be anything.

[funkyd77]

Sam,

I'm not so sure that the sign would make any difference

imagine the numbers 1,2,3,4 and 5, this gives you

1,1,1,1

the numbers 3,4,5,6,7 also give you

1,1,1,1

i think the algorithm that invitro is talking about would give you 1,2,2,3 (for 1,2,3,4,5) and 1,4,2,5 (for 3,4,5,6,7)

because after the difference between the first 2 numbers (a and b in my previous post) you then start to take the difference between the next number (c) and the last difference (w), not the next number (c) and the previous number (b).

at least i think thats what he means - and i still think it can't be done though - no matter how you rearrange the numbers you still end up with too many unknowns and not enough knowns...

[Jack_the_box]

if i understood corectly you are taking a set of random numbers (x1,x2,x3,x4,x5) and calculating the total difference.
(i.e.) y1=x1
y2=x2-y1
y3=x3-y2
y4=x4-y3
y5=x5-y4
Doing this gives you a new set of numbers (y1,y2,y3,y4,y5).
if i am understanding the question, you are asking How to use the new set of numbers to find the orginal Randome set (x1,x2,x3,x4,x5)

Try this

x1=y1
x2=y2+y1
x3=y3+y2
x4=y4+y3
x5=y5+y4
For Example
x1=2
x2=5
x3=6
x4=9
x5=13
then
y1=2 : =2
y2=5-2: =3
y3=6-3: =3
y4=9-3: =6
y5=13-6:=7
now to find the orginal set of numbers
x1=2 : =2
x2=3+2: =5
x3=3+3: =6
x4=6+3: =9
x5=7+6: =13

If this helps you ,let Me Know
[email protected]

[shub]

What you're doing looks very similar to something I've seen in a numerical analysis class I have taken. I don't recall anything about working backwords with the problem, but that doesn't mean it's not possible. I suggest searching for information on difference tables, since that is what you are basically doing. They are commonly used for polynomial interpolation.

[Illuminator]

1---3   4   6   9
  |     |   |   |
  2-----|   |   |
     |      |   |
     2 ---- |   |
         |      |
         4------|
             |
             5

Above is a graphical representation of what your algorithm does. 1 and 3 result in 2 which is combined with 4 to get 2 and so on down to 5.

At each intersection where the new result if formed you must have two known numbers...this works the same in reverse. You start with 5 and 9 so you can find the third number which is 4. In order to progress further back you must have more information since you can not form 2 unique numbers from the one result.

You must have more information to retireve the values of both unknown number sets.

[Cahlel]

Hmmm... Matrixcies MIGHT work, but that would take a LOT of computing power because it's really hard to put in a matricies prgram, made one once and boy was it slow, anyway, when you stated (the second time)
so its 4 - 2 = 2 (then u do the same with the next #)
6 - 2 = 4 (and so on)
9 - 4 = 3
^
~~~~~~~~^
right there is a mathmatical error that might of screwed you up, anyway, just thought you might want to know....



__________________________________________________
Wisdom is supreme, therefore get wisdom, |
though it costs all you have, get understanding. |
Proverbs 4:7 |
__________________________________________________|

[Sparks]

as other people have noted there are 2 problems with your plan.
First you don't have enough equations for the number of variables you have. Unless I'm missing a higher math secret, you have to have as many equations as you have unknowns. If you only give the values of the last difference and the last random number, then you have 7 unknowns (a,b,c,d,w,x,y) and only 4 equations. If you add three more relations between your existing variables it will be (almost) solvable.
Ex.
a-b = w
c-w = x
d-x = y
e-y = z
and something like
a-e = d
b-e = c
z-w = x
If you know z and e then you can do a few substitutions and solve the system. Well, you could except that you are disregarding the sign of the differences. If you disregard the sign there are multiple solutions to each variable.
Ex.
z = 5, e = 9
|9 - y| = 5
y = 4 or 14
when you sub in y to another equations you have to consider both cases. Each case gives you two possible answer for each variable. Say you've done some math and you know d = 3 or 5 (i just arbitarially chose those values)
you have to consider
|3 - x| = 4
|5 - x| = 4
|3 - x| = 14
|5 - x| = 14
so x could have 8 different values.
I don't know if it'll fit into your project, but if you add 3 more realtions between your variables and have sign matter, then you can solve the system.

Sorry if i went a bit overboard on the explanation.
Oh, and if i've got this wrong please tell me.

[Dim A]

So do you have an application you intend this for? Encryption or something of the likes... or is it purely academic.

So far I'd have to agree with most of the stuff posted above... You just need more information, but there should be a way to do it with a third column.

I'll have to think about it some more... If I know what you intend it for, that may help.

[invitro]

Ummm, yes im going to put this into an application. What its going to be I can't say at THIS time.



But IF i ever get it to work, i think this will be a 1 of a kind, In the world. I dont think anyone attempted to do this yet.

I just don't know if its possible.
I will look at all the equations right now and try to figure something out.

All i need is to get this equation working. And if it works, and i make my prog. VB world will be the first to hear about it, guarante!
So bare with me guys. This should be good


And Jack_the_box
I think your equation would probably work, but im not traying to get the original numbers with the new existing sequence. Im traying to revrese the sequence so I get the missing numbers. The extra colum(s) is there to help understand what im traying to say, but that colum is also remained unknown except for a couple of numbers.



[Edited by invitro on 08-03-2000 at 06:16 PM]

[kedaman]

Gaah, this won't work Invintro

Illuminator had a good point there, you have two unknowns : second last difference/the second last number

They could be any number.

Here's another illustration, the first line is the differences, the second is the numbers:

 1 2 2 4 5
1 3 4 6 9

You notice each number is the sum of the differences on both sides, therefore they are independent.

[Reddawn]

As many have posted so far, it is just as simple as this:
"The number of your 'independent' equations should equal to the number of your unknowns, to have a finite solution."

BUT,

This is only valid for a finite solution requirement. That is your relation should be one-to-one. However, if you are OK with picking up any of the infinite solutions, then what you should do is to randomly pick numbers as many as your lacking equations (#unknowns - #equations), then assign them to your unknowns ([#unknowns - #equations] of those), and solve the equations. More openly;

a-b = w .....(1) 4 eqns, 7 unknowns (a,b,c,d,w,x,y)
c-w = x .....(2) #eqn - #unknown = 4-7 = 3
d-x = y .....(3) Make up 3 values; 1, 5, 7
9-y = 2 .....(4) Assign them as; a=1,b=5,c=7

=>

y=9-2=7 ; w=a-b=1-5=-4 ; x=c-w=7-(-4)=11 d=y+x=7+11=18

so;

a=1 , b=5 , c=7 , d=18 , w=-4 , x=11 , y=7

See how it is solved?

By this method you can trial many combinations of these variables through a code. If you have an oppurtunity to set constraints for the range of these three variables, then you can identify the ranges of the solution set, as well. But, no unique (finite) solution will ever be possible.

That's my approach. I hope it helps..

[invitro]

I guess this will never get solved.

Ok well if I cant work with differences. Is there any way I can setup this kind of equation?

Maybe with addition or multiplication. Or with ANY other kind of method.

Does anybody think this is even possible and if I should bother?

[kedaman]

You could specify more information, but on the other hand, what's the whole idea of this invintro?

[Reddawn]

I know this is not the right way of proposing it; but I have to solve some INET problems urgently. Could you guys check the related posts, as well?

Sorry from all I bothered, and thanx for those showing interest.

[DrkMatter]

Of course you should bother!!! There's always a way of solving problems, at least in part.

But the problem here is the follow: you want us to help you solve a problem which conditions seems to change at your will!!! =P
First you needed to find all unknowns, including the difference, and now we can just forget about that part and replace it with others operations...

Solve THIS part of the problem first before asking for any further help. What will be the practical outcomes of the results,and what exactly must you mathematically extract from the system?

I can't solve my own problems without knowing these, therefore others'... =P

[invitro]

Ok ok, heres my idea of what I want to do with this!
I know VB is a bad language and slow for this type of work, but what im traying to do is make a compression tool.

It would be SLOW I know, but if it works, it would be a 1 of its kind, slow compression tool.

As u know, every character has a ascii # to it right?

Lets say A = 32, and B = 33 C = 34

I havea text file I want to zip, ABC is iniside.
3 byte file.

What I was planning on doing is taking the difference of all the characters, just like in the equation and at the end, I was hoping to get only a few numbers needed to solve the equation backwards.

Now imagine, if this actually worked, any file size could be zipped into just a few bytes.
Even though it would be slow,, but its the idea that counts.

Now do you all see what im traying to do?
I need to make a sequence of numbers, that provides the smallest outcome possible, for a small file compression.


I was thinking of using Difference of Numbers to make my ending peace, but I wouldent be able to reverse the equation so far. This is what im tarying to solve.

Good idea?... or not?

[Guv]

I keep seeing this Thread getting more replies. Reddawn & Sparks (& perhaps a few others) have the right idea. You just do not have enough data. Let me attack your original problem with brute force donkey mathematics. In your first Post you gave the following equations.

X1 - X2 = A# ( - does not mean nagative, means difference)
X3 - A# = B#
X4 - B# = C#
11 - C# = 2

If difference between X1 and X2 is say 5, then either X2-X1 = 5 or X1-X2 = 5 (I think this is what you mean). This interpretation implies that the first equation contains less information than X1-X2=A

First, let us try to solve your problem assuming you really mean (X1-X2) = A

In second equation, substitute info gained from first.

X3-(X1-X2) = B

Then substitute for B in equation.

X4-[X3-(X1-X2)] = C, which simplifies to: X4-X3+X1-X2 = C

Now 11-C = 2, which implies that C = 9

So: X4-X3+X1-X2 = 9

You have one equation in 4 unknowns. You just do not have enough information to determine the 4 unknowns. X1, X2, X3 could be anything. Given any values for X1, X2, X3 you could determine a value for X4 which would work. If the above equations relate to what you call "differences", then the situation is even worse.

Does the above give you the picture?

[Guv]

After Posting a reply, I realized that I have another thought on your problem.

From your later Posts, it looks as though you are trying to develop a compression algorithm.

If so, you should realize that excellent (and some not so good) minds have worked on compression algorithms for at least 40 years. If you want to come up with a better mousetrap, you should look at the plans for previous mousetraps to avoid reinventing old ideas. Einstein once said that a midget standing on the shoulders of a giant can see farther than the giant (he meant that he studied a lot of classical physics before developing his own theories). Perhaps a fresh mind looking at some old algorithms can see something that was overlooked.

A man named Shannon developed some important concepts in Information Theory. That area of knowledge indicates some limits on how good compression algorithms can be.

[parksie]

Check out the Lempel-Zef-Welch compression algorithm. There's lots of documentation on it, as well as a relatively accessible description by Jean-Loup Gailly (writer of the ZLib compression library).

[invitro]

Thanks i will look into that right now.

And thanks again for all the replyes.

[parksie]

Here's the link: ftp://ftp.freesoftware.com/pub/infozip/zlib/zlib.html