Letters to the editor, April 2010

This a traditional letter column. You are encouraged to write a letter of comment on anything that you find worthy of comment. It will (may) be published in this column along with my reply. As editor I reserve the right to delete material; however I will not alter the undeleted material. E-mail to me that solely references the contents of this site will be assumed to be publishable mail. All other e-mail is assumed to be private. And, of course, anything marked not for publication is not for publication. Oh yes, letters of appreciation for the scholarly resources provided by this site will be handled very discreetly. This page contains the correspondence for April 2010.

Index of contributors

• Jaap Lagerweij
• MeowMeow, Tiger Eyes, Big Kitty, Puff Daddy
• John Caplinger
• Ruth Seymour
• Anthony R. Lewis, PhD, FN
• Bron Campbell Nelson
• Eric Shackle
• Ashley Kjonaas
• Suford
• gallois evariste
• Wendi Rinehart

Other Correspondence Pages

• Master page for correspondence
  
• January 2010 correspondence
  
• February 2010 correspondence
  
• March 2010 correspondence
  

From: Jaap Lagerweij
Date: 9 March 2010
Subj: My Earlier Letter Was Returned Undelivered

Attention,

My name is Jaap Lagerweij, I am notifying you again as my earlier letter was returned undelivered. I hereby attempt to reach you again by this same email address. We are conducting a standard process investigation on behalf of “HEMA and Praxis Group”, the International banking conglomerate.

This investigation involves a partner who shares the same surname with you and also the circumstances surrounding investments made by this client at a financial institution. He died in testate and nominated no successor in title over the investments made with this financial institution. I would respectfully request that you keep the contents of this mail private and respect the integrity of the information you come by as a result of this mail, which will be beneficial to both parties concerned, contact me urgently through email for more detail information.

I don’t believe that your partner and I are related. You say that he died in testate whereas I live in sd state. It is quite obvious to me that you are proposing an immoral and illegal transaction. If you immediately forward 10,000 euros to me in small bills I will say nothing about your actions. Otherwise I will be compelled to expose your criminal defalcations by publishing your email on my web site.

From: MeowMeow, Tiger Eyes, Big Kitty, Puff Daddy
Date: 24 March 2010
Subj: Hey Tommy!

Tommy ~ Welcome to the Harter Gravy Train! Let us tell you, you’ve picked a good one. Suckers – all of ’em in this family. Course, us California Cats figured this out a LONGGGGG time ago. Hey, we even know how to drink out of water dishes and daintily immerse our heads in our food. Come out and visit some time – we’ll make sure you have a good time. Cheers,
MeowMeow, Tiger Eyes, Big Kitty, Puff Daddy

Water dishes are for effete blue state cats. I am a cowboy cat! Even though I’m a cowboy cat I can do with plenty of lap time. You sure are right about the Harter Gravy Train. I’m gonna wear that food dish out!

– Tommy

From: John Caplinger
Date: 1 April 2010
Subj: The Cold Equations

Dear Mr. Harter,

Please allow me to convey my appreciation for your considered critical study of “The Cold Equations”. I was ruminating about sending a friend a quick summary of the story, she is a few weeks away from getting into a bit of a pickle, is marginally interested in science fiction, and might profit from considering the point that sometimes you can get yourself into situations that have no good outcome. In order to refresh my memory, I checked the wiki article and found reference to your writing.

I don’t know if I will follow through with the email to my friend, except perhaps to point her at your critique. I am, however, personally grateful in that I have been sharpening my own writing skills lately, with an eye to putting some of my own ideas out there. I found your critique extremely illuminating.

I’ve been reading SF since the Nineteen Fifties. I think one thing that could be brought to the common zeitgeist is the idea that society changes. We are so used to seeing every era recast in our own current set of standards that we cannot entertain the idea that, at one time, a single sentence written would evoke a completely different mindset in a reader than that of a reader from another time. However, I keep finding bits and bytes here and there that challenge my simplistic assumptions, and that force me to consider what it is I actually believe I have to say. I was shocked (to the core) to find a writing on the net by Michael Moorcock, for instance, that challenges the assumptions behind writings by Asimov, Heinlein, et al basically calling them fascists, superficially, but more importantly actually challenging their world, the beliefs they held, that Mr. Moorcock does not share. First I was appalled, then I was thoughtful, and then I started trying to figure out how to write something better than either group could&

