Progressions and Compression (Sundaresh Venugopal, 10:49 02/06/2006) -------------------------------------------------------------------- Underlying is the genesys of an idea for compression. The problem of compression, when stated plainly is this. We need a robust technique for representing a large amount of data in as condensced a form as possible. Viewed in an abstract sense, this means representing a larger number by a smaller one. We approach the problem by working backwards.Assume that the problem has already been solved and we have smaller number C, representing the code for the message M, we now begin the decoding process, that of building the larger number constructively from the smaller one. Since we have to construct a larger number, the fastest way to do so would be to increase it by as much as possible. When viewd in this light, a simple solution readily and automaticlly presents itself M = M + c C = C - D The first step builds up the message and the second step decreases the code.Clearly these two stes have to be performed repeatedly in a loop. Now there remains to test the feasibility of this idea. This means answering precisely two related questions, namely 1) By exactly how much should the code be reduced ? and 2) Exactly how many times should the process be repeated ? Clearly the answer to both these questions depends on the message M itself. If D is constant, clearly the values of C go through an arithmetic progression. This leads us to conjecture that probably a more general and better strategy would be to actually increase C rather than to decrease it. This way, C which represents the initial term of the series can be small rather than large, provided D is also not too large. This also conforms with our conventional way of regarding any arithmetic or geometric progression and also encourages us that if we employed a geometric progression in place of an arithmetic one, the build up of M will be at a geometric rate instead of the arithmetic rate, and therefore that much faster. There now remains to answer the second question. Assuming that the code C and the common difference D is all the information available while decoding, how do we know when to stop the process, ie the number of terms of the sequence N, which is also the number of iterations. Suppose we let N = C, then the sum to N terms of the A.P. must satisfy (C ^ 2) + (D * C * (C - 1) / 2) = M or (D + 2)(C ^ 2) - (D * C) = 2 * M which is a quadratic equation in C whose roots are C = (D +/- sqrt((D ^ 2) + (8 * M * (D + 2)))) / 2 Since D can be arbitrarily chosen, therefore we select D as the positive integer value such that the discriminant is a perfect square. The encoding here is a simple formula. Clearly the compression ratio afforded per pass by this technique is about 50%. Instead of N = C , if we let N = (C ^ 2), we will get the following equation, (D * (C ^ 4)) + (2 * (C ^ 3)) - (D * (C ^ 2)) = (2 * M) which may or may not have a formula solution. Atleast I am not averse to considering employinag numerical methods to exactly solving this equation. Clearly the compression afforded per pass here is about 75%. We can also consider decoding M as a geometric progression, with common ratio R instead of the common difference D.Clearly the sum to N terms of the G.P. must satisfy, the following equation C * ((R ^ N) - 1) / (R - 1) = M Here if we let (R - 1) = C, we will obtain (R ^ N) - 1 = M or R = (M + 1) ^ (1 / N). The special case where N is a power of 2 might be worth considering. Note that to decode the value of R must be precise or exact. Any representation of R which employs a floating point single precision or double precision or any other extended scientific representation of real numbers which can result in a loss of significance will result in lossy compression.Theoretically R can be any real number and a majority of the real numbers are irrational, but we are only interested in rational numbers of a reasonably finite precision. This being the case, we may also consider representing R as the pair of integers (P,Q) where P and Q are mutually prime. The number R itself may be a proper or an improper fraction. Here again the encoding is a simple formula. Can other forms of series or progressions, with interesting and desirable properties serve as the basis for compression ? Probably, but at least we do have two very simple and robust and rudimentary techniques based on these two classic progressions.