|
Math guys will cite the pigeonhole principle here. Since I'm a math guy, I'll do it 
It says that if you have n pigeons and m pigeonholes, with n > m, and you put each pigeon into a hole, you must end up with at least one pigeonhole that has more than one pigeon.
Let's apply this to your problem. You want to add two numbers in the range [0,255], getting a result in the range [0,255], and have the operation be reversible. Each "pigeon" will be a pair of numbers. Each "pigeonhole" will be a number in [0,255] representing their sum. Your goal is achievable if we can put all possible pairs into the pigeonholes and end up with only one pair per pigeonhole.
Let's assume it is possible and work towards a contradiction.
To restrict the sums to [0,255] let's consider just the inputs in [0,127]. The number of possible pairs is C(128,2)+128 = 8256. C(128,2) is the number of ways to choose two different numbers from [0,127], and 128 is the number of ways you can choose the same number twice from [0,127].
Since 8256 > 256, we know from the pigeonhole principle that there is at least one number in [0,255] that can be the result of more than one sum of numbers in [0,127]. This contradicts our assumption, so your goal is not achievable with the input set of [0,127].
Since the full input set of [0,255] yields more pigeons, we can conclude your goal is not possible over that set either.
|
|
|
|
|
This is all true in a sense, but there's always a way to work around it, if we're creative enough. Look at homonyms in the English language: one word can have any number of meanings, and our brain just sorts them by context. All we need is an agile enough algorithm to do the same.
Say we come to the number 63, which on one iteration expanded to the numbers x and y. Then, by altering the context on the next iteration, it could produce the numbers b and r, even though it's the same number. This is why I'm thinking a seeded rand operation could make it work... somehow. I just don't know how.
We just have to think outside the pigeonhole.
"Go to, I’ll no more on’t; it hath made me mad." - Hamlet
|
|
|
|
|
Are you disputing my proof or just ignoring logic altogether?
|
|
|
|
|
Both maybe. I don't know to be honest. Mostly I'm just thinking out loud.
"Go to, I’ll no more on’t; it hath made me mad." - Hamlet
|
|
|
|
|
Do you have limits on what the input values are? You example mentions "127" and "65". If the input are bytes and the input values restricted to 127 or less then New value = Value 1 << 4 + value 2
But I'm guessing it's not that easy
cheers,
Chris Maunder
CodeProject.com : C++ MVP
|
|
|
|
|
The values are all bytes... 0 - 255. Both in and out. I believe the 127 thing was just an example someone used.
The general consensus so far is that it can't be done. I'm of the opinion that you can do anything if you're creative enough. I'm open to being wrong of course.
The main argument against it so far, if I'm understanding them, is that you can't map 255 * 255 combinations onto 255 destination points. I'm thinking it can be done with a seeded rand function somewhere in the mix. Sure a + b will always equal c, but if you throw in x somewhere in a predictable and repeatable way, you can get any result you want for c, and you can work backwards again to figure out what a and b were.
I just don't know how to do it, and that's the problem.
"Go to, I’ll no more on’t; it hath made me mad." - Hamlet
|
|
|
|
|
Kevnar wrote: The values are all bytes... 0 - 255.
Then you're screwed. You can't fit two eggs in the same cup at the same time.
Sorry mate
cheers,
Chris Maunder
CodeProject.com : C++ MVP
|
|
|
|
|
This is probably why I haven't figured it out on my own yet. I'm usually pretty agile at making complicated things work. This one just handed my ass to me though.
"Go to, I’ll no more on’t; it hath made me mad." - Hamlet
|
|
|
|
|
Not doable, but it reminds me of "Contact" by Michael Crichton
If I follow the theory properly, the aliens do something like that, but it's only prime numbers, I think added together, and eleven of them at a time.
So you take a value and find the eleven primes that add up to it... but you have no idea what the original order was. At any rate, it's also an unworkable process.
|
|
|
|
|
Simple answer is no. Long answer is maybe.
For example, if your number A is guaranteed to never reach 19 and the other number B is guaranteed to never reach 13 then you can add them with the following formula:
C=A*13+B
The value C always fits in 1 byte. The individual values can be recovered with the formula:
A=C/13
B=C%13
This is not a simple bit combination, since A needs 5 bits, B needs 4 bits, and C needs 8. But, to be honest, the largest A times the largest B cannot exceed the 8 bits of capacity of C. This can, of course, be generalized to other bit sizes.
So, no magical compression here, and no violation of the principle of the conservation of energy in the universe.
All forms of turbo-coding (ones that use state machines behind the sceenes to help determine what the numbers could be when spliting them back again) like the ones I've seen posted here (mentioning rand) do not guarantee you can recover the original exactly. So, to compress executables I wouldn't use turbo-coding, but for audio files then maybe... if the state machines are clever enough.
Rogério Rilhas
|
|
|
|
|
So it works, but only with numbers from 19 and under. Hmmm. Well, unfortunately it's gotta work with numbers between 0 and 255 somehow.
I've been thinking about this for the past month now, and the naysayers seem to be correct. It can't be done. But the more I think about how impossible it is, the more I feel like there's some sort of work-around, some back door solution to it that we're all just not thinking of.
So I'll keep thinking about it. Thanks for your help. Let me know if you think of anything else.
"Go to, I’ll no more on’t; it hath made me mad." - Hamlet
|
|
|
|
|
He he he... well.. to be honest... I'm with the naysayers. It is a powerful argument that it cannot be done, and I am one to think that the argument cannot be defeated.
I thought about the more general formula and for you to be able to acomplish fitting 2 numbers A and B into an 8-bit value then it is necessary that max(A)*(max(B)+1)<=255 (the most accurate version needs more elements). You can achieve that with any pair of integer values for A and B that satisfy the condition, not necessarilly below 19. You could have A in the range [0;127] and B in the range [0;1], for example. That would work, because max(A)=127 and max(B)=1, so max(A)*(max(B)+1)=127*(1+1)=254. Or A in [0;50] and B in [0;4].
The closest thing to a work-around I can think of is this trick. But it is a trick. This is because I'm adding the additional information (assumption) that A and B are limited. An 8-bit value can store a given amount of information (lets call that amount 256). Whatever you do with the numbers cannot exceed a global mount of information greater than 256 otherwise it will not be reversible. The trick I presented is that the 2 numbers A and B, together, do not posess more information than 256, so they can fit in an 8-bit value reversibely. The external information required is the limits of the 2 numbers, which, of course, will be visible in the code (the operands for the / and % operations).
The fact that the sum of the bits necessary to represent A and B exceeds 8 is not relevant. For example, I need 5 bits to represent the number 17, but a lot of combinations of those 5 bits are not being used. So, I can use that "extra storage space" to accomodate part of another number. But the numbers should not "overlap", and that is why I should use only the combinations of 5 bits that I din't use before (like 18, 19, 20, ..., and 31) for the other number. This is why I have added the condition where their multiplication is below 256.
Other work-arounds will also need external knowledge. For example, if you know that the 2 numbers A and B are always double of the previous 2 numbers a and b, then, of course, you need 2 bytes for a and b and zero bytes for A and B. So, you successfully compressed 4 bytes to 2 bytes reversibely, since when you receive the 2 a and b bytes you automatically decode A and B without any more bytes.
This external knowledge is the basis of turbo coding, and can be, in fact used, to add extra information to the transmitted bits. This information is not much though, so turbo coding is maily used for error correction (where you lose only a few bits and so the little external knowledge that can be provided can help recover the values that those lost bits should have).
Other forms of external knowledge exist. For example, windows executables always start with the characters M and Z. These 2 characters can be easilly compressed if your application is compressing windows executables. And if the executable was built for INTEL processors than you can compress many of the bytes by knowing which instructions are valid on INTEL processors (and assume the executable will not contain invalid instructions, which is normal). If built for other processors the same reasoning applies. So, as you can see, many forms of external knowledge can be used, but if the external knowledge must be transmitted (telling the decoder that it is dealing with INTEL Windows executables, or MOTOROLA Macintosh executables) then you usually loose more than you gain.
So, in general, given 2 numbers A and B each with any random value between 0 and 255, you cannot join them with whatever operation into a single 8-bit value and later recover them back individually. This is a pretty well know fact in the theory of information (there are mathematical tools and thechniques to analyze how much information somthing really has).
You can mess with the "random" (thus introducing som external knowledge) to try and make things possible (like I did limiting the range for A and B), but there is nothing you can do to the "operation" if you do not change the "random". And there is not a lot of room for creation. You will have to alter the "random" factor to achieve anything new, and at this level (of external information) you are completely free to try out new stuff.
Anyway, I now see this message is getting quite long. I sugest you take a look at http://en.wikipedia.org/wiki/Information_theory[^] for a simple introduction to information theory.
Rogério Rilhas
|
|
|
|
|
Thanks Rogério.
The thing that convinced me that it can't be done is thinking of it in terms of a 256 x 256 grid, with numbers from 0 to 255 down the x and y axis. Each combination of two numbers needs to be unique in order to be retrieved. But 255^2 is 65025 necessary combinations. Therefore impossible, right? That's what someone pointed out in the discussion above. I finally understood what they were referring to while thinking about it on the bus.
However, all that means is that it's impossible while trying to organize the information on a grid. If there's one thing the history of scientific discovery has taught me, it's that there's always another way, if you search long enough, think deep enough, and get creative enough; there's always a work-around somewhere. I may never discover myself, but someone will.
All I know is that it's definitely gonna require some external information.
"Go to, I’ll no more on’t; it hath made me mad." - Hamlet
|
|
|
|
|
 HI,