That, and other explorations, led me to the perfect mindset to read your article. I think I understand, both how the writer and John W. Campbell could have lived in a mindset where such thoughts as culpability on the part of the administration were simply unthinkable, or irrelevant. On the other hand (as I think you imply) there was a deeper setting in this story that consideration would bring to light exactly as you have. Whether Campbell and Godwin went that far in their thinking does not seem either determinable or a necessary datum. And, finally, on the gripping hand such depth is exactly what I want to embed in my stories, while still writing something entertaining enough to enchant folks away from their beer money.

So, thank you for the article, and I hope to have time in the future to return many times to your web matrix and immerse myself.

John Caplinger

http://www.figure5.com/~john/

Thank you for an interesting letter. Moorcock was very good at needling the Gods of the Golden Age. I fondly recall a Boskone panel in which Lester Del Rey and Isaac Asimov fulminated about an English New Wave panel that featured some of Moorcock’s gibes. On the other hand Moorcock was skewered nicely in Sharon McCrumb’s “Bimbos of the death sun”. Thus was the biter bitten by a better bite.

I would be wary of assuming the Campbell lived in a mindset that where such thoughts… He was of a crankish temperament, prone to crochets. That said, he was fond of finding his way onto the opposite side of almost any fence. I recall an ASF story in which an alien advocate for a species being mistreated by the humans came to Earth to teach humans a better morality. He is surprised to discover that all of the individual humans he meets are good people who are moral by his standards. Eventually he is imprisoned as an enemy of the state. It is thus he learns that governments are intrinsically immoral and self serving regardless of the morality of the people in it.

The issue is simple. Individuals have limits; organizations do not.

The recognition that words and language have different meanings across time is a commonplace of literary and social theory – now. I’m not sure that this always was true. In our times a Barbara Tuchman could write “A Distant Mirror” in which people of the fourteenth century think differently than we do. In our times Jorge Luis Borges could think of a Pierre Menard rewriting Don Quixote with the same words but with modern meanings. These days each generation rewrites history, knowing that it has been rewritten countless times before. Was it always so, or was there a time when history was simply history, an invariant account of the events of the past needing no reinterpretation.

And can one concern one’s self with such thoughts and still tell a good story?

I will be happy to read your brilliant essay, “A critical comparison of Cordwainer Smith and Isaac Asimov”, if you ever choose to write it.

From: Ruth Seymour
Date: 6 March 2010
Subj: Petra

Thank you for posting this lovely poem. I am visiting Petra next week.
Ruth

Thanks for writing. I envy you for having the chance to visit Petra.

From: Anthony R. Lewis, PhD, FN
Date: 20 March 2010
Subj: Tommy

Finally, your virtue has been rewarded. Someone has been observing your good deeds for the elderly. Enjoy.

How fortunate for me.

Life keeps changing. This may be a good thing.

From: Bron Campbell Nelson
Date: 16 March 2010
Subj: Sorting of “almost sorted” arrays

