Newsgroups: comp.lang.c From: hoey@ai.etl.army.mil (Dan Hoey) Date: 24 Jan 89 20:21:35 GMT Subject: Re: Programming gems (Bit-reversed counting) Several bit permutations can be achieved by shifting a subset of the bits of an N-bit number O(N) times. Most of the interesting ones are characterized by moving bit I to bit R(I) where R is a function that permutes the bits of its argument and complements some subset of those bits. Common examples of such permutations are reversing the bits, performing a perfect shuffle on the bits, and--approximately--a couple of the permutations used in the DES encryption standard. For reversing the bits of a 32-bit number, the following code suffices. long BitRev(n) register long n;{ n = ((n >> 1) & 0x55555555) | ((n << 1) & 0xaaaaaaaa); n = ((n >> 2) & 0x33333333) | ((n << 2) & 0xcccccccc); n = ((n >> 4) & 0x0f0f0f0f) | ((n << 4) & 0xf0f0f0f0); n = ((n >> 8) & 0x00ff00ff) | ((n << 8) & 0xff00ff00); n = ((n >> 16) & 0x0000ffff) | ((n << 16) & 0xffff0000); return n; } --- Newsgroups: comp.lang.lisp From: hoey@ai.etl.army.mil (Dan Hoey) Date: 17 Mar 89 18:42:19 GMT Subject: Re: Garbage Collecting symbols tt...@opus.cdc.com (Tuyen Tran) writes: >If the only path from the root to a symbol is through the symbol's >package, and the symbol's value/function/plist cells are empty, is it >safe to remove the symbol? It's not ``safe'' in the sense of being invisible to the user, who may be using the package as a way of storing a set of strings that are later to be retrieved with DO-SYMBOLS. That is why all lisps that I know of that GC interned symbols do so under control of a user-selectable switch. Maclisp called its switch something like GCTWA, for ``GC truly worthless atoms''. Back in those days they often called symbols ``atoms.'' >Some LISPs use the existance of a symbol on a package to shadow >inherited symbols of the same name. It seems to me that removing >empty symbols in some cases would affect the behavior of the >system. Your definition of these symbols as having their only path ``through the package'' leaves something to be desired. All definitions I've heard of that deal with TWA's specify that there be no pointer to them other than that implicit in the symbol's accessibility through DO-SYMBOLS or equivalent. Thus the symbol's presence on the PACKAGE-SHADOWING-SYMBOLS list of the package would preserve it from collection. If you explicitly UNINTERN a shadowing symbol, then Common Lisp removes it from the shadowing-symbols list. Thus it is impossible to determine whether the system uses the presence of the symbol or its membership in the shadowing- symbols list to perform shadowing. Dan --- Newsgroups: rec.puzzles, sci.logic From: hoey@ai.etl.army.mil (Dan Hoey) Date: 29 Mar 89 20:47:05 GMT Subject: Re: Weighing 5 balls sap...@eniac.seas.upenn.edu (David Sapery @ U. of Penn) writes: >Given 5 balls, no two of equal weight, can you determine the order, >by weight, in no more than SEVEN weighings on a balance scale? Yes. On a related note, for what N are the minimum number of comparisons for sorting N objects known? Dan --- Newsgroups: rec.puzzles, sci.logic From: hoey@ai.etl.army.mil (Dan Hoey) Date: 30 Mar 89 21:11:33 GMT Subject: Re: Weighing 5 balls I write: >On a related note, for what N are the minimum number of comparisons >for sorting N objects known? I shouldn't have been so glib, for as Stavros Macrakis has pointed out to me, it may actually be easier to sort balls with a balance than with comparisons. The reason is that you can put more than one ball on each side of the balance. Does anyone know of a case where this ability is useful? Dan --- Newsgroups: sci.math From: hoey@ai.etl.army.mil (Dan Hoey) Date: 3 Apr 89 17:51:25 GMT Subject: Re: Interesting numbers stei...@bgsuvax.UUCP (Ray Steiner) writes: >In article 6043 some interesting properties of 1729 were discussed. >...It turns out that 1729 is the second smallest absolute pseudoprime >number(the smallest being 561). Proof may be found on p.217 of >Sierpinski's book ELEMENTARY THEORY OF NUMBERS. Pseudoprime numbers are also called Carmichael numbers. They were discussed on the sci.crypt list in February. Two respondents published lists of Carmichael numbers, giving the first three as 561, 1105, and 1729. I have checked these three numbers, and they are indeed Carmichael numbers. What does Sierpinski's book prove? Dan --- Newsgroups: comp.lang.lisp From: hoey@ai.etl.army.mil (Dan Hoey) Date: 25 Apr 89 18:30:43 GMT Subject: Re: multiple values and conditionals vaug...@puma.cad.mcc.com (Paul Vaughan) writes of a multiple-value OR, specified to return all the values of the first form that returns a non-NIL first value. He motivates it with >(defun lookup (key primary-table secondary-table) > (declare (values value found found-key)) > (mv-or (gethash key primary-table) (gethash key secondary-table))) But in this case we probably want a MV-OR that returns the values of the first form to return a non-NIL *second* value. Furthermore, using a generalized MV-OR requires MULTIPLE-VALUE-LIST, which conses; for combining results of GETHASH we prefer MULTIPLE-VALUE-BIND or MULTIPLE-VALUE-SETQ, which generate no garbage but must be written with knowledge of the number of values to handle. Dan --- Newsgroups: rec.games.board From: hoey@ai.etl.army.mil (Dan Hoey) Date: 1 May 89 22:15:47 GMT Subject: Re: NIM solution k...@naucse.UUCP (Ken Collier) writes: >I am interested in finding either a mathematical solution or a >rule-based solution to the following variation on the game of NIM. >You have a 5x5 rectangle of markers. Each player may remove up to 3 >markers from any row or column, the markers removed do not have to be >adjacent. The players take turns removing markers and the player who >can remove the final marker(s) is the winner. If you accept a rule like ``move to one of these 11,133 positions'', then I have a solution. Generated by computer, of course, and not checked by hand. It claims that the first player must take three markers to win. >It is this last stipulation which makes the program so difficult. >If the winner were the player who did not go last their are >manystrategies for a guaranteed win. That is surprising, since misere play is usually harder to analyze. Please let me know about one of these strategies. Dan --- Newsgroups: sci.math From: hoey@ai.etl.army.mil (Dan Hoey) Date: 24 May 89 18:39:48 GMT Subject: Re: mathematics contest This subject has been done to death so often, I don't suppose it's really worthwhile trying to correct the many misapprehensions, but the mistaken corrections are hard to pass up. hollo...@ttidcb.tti.com (The Polymath) writes: > You're a contestant on Wheel of Fortune (Come on down!). Monty Hall > has just presented you with three doors, behind one of which is a > fabulous prize. You make your choice. Monty opens one of the other > doors. No prize is revealed. He offers you a chance to change your > choice. > Are you better off changing your choice? Does it matter? The > counter-intuitive, but correct, answer is yes, you are more likely > to win if you change your choice. There's a rumor going around that Monty doesn't offer you the chance to change unless you chose the fabulous prize the first time. If that rumor is true, then it never pays to change. Hollombe is assuming that Monty always offers a second choice. >...I didn't believe it either, and found the mathematical proof >confusing, so I simulated the situation in software and ran 1 million >iterations. Gag me with a roulette wheel. Simulations don't prove anything if your model is wrong. >... (and the odds of the key being in the box chosen are 1/6, >assuming it wasn't under one of those turned up). Wrong. Under the assumption that it wasn't under one of the first four (and assuming that the four were chosen at random, and without respect to the accuracy of your choice) the conditional probability is 1/2. It is when you *don't* include the assumption that the probability is 1/6. And in any case, the *odds* are 1:1 or 1:5, respectively. My estimate is that this posting will provoke thirty posts, by people who find proofs confusing, onto sci.dot.for.gods.sake.math. And people wonder why we're in this handbasket and where we're going. Dan Hoey --- Newsgroups: rec.arts.movies From: hoey@ai.etl.army.mil (Dan Hoey) Date: 19 Jun 89 14:56:12 GMT Subject: Re: MIRACLE MILE moria...@tc.fluke.COM (Jeff Meyer) writes: >... the general consensus of the audience was that it would take >pretty strong film reviewer support to get people to get up and go >and see it. As one woman said, "Nuclear armageddon doesn't have a >lot of pull in my neighborhood." The problem is that until you see it, it's hard to believe there can be an upbeat film about the end of the world. My advice is to see it, right now, if it hasn't gone away already. I found that the exercise of looking it up in a paper, dropping everything, and taking the 15 minute drive with my friend to the screening 20 minutes later was an exercise that paid us a thematic bonus. DC area folk, I think it's only left at the Cineplex Wisconsin. Dan Hoey --- Newsgroups: sci.math From: hoey@ai.etl.army.mil (Dan Hoey) Date: 20 Jul 89 20:53:04 GMT Subject: Re: Clicking on Irregular Shapes (and the four color problem) tland...@sequent.UUCP (Troy Landers) writes: (referring to the Four Color Theorem) > This theorem has already been proven ... by a computer at the > University of Illinois. har...@oravax.UUCP (Douglas Harper) writes: >...The theorem was _not_ proved by a computer. Dr. Kenneth Appel >and Dr. Wolfgang Haken (both of the mathematics department of the >University of Illinois at Urbana-Champaign) proved it, using a >computer as a tool in developing their proof. To say that Appel and Haken proved it is also questionable, given that some steps of the proof have been performed by the computer. In fact, so many steps were performed by the computer that neither Appel nor Haken nor any other human has read all the steps. What Appel and Haken proved was that the computer, correctly operating with their program, should not declare the problem solved unless the four-color theorem was true. They then observed that the computer declared the problem solved. There is still no real consensus among mathematicians on whether this amounts to a proof of the four-color theorem, though it is certainly very strong evidence for the theorem being true. Dan Hoey --- Newsgroups: sci.math From: hoey@ai.etl.army.mil (Dan Hoey) Date: 24 Jul 89 16:25:19 GMT Subject: Re: Clicking on Irregular Shapes (and the four color problem) jk...@andrew.cmu.edu (Joe Keane) writes: >hoey@ai.etl.army.mil (Dan Hoey) rites: >>There is still no real consensus among mathematicians on whether >>this amounts to a proof of the four-color theorem, though it is >>certainly very strong evidence for the theorem being true. >I think any proof is just `strong evidence for the theorem being true'. I must disagree. Not that proofs can contain errors--no one denies that they can. But a proof is more than ``evidence'', it is evidence that is understandable, and which has been understood, and which can be checked for correctness by being understood by other mathematicians. At least, this is the understanding of ``proof'' that has been held among mathematicians before it became possible to manipulate the objects of mathematics without understanding them. This is my understanding of a viewpoint that was hotly debated when Appel and Haken's results first came out. I have not followed the course of the debate over the years, but I have heard that the furor is dying down not so much by conversion, but by attrition of the more conservative viewpoints. I did not, and will not, participate in that debate. It is a topic for philosophers of mathematics, which I am not. I am presenting this only to sketch a distinct opinion. Dan --- Newsgroups: comp.protocols.tcp-ip From: hoey@aic.nrl.navy.mil (Dan Hoey) Date: 25 Jul 89 18:33:15 GMT Subject: Re: trace route to OZ (indeed!) pvo3...@OCE.ORST.EDU (Paul O'Neill) writes: >20 La_Jolla,CA.NSS.NSF.NET (129.140.6.14) 1240 ms * 1370 ms >21 La_Jolla,CA.NSS.NSF.NET (129.140.6.11) 1390 ms 1320 ms 1460 ms Say what you like about the bad old host table days, but at least we didn't get any commas in the host names back then. I can't even find out the mail address for whatever zone 14.6.140.129.IN-ADDR.ARPA is in, but I can hope that the postmasters at the authoritative servers may be able to figure it out. Considering what would happen if this name got into a mail header, I just wonder if it's possible to get CRLFs into the canonical name, leading to wholesale rewriting of mail headers through host name canonicalization. But surely that's impossible.... Dan --- Newsgroups: rec.arts.sf-lovers From: hoey@ai.etl.army.mil (Dan Hoey) Date: 25 Jul 89 20:24:58 GMT Subject: Re: As long as L Ron Hubbard is being discussed.. t...@hoptoad.UUCP (Tim Maroney) writes: >What I want to know is, how does bridge expect us to take seriously >their claims that they're divorced from the Church of Scientology as >long as so much of Bridge's budget goes to hawking this Dianeticist >book? It's my understanding that Dianetics is independent of the Chur-Sci. Like meditation, some relatively sane people find it useful in dealing with whatever problems. Chur-Sci seems to be a cult that sprung up around Dianetics and Elron, that is rumored to include brainwashing, economic parasitism, authoritarian hierarchy, and the Xemu mythology. It looks like Dianetics:Scientology::Meditation:Guru Mahesh Yogi::Christ:Xian Churches from where I'm sitting. But then it's all oatmeal to me, and your mileage may vary. I hope nobody's too offended if I stepped in their dogma. As for where Bridge fits into the equation, I can't help you a whole lot. It's just that publishing and promoting Dianetics doesn't automatically make them Churchers, I don't think. Dan ``I Trekkies'' --- Newsgroups: comp.lang.lisp From: hoey@ai.etl.army.mil (Dan Hoey) Date: 4 Aug 89 21:01:44 GMT Subject: Re: what does "destructively sorted" mean in KCL? shiff...@sun.UUCP (Hank Shiffman) writes: >>>foo >>(1 3 9 4 -2 0 9) >>>(sort foo #'>) >>(9 9 4 3 1 0 -2) >>>foo >>(1 0 -2) ... >Keep in mind that since SORT is a function, (sort foo #'>) causes sort >to be handled the *value of FOO*, not the symbol itself. So SORT (as >it's currently defined) couldn't put sorted list back into FOO even if >it wanted to. Actually, you can make this work by using the cons cell you are given as the head of the list. For example, (defun my-sort (original &rest sortargs) (let ((sorted (apply #'sort original sortargs))) (unless (eq original sorted) (rotatef (car sorted) (car original)) (setf (cdr (do ((s sorted (cdr s))) ((eq (cdr s) original) s))) sorted) (rotatef (cdr original) (cdr sorted)))) original) doesn't CONS but does give its argument the value of the sorted list. This, however, requires that SORT return a list of which its argument is a tail, which is not explicitly required by CLtL. Dan --- Newsgroups: sci.physics From: hoey@ai.etl.army.mil (Dan Hoey) Date: 7 Aug 89 22:13:35 GMT Subject: Special relativity and FTL and Time travel m...@v7fs1.UUCP (Mike Van Pelt) writes, ``I keep hearing [that FTL travel (or communication) implies travel (or communication) into the past].... However, I'm not convinced. Maybe I'm missing some vital detail, but the explanations seem to boil down to [a variation on the paradox of the twins]....'' No, the problem is not due to, or even particularly related to, the twins' paradox. The amount of time traveled into the past is not equal to the time lost by the younger twin, or anything like that. The problem is that by special relativity, travel/communication that is FTL in one inertial frame must be into the past in some other frame. By use of such travel/communication in two frames, we can construct travel/communication that is into the past without moving an inconvenient distance away. For an explicit construction of this, I recommend any reasonable published treatment of Lorentz transformations. If you are allergic to published works, these things appear on the network with surprising regularity (e.g., Eric Smith, <2...@uwovax.uwo.ca>). He continues, ``By the way, for this one you need general relativity, as one of the reference frames is under acceleration....'' The idea that special relativity is needed for the twins' paradox or the FTL => into the past construction has also appeared on the net repeatedly, but the idea is false. The twins' paradox appears in a version that involves acceleration only at the beginning and end of long inertial trips. If we postulate that the acceleration ages the twin (so as to vitiate the difference in the rate of aging) we need only increase the length of the trip enough to overcome the aging due to acceleration. I assume for this argument that the amount of aging due to acceleration is independent of the place and time that the acceleration takes place. When we convert FTL travel/communication into travel/communication into the past we must transfer the body/information between points in the same reference frame, i.e. not accelerated with respect to each other. But if we have an FTL effect that arrives in an accelerated frame, and we postulate that it takes time to decelerate/transmit into the reference frame, then the time can be made up by making the trip longer, so as to go further into the past, to make up for the time lost in changing frames. I assume that the (subluminal) velocity at the end of the trip is independent of the length of the trip, and the time lost in changing frames is independent of the time and place at which the change is performed. As for the request from mak...@tukki.jyu.fi (Otto J. Makela) that the effect be explained ``in simple but still GR-type maths,'' the general theory of relativity, while perhaps not worked out completely in all of its details, presupposes the the special theory: SR is GR restricted to inertial frames. So these SR arguments are GR, too. Dan Hoey --- Newsgroups: rec.arts.sf-lovers Date: 7 Aug 89 23:24:52 GMT From: hoey@ai.etl.army.mil (Dan Hoey) To: SF-LOVERS Subject: Corkage at Noreascon three n...@scifi.UUCP (Nicholas J. Simicich) writes: >For some reason, the Noreascon Committee failed to negotiate corkage >into the hotel contract at the Sheraton. I never heard any commitment from N3 that they could or would convince the Sheraton to waive corkage. Nor did I hear any such commitment from the Boston in '89 bid committee. Rather, I have heard that Boston hotels are notable in their immovability on the corkage issue. >I see three possibilities: one is that the rules, as given, apply >only to "open" parties, and that, strictly speaking, @ is a closed >party. I understand that corkage applies to any party in the Sheraton that the Sheraton finds out about. >... party attendees might just think about bringing a six pack or >some soft drinks rather than the usual contributions. Again, these would still be in violation of the hotel's rules. I have no idea what the reaction of the hotel would be if thousands of fans started carrying six packs around. >Finally, we might just smuggle all of the party supplies in. A time-honored solution. I thought everyone did that. >... they should have given up and moved the con a long time ago. I think this is wishful thinking. There were a lot of problems resulting from the Sheraton's 1987 attempt to renege on N3, but moving the convention would probably have resulted in larger dislocations. I wish they had been able to negotiate corkage, but I'm not surprised they weren't. Dan Hoey --- Newsgroups: sci.math From: hoey@ai.etl.army.mil (Dan Hoey) Date: 11 Aug 89 18:30:40 GMT Subject: Re: proof by contradiction Avoidance of proof by contradiction is one of the hallmarks of Constructivist mathematics, a logical discipline associated with L. E. J. Brouwer. This school accepts only those mathematical objects that can be constructed in some finite way from primitive objects. The school is not widely accepted in its strict form, as an epistemological gauge of what is proven and what isn't. However, I have heard of some work that attempts to convert a constructive proof into a computer program for calculating the constructed object. If nothing else, a proof that uses contradiction bars the use of such tools. I'm sorry to be so vague on the subject, but all I know comes from a talk I heard eight years ago. I think the research was going on at Cornell or Princeton, in case that helps. Dan Hoey --- Newsgroups: comp.dcom.lans From: hoey@ai.etl.army.mil (Dan Hoey) Date: 18 Sep 89 16:05:32 GMT Subject: Re: high speed networking between buildings e...@ursa-major.spdcc.COM (Steve Elias) writes: > consider using broadband coax as well.... But of course, in the words of Charles Hedrick, ``We do not recommend running copper of any kind between buildings. You can sometimes get away with it, but it's asking for trouble.'' Dan --- Newsgroups: sci.math From: hoey@ai.etl.army.mil (Dan Hoey) Date: 3 Oct 89 19:37:46 GMT Subject: Re: A nice problem (solved and extended) [ I posted a version of this proof a week ago, but I understand it never made it to the net. In case some of you saw the first version, this one has some new, nifty stuff at the end. ] Michael Pak asks (approximately): Let a,b be positive integers, and let K(a,b)=(a^2+b^2)/(ab+1). Prove that if K(a,b) is an integer, then K(a,b) is the square of an integer. Proof: If a=b, then K(a,b)=K(a,a)=(2a^2)/(a^2+1) = 2 - 2/(a^2+1), so a^2+1 <= 2. This holds in case a=1, in which case K(a,b)=K(1,1)=1, the square of 1. In the following we assume a > b, and prove by induction on a. For the base case, if a=1, then the theorem is vacuously true, since there is no positive integer b < a. Inductively assume the theorem holds for K(x,y) whenever 0= 0, II. kb - a < b, and III. k = K(b,kb-a) That will complete the induction, since then we have either reduced the problem to an assumed case K(b,kb-a), or we have kb-a=0, in which case k=K(b,0)=a^2, a square. In the following, we will use the identity kb-a = (b^3-a)/(ab+1), which arises from the definition of k. Step I. Since a and b are positive, 1 <= b, so 1 < b^3/a + 1/a + b (adding b^3/a+1/a on the right), -1/a - b < b^3/a - 1 (subtracting 1/a + b + 1 from both sides), -1 < (b^3 - a)/(ab + 1) (multiplying by a/(ab+1)), = kb - a Since kb-a is an integer, this means that kb-a >= 0. Step II. b < a, so b < a + a/b^2 + 1/b (adding a/b^2 + 1/b on the right), so b - a/b^2 < a + 1/b (subtracting a/b^2 from both sides), so (b^3-a)/(ab+1) < (ab^2+b)/(ab+1) (multiplying by b^2/(ab+1)), so kb - a < b Step III. K(b,kb-a) = (b^2 + (kb-a)^2) / (b(kb-a) + 1) = (b^2(ab+1)^2 + (b^3-a)^2) / ((b(b^3-a) + (ab+1))(ab+1)) = (a^2b^4 + 2ab^3 + b^2 + b^6 - 2ab^3 +a^2) / ((b^4-ab+ab+1)(ab+1)) = (a^2b^4 + b^6 + b^2 + a^2)/((b^4+1)(ab+1)) = (a^2 + b^2)/(ab+1). QED. This also give us explicit recurrences for the values of (a,b) for which K(a,b) is an integer: Let a[i,0]=0, a[i,1]=i, a[i,j+1] = i^2 a[i,j] - a[i,j-1]. then K(a[i,j+1],a[i,j]) = K(a[i,j],a[i,j+1]) = i^2 are all the integer values of K on nonnegative integers. It seems to me that if we let the polynomial p[j](x) = sum[t=1 to ceiling(j/2)] C(j-t,t-1) (-1)^(t+1) x^(2j+3-4t), then a[i,j]=p[j](i). (These are essentially the same polynomials that Gregory Rawlins has independently discovered). I wouldn't be surprised if these polynomials have a name or a simpler form, but I don't know it. If we relax the constraint that a and b must be positive, we see immediately that K(-a,-b)=K(a,b), so the only new values we will find are cases of the form K(a,-b) = K(-a,b) for positive a and b. Except for (1,-1), where K(a,b) is undefined, we have K(a,-b)<0. A modification of the previous proof yields: If K(a,-b)=-k, an integer, for a>b>0, then either b=1 and a=2 or 3, or 0 <= kb - a < b and K(b,-(kb-a)) = -k. This implies that K(a,-b)=-5, and (a,b) are adjacent terms in the series q[0]=1, q[1]=2, q[i+1]=5q[i]-q[i-1]. The q[i]'s form the double-ended sequence ... 7369 1538 321 67 14 3 1 2 9 43 206 987 4729 .... The negative case is disappointingly sparse, but we might want to consider extending this to complex numbers. Instead of the integers, we can use another ring, such as the Gaussian integers G=Z+iZ. Certainly for z in G, K(p[j](z),p[j+1](z)) will be in G. We can find some other solutions from the identities K(ia,-ib)=-K(a,b), K(a,ia)=0, and K(a*,b*)=K(a,b)* (using * for the complex conjugate). Then when we find a pair, we can extend it to a sequence with K(a,b)=K(b,kb-a) as above. The following cases are the only ones I've seen that don't arise trivially from the above arguments, though I imagine there are more, and these may be examples from infinite classes. k Series 2+i: ... 27-37i -1-22i -7-8i -5-i -2+i i 1+i 1+2i -1+4i -7+5i -18-i ... 4: ... -15+26i -4+7i -1+2i i 1+2i 4+7i 15+26i 56+97i ... 1: 2i 2+i 2-i -2i -2-i -2+i 2i 2+i (cyclic) 1: 8i 7+4i 7-4i -8i -7-4i -7+4i 8i 7+4i (cyclic) Of course we could look in the algebraic integers (roots of monic Z[x]), or in subrings of finite fields. But I won't, just now. Dan --- Newsgroups: comp.protocols.tcp-ip.domains From: hoey@ai.etl.army.mil (Dan Hoey) Date: 19 Oct 89 16:52:16 GMT Subject: Re: Pilot Project: Hosts Table To Be Available Over Internet berns...@hpuxa.ircc.ohio-state.edu (Dan Bernstein) writes: > As a pilot project, we are going to make available to the Internet > a hosts table. > Sites with reliable name server access should not need this table. Actually, name servers don't help much with some questions that a host table is good for. Like ``What is the NIC's name?'' and ``There's some host called QUABBIN something something and what is the whole name?''. I wonder if the new host table will help us answer the question ``Somebody's name server is putting out a host name with a comma (,) in it'' that was the subject of a few notes earlier. Come to think of it, I'd like to know if there are any wierd characters floating around the DNS. Such questions could be easier asked of some sort of server that searches a host table, rather than giving you the whole table to search. Also, that server could incrementally maintain its database. But I don't see anyone RFCing such a service. Dan --- Newsgroups: comp.lang.lisp From: hoey@ai.etl.army.mil (Dan Hoey) Date: 29 Nov 89 20:50:30 GMT Subject: Re: Are "destructive" functions really destructive? moore%cdr.utah....@cs.utah.edu (Tim Moore) writes: >If delete's behavior really bothers you, you can construct a deletef >macro like: >(defmacro deletef (item place) > `(setf ,place (delete ,item ,place))) >Obviously this isn't completely equivalent to delete; caveat emptor Perhaps something more like (defmacro deletef (item place &rest delete-options &aux (itemv (gensym))) (multiple-value-bind (vars vals store store-form access-form) (get-setf-method place) `(let* ((,itemv ,item) ,.(mapcar #'list vars vals) (,(car store) (delete ,itemv ,access-form ,@delete-options))) ,store-form ,(car store)))) Dan --- Newsgroups: comp.lang.lisp From: hoey@ai.etl.army.mil (Dan Hoey) Date: 30 Nov 89 13:53:36 GMT Subject: Re: NCONC & Functions r...@KRONOS.ADS.COM (Bob Riemenschneider) writes: >One last note: a lot of Lispers think of this behavior [modifying quoted >structure in a function definition] as a feature rather >than a bug. Consider the following program .... I used to think so, too, but the designers of Common Lisp have decided that modifying quoted structure is an error. The rationale is to allow two features that they thought outweighed the utility of this technique: 1. The compiler is free to collapse all EQUAL quoted structures into one, saving some amount of space. I do not know if this is implemented by any compiler. 2. The system is free to put quoted structure into write-protected memory, and thus signal an error if the user accidentally modifies the structure. I am somewhat uncomfortable with this, since it also prevents the user from purposefully modifying the structure, but since some lisp machine manufacturers have implemented this feature, I don't think it's worth debating. The sort of work-around that I believe is approved is (1) for now, use a special variable, and (2) when enough lisps support it, go to DEFUNs with a lexical environment, such as (borrowing Bob's code) + (let ((aux (list 1 1))) (defun fibon (n) (if (or (eq n 0) (eq n 1)) 1 ! (fibonaux n aux)))) Dan --- Newsgroups: comp.sys.sun From: hoey@aic.nrl.navy.mil (Dan Hoey) Date: 20 Dec 89 19:56:24 GMT Subject: .getwd and .getwdCNNNNN We at last have a way to prevent users from stepping on each other's temporary files in 4.3BSD (and therefore SunOS 4.0.3). I do a ``chmod +t /tmp'' so that /tmp/* can only be deleted by owner or superuser. But we have been seeing problems with /tmp filling up with thousands of files named .getwdCNNNNN, where C is a letter, either ``a'' or ``b'', and NNNNN is a process ID. These are apparently related to /tmp/.getwd, which ``man 3 getwd'' says ``exists for the sole purpose of the getwd() library routine; no other software should depend on its existence or contents.'' It seems like these files tend to get created when two or more users of a machine are calling system(3) lots of times. Is there a good way to cut down on the creation of these files? I am really getting tired of having to fix people's Suns when their filesystem becomes full. Could someone at least explain to me the purpose and use of these files? Under what circumstances are they created and deleted? Dan Hoey Hoey@AIC.NRL.NAVY.MIL --- Newsgroups: rec.puzzles From: hoey@ai.etl.army.mil (Dan Hoey) Date: 20 Dec 89 20:01:01 GMT Subject: Re: Old chestnut (spoiler) a...@myrias.com (Alfred Nykolyn) writes: >Find 3 points with integer coordinates in the XY plane that >form an equilateral triangle. There are no such three points. For if there were, we could translate the figure so that one of the points is at the origin. (We could *not* necessarily rotate the figure so that a second point is on the X-axis, as Randall Rathbun suggested. Rotation could move a point from integer coordinates to non-integer coordinates.) Also, if the four nonzero coordinates have a common factor, we may divide through by their GCD to form a minimal equilateral triangle. Let the endpoints be O=(0,0), A=(Xa,Ya), and B=(Xb,Yb). To have an equilateral triangle we must have |A|^2 = |B|^2 = |A-B|^2. Now |A|^2 mod 4 is 0, 1, or 2 according as Xa and Ya are both even, mixed, or both odd. Since |B|^2 is equal, Xb and Yb must have the same population of even coordinates. Similarly, Xa-Xb and Ya-Yb must also have the same population of even coordinates. If Xa and Ya are both odd then Xb and Yb must both be odd, so Xa-Xb and Ya-Yb will both be even, so the triangle is not equilateral. If Xa and Ya have mixed parity, then Xb and Yb must have mixed parity. This will make Xa-Xb and Ya-Yb both even (if Xa and Xb have the same parity) or both odd (if not). In either case the triangle is not equilateral. If Xa and Ya are both even, then Xb and Yb must both be even, contradicting the minimality of the triangle. Therefore no such triangle exists. Dan --- Newsgroups: sci.math, comp.theory From: hoey@ai.etl.army.mil (Dan Hoey) Date: 21 Dec 89 01:08:40 GMT Subject: Re: Rubik's Cube Problem From chr...@garfield.MUN.EDU (Chris Paulse): > If I had a solved Rubik's cube, and the colors on each face were > just stickers on the black plastic surface, if I exchanged some > of the stickers, would the cube still be solvable in the normal way? The probability, given an arrangement of the 54 stickers chosen uniformly from the 54! possible permutations, is 6 8 12 9! 6! 3 8! 2 12! 40,122,452,017,152 -------------------- = --------------------------------------- 54! 12 130,253,249,618,151,492,335,575,683,325 -16 = approx 3.08 10 The way this works is that there are 9!^6 6! ways of putting the stickers on so that the cube is already solved, and 3^8 8! 2^12 12!/12 - 1 unsolved cubes corresponding to each solved cube. Previous posters answering ``1/12'' are responding to the question, ``if I put the twelve edge pieces and eight corner pieces of a Rubik's cube together at random, would it then be solvable in the normal way? Dan --- Newsgroups: rec.puzzles From: hoey@ai.etl.army.mil (Dan Hoey) Date: 21 Dec 89 20:16:08 GMT Subject: Re: Old chestnut t...@lambda.UUCP (Tony Warnock) writes: > Impossibility of an equilateral triangle with integer vertices: > Without loss of generality, one vertex may be taken to be (0,0). [ He shows that the angle at that vertex has a rational tangent. ] > This argument also shows that any triangle with vertices at integral > coordinates must have at least one angle with a rational tangent. I hesitate to amend an article that hits the nail so squarely on the head, but: The argument in fact shows that in any such triangle all three angles must have rational tangents. In fact, this yields a condition for being able to place a triangle's vertices on a grid (up to similarity, i.e., by translation, rotation, and magnification). A triangle with two angles whose tangents are a/c and b/d may be constructed with vertices at (0,0), (ad-bc,0), and (ad,cd). Thus Randall Rathbun's initial assumption that one side of the triangle could be placed on the x-axis turns out to be true. Still open: Does anyone know the condition for placing a triangle on the ``lattice'' points of a triangular grid? Can we characterize integer-vertex triangles up to congruence, rather than up to similarity? In other words, what sizes of a triangle can be placed on a grid? Dan ---