wlod@netcom.COM (Wlodzimierz Holsztynski) (04/06/91)
In article <28916@dime.cs.umass.edu> picquend@unix1.cs.umass.edu (Marc Picquendar) writes: >Could someone please send me a program that will print the digits >of PI in reverse order? Thanks in advance ... Any program will do assuming that you're satisfied with one line of digits. Just print out a line of any junk. Then many printers will print the next line with your PI in the reversed order, starting from the right margin towards left. Wlodek PS. :-)
jmartin@secola.Columbia.NCR.COM (John Martinez) (04/07/91)
> [some question about generating the digits of PI in reverse order]
Ok, I'll bite: What the blazes does this question mean?
_Surely_ the original poster is aware that PI is irrational* and that
irrational numbers have NO LAST DIGIT; so, strictly speaking, it is impossible
to generate the digits of PI in reverse order, since you would have no starting
point!
On the other hand, if the poster meant "how can I generate the first n
digits of PI in reverse order?" then I don't understand what is so hard about
the problem: several people have already posted programs which will generate
the first n digits in forward order, so use one of these, pushing each digit
onto at stack, then when you have calculated your n digits, pop them off
the stack one at a time to get your reverse order (granted, if you have
enough digits, the stack implementation may need to slough stuff off to
disk, depending on your operating system, etc. This _might_ be a
challenge for a beginner.)
BTW, I _do_ think this whole PI / e thread of discussion is interesting, but
would some clever person try and relate it to data compression? :)
-(-- John
* At least, I am _told_ PI is irrational, and I personally believe it,
although I have never seen a proof - not that I would understand this
proof if it came up and bit me :*)
--
John V.Martinez
NCR Network Products Division
jmartin@secola.Columbia.NCR.COM
(803)739-7671 vplus:633-8854ahill@hpdmd48.boi.hp.com (Andy Hill) (04/09/91)
> > BTW, I _do_ think this whole PI / e thread of discussion is interesting, but > would some clever person try and relate it to data compression? :) > Certainly. I would like to compute PI to one billion decimal places on my Apple IIe, and then store it on a single floppy, so that I can sneakernet it to my friend's Cray MP to compare results. In order to do so, I need to have really excellent data compression. Do I win a prize???? BTW, since this IS comp.compression, have any of you come up with a reasonable approach to time compression? I'd sort of like to be alive when the computation finishes... Andy ( :-) ,for the VERY humor challenged...)
melby@daffy.yk.Fujitsu.CO.JP (John B. Melby) (04/09/91)
>>Could someone please send me a program that will print the digits >>of PI in reverse order? Thanks in advance ... > >Any program will do assuming that you're satisfied with one line of digits. >Just print out a line of any junk. Then many printers will print [...] If I recall correctly, any program that spews out an arbitrary line of numbers will be printing a series of digits from pi, and by the same token, will also be printing a series of digits from pi backwards. (Does anyone have a proof of this?) I think this is also the case for non-integral square roots of integers. (Why is this pi stuff in comp.compression, anyway? Is it supposed to show how one can compress a transcendental expansion of infinite length into a program that is written in Obfuscated C? :-) ) ----- John B. Melby Fujitsu Limited, Machida, Japan melby%yk.fujitsu.co.jp@uunet
jpc@fct.unl.pt (Jose Pina Coelho) (04/09/91)
In article <24380001@hpdmd48.boi.hp.com> ahill@hpdmd48.boi.hp.com (Andy Hill) writes: > > BTW, I _do_ think this whole PI / e thread of discussion is interesting, but > would some clever person try and relate it to data compression? :) > Certainly. I would like to compute PI to one billion decimal places on my Apple IIe, and then store it on a single floppy, so that I can sneakernet it to my friend's Cray MP to compare results. In order to do so, I need to have really excellent data compression. Won't work, PI is uncompressible, one billion digits won't fit in a diskette. On the other hand, if you run the program on the cray you'll have PI in the cray in a lot less time (after all, diskettes are slow). Do I win a prize???? No, you forgot that important detail. BTW, since this IS comp.compression, have any of you come up with a reasonable approach to time compression? I'd sort of like to be alive when the computation finishes... Easy: 03:41 jpc$ compress -v time time: Compression: 92.71% -- replaced with time.Z -- Jose Pedro T. Pina Coelho | BITNET/Internet: jpc@fct.unl.pt Rua Jau N 1, 2 Dto | UUCP: ...!mcsun!unl!jpc 1300 Lisboa, PORTUGAL | Home phone: (+351) (1) 640767 - If all men were brothers, would you let one marry your sister ?
otto@tukki.jyu.fi (Otto J. Makela) (04/10/91)
In article <JPC.91Apr9141953@alfa.fct.unl.pt> jpc@fct.unl.pt (Jose Pina Coelho) writes:
Won't work, PI is uncompressible, one billion digits won't fit in a
diskette. On the other hand, if you run the program on the cray you'll
have PI in the cray in a lot less time (after all, diskettes are slow).
I wouldn't be so sure about it. Pi is globally high-entropy but locally
displays repeated sequences etc., which should make it compressable. Of
course it doesn't compress very much, but it does compress some.
--
/* * * Otto J. Makela <otto@jyu.fi> * * * * * * * * * * * * * * * * * * */
/* Phone: +358 41 613 847, BBS: +358 41 211 562 (USR HST/V.32, 24h/d) */
/* Mail: Kauppakatu 1 B 18, SF-40100 Jyvaskyla, Finland, EUROPE */
/* * * Computers Rule 01001111 01001011 * * * * * * * * * * * * * * * * */olaf@qin.Berkeley.EDU (Olaf Brandt) (04/10/91)
In article <JPC.91Apr9141953@alfa.fct.unl.pt> jpc@fct.unl.pt (Jose Pina Coelho) writes: > >Won't work, PI is uncompressible, one billion digits won't fit in a >diskette. On the other hand, if you run the program on the cray you'll >have PI in the cray in a lot less time (after all, diskettes are slow). I know I can describe PI exactly with a very short function (short compared amounts to evaluating it to the desired precision. PI is very compressible. olaf
wilf@sce.carleton.ca (Wilf Leblanc) (04/10/91)
otto@tukki.jyu.fi (Otto J. Makela) writes: >In article <JPC.91Apr9141953@alfa.fct.unl.pt> jpc@fct.unl.pt (Jose Pina Coelho) writes: > Won't work, PI is uncompressible, one billion digits won't fit in a > diskette. On the other hand, if you run the program on the cray you'll > have PI in the cray in a lot less time (after all, diskettes are slow). >I wouldn't be so sure about it. Pi is globally high-entropy but locally >displays repeated sequences etc., which should make it compressable. Of >course it doesn't compress very much, but it does compress some. >-- This post started out as a joke, and most in net.land may think it is still a joke. Pi, e, 1.00, and any number we can generate with a finite length program is (very) compressible, and contains very little information. Using Pi as the basis for a compression algorithm is also rather foolish (IMHO), since why should Pi have any better properties than any other random (or pseudo-random) sequence ?? Pi is Pi is Pi, and has slightly more information than 1, but slightly less than 2.2, and not just because Pi can be written with 2 chars, and 2.2 requires 3 (-; So the bottom line is that I'll shutup about Pi now, and hope that this thread will end soon. -- Wilf LeBlanc, Carleton University, Systems & Comp. Eng. Ottawa, Canada, K1S 5B6 Internet: wilf@sce.carleton.ca UUCP: ...!uunet!mitel!cunews!sce!wilf Oh, cruel fate! Why do you mock me so! (H. Simpson)
matthew1@garfield.cs.mun.ca (Matthew J. Newhook) (04/11/91)
otto@tukki.jyu.fi (Otto J. Makela) writes: >In article <JPC.91Apr9141953@alfa.fct.unl.pt> jpc@fct.unl.pt (Jose Pina Coelho) writes: > Won't work, PI is uncompressible, one billion digits won't fit in a > diskette. On the other hand, if you run the program on the cray you'll > have PI in the cray in a lot less time (after all, diskettes are slow). >I wouldn't be so sure about it. Pi is globally high-entropy but locally >displays repeated sequences etc., which should make it compressable. Of >course it doesn't compress very much, but it does compress some. >-- I'd be inclined to say that you can compress pi by a considerable amount. Ok... Assume 8 bits per byte. Storing, say, 1000 digits of pi would therefore take up 8008 bits (1000 * 8 + 1 * 8, for the . in 3.14...). Since we only get characters from 0-9 ignoring the . then we can encode any digit in 4 bits. Like so... 0000 - 0 0001 - 1 0010 - 2 0011 - 3 0100 - 4 0101 - 5 0110 - 6 0111 - 7 1000 - 8 1001 - 9 So compression would be 50 %. Not too bad. Of course this is just for pi.... but I think I've made my point. > /* * * Otto J. Makela <otto@jyu.fi> * * * * * * * * * * * * * * * * * * */ > /* Phone: +358 41 613 847, BBS: +358 41 211 562 (USR HST/V.32, 24h/d) */ > /* Mail: Kauppakatu 1 B 18, SF-40100 Jyvaskyla, Finland, EUROPE */ >/* * * Computers Rule 01001111 01001011 * * * * * * * * * * * * * * * * */ Matthew Newhook -- ----------------matthew1@garfield.cs.mun.ca "Living in the limelight; the universal dream for those who wish to seem. Those who wish to be must put aside the alienation, get on with the facination, the real relation, the underlying theme" - Rush
rpw3@rigden.wpd.sgi.com (Rob Warnock) (04/12/91)
In article <JPC.91Apr9141953@alfa.fct.unl.pt> jpc@fct.unl.pt (Jose Pina Coelho) writes: +--------------- | Certainly. I would like to compute PI to one billion decimal places on my | Apple IIe, and then store it on a single floppy, so that I can sneakernet | it to my friend's Cray MP to compare results. In order to do so, I need | to have really excellent data compression. | | Won't work, PI is uncompressible, one billion digits won't fit in a | diskette. On the other hand, if you run the program on the cray you'll | have PI in the cray in a lot less time (after all, diskettes are slow). +--------------- But the point was that he wanted to *compare results*. That is, he's not sure if his IIe is computing the same value for Pi as the Cray. For purposes of *comparison*, you can indeed achieve a very *high* degree of "compression", by transporting only "signatures", a.k.a. checksums. That is, on each machine compute a billion digits of Pi, and checksum it with several (hopefully) independent checksums. CRC-32, Snuffle, and MD4 come to mind. [Try sci.crypt for more examples.] Then transport the checksums and compare those. If all are equal, then with some fairly high degree of probability, the billion digits of Pi were equal. Note that since the result is not certain, only highly confident, I guess this is a form of "lossy compression", no? ;-} ;-} -Rob ----- Rob Warnock, MS-1L/515 rpw3@sgi.com rpw3@pei.com Silicon Graphics, Inc. (415)335-1673 Protocol Engines, Inc. 2011 N. Shoreline Blvd. Mountain View, CA 94039-7311
madler@nntp-server.caltech.edu (Mark Adler) (04/12/91)
>> So compression would be 50 %. Not too bad. Of course this is just for >> pi.... but I think I've made my point. I can compress pi infinitely. Here is all of the digits of pi (an infinite number) represented finitely: "The ratio of the circumference of any circle to its diameter". Many other finite representations are possible, of course. Like a program that generates pi in decimal. Mark Adler madler@pooh.caltech.edu
dfs@doe.carleton.ca (David F. Skoll) (04/12/91)
In <1991Apr11.022122.26142@garfield.cs.mun.ca> matthew1@garfield.cs.mun.ca (Matthew J. Newhook) writes: >I'd be inclined to say that you can compress pi by a considerable amount. >Ok... Assume 8 bits per byte. Storing, say, 1000 digits of pi would therefore >take up 8008 bits (1000 * 8 + 1 * 8, for the . in 3.14...). >Since we only get characters from 0-9 ignoring the . then we can encode >any digit in 4 bits. Like so... So, you're expressing Pi in BCD? Why not go whole hog and express it in straight binary, thus using somewhat under 4 bits per digit. But Pi is obviously immensely compressible - write a program to compute it to any desired accuracy. The length of such a program will be much less than the length of the closest approximation to Pi that it can compute on a decent computer. The whole issue of maximum compression possible is a very sticky one. Assuming that (for some reason!) you transmit Pi very (very!) often. Just make your compressors and decompressors very smart about generating Pi, use a Huffman code, and you can compress Pi down to 1 bit. (And that's about as good as it gets! :-)) -- David F. Skoll
stephen@estragon.uchicago.edu (Stephen P Spackman) (04/13/91)
In article <1991Apr12.104200.1691@nntp-server.caltech.edu> madler@nntp-server.caltech.edu (Mark Adler) writes:
I can compress pi infinitely. Here is all of the digits of pi (an
infinite number) represented finitely:
"The ratio of the circumference of any circle to its diameter".
I'm bothered by the absence of a signature. How do I know what
language to interpret this string in? The amount of context I have
absorbed over my life to enable me to read news in English and
understand this little joke is immense.
But it's also finite, while the expansion of Pi is not.
Which fact causes me to have greivous doubts about the existence of Pi
in any meaningful sense.
What in fact characterises the set of bitstrings that humans will ever
be interested in representing? This is an important question for data
modelling.
See? We were talking about compression all along.
stephen p spackman stephen@estragon.uchicago.edu 312.702.3982gwyn@smoke.brl.mil (Doug Gwyn) (04/16/91)
In article <STEPHEN.91Apr13001812@estragon.uchicago.edu> stephen@estragon.uchicago.edu (Stephen P Spackman) writes: >In article <1991Apr12.104200.1691@nntp-server.caltech.edu> madler@nntp-server.caltech.edu (Mark Adler) writes: > "The ratio of the circumference of any circle to its diameter". >... How do I know what language to interpret this string in? >The amount of context I have absorbed over my life to enable me >to read news in English and understand this little joke is immense. >But it's also finite, while the expansion of Pi is not. Obviously that was just an example. We could negotiate some acceptable common language for expressing mathematical predicates, then use more precise language entirely within the agreed-upon terms, perhaps: Pi =def Real_num s.t. for_all c(r) s.t. (c(r) is_curve in E2 & p is_pt_on_curve c(r) <=> p is_point in E2 & |p| = r & r is_Real_num), Pi = Circumf c(r) / Diam c(2) Well, this could be improved but you get the idea. (Perhaps Mathematica would be a suitable language for such expressions.) The information required to express the formula is not very large, on the order of a couple of hundred bits or less, given the base language (whose information content would in effect be amortized over all uses of the language, and thus be negligible per usage). >Which fact causes me to have greivous doubts about the existence of Pi >in any meaningful sense. ? That's just the standard question, what does it mean to say that a mathematical object "exists". Clearly it is not meaningless, and you can decide for yourself what the best meaning is after consulting some works on the philosophy of mathematics. >What in fact characterises the set of bitstrings that humans will ever >be interested in representing? This is an important question for data >modelling. An important but often overlooked point is that, analogously to the fact that there are no absolute probabilities but only conditional probabilities, so also there is no absolute information content but only information for discriminating in favor of some event over another in a given context of knowledge. If you send me the first million bits of Pi, you haven't sent me much information since I'll recognize the probable message from its first few bits and the remaining bits will then all be redundant. However, if you send a similar message with several of the bits altered, it would have a comparatively high information content due to the relatively lower level of redundancy (I could predict most of the trailing bits with high probability, but not all of them.)
jjensen@convex.UUCP (James Jensen) (04/16/91)
In article <STEPHEN.91Apr13001812@estragon.uchicago.edu> stephen@estragon.uchicago.edu (Stephen P Spackman) writes: >What in fact characterises the set of bitstrings that humans will ever >be interested in representing? This is an important question for data >modelling. I don't think the set exists. As soon as you define the set some trouble maker will wonder "So whats the smallest string not in this set?" and try and send it over email. Then your compression program will core dump. :-) Jim Jensen - jjensen@convex.com
gwyn@smoke.brl.mil (Doug Gwyn) (04/17/91)
In article <1991Apr16.140125.17898@convex.com> jjensen@convex.UUCP (James Jensen) writes: >I don't think the set exists. As soon as you define the set some trouble >maker will wonder "So whats the smallest string not in this set?" ... So, what is the least positive integer not expressable in less than 13 English words?
vd09+@andrew.cmu.edu (Vincent M. Del Vecchio) (04/17/91)
jjensen@convex.UUCP (James Jensen) writes: > In article <STEPHEN.91Apr13001812@estragon.uchicago.edu> stephen@estragon.uchicago.edu (Stephen P Spackman) writes: > > >What in fact characterises the set of bitstrings that humans will ever > >be interested in representing? This is an important question for data > >modelling. > > I don't think the set exists. As soon as you define the set some trouble > maker will wonder "So whats the smallest string not in this set?" and try > and send it over email. Then your compression program will core dump. :-) > > Jim Jensen - jjensen@convex.com No; it's a lossless compression program and has to work on everything; it's just that if you give it something not in the set it will output something larger. Whether or not the set exists or is well defined is another, more philosophical matter. However, I think it can be very useful to consider characteristics the set might have if it were possible to define it. -Vincent Del Vecchio vd09@andrew.cmu.edu
stephen@estragon.uchicago.edu (Stephen P Spackman) (04/17/91)
In article <15869@smoke.brl.mil> gwyn@smoke.brl.mil (Doug Gwyn) writes: In article <1991Apr16.140125.17898@convex.com> jjensen@convex.UUCP (James Jensen) writes: >I don't think the set exists. As soon as you define the set some trouble >maker will wonder "So whats the smallest string not in this set?" ... So, what is the least positive integer not expressable in less than 13 English words? It could be contested that this number isn't interesting to represent! (Only its representation is intresting...) ;-) ---------------------------------------------------------------------- stephen p spackman Center for Information and Language Studies systems analyst University of Chicago ----------------------------------------------------------------------