I’m hoping to find the time to get back to this soon. In thinking about the optimization of the inner loop of a merge sort (e.g. as found in http://richardhartersworld.com/cri/2009/optmerge.html ), I found I was dissatisfied with the need for the loop nest. After some thought, I hit upon the idea in the code below. Let me emphasize that I have not tested (or even compiled!) the code. I was interested in seeing if you agreed that this idea should work, or if there is some obvious hole I’m missing.

//////////////////////////////////////////////////////////////////////////
// This routine requires that C be distinct from A and/or B,
// and  (abs(lenA-lenB) <= 1).
//
// A occurs before B in the original order, so in case of ties,
// elements of A come before elements of B.
void
mergeStep(
  INFO A[], int lenA,
  INFO B[], int lenB,
  INFO C[])
{
  // "t" for "top"; "b" for "bottom"
  int tA = 0, tB = 0, tC = 0;
  int bA = lenA - 1, bB = lenB - 1, bC = lenC - 1;
  int minLen, count;
  ////////////////////////////////////////////////////////////////////////
  // The standard formulation of this would merge A and B into C until
  // one of A or B was exhausted, then copy the remainder.  However, this
  // necessitates checking for the end condition for both arrays at each
  // element.  Since this is the innermost loop of the sort, we would
  // like to reduce these checks.  So here we use a slightly more complex
  // scheme:
  //
  //  (1) Set "minLen" to the minimum of lenA and lenB
  //
  //  (2) Merge minLen elements into C using a standard "forward" merge.
  //      By "forward" we mean the standard method of comparing the
  //      elements at the front of the arrays, and copying one of them
  //      into C.   Since we only merge minLen elements, we cannot
  //      overrun either array, so we don't need to check.
  //
  //  (2) Merge minLen elements into C using a "backwards" merge.
  //      By "backwards" we mean applying the *inverse* comparison to
  //      the elements at the *back* of the arrays, and copying one of
  //      them into the *bottom* of C.  Since we only merge minLen
  //      elements, we cannot overrun either array.
  //
  // The important point here is that since we are moving elements into
  // C in sort order, the elements moved by step (2) into the top of C
  // are necessarilly disjoint from the elements moved by step (3) into
  // the bottom of C.  So we not only don't overrun the arrays, we also
  // do not move duplicate elements.
  //
  //  (3) This leaves us with abs(lenA - lenB) elements that might be
  //      anywhere and that need careful checking.  But in a mergesort
  //      routine, we can arrange for abs(lenA - lenB) to be either zero
  //      or one, so the cost of doing this is tiny.
  //
  // The drawback to this scheme is that it requires that the array C
  // be distinct from either A or B.  In some implementations of merging,
  // the array B would be in the bottom part of C, and that does not work
  // with the method given above.
  ////////////////////////////////////////////////////////////////////////
  minLen = (lenA < lenB) ? lenA : lenB;
  // Forward merge minLen elements into the top of C
  for (count = minLen;  count > 0;  --count) {
    C[tC++] = IS_BEFORE(B[tB], A[tA])  ?  B[tB++]  :  A[tA++] ;
  }
  // Backwards merge minLen elements into the bottom of C
  for (count = minLen;  count > 0;  --count) {
    C[bC--] = IS_BEFORE(B[bB], A[bA])  ?  A[bA--]  :  B[bB--] ;
  }
  // Deal with the last element (if any)
       if (tA == bA) C[tC++] = A[tA++];
  else if (tB == bB) C[tC++] = B[tB++];
  // Check we didn't screwup
  assert((tA == bA+1) && (tB == bB+1));
}

My apologies for not getting back to you sooner. I don’t know whether your scheme would run faster or not, but it is clever. Here is a quick analysis. Here is a code fragment from the optimization page:

        for (index = m;index--;) {
            while (*y < *x) *z++ = *y++;
            *z++ = *x++;
        }

where m is the length of the chosen segment. Here is a translation into goto based code:

      i = m
      goto L3                   // Executed once
L1:   if (*x <= *y) goto L2     // Executed 2*m-r times
      *z++ = *y++               // Executed m-r times
      goto L1                   // Executed m-r times
L2:   *z++ = *x++               // Executed m times
L3:   if (i-- > 0) goto L1      // Executed m times

where r is the length of the unmerged part of the other segment. The operations performed are:

      compares:        2*m-r
      test against 0:  m
      transfers:       2*m+1
      assignments:     2*m

Now we do the same for one of the two loops in your new code:

      i = m
      goto L3                   // Executed once
L1:   if (*x > *y) goto L2      // Executed m times
      *z++ = *x++               // Executed m/2 times
      if (i-- > 0) goto L1      // Executed m/2 times
      goto L4                   // Executed once
L2:   *z++ = *y++               // Executed m/2 times
L3:   if (i-- > 0) goto L1      // Executed m/2 times
L4:

There are two loops in the new code so we have to double our counts of operations. We get:

      compares:         2*m
      tests against 0:  2*m
      transfers:        3*m+1
      assignments:      2*m

In short, we have m extra tests against 0 and m extra transfers because there are two loops rather than one. However we can use one loop and get essentially the same counts. The upshot is that the performance of each depends on compiler magic, i.e., things like performing both branches of a conditional in parallel.

… continued on next rock

Richard –
Thanks for the insightful analysis of the algorithm. Since my last note I in fact did implement several different variations of this stuff, and the version from your web page proved to be the best. I still think mine looks prettier however :-).

