kym@bingvaxu.cc.binghamton.edu (R. Kym Horsell) (03/23/91)
In article <22594:Mar2204:02:1691@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: >In article <1991Mar21.200631.1925@nntp-server.caltech.edu> gwoho@nntp-server.caltech.edu (g liu) writes: >> of course, the compresser machine must be MUCH bigger than the decompressor. >> (if the decompressor has n bits of memory, the compressor must >> somehow remember which of the 2^n possable states of the decompressor >> machine the decompressor has been in.) >> if you disagree with this, you are wrong. > >Sorry, you're wrong. As anyone can look up in Knuth, you can detect >cycles in a state machine *without* remembering what states the machine >has been in. You need just one copy of the machine, running twice as >fast. This hardly qualifies as ``MUCH bigger.'' Dan is right but even righter than he thinks. :-) I think Brent has pointed out a modification of Floyd's original proposal that uses additional O(log n) storage instead of O(n). Instead of having a duplicate machine run twice as fast you have one run exponentially faster (i.e. if the sequence of states is [s0 s1 ...] then Floyd compares s_k with s_{2k}; Brent compares s_k with s_{2^k}). I understand that Bren't technique is optimial in storage. From memory I think both techniques are guaranteed to find a cycle within 3 repetitions of a loop. There is a little problem with Brent's scheme, however. -kym