Newsgroups: comp.lang.c From: hoey@nrl-aic.arpa (Dan Hoey) Date: Fri, 2-Jan-87 11:31:00 EST Subject: Palindromic and portable automatic program Robbert van Renesse sends us what he calls a ``PORtable Self-Reproducing Obfuscated Palindrome.'' In an effort to make his anagram palindromic, he commits an unfortunate misnomer. The program he sent is not portable, because it relies on the ASCII encodings for double-quote, newline, and (!) comma. Here is a 356-character self-reproducing palindrome without character set dependencies. The program contains no newlines, although I have inserted a few here to avoid mailer difficulties: ================================================================ /**/main(){char*a=/*/};)q,q,a,q,q,811+a(ftnirp;'"'=q,/**/" /**/main(){char*a=/*/};)q,q,a,q,q,811+a(ftnirp;'c%'=q,/**/c% s%c%/**/,q='c%';printf(a+118,q,q,a,q,q);}/*/=a*rahc{)(niam/* */main(){char*a=/*/};)q,q,a,q,q,811+a(ftnirp;'%c'=q,/**/%c%s %c/**/,q='%c';printf(a+118,q,q,a,q,q);}/*/=a*rahc{)(niam/**/ "/**/,q='"';printf(a+118,q,q,a,q,q);}/*/=a*rahc{)(niam/**/ ================================================================ Some compilers may have problems with programs that do not end with newline. To avoid this difficulty, you may prefer the following 561-character self-reproducing palindrome. This program is two lines long, consisting of an empty line and a 559-character line; again I have folded the long line. ================================================================ /**/main(){char*a=/*/};)n,s,s,s,q,q,a,q,q,s,s,s,n,191+a(ftnirp ;'n\'=n,'\\'=s,'"'=q,/**/"c%/**/main(){char*a=/*/};)n,s,s,s,q, q,a,q,q,s,s,s,n,191+a(ftnirp;'nc%'=n,'c%c%'=s,'c%'=q,/**/c%s%c %/**/,q='c%',s='c%c%',n='c%n';printf(a+191,n,s,s,s,q,q,a,q,q,s ,s,s,n);}/*/=a*rahc{)(niam/**/c%c/**/main(){char*a=/*/};)n,s,s, s,q,q,a,q,q,s,s,s,n,191+a(ftnirp;'n%c'=n,'%c%c'=s,'%c'=q,/**/% c%s%c/**/,q='%c',s='%c%c',n='%cn';printf(a+191,n,s,s,s,q,q,a,q ,q,s,s,s,n);}/*/=a*rahc{)(niam/**/%c"/**/,q='"',s='\\',n='\n'; printf(a+191,n,s,s,s,q,q,a,q,q,s,s,s,n);}/*/=a*rahc{)(niam/**/ ================================================================ I would appreciate hearing of any improvements to these programs. Dan Hoey 1U23R11R'''1U23R11R''' --- Newsgroups: comp.lang.c From: hoey@nrl-aic.arpa (Dan Hoey) Date: Wed, 14-Jan-87 13:43:01 EST Subject: Re: conditional expression evaluation question From: "George M. Sipe" Date: 12 Jan 87 21:40:40 GMT ... Does C guarantee execution of portions of a conditional expression, even when the result is known after partial evaluation?.... The semantics of the expression ``((*cp++ | *cp++ | *cp++) == 0)'' includes the side-effect of incrementing ``cp'' three times, and so must be preserved by any correct optimizer. Even if the optimizer, by clever program analysis, could deduce that in some program ``cp'' was already pointing to a block of zeroes, and so could optimize away the entire test (or the entire loop), it would have to leave in the increments. I can't estimate the likelihood of someone writing an opitimizer that is incorrect in this respect. However, the language explicitly leaves the *order* of these side-effects unspecified, except of course that each increment of ``cp'' must be preceded by the corresponding dereference. However, the optimizer is free to postpone all of the increments until after all the dereferences, so you may end up executing something that acts like while (cp < end && triples < MINSKIP) { if ((*cp | *cp | *cp) == 0) ++triples; else triples = 0; cp += 3; } which is not what you want. I think the rewritten code is fine, though I would tend to use cp[1] instead of *(cp+1), and I would also tend to use a conditional-or (||) instead of logical-or (|) and conditional-not (!) instead of a comparison (== 0). But that's just how I write. Dan Hoey --- Date: 23 Mar 1987 16:06:21 EST (Mon) From: Dan Hoey Subject: Re: Correlated random numbers To: Physics@SRI-Unix.arpa, "Keith F. Lynch" Date: Sat, 21 Mar 87 12:47:13 EST From: "Keith F. Lynch" You posit a random number generator producing random numbers uniformly distributed on [-1, 1], and ask to ...generate two "random" real numbers with an even distribution between -1 and +1, with a desired correlation? ... (The correlation of two numbers [sic] is formally defined as the expectation of their product divided by the square root of the product of the expectation of their squares.... [for ``numbers'' read ``random variables''.] The above statistic is usually called the ``correlation coefficient'' of the random variables when the expected values are zero. When the expected values are not zero, subtract the expected values from the random variables in your definition. There is a simple answer to your question. Given a random variable R uniform on [-1,1] and a desired correlation coefficient C, define R' = R when abs(R) < ((C + 1)/2)^(1/3) -R when abs(R) > ((C + 1)/2)^(1/3). Then R' is uniformly distributed on [-1,1] and the correlation coefficient of R and R' is C. Dan --- Date: 29 Mar 1987 19:20:53 EST (Sun) From: Dan Hoey Subject: Re: Randomness To: KFL@AI.AI.MIT.EDU Keith, Sorry I didn't respond to you request for ``plane-filling'' distributions. I have some answers for that, too. But just in case you missed it, this just showed up on PHYSICS.... . . . I wonder if anyone is considering gatewaying sci.math to Internet. Maybe the CSNET guy who recently took over the sci.math.symbolic list.... Anyway, to your new problem Date: Sun, 29 Mar 87 17:56:20 EST From: "Keith F. Lynch" ...It is no longer important that the random variables have a flat distribution. What is important is that: 1) The expectation of each random variable be zero, i.e. the mean is zero. This is just normalization, since the correlation coefficent of X wrt Y is unchanged if we replace X with X-E(X). 2) The autocorrelation of each random variable is zero, i.e. the power spectral density is flat out to the Nyquist limit. I'll need to look this stuff up to understand it. I'm working from home, and my references are at work. You say it works for uniform on [-1,1], so I'll mostly just assume that. Later, you consider uniform discrete {-1,1} -- if that's acceptable, it may simplify the problem. 3) The variance (expectation of the square) be as specified. If you can make it 1, I can scale it. For uniform X on [-1,1], E(X^2) = 1/3, so I guess you are scaling already. And considering, I guess the correlation coefficient is invariant under scaling one of the RV's, so this again doesn't make the problem harder. 4) There may be ANY NUMBER of random variables, and the correlations between them must be as specified.... This is interesting. You might also consider the N-way correlation coefficent, which I think is E(product[i=1,...,n](X[i])) ------------------------------------- (product[i=1,...,n](var(X[i])))^(1/2) but that might be difficult. Your solution solved the problem just fine for two random variables. But I can't find a way to generalize it to three or more random variables. Here's another solution. Suppose you have pairs of RV's, (X1,Y1) and (X2,Y2), such that (var(Xi) var(Yi)) is constant. Let (X,Y) = (X1,Y1) with probability p and (X2,Y2) with probability (1-p). Then the correlation coefficients satisfy: CC(X,Y) = p CC(X1,Y1) + (1-p) CC(X2,Y2). This could work with the original correlation-1 and correlation-(-1) RV-pairs to solve your original problem. And it could be adulterated with your correlation-0 RV-pair to solve the problem of the RV-pair covering the square. I nearly sent you this, but I was beginning to suspect I would then be asked for an RV-pair with a continuous, or at least nonsingular, distribution over the square. I played with this some, and I think it shouldn't be too hard, but my calculus is pretty rusty. Anyway, this could solve many instances of the N-variable case, and it may be that it could solve all the ones that have solutions. We form a basis of RV-tuples of the form B[1],...,B[N], with B[1] uniform on [-1,1], and B[2],...,B[N] all either B[1] or -B[1]. There are 2^(N-1) such basis tuples. Take the entries in the correlation matrix for such a tuple as coordinates in N^2-dimensional Euclidean space. Likewise map the matrix for our target distribution. If the target point lies within the convex hull of the basis points, then the target point can be expressed as an interpolant of basis points, and the target distribution can be interpolated from the basis distributions. (An interpolant of A1,A2,...,AN is R1 A1 + R2 A2 + ... + RN AN with all Ri in [0,1], and summing to 1.) I came up with a completely different method for doing this.... I then take the square root of [the correlation coefficient] matrix. If I multiply a vector of uncorrelated random variables which always equal -1 or +1 by the matrix, I will get a vector of correlated random variables with a variance of 1 and a mean of 0, which is just what I want. Unfortunately this only works for two (or one) random variables. I don't understand why it works at all, so I don't understand why it fails for three or more random variables. I don't know why it works, either. It occurs to me that there must be constraints on what correlations three random variables can have. For instance if cor(XY) is 1, then cor(YZ) must be equal to cor(XZ) (I think). Yes, since cor(XY)=1 => prob(X=Y)=1. This is related to the inequality (Schwartz's?) that implies that correlation coefficents lie in [-1,1]. Is there any general rule? Probably we need to examine the inequality more closely. I'll do it if I find the time, or maybe you should. I know there is a multiple-variable analogue of the inequality. Let me know what you find out. Maybe you should ask karl%haddock.uucp@seismo.css.gov to copy you on the sci.math discussion. Dan --- Date: 1 Apr 1987 01:03:59 EST (Wed) From: Dan Hoey Subject: Re: Randomness To: KFL@ai.ai.mit.edu Keith, I've looked a little more at the case of three RV's on {0,1}, and can now give you the set of correlations that can be achieved. Let the RV's be X1, X2, and X3 and their correlations be C12, C13, and C23. Then any correlation vector must lie in the regular tetrahedron defined by the inequalities: 0 <= 1 - C12 + C13 - C23 = 4 Prob(X2 NE X3 = X1) 0 <= 1 + C12 - C13 - C23 = 4 Prob(X1 = X2 NE X3) 0 <= 1 - C12 - C13 + C23 = 4 Prob(X1 NE X2 = X3) 0 <= 1 + C12 + C13 + C23 = 4 Prob(X1 = X2 = X3) The vertices of the tetrahedron are (1,1,1), (1,-1,-1), (-1,1,-1), and (-1,-1,1). Thus in your example C12=.9, C23=-.8, the first equation give us C13 >= -.9 and the third gives us C13 <= -.7 . Unfortunately the proof is the straightforward case analysis of the probabilities, solving the linear system you get when you express the correlations in terms of the four probabilites. It doesn't generalize to continuous distributions or more than three RV's. I checked, and the inequality that ensures that the correlations be in [-1,1] is called the Cauchy inequality in the book I looked at, and probably it's the one also called the Cauchy-Bunyakovski-Schwartz inequality. I haven't looked at its generalizations. Depending on where you look, they may talk more about covariances than correlation coefficients. But if you scale all the RV's so they have variance 1, it's the same thing. In case this terminology is unfamiliar, cov(A,B) = E(AB), var(A,B)=E(A^2). --- Date: 2 Apr 1987 02:48:54 EST (Thu) From: Dan Hoey Subject: Re: Randomness To: "Keith F. Lynch" Keith, From: "Keith F. Lynch" Thanks. Lambert Marteens came up with a simpler formula for the constraints. If A,B, and C are three correlations (for instance C12, C23, C13), then A^2 + B^2 + C^2 <= 1 + 2ABC. From this it follows that given an A and a B, C must be at least AB - SQRT((A^2 - 1) * (B^2 - 1)) and can be at most AB + SQRT((A^2 - 1) * (B^2 - 1)). Interesting. His inequalities are weaker than mine, but it may be he hasn't made the assumption (as I have) that the RV's can take on only the values -1 and 1. So I get AB - MIN((1-A)(1-B), (1+A)(1+B)) <= C <= AB + MIN((1-A)(1+B), (1+A)(1-B)) whereas he uses the geometric mean instead of MIN, yielding a larger interval. Is his proof, or an indication of his method, online? If communicating electronically, I'd appreciate copies. I do not know what it would be for the six correlations between four random variables. I've been working on this, and I may in fact call upon poor MX for some help. I considered considering tetrahedra and higher dimensional simplexes (simplices?). But I couldn't even figure out what the side length rules were, i.e. given six side lenghts, could those sides be assembled into a tetrahedron? I did some work on this a while back. Basically, you solve for the altitude, and if that's imaginary you haven't got a tetrahedron. If I can find the equation, I'll send it along, but I don't know what this has to do with random variables and correlations. What I am really trying to do is generate N random variables with a specified set of correlations. Except for N < 3, I have had no success as yet. Well I gave it to you for the restricted range of correlations I showed: 0 <= 1 - C12 + C13 - C23 = 4 Prob(X2 NE X3 = X1) 0 <= 1 + C12 - C13 - C23 = 4 Prob(X1 = X2 NE X3) 0 <= 1 - C12 - C13 + C23 = 4 Prob(X1 NE X2 = X3) 0 <= 1 + C12 + C13 + C23 = 4 Prob(X1 = X2 = X3) You take the sums of correlations, divide by four, and get four probabilities summing to one. Pick X1 equiprobable from {-1,1}, and pick one of the four cases according to their probabilities. Then X2 and X3 are either X1 or -X1, according to which case you picked. Either this is tougher than I thought, or I am dumber than I thought. Well, it doesn't seem too easy, and I think we're all missing something--that is, unless Marteens has figured it all out. I'd really like to know if he can demonstrate RV's with the correlations he gives. One curious spinoff is I now have an exact solution for the square root of a two by two matrix. What a pity I have no use for it now. It doesn't seem to generalize to 3 by 3 or larger. Seems to me I saw a method once, but I can't say where offhand. What is the square root of a 2x2? --- Date: 2 Apr 1987 04:46:54 EST (Thu) From: Dan Hoey Subject: Randomness with 4 RV's To: KFL@ai.ai.mit.edu Here's the answer for four RV's X0,X1,X2,X3 on {-1,1}, with correlation coefficients Cij. Consider the eight quantities LH1 = C02 + C03 + C12 + C13 } { C12 + C13 + C23 + 1 = RH0 LH2 = C01 + C03 + C12 + C23 } <= { C01 + C02 + C12 + 1 = RH3 LH4 = C01 + C02 + C13 + C23 } { C01 + C03 + C13 + 1 = RH5 LH7 = 0 } { C02 + C03 + C23 + 1 = RH6 The <= means that the MAX of the LHi must not exceed the MIN of the RHi. A set of RV's with the desired correlations can be constructed by taking a value M between the MAX of the LHi and the MIN of the RHi. Then choosing X0 equiprobable on {-1, 1}, choose X0=-X1=-X2=-X3 with probability (RH0-M)/4 X0= X1=-X2=-X3 with probability (M-LH1)/4 X0=-X1= X2=-X3 with probability (M-LH2)/4 X0= X1= X2=-X3 with probability (RH3-M)/4 X0=-X1=-X2= X3 with probability (M-LH4)/4 X0= X1=-X2= X3 with probability (RH5-M)/4 X0=-X1= X2= X3 with probability (RH6-M)/4 X0= X1= X2= X3 with probability (M-LH7)/4 I got this result from Macsyma. Basically, you take the six equations defining the correlations in terms of the probabilities, and the equation that says the probabilities sum to 1. That's seven equations, you solve for seven of the probabilities. The eighth probability, M/4, shows up in all 7 solutions, and you isolate that probability. The inequalities arise from assuming that all the probabilities are nonnegative. Any problem of this form could be cast as a linear programming problem using this method. The equations state the correlation coefficients in terms of the probabilites, and that the probabilities sum to 1. The inequalities state that the probabilites are nonnegative. Put it in your favorite LP solver and you get the probabilities, if any. Unfortunately, this still only answers the question for discrete random variables. --- Date: 2 Apr 1987 06:09:28 EST (Thu) From: Dan Hoey Subject: Correlations To: pom%under.s1.gov@mordor.s1.gov, Physics@SRI-Unix.arpa, KFL@ai.ai.mit.edu From: pom%under.s1.gov@mordor.s1.gov ...Your correlations problem is trivial. Somebody did posted [sic] an answer - do you fing [sic] it 'wrong'. If Peter is referring to my earlier answer, that answer only considered the case of two random variables. If he is referring to another answer, it never made it to the Internet. To get [an] even more general answer read up on [the] multivariate Gaussian distribution ( W(X.i) = exp( - X*A*X) ) where A is a matrix. Obviously, you can create such (e.g. by sumation [sic]) and A will determine [the] cross-corelation [sic] matrix between components of X).... As abrasively and carelessly as he puts it, Peter seems to be pointing to the right answer. From EDM I find that the multivariate Gaussian distribution, also known as the multivariate normal distribution, is determined from a covariance matrix A, whose i,j element is cov(xi,xj). The density function of the distribution, a function of X=(x1,...,xn), is -n/2 -1/2 -1 (2 pi) |A| exp(- X A X' / 2). This leads me to believe that the answer to the interesting question, that of whether a given system of correlations can be achieved, is the answer implicit in the above distribution. The system must have a covariance matrix with a positive determinant. (Some cases of a zero determinant are possible using a lower-dimensional distribution). Dan --- Date: 20 Apr 1987 19:13:45 EST (Mon) From: Dan Hoey To: SF-LOVERS Subject: Fantasy and Science Fiction Conventions Cc: george%scirtp.uucp@seismo.css.gov From: seismo!mcnc!rti-sel!scirtp!george (Geo. R. Greene, Jr.) >...I'm really amazed that NESFA hasn't tried this already. They >don't have to tell the Sheraton that they're NESFA. They can just >arrange to procure (separately) reservations for all of "their" >people (fans, pros, dealers, artists, whatever) at the hotel that >weekend. While it is amusing to watch this clown expound on a subject he knows nothing about, I feel a warning is in order. So kiddies, don't try swallowing any of this stuff at home, it can interfere with your perception of reality. And if you can find 2000 friends who want to check into a hotel with you, be sure to let the hotel know, so they don't arrest you for inciting to riot. Apologies to all of you who have been to a con and know this already. Dan --- Date: Mon, 27 Apr 87 16:47:22 -0400 (EDT) From: Dan Hoey To: Cube Lovers Subject: Rubik's Cube If you happen by the Boston area, you can get Rubik's Revenge at Games People Play in Cambridge. A harder problem is to get an ordinary magic cube. I haven't seen one for sale in years. Dan --- Date: Wed, 24 Jun 87 02:40:53 -0400 (EDT) From: Dan Hoey To: Cube Lovers Subject: Groups of the larger cubes Last year Rodney Hoffman cited an article by J. A. Eidswick (in the March 1986 Math Monthly) that develops a general approach to analyzing several magic polyhedra. Did anyone else go read this one? Of particular interest is Eidswick's analysis of the larger three- dimensional cubes. The article shows that the only constraints on these cubes are the permutation parity constraints implicit in the generators and the corner and edge orientation constraints we already know about. Eidswick shows that this even holds for the ``theoretical invisible group'', where we imagine that the interior of the magic N-cube is a magic (N-2)-cube that must be solved simultaneously. The solution method he presents is to solve the parity problems by applying zero or one qtw at each of the floor(N/2) depths, then to work with commutators (aka mono-ops) to solve the rest of the cube, piece by piece. As a supplement to that article, here are the number of positions G[t](N) of the N^3 magic cube, where t, a subset of {s,m,i}, indicates the set of traits we find interesting: s (for N odd) indicates that are working in the Supergroup, and so take account of twists of the face centers. m (for N > 3) indicates that the pieces are marked so that we take account of the permutation of the identically-colored pieces on a face. i (for N > 3) indicates that we are working in the theoretical invisible group, and solve the pieces on the interior of the cube as well as the exterior. I will assume that the M and S traits apply to the interior pieces as if they were on the exterior of a smaller cube. A formula for the number of positions is 2^A (8!/2 3^7)^B (12!/2 2^11)^C (4^6/2)^D (24!/2)^E G[t](N) = --------------------------------------------------- 24^F (24^6/2)^G The following table gives the values of parameters A-G, depending on the traits, and on whether N is even or odd. Parameter Traits (N odd) (N even) (Parity) A = (N-1)/2 N/2 (Corners) B = i (N-1)/2 N/2 ~i 1 1 (Edge centers) C = i (N-1)/2 0 ~i 1 0 (Face centers) D = ~s 0 0 s,i (N-1)/2 0 s,~i 1 0 (Other cubies) E = i (N+4)(N-1)(N-3)/24 N(N^2-4)/24 ~i (N+1)(N-3)/4 N(N-2)/4 (Whole-cube) F = 0 1 (Color cosets) G = m 0 0 ~m,i (N^2-1)(N-3)/24 N(N-1)(N-2)/24 ~m,~i (N-1)(N-3)/4 (N-2)^2/4 In any case, the size of the group is exponential in a polynomial in N; the polynomial is cubic if trait "i" is present and quadratic otherwise. Here is a table of numeric approximations for cubes up to 10^3. Traits excluding s N {} {m} {i} {m,i} 2 3.674e6 3.674e6 3.674e6 3.674e6 3 4.325e19 4.325e19 4.325e19 4.325e19 4 7.401e45 7.072e53 3.263e53 3.118e61 5 2.829e74 2.583e90 6.117e93 5.585e109 6 1.572e116 1.310e148 3.077e170 2.451e210 7 1.950e160 1.484e208 2.982e253 2.072e317 8 3.517e217 2.335e289 3.247e388 1.717e500 9 1.417e277 8.208e372 5.283e529 2.126e689 10 8.298e349 4.007e477 4.041e738 1.032e978 Traits including s N {s} {s,m} {s,i} {s,m,i} 3 8.858e22 8.858e22 8.858e22 8.858e22 5 5.793e77 5.289e93 2.566e100 2.343e116 7 3.994e163 3.039e211 2.562e263 1.780e327 9 2.902e280 1.681e376 9.293e542 3.740e702 Enough, then, of what are essentially Eidswick's results. In my next message, I plan to produce lower bounds for solving these cubes. Dan --- Date: Wed, 24 Jun 87 08:54:48 -0400 (EDT) From: Dan Hoey To: Cube Lovers Subject: Lower bounds for the 3^N cubes The ability to calculate the sizes of large cube groups prompts me to generalize the lower-bound machinery we have for magic cubes, to see how it behaves asymptotically. The machinery we have uses the three isomorphic Abelian groups A(N) generated by the three sets of parallel generators for the N^3 cube. Since the group of the N^3 cube is a quotient of the free product of three copies of A(N), we can upper-bound the number of positions close to SOLVED in the cube group by the number of positions close to SOLVED in the free product. This implies a lower bound for the diameter of the cube group. One useful tool for group diameter work is the Poincare series. The Poincare series of a finitely generated group is the power series p(z) in which the coefficient of z^d is the number of group elements of length d. When the group is finite, the power series is a polynomial. For our analysis, we will need the Poincare polynomial of A(N). When N is odd, the analysis is straightforward, since A(N) is the direct product of (N-1) cyclic groups of order 4. Let S be the set of generators for A(N), |S| = 2(N-1) including inverses. Now suppose we take a subset T of S. We can construct a group element F(T) by multiplying the elements of T together, *except* that when both a generator G and its inverse G' appear in T we replace them with G^2. It is easy to see that F is a bijection between the power set of S and the group A(N). The interesting thing about F is that the length of F(T) is |T|. So the number of length-d elements of A(N) is the number of d-element subsets of S, and the binomial theorem gives us the Poincare polynomial of A(N): p(z) = (z+1)^(2(N-1)). When N is even, we are in considerably murkier waters. It's easy enough in the Cutist analysis I presented on 1 June 1982: There are N-1 ways of cutting the cube into two pieces perpendicular to each axis, and so 2(N-1) generators of A(N), and the analysis proceeds as above. But a year later I converted to Eccentric Slabism, and I suppose I should present that analysis here. In the Slabist interpretation, the generators of A(N) are the 2N quarter-turns of unit-thickness slabs. But to avoid charging for whole-cube moves, we must single out a particular slab S0 for which a turn is equivalent to turning each of the other slabs {S1,S2,...,SN} in the opposite direction. The Poincare polynomial for A(N) is p(z) = ((z+1) (SUM[0<=i=10, use 13 1/((3/2)^(1/24) - 1) 58.693 approximation for N+1). 15 1/((3/2)^(1/28) - 1) 68.558 17 1/((3/2)^(1/32) - 1) 78.423 19 1/((3/2)^(1/36) - 1) 88.288 21 1/((3/2)^(1/40) - 1) 98.153 Clearly R grows proportionally to N, so our asymptotic lower bound will be somewhere around Log[N](G[t](n)), which is O(N^3/log(n)) for the theoretical invisible groups (trait i) and O(N^2/log(n)) for the surface groups. This is as opposed to Eidswick's upper bounds, which are O(N^3) and O(N^2), respectively. So the gap increases, but not terribly quickly. It is interesting to compare this with the sort of behavior we see in the 8-puzzle, 15-puzzle, ..., N^2-1-puzzles, as Jim Saxe suggested to me many years ago. The N^2-1-puzzle has (N^2)!/2 positions and 2 to 4 possible moves, so the lower bound based on this sort of counting argument is O(log((N^2)!)) = O(N^2 log N). Yet we know that we can put O(N^2) pieces at a distance of O(N) from their home, so God's number for the puzzle is O(N^3). It is pleasant to see that our bounds on the cubes are tight to within a log factor. Dan --- Newsgroups: comp.protocols.tcp-ip From: hoey@NRL-AIC.ARPA (Dan Hoey) Date: Fri, 24-Jul-87 13:39:34 EDT Subject: Re: new lines Date: Mon, 20 Jul 87 19:55 PDT From: Kevin Carosso <@YMIR.BITNET:K...@ENGVAX.SCG.HAC.COM> Subject: Re: wollongong telnet and new line processing To: tcp...@sri-nic.ARPA X-Vms-To: IN%"tcp...@sri-nic.arpa" I traced the problem to the fact that "telnetd.c" has the following in it: ... What's really laughable about the 4.3 code is that if the is split across whatever buffer boundary telnetd is using, the code turns it into instead of . I don't think it's right to map to . I changed it to map to instead, and everything works just fine. ...I suppose another approach might be to say that the Bridge TELNET code is broken and that it shouldn't be sending when you type "carriage return" but should send .... Well, given that is supposed to be the ``normal'' line terminator, it should probably correspond to the big button on your keyboard. The real bug in the Bridge TELNET is that it apparently gives the user no way of sending a . Telnet user programs should provide some way of sending all three of , , and . On two-button keyboards (RETURN/LF or RETURN/INDEX) this probably means you need to be able to tell telnet what mapping you want. Dan --- Date: 29 Jul 1987 01:32:15 EDT (Wed) From: Dan Hoey Subject: Misdirected discussion To: "Keith F. Lynch" Cc: eagle!sph@ucbvax.berkeley.edu (S.P.Holmes) From: "Keith F. Lynch" Subject: Keep Space safe for Space? > From: eagle!sph@ucbvax.berkeley.edu (S.P.Holmes) Why don't you lighten up a little. Everyone agrees that 90% of what is posted is junk, but no two people ever agree on WHICH 90%. Everything that I post, and everything I have seen that REM has posted, has had something to do with space.... Well, that message had nothing to do with space. Please carry on your argument privately. Dan --- Date: Thu, 30 Jul 87 15:46:10 -0400 (EDT) From: Dan Hoey To: Cube Lovers Subject: Planar positions of Rubik's Magic PLANAR POSITIONS OF RUBIK'S MAGIC, THE 8 SQUARE PUZZLE by P Beck and D Hoey, July 1987 or , This is a catalog of the 96 planar positions of the 8-square Rubik's Magic puzzle. The list is based on two rules for positioning the eight squares. RULE 1--Placement: Let the pieces be numbered from 1 to 8. Any planar position must consist of squares in the pattern ``2x4'' or ``3x3'' A B C D A B C H G F E H E D G F where A,B,C,D,E,F,G,H is a cyclical rearrangement of 1,2,3,4,5,6,7,8. These patterns can also be rotated or reflected. Both the 2x4 and the 3x3 patterns have eight rotations and reflections, and there are eight possible assignments of the numbers 1-8 to the letters A-H. However, a 180-degree rotation of the 2x4 is equivalent to a reassignment of the numbers. So there are only 32 different 2x4 positions, while there are a full 64 of the 3x3 positions. RULE 2--Orientation: The pieces fit together as if the four edges of each unrotated piece were +-b-+ +-d-+ labeled a O c for odd-numbered pieces, and a E c for even-numbered +-d-+ +-b-+ pieces, and the small letters must match where neighbors abut. From rule 1, it is apparent that when neighbors abut, one of them must be an even-numbered piece and the other odd. From rule 2, we observe that if a piece is rotated by 0 or 180 degrees, then its top and bottom neighbors must be rotated the same amount and its left and right neighbors must be rotated 180 degrees differently. In this catalog, piece 1 will be placed in its unrotated orientation. Then the orientation of each piece is determined from its position relative to piece 1, and the entire position is determined by the choice of pattern under rule 1. TRANSFORMATION: Each 2x4 position can be directly transformed into any of four 3x3 positions, by folding out either end to either side. Each of the 3x3's can be directly transformed into either a vertical or a horizontal 2x4. SYMBOLOGY: Plain numbers indicate an unrotated piece, while numbers followed by an asterisk indicate pieces rotated 180 degrees. The use of numbers seems to be the most popular alternate graphics pattern at this time, as it most clearly shows what is happening as the puzzle is manipulated. ACKNOWLEDGEMENT: Thanks to Rodney Hoffman for reviewing a preliminary version of the catalog and the inspiration to prepare it in the first place. THE CATALOG: >>>16 VERTICAL POSITIONS +--+--+ +--+--+ +--+--+ +--+--+ |1 |8*| |1 |2*| |8*|1 | |2*|1 | +--+--+ +--+--+ +--+--+ +--+--+ |2 |7*| |8 |3*| |7*|2 | |3*|8 | +--+--+ +--+--+ +--+--+ +--+--+ |3 |6*| |7 |4*| |6*|3 | |4*|7 | +--+--+ +--+--+ +--+--+ +--+--+ |4 |5*| |6 |5*| |5*|4 | |5*|6 | +--+--+ +--+--+ +--+--+ +--+--+ +--+--+ +--+--+ +--+--+ +--+--+ |8 |7*| |2 |3*| |7*|8 | |3*|2 | +--+--+ +--+--+ +--+--+ +--+--+ |1 |6*| |1 |4*| |6*|1 | |4*|1 | +--+--+ +--+--+ +--+--+ +--+--+ |2 |5*| |8 |5*| |5*|2 | |5*|8 | +--+--+ +--+--+ +--+--+ +--+--+ |3 |4*| |7 |6*| |4*|3 | |6*|7 | +--+--+ +--+--+ +--+--+ +--+--+ +--+--+ +--+--+ +--+--+ +--+--+ |7 |6*| |3 |4*| |6*|7 | |4*|3 | +--+--+ +--+--+ +--+--+ +--+--+ |8 |5*| |2 |5*| |5*|8 | |5*|2 | +--+--+ +--+--+ +--+--+ +--+--+ |1 |4*| |1 |6*| |4*|1 | |6*|1 | +--+--+ +--+--+ +--+--+ +--+--+ |2 |3*| |8 |7*| |3*|2 | |7*|8 | +--+--+ +--+--+ +--+--+ +--+--+ +--+--+ +--+--+ +--+--+ +--+--+ |6 |5*| |4 |5*| |5*|6 | |5*|4 | +--+--+ +--+--+ +--+--+ +--+--+ |7 |4*| |3 |6*| |4*|7 | |6*|3 | +--+--+ +--+--+ +--+--+ +--+--+ |8 |3*| |2 |7*| |3*|8 | |7*|2 | +--+--+ +--+--+ +--+--+ +--+--+ |1 |2*| |1 |8*| |2*|1 | |8*|1 | +--+--+ +--+--+ +--+--+ +--+--+ >>16 HORIZONTAL POSITIONS +--+--+--+--+ +--+--+--+--+ +--+--+--+--+ +--+--+--+--+ |1 |8*|7 |6*| |1 |2*|3 |4*| |2 |3*|4 |5*| |8 |7*|6 |5*| +--+--+--+--+ +--+--+--+--+ +--+--+--+--+ +--+--+--+--+ |2 |3*|4 |5*| |8 |7*|6 |5*| |1 |8*|7 |6*| |1 |2*|3 |4*| +--+--+--+--+ +--+--+--+--+ +--+--+--+--+ +--+--+--+--+ +--+--+--+--+ +--+--+--+--+ +--+--+--+--+ +--+--+--+--+ |2*|1 |8*|7 | |8*|1 |2*|3 | |3*|4 |5*|6 | |7*|6 |5*|4 | +--+--+--+--+ +--+--+--+--+ +--+--+--+--+ +--+--+--+--+ |3*|4 |5*|6 | |7*|6 |5*|4 | |2*|1 |8*|7 | |8*|1 |2*|3 | +--+--+--+--+ +--+--+--+--+ +--+--+--+--+ +--+--+--+--+ +--+--+--+--+ +--+--+--+--+ +--+--+--+--+ +--+--+--+--+ |3 |2*|1 |8*| |7 |8*|1 |2*| |4 |5*|6 |7*| |6 |5*|4 |3*| +--+--+--+--+ +--+--+--+--+ +--+--+--+--+ +--+--+--+--+ |4 |5*|6 |7*| |6 |5*|4 |3*| |3 |2*|1 |8*| |7 |8*|1 |2*| +--+--+--+--+ +--+--+--+--+ +--+--+--+--+ +--+--+--+--+ +--+--+--+--+ +--+--+--+--+ +--+--+--+--+ +--+--+--+--+ |4*|3 |2*|1 | |6*|7 |8*|1 | |5*|6 |7*|8 | |5*|4 |3*|2 | +--+--+--+--+ +--+--+--+--+ +--+--+--+--+ +--+--+--+--+ |5*|6 |7*|8 | |5*|4 |3*|2 | |4*|3 |2*|1 | |6*|7 |8*|1 | +--+--+--+--+ +--+--+--+--+ +--+--+--+--+ +--+--+--+--+ >>16 NORTHWEST POSITIONS +--+--+ +--+--+ +--+--+ +--+--+ |1 |8*| |1 |2*| |8*|1 | |2*|1 | +--+--+--+ +--+--+--+ +--+--+--+ +--+--+--+ |3*|2 |7*| |7*|8 |3*| |6 |7*|2 | |4 |3*|8 | +--+--+--+ +--+--+--+ +--+--+--+ +--+--+--+ |4*|5 |6*| |6*|5 |4*| |5 |4*|3 | |5 |6*|7 | +--+--+--+ +--+--+--+ +--+--+--+ +--+--+--+ +--+--+ +--+--+ +--+--+ +--+--+ |7*|6 | |3*|4 | |2 |3*| |8 |7*| +--+--+--+ +--+--+--+ +--+--+--+ +--+--+--+ |1 |8*|5 | |1 |2*|5 | |8*|1 |4*| |2*|1 |6*| +--+--+--+ +--+--+--+ +--+--+--+ +--+--+--+ |2 |3*|4 | |8 |7*|6 | |7*|6 |5*| |3*|4 |5*| +--+--+--+ +--+--+--+ +--+--+--+ +--+--+--+ +--+--+ +--+--+ +--+--+ +--+--+ |7*|8 | |3*|2 | |6*|5 | |4*|5 | +--+--+--+ +--+--+--+ +--+--+--+ +--+--+--+ |5 |6*|1 | |5 |4*|1 | |8 |7*|4 | |2 |3*|6 | +--+--+--+ +--+--+--+ +--+--+--+ +--+--+--+ |4 |3*|2 | |6 |7*|8 | |1 |2*|3 | |1 |8*|7 | +--+--+--+ +--+--+--+ +--+--+--+ +--+--+--+ +--+--+ +--+--+ +--+--+ +--+--+ |5 |6*| |5 |4*| |6*|7 | |4*|3 | +--+--+--+ +--+--+--+ +--+--+--+ +--+--+--+ |3*|4 |7*| |7*|6 |3*| |4 |5*|8 | |6 |5*|2 | +--+--+--+ +--+--+--+ +--+--+--+ +--+--+--+ |2*|1 |8*| |8*|1 |2*| |3 |2*|1 | |7 |8*|1 | +--+--+--+ +--+--+--+ +--+--+--+ +--+--+--+ >>16 NORTHEAST POSITIONS +--+--+ +--+--+ +--+--+ +--+--+ |1 |8*| |1 |2*| |8*|1 | |2*|1 | +--+--+--+ +--+--+--+ +--+--+--+ +--+--+--+ |2 |7*|6 | |8 |3*|4 | |7*|2 |3*| |3*|8 |7*| +--+--+--+ +--+--+--+ +--+--+--+ +--+--+--+ |3 |4*|5 | |7 |6*|5 | |6*|5 |4*| |4*|5 |6*| +--+--+--+ +--+--+--+ +--+--+--+ +--+--+--+ +--+--+ +--+--+ +--+--+ +--+--+ |8 |7*| |2 |3*| |7*|8 | |3*|2 | +--+--+--+ +--+--+--+ +--+--+--+ +--+--+--+ |1 |6*|5 | |1 |4*|5 | |6*|1 |2*| |4*|1 |8*| +--+--+--+ +--+--+--+ +--+--+--+ +--+--+--+ |2 |3*|4 | |8 |7*|6 | |5*|4 |3*| |5*|6 |7*| +--+--+--+ +--+--+--+ +--+--+--+ +--+--+--+ +--+--+ +--+--+ +--+--+ +--+--+ |6 |7*| |4 |3*| |3 |4*| |7 |6*| +--+--+--+ +--+--+--+ +--+--+--+ +--+--+--+ |5 |8*|1 | |5 |2*|1 | |2 |5*|6 | |8 |5*|4 | +--+--+--+ +--+--+--+ +--+--+--+ +--+--+--+ |4 |3*|2 | |6 |7*|8 | |1 |8*|7 | |1 |2*|3 | +--+--+--+ +--+--+--+ +--+--+--+ +--+--+--+ +--+--+ +--+--+ +--+--+ +--+--+ |6*|5 | |4*|5 | |5 |6*| |5 |4*| +--+--+--+ +--+--+--+ +--+--+--+ +--+--+--+ |7*|4 |3*| |3*|6 |7*| |4 |7*|8 | |6 |3*|2 | +--+--+--+ +--+--+--+ +--+--+--+ +--+--+--+ |8*|1 |2*| |2*|1 |8*| |3 |2*|1 | |7 |8*|1 | +--+--+--+ +--+--+--+ +--+--+--+ +--+--+--+ >>16 SOUTHWEST POSITIONS +--+--+--+ +--+--+--+ +--+--+--+ +--+--+--+ |1 |2*|3 | |1 |8*|7 | |8*|1 |2*| |2*|1 |8*| +--+--+--+ +--+--+--+ +--+--+--+ +--+--+--+ |8 |7*|4 | |2 |3*|6 | |7*|6 |3*| |3*|4 |7*| +--+--+--+ +--+--+--+ +--+--+--+ +--+--+--+ |6*|5 | |4*|5 | |5 |4*| |5 |6*| +--+--+ +--+--+ +--+--+ +--+--+ +--+--+--+ +--+--+--+ +--+--+--+ +--+--+--+ |3 |2*|1 | |7 |8*|1 | |2 |3*|4 | |8 |7*|6 | +--+--+--+ +--+--+--+ +--+--+--+ +--+--+--+ |4 |5*|8 | |6 |5*|2 | |1 |8*|5 | |1 |2*|5 | +--+--+--+ +--+--+--+ +--+--+--+ +--+--+--+ |6*|7 | |4*|3 | |7*|6 | |3*|4 | +--+--+ +--+--+ +--+--+ +--+--+ +--+--+--+ +--+--+--+ +--+--+--+ +--+--+--+ |3*|4 |5*| |7*|6 |5*| |4 |3*|2 | |6 |7*|8 | +--+--+--+ +--+--+--+ +--+--+--+ +--+--+--+ |2*|1 |6*| |8*|1 |4*| |5 |6*|1 | |5 |4*|1 | +--+--+--+ +--+--+--+ +--+--+--+ +--+--+--+ |8 |7*| |2 |3*| |7*|8 | |3*|2 | +--+--+ +--+--+ +--+--+ +--+--+ +--+--+--+ +--+--+--+ +--+--+--+ +--+--+--+ |4*|5 |6*| |6*|5 |4*| |5 |4*|3 | |5 |6*|7 | +--+--+--+ +--+--+--+ +--+--+--+ +--+--+--+ |3*|2 |7*| |7*|8 |3*| |6 |7*|2 | |4 |3*|8 | +--+--+--+ +--+--+--+ +--+--+--+ +--+--+--+ |1 |8*| |1 |2*| |8*|1 | |2*|1 | +--+--+ +--+--+ +--+--+ +--+--+ >>16 SOUTHEAST POSITIONS +--+--+--+ +--+--+--+ +--+--+--+ +--+--+--+ |1 |2*|3 | |1 |8*|7 | |8*|1 |2*| |2*|1 |8*| +--+--+--+ +--+--+--+ +--+--+--+ +--+--+--+ |8 |5*|4 | |2 |5*|6 | |7*|4 |3*| |3*|6 |7*| +--+--+--+ +--+--+--+ +--+--+--+ +--+--+--+ |7 |6*| |3 |4*| |6*|5 | |4*|5 | +--+--+ +--+--+ +--+--+ +--+--+ +--+--+--+ +--+--+--+ +--+--+--+ +--+--+--+ |3 |2*|1 | |7 |8*|1 | |2 |3*|4 | |8 |7*|6 | +--+--+--+ +--+--+--+ +--+--+--+ +--+--+--+ |4 |7*|8 | |6 |3*|2 | |1 |6*|5 | |1 |4*|5 | +--+--+--+ +--+--+--+ +--+--+--+ +--+--+--+ |5 |6*| |5 |4*| |8 |7*| |2 |3*| +--+--+ +--+--+ +--+--+ +--+--+ +--+--+--+ +--+--+--+ +--+--+--+ +--+--+--+ |5*|4 |3*| |5*|6 |7*| |4 |3*|2 | |6 |7*|8 | +--+--+--+ +--+--+--+ +--+--+--+ +--+--+--+ |6*|1 |2*| |4*|1 |8*| |5 |8*|1 | |5 |2*|1 | +--+--+--+ +--+--+--+ +--+--+--+ +--+--+--+ |7*|8 | |3*|2 | |6 |7*| |4 |3*| +--+--+ +--+--+ +--+--+ +--+--+ +--+--+--+ +--+--+--+ +--+--+--+ +--+--+--+ |3 |4*|5 | |7 |6*|5 | |6*|5 |4*| |4*|5 |6*| +--+--+--+ +--+--+--+ +--+--+--+ +--+--+--+ |2 |7*|6 | |8 |3*|4 | |7*|2 |3*| |3*|8 |7*| +--+--+--+ +--+--+--+ +--+--+--+ +--+--+--+ |1 |8*| |1 |2*| |8*|1 | |2*|1 | +--+--+ +--+--+ +--+--+ +--+--+ >>END OF CATALOG --- Newsgroups: comp.unix.wizards From: hoey@nrl-aic.arpa (Dan Hoey) Date: Fri, 14-Aug-87 11:26:03 EDT Subject: Telnet flow control Date: Tue, 9 Jun 87 07:39:24 EDT From: scott@gateway.mitre.ORG To: unix-wiza...@BRL.ARPA Subject: Telnet flow control ...The problem is that the distributed telnet turns off local flow control (UCB telnet that is, I can't speak for other telnets). Here is a modified ``mode'' function taken from a 4.2bsd telnet that reinstates local flow control.... John ... tc = ¬c; tc->t_stopc = otc.t_stopc; /* hacks to allow */ tc->t_startc = otc.t_startc; /* flow control */ ltc = &noltc; .... Well, I got the same complaints, but I am *not* willing to forgo the ability to send ^S/^Q to the remote host. The easy way to do this was to also copy the ^V (literal-next) out of the terminal characteristics. So if you want to send ^S, ^Q, or ^V over the telnet, you precede them with ^V. Since this would annoy people people who just want to type ^S and damn the flow control, I put the whole thing under control of a telnet flag (-x) and command (xonxoff) that toggles the state. The relevant section of the mode routine then looks like ... tc = ¬c; ltc = &noltc; if (xonxoff) { tc -> t_startc = otc.t_startc; tc -> t_stopc = otc.t_stopc; ltc -> t_lnextc = oltc.t_lnextc; } else tc -> t_startc = tc -> t_stopc = ltc -> t_lnextc = -1; .... Maybe when I fit it into 4.3 I'll send the fixes to Berkeley, though after the CRLF wars I'm not sure they'll want to listen. Dan Hoey Internet: Hoey@NRL-AIC.ARPA UUCP: IICP: WEALLCP: for MCP --- Newsgroups: comp.lang.c From: hoey@nrl-aic.arpa (Dan Hoey) Date: Thu, 20-Aug-87 15:46:46 EDT Subject: Perror complication From: der Mouse Subject: Re: Accessing argc & argv from a functi Date: 5 Aug 87 07:33:09 GMT ... Well over half of all the calls to perror() I write look like perror((char *)0); because the prefix is more complicated than a single string, so I have fprintf(stderr,....); before the perror(). Then you had better save and restore errno around the call to fprintf, in case fprint makes a failing syscall. Wish perror() were printflike, perhaps like syslog() - syslog() accepts a printf format, except that %m means insert sys_errlst[errno]. Maybe that's why sendmail sometimes says ``Not a typewriter''? Dan Hoey Hoey@NRL-AIC.ARPA --- Newsgroups: comp.unix.wizards From: hoey@nrl-aic.arpa (Dan Hoey) Date: Fri, 21-Aug-87 17:57:07 EDT Subject: Building a 4.3BSD kernel under 4.2 Our upgrade path to 4.3 is to build the kernel under 4.2, then slide it in. But we have a few jimmies sprinkled on our vanilla sources, so I have to patch them. Last thing before patching, I decided to make sure I could correctly use the 4.3 cc, ld, /usr/include, etc. to build a 4.3 kernel. The test I decided on was to try to build an exact copy of the distributed 4.3 GENERIC kernel. So I mv'ed /4.3/GENERIC to /4.3/origGENERIC, and started building, using ``cmp -l'' and ``nm -n'' to check for differences between /4.3/{orig,}GENERIC/vmunix. I had to edit my /4.3/GENERIC/version so that /4.3/{orig,}GENERIC/vers.c would have the same length. (I changed it to "2 \n" though your mileage may differ). The hardest part was figuring out that I needed the 4.3 version of /usr/ucb/symorder. Why is some random ucb binary needed to make the kernel? RTFM. But why did they change it for 4.3? I couldn't tell you, but it definitely makes a difference in the order of symbol table entries. I'm not sure I needed to link all the other files, but they seemed likely. Anyway, I succeeded in building a kernel for which the only differences were in the version strings. Here is a shell script I use to install the 4.3 tools needed to compile the kernel, and it may be useful to you if you want to build a 4.3 kernel under 4.2. The only tailoring you will need is to change the definition of NEW to the place you put the 4.3 tools. Oh, and you might want to warn your users that for the duration of the tests they shouldn't trust the C compiler, due to possible version skew between /usr/include and /usr/lib and your running system. Dan Hoey Hoey@NRL-AIC.ARPA #! /bin/sh # # 4.3mode: Install enough tools to build 4.3 kernel on 4.2 system. # Do "init" before anything else, "undo" before redoing "init". # Make changes in FILES only with "4.3mode undo"ne # # 4.3mode init -- sets up symbolic links # 4.3mode on -- switches links to 4.3 copies # 4.3mode off -- switches links back to 4.2 copies # 4.3mode undo -- undoes the symbolic links # # Set NEW to where you have put part of your 4.3 directory tree, # including all files in FILES. # NEW="/aic3/4.3utils/" FILES=" lib usr/include sys usr/sys bin/as bin/cc bin/ld \ etc/config usr/lib/gcrt0.o usr/ucb/symorder" NEEDBACK="! -r";RM="rm"; MV="mv" LN="ln -s"; LNP="/"; LNS=".4.2" case "$1" in init) NEEDBACK="-r"; RM="false"; MVT=".4.2";; undo) LN="false"; MVF=".4.2";; on) MV="false"; LNP="${NEW}"; LNS="";; off) MV="false";; *) echo "Usage: $0 init|on|off|undo"; exit 1;; esac for F in ${FILES} do if [ '(' ! -r /${F} ')' -o '(' ! -r ${NEW}${F} ')' -o \ '(' ${NEEDBACK} /${F}.4.2 ')' ] then echo "Problem with /${F}, /${F}.4.2, or ${NEW}${F}" ABORT="exit 1" fi done ${ABORT} for F in ${FILES} do ${RM} /${F} ${MV} /${F}${MVF} /${F}${MVT} ${LN} ${LNP}${F}${LNS} /${F} done --- Date: 15 Sep 1987 12:44:52 EDT (Tue) From: Dan Hoey To: SF-LOVERS Subject: Wizard of the Pigeons (was Fantasy Recs) Cc: (Mary Malmros) From: (Mary Malmros) >_Wizard of the Pigeons_ is about a man known only as Wizard. He >lives in present-day Seattle, and one day (before this story >begins) he discovers that magic really exists.... and we must note, the magic camouflages itself as mundane reality to the ordinary people of Seattle. Another way of reading WotP is that the wizard is schizophrenic and unable to separate his fantasies of magical happenings from the mundane reality in which he lives. In case you are about to dismiss this as the hackneyed ``... but it was all a dream'' plot device, I must beg to differ--Lindholm skillfully makes both readings equally valid, and manages to find a new point of view that is simultaneously realistic and fantastic. It is easy to see why this might not appeal to the earlier poster who complained that ``the hero was a sniviling [sic] wimp''. This is not a typical heroic/swords-and-sorcery/Tolkien-ripoff story, and its characters and plot do not lend themselves to the sort of vicarious escape that such stories generally cater to. But if you want a book that covers new ground in imaginative writing, I would recommend it wholeheartedly. Dan Hoey --- Date: 5 Nov 1987 11:39:10 EST (Thu) From: Dan Hoey To: RISKS Subject: Re: Unix password encryption, again? In Risks 5.48, Russ Housley asks whether Unix's ``modified DES'' is a one-way hash. Let us first pick nits: he was not asking this of the modified DES per se, but of the Unix password mapping algorithm. The DES and modified DES are cryptosystems, while the password mapping is a transformation from the user's password to an ``encrypted'' version. Confusion arises because the password mapping algorithm uses the modi- fied DES as a subroutine, so there is a strong temptation to say that the password has been ``encrypted by the modified DES''. This usage of the term ``encrypt'' is at odds with the common cryptological concept of a transformation by which information is transformed for later decryp- tion by a secret algorithm, or an algorithm that uses a secret key. A second point of terminology concerns the term ``one-way hash'', which has been interpreted in four different ways by me and the three people I have discussed it with in private communication. Russ Housley used the term for the composition of a hash function and a one-way function. (A ``hash'' function is a function that maps a large domain to a smaller range. A ``one-way'' function is a function that is computationally infeasible to invert.) When Matt Bishop (Risks 5.49) answered that the password mapping was not a one-way hash, he was referring to the fact that the password mapping is not a good hash function--the only hashing that goes on is ignoring all but the first eight characters. Peter Neumann interpreted ``one-way'' as referring to a function that maps many-to-one (a reading invited by the term ``hash''). Certainly, it is impossible in a sense to invert a many-to-one function F, since X cannot be determined from F(X). My understanding of a one-way function is one for which it is hard to find any X' for which F(X')=F(X). Such a function can be either many-to-one or one-to-one; I suspect that the password mapping is many-to-one even on eight-character passwords. So, in answer to Russ's question, the password mapping is designed to be a one-way function, but we have no proof that it succeeds. In a prac- tical sense, no one knows whether the password function is hard to invert, though no one has reported an easy way. In a theoretical sense, if P=NP (and perhaps if not) then no one-way functions exist. But even if the password mapping algorithm is a one-way function, it is not very secure. Any one-way function can be broken by trying all of the possible inputs. In his message, Matt illustrated this with an example of 100 users who chose passwords from a 25,000-word dictionary. He described the effect of the modified DES, noting that a search for the passwords would require 2,500,000 password mappings, and concluded that ``the time for such a search should be unacceptably high.'' In a later private communication, he clarified this. The example he gave was intended only to describe the purpose of the modification to DES, and not to claim that 2,500,000 password mappings are a serious barrier to password breaking. You might not realize that if you use the software distributed with Unix, which would require ten days for the task on a SUN 3. But last year, Robert W. Baldwin announced a way of speeding up the password mapping by a factor of 300, using VAX assembler code and some tricks. Using his tricks and some of my own, I wrote a fairly fast password mapping in C, and in fact Matt Bishop has his own fast C implementation. So those 2,500,000 mappings can be undertaken by Matt on his SUN 3 in about eight hours, or by Bob on his VAX 8600 in about forty minutes. And if Rick Gumpertz is still out there with his Cray, carry a laser. The clear and present risk to a Unix system is that the users may have chosen passwords that can be found in a list of words, of words spelled backwards, of first names, of the first letters of famous quotations, of possible license plate numbers, of the six-letter strings, of the eight-digit strings, of the geometrical keyboard patterns, or any other fairly short machine-accessible list. I am horrified at the amount of verbiage it takes to straighten out these simple misunderstandings. If you want to know more about the issues, read Morris and Thompson's ``Password Security: A Case History'' in the November 1979 CACM or your Unix Manual Set (volume 2, or System Manager's Manual, depending on how your set is organized). Please do not court the wrath of the S. P. F. D. H. by further flogging this dead horse, or me. Dan Hoey [This message is the result of extensive trialogue among Dan, Matt Bishop, and PGN. There were enough confusions exhibited by other readers in other messages -- including a bunch which have not been included in RISKS -- that it seemed worthwhile to try to set the record straight. I hope this won't lead to further confusion. PGN] ---