Oh yes, it it prettier. Something so elegant deserves a better fate. If you don’t mind I will add some (attributed) material about it to the web page.

I suppose it comes in the category of final polishing. Still, it is simple.

1) I found that using memcpy rather than a copy loop was actually ever-so-slightly slower when the input was random. No doubt this is because with random input, the tail is likely to be very short, and not pay back the procedure call overhead. However, in the production version I intend to keep the memcpy since even worst case the difference is very small, and with longer tails I suspect the potential gain is worth it. [Admittedly, suspicion is not a substitute for measurement.]

Now we are getting into territory where platform and implementation are the determining factors. If the machine has a block copy instruction and if the implementation uses it in memcpy, then using memcpy will be much faster than a copy loop. A good optimizer will check on the size and will inline optimized copy code. I suspect the quality of implementations varies a lot.

That makes sense. I haven’t taken the time to work out the code but I am confident that a variant of that trick can be used in all cases. It’s probably worthwhile since it eliminates copying and checking for copying. I will think about it.

You would think so. However C in general doesn’t deal well with subscripted arrays; I have the impression that the cases where X[i++] can be optimized are specialized.

Can’t you explain to them that doing fun stuff is part of the job description?

I was hoping to get at least parts of this withdrawn due to “prior art” based on http://richardhartersworld.com/cri/2004/ksort.html#heap i.e. your heap version of k-sorting, but I haven’t yet figured out how to reach the patent examiner to communicate with.

[snip code] Return to index of contributors

From: Eric Shackle
Date: 4 April 2010
Subj: Dear Ma and Pa

Did Richard Harter write that hilarious story, or do you know the author’s name?

I’m still trying to find his identity. The story has gone around the world, being improved along the way.

I wrote about it in December 2002: http://www.bdb.co.za/shackle/articles/hillbilly.htm

