home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / comp / compress / 3057 < prev    next >
Encoding:
Internet Message Format  |  1992-08-19  |  2.1 KB
  1. Path: sparky!uunet!wupost!sdd.hp.com!elroy.jpl.nasa.gov!ames!pacbell.com!pacbell!osc!jgk
  2. From: jgk@osc.COM (Joe Keane)
  3. Newsgroups: comp.compression
  4. Subject: Re: Compression technique mentioned in PCW
  5. Summary: You can't win.
  6. Keywords: golden ratio
  7. Message-ID: <5704@osc.COM>
  8. Date: 20 Aug 92 03:14:52 GMT
  9. References: <1992Aug18.155518@sees.bangor.ac.uk>
  10. Reply-To: Joe Keane <jgk@osc.com>
  11. Organization: Versant Object Technology, Menlo Park, CA
  12. Lines: 31
  13. Weather: sunny, high 75, low 55
  14. Moon-Phase: waning gibbous (63% of full)
  15.  
  16. In article <1992Aug18.155518@sees.bangor.ac.uk> mather@sees.bangor.ac.uk (Paul
  17. Mather) writes:
  18. >However, in the compression scheme mentioned in the letter, instead of
  19. >using a stout piece of oak :-), the decimal fraction was compressed by
  20. >determining two numbers, a and b, such that a/b = N.  To transmit the
  21. >original file, one need only transmit a and b.  Decompression would
  22. >involve calculating a/b and enumerating the result.
  23.  
  24. >When my friend asked me what I thought of the proposed method, my gut
  25. >reaction was to say that finding the values of a and b sounded pretty
  26. >intractable to me.  It also occurred to me that it was likely that for
  27. >some N the enumeration of the integers a and b could be longer than N
  28. >itself but my number theory is very rusty so I didn't speculate on that
  29. >to my friend. :-)
  30.  
  31. This trick of turning decimals into rationals doesn't buy you much.  Of course
  32. you should suspect that, since if it worked all the time, you would have a
  33. general method of compressing anything.  The only exception i can think of is
  34. that if you know your digits string ends with a repeated pattern, then you may
  35. be able to get some gain.  But then there are simpler ways to take care of
  36. this case.
  37.  
  38. We want to find the smallest p and q such that p/q starts with a given string
  39. of digits.  This is a simple exercise in continued fractions.  You can look up
  40. theorems about approximating with rationals to see how big we expect p and q
  41. to be.  The answer is that if you want to match N digits, the length of p and
  42. q will usually be around, surprise surprise, N/2.
  43.  
  44. --
  45. Joe Keane, amateur mathematician
  46. jgk@osc.com (uunet!amdcad!osc!jgk)
  47.