i m transportation engg. M.Tech student.
my project is application of genetic algorithm for bus route network design. as i m not software engineer, it is dificult for me t prepare the code for GA. my main work is to apply the GA for bus network design.
if anybody can help me for this, i will be very much thankful.
HAVE A NICE DAY
|
|
|
|
|
Hi man,
if u get a solution for this , please mail me at karamcbose@yahoo.com
|
|
|
|
|
Pls, formalize your task with more details: street net complexity, number of projected routs, population density and distribution over a city and so on. Though the GA is very simple for realization, the information you have supplied is too poor.
P.S. Your post sounds like you don't know what you want.
|
|
|
|
|
dead_link wrote: P.S. Your post sounds like you don't know what you want.
I have to disagree. It's quite clear to me that both of htem want the answer to the same homework problem. 
--
Rules of thumb should not be taken for the whole hand.
|
|
|
|
|
hi,
thanx for reply.
actually i m at starting stage, firstly i want to develope the GA code and then to apply it for small test network for checking the results.
i think matlab will be better option to solve GA.
i have downloded GA toolbox for matlab. i m learning it.
HAVE A NICE DAY
|
|
|
|
|
hi,
i m trying for that but to start from, i m not understanding whether to use matlab or c language.
what u r doing in this area?
mail me in detail, so that we both can do something together.
have a nice day
|
|
|
|
|
I have a set of strings (seach terms) and a data string, and I'm loking for the first occurence of one of the search terms in the data string.
(Brute force: try each string at each char, until one match is found O(n^2))
Modification:
I have a map(string org, string new) with string replacements, and a data string. In data, replace all occurences of "org" by "new".
(Brute force: assuming that org and new strings don't overlap, do a string.replacealloccurences(org,new) for each replacement pair)
Are there any better approaches than the brute force?
Developers, Developers, Developers, Developers, Developers, Developers, Velopers, Develprs, Developers!
We are a big screwed up dysfunctional psychotic happy family - some more screwed up, others more happy, but everybody's psychotic joint venture definition of CP
Linkify!|Fold With Us!
|
|
|
|
|
Which language are you using ?
Blog Have I http:\\www.frankkerrigan.com
|
|
|
|
|
C++, but I'm more interested in the underlying algorithms.
Developers, Developers, Developers, Developers, Developers, Developers, Velopers, Develprs, Developers!
We are a big screwed up dysfunctional psychotic happy family - some more screwed up, others more happy, but everybody's psychotic joint venture definition of CP
Linkify!|Fold With Us!
|
|
|
|
|
How about sorting the search terms so that if you had 5 terms starting with the same letter and only two from other letters and one of the other two is first, then you search for the first character first and then the word.
If you're only interested in the first occurrence of any search term, then starting with the word that begins with the most common letter is probably faster. You can probably use statistics (ugh!) to determine which word has the most common letters.
"Oh, what a tangled web we weave, when first we practice to deceive." - Sir Walter Scott
Web - Blog - RSS - Math - LinkedIn - BM
|
|
|
|
|
peterchen wrote: I have a map(string org, string new) with string replacements, and a data string. In data, replace all occurences of "org" by "new".
(Brute force: assuming that org and new strings don't overlap, do a string.replacealloccurences(org,new) for each replacement pair)
A way would be to do the replacements in the right order. If you have two pairs, and the "new" of the first one is the same as the "old" of the second, then you need to do the second replacement first, so the "new" values from the first don't get replaced. For n pairs a solution would look like this (in pseudocode):
for 0 to number of pairs
foreach pair of replacements in alreadyadded
if new pair."old" is the same as currentpair."new"
insert pair before currentpair and break loop
end
if not inserted yet insert at the end
end for
|
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