[Eric Shackle is a retired Australian journalist whose hobby is searching the Internet and writing about it. He is copy editor of Anu Garg’s Seattle-based A Word A Day http://wordsmith.org newsletter, which is e-mailed five days a week to more than 900,000 wordlovers in 200 countries. Eric’s blog, LifeBeginsAt80, is posted at http://lifebeginsat80.blogspot.com/

Being him, I can speak for Richard Harter, and I can say with confidence that he did not write the story. He got the story from the August 20, 2002 mailing of www.laffaday.com. You might try writing them and seeing where they got the story. Their listed archives don’t go back that far, but you might have some luck. It turns out, though, that Snopes has the scoop. It is definitely pre internet. It goes back at least to the Saturday Evening Post circa 1952.

Given the timing the story was probably injected into the internet by laffaday.com. AFAIK Harter’s copy is the oldest one on the web. I hope this helps.

Cheerily,
Richard Harter

From: Ashley Kjonaas
Date: 26 March 2010
Subj: A Letter from an Inhabitant of Baja Canada

I just read your Menace from the North article about North Dakota. I come from Fargo, and I have to say that I was highly amused! I had to write you an email to tell you: thanks for the laugh–it was a good one!Thank you! And I hope you’ve gotten to Alaska!

You’re welcome. Thank you for the kind words. By the bye, do you suppose there is any chance that I could get a contract with the North Dakota department of tourism?

From: Suford
Date: 23 March 2010
Subj: Tommy

Hey Harter…

That “kitten” looks about a year old–which would have made it about the right age to “fix”– how much does he weigh and what did the vet say about how old he was? He looks like he could be another “Josephine”. He’s even gray (though I don’t think J-fiend had any white spots).

A real kitten runs around all the time: around the room, over you, up and down, and around the room, and over you… This is clearly a mature-for-his-age catling. So you do have SOME reward for your virtue.

As long as you don’t feed them in the morning (thus giving them an incentive to wake you up), I don’t see the downside to Thomas sleeping with you. But then our cats have always slept with us, so of course I wouldn’t see it.

Enjoy your doom…

He is sort of in between being a kitten and being a cat. When he first moved in he was fairly quiet as young cats go. Now that he has settled in he seems to have decided that it is quite alright to play kitten. He tears around a lot. The vet thought he was between six and nine months old which seems to match his behaviour. I weighed him after several days and he weighed in at 6.2 lbs. Currently he weighs in at 7.4 lbs. I suspect he is going to be a BIG kitty.

From: gallois evariste
Date: 18 March 2010
Subj: About Unordered Radix Trees

First i would to thank you for your great paper about Radix Trees(http://richardhartersworld.com/~cri/2007/urtree.html) (it’s better than the wikipedia article).

I’m a student at university paris VI, and i want to implement a telephone prefix matching in c in a real time environment:

I receive from a telephony switch in real time all the called numbers around the world,example:

   number : 33 1234567890(33 is France)
   number : 1 87745678901(1 is USA)
   number : 39 1234567890(39 is Italy)

i”m now trying to implement it using your htree.c or utree.c and i want to ask you if the performance will be much better and faster than regex? and if the answer is yes what 

you suggest me to do?

Thanks in advance for your help.(and excuse my english -:).

[code snipped]

It is not clear to me whether you are getting the numbers as a single string of digits or whether you are getting them as a two item record consisting of a country prefix and a “within the country” number. In the latter case the prefix is a well defined key. You could use any of a number of lookup methods, e.g., a trie, a urtree, a hash table, or some sort of search tree. I am assuming that the numbers are simple strings of digits. In that case your problem is not suitable for an unordered radix tree. The difficulty is that you need to know the key length (in this case, the prefix length) in advance; however this length is not known until you have extracted the key length.

You could use a trie or a patricia tree. You could even hand code the lookup as a suite of nested switches.

So why does your code run slowly? A trie (or even a search tree) would be faster than a linear search through the country table. Even so, a linear search needn’t be all that bad. The problem in your code is that each cycle of the search loop is expensive. In one cycle you call malloc, regcomp, regexec, regfree, and free.

The simple thing to do is have an array of prefixes as strings, and check whether the prefix matches the beginning of the number. The code might look something like this:

len_arrray = sizeof(prefix)/sizeof(prefix[0]);
for (i=0; i < len_array; i++) {
    for (ch = prefix[i], j=0;*ch == number[j];j++,ch++);
    if (!*ch) return i;
}
return -1;

WARNING: CODE NOT TESTED.

Something like this should run a lot faster than your code. If this doesn’t buy you enough then you should look at more sophisticated data structures. I hope this helps.

From: Wendi Rinehart
Date: 9 March 2010
Subj: Richards World revisited

Good Morning Richard,

Just had to write to let you know how much I enjoyed reading your editorials and other stories. Its been awhile since I visited your site and this a.m. got acquainted again.

You’ve made my day with your ” tongue-in-cheek” humor and have really missed it.

Wendi

It is good to know that you enjoyed the site. I wasn’t aware that I had made your day. As you may know, one of my many little jobs and side projects is making days. Most of them are standard models using off the shelf components. I must admit that I have taken to getting my mornings and afternoons from Costco. I would like to buy American but I just can’t afford it, the besides of which, Mandarin Mornings do have a certain charm. Nights I get from Nocturnal Aviation Corp. They are recycled, but they are cleaned up fairly well.

I also do some specialty work for some of the more select catalogs. I suspect that is where you got yours. It is always good to hear from satisfied customers.

Return to index of contributors