The Lumber Room

"Consign them to dust and damp by way of preserving them"

Big O() notation: a couple of sources

with one comment

This post contains, just for future reference, a couple of primary sources relevant to the O (“Big O”) notation:

  1. Some introductory words from Asymptotic Methods in Analysis by de Bruijn
  2. An letter from Donald Knuth on an approach to teaching calculus using this notation.

Read the rest of this entry »

Written by S

Thu, 2014-03-13 at 16:33:20 +05:30

Visualizing product of permutations

leave a comment »

A simple pedagogical trick that may come in handy: represent a permutation \sigma using arrows (curved lines) from k to \sigma(k) for each k. Then, the product of two permutations can be represented by just putting the two corresponding figures (sets of arrows) one below the other, and following the arrows.

Representing permutations and products of permutations.

Representing permutations and products of permutations.

The figure is from an article called Symmetries by Alain Connes, found via the Wikipedia article on Morley’s trisector theorem (something entirely unrelated to permutations, but the article covers both of them and more).

I’m thinking how one might write a program to actually draw these: if we decide that the “height” of the figure is some h, then each arrow needs to go from some (k, 0) to (\sigma(k), h) (using here the usual screen convention of x coordinate increasing from left to right, and y coordinate increasing from top to bottom). Further, each curve needs to have vertical slope at its two endpoints, so that successive curves can line up smoothly. The constraint on starting point, ending point, and directions at the endpoints defines almost a quadratic Bezier curve, except that here the two directions are parallel. So it’s somewhere between a quadratic and the (usual) cubic Bezier curve, which is given by the start point, end point, and derivatives at the start and end point. (Here we only care about the direction of the derivative; we can pick some arbitrary magnitude to fix the curve: the larger we pick, the more smooth it will look at the ends, at the cost of smoothness in the interior.)

Even knowing the curve, how do we generate an image?

Written by S

Thu, 2014-03-06 at 23:15:44 +05:30

The letter in Roister Doister

leave a comment »

An early English example of resegmentation for change of meaning: Merygreeke’s letter to the Dame Custance, from Ralph Roister Doister (c. 1553), the first comedy to be written in the English language. [Aside: Shakespeare born in 1564 started had written all his plays before 1613, only 60 years from then.]

The example also shows that enjambment (no pause at end of line) did indeed exist in early English as well.

Scene 4

Sweete mistresse where as I loue you nothing at all,
Regarding your substance and richesse chiefe of all,
For your personage, beautie, demeanour and wit,
I commende me vnto you neuer a whit.
Sorie to heare report of your good welfare.
For (as I heare say) suche your conditions are,
That ye be worthie fauour of no liuing man,
To be abhorred of euery honest man.
To be taken for a woman enclined to vice.
Nothing at all to Vertue gyuing hir due price.
Whersore concerning mariage, ye are thought
Suche a fine Paragon, as nere honest man bought.
And nowe by these presentes I do you aduertise
That I am minded to marrie you in no wise.
For your goodes and substance, I coulde bee content
To take you as ye are. If ye mynde to bee my wyfe,
Ye shall be assured for the tyme of my lyfe,
I will keepe ye ryght well, from good rayment and fare,
Ye shall not be kepte but in sorowe and care.
Ye shall in no wyse lyue at your owne libertie,
Doe and say what ye lust, ye shall neuer please me,
But when ye are mery, I will be all sadde,
When ye are sory, I will be very gladde.
When ye seeke your heartes ease, I will be vnkinde,
At no tyme, in me shall ye muche gentlenesse finde.
But all things contrary to your will and minde,
Shall be done: otherwise I wyll not be behinde
To speake. And as for all them that woulde do you wrong
I will so helpe and mainteyne, ye shall not lyue long.
Nor any foolishe dolte, shall cumbre you but I.
Thus good mistresse Custance, the lorde you saue and kepe,
From me Roister Doister, whether I wake or slepe.
Who fauoureth you no lesse, (ye may be bolde)
Than this letter purporteth, which ye haue vnfolde.

Scene 5

Sweete mistresse, where as I loue you, nothing at all
Regarding your richesse and substance: chiefe of all
For your personage, beautie, demeanour and witte
I commende me vnto you: Neuer a whitte
Sory to heare reporte of your good welfare.
For (as I heare say) suche your conditions are,
That ye be worthie fauour: Of no liuing man
To be abhorred: of euery honest man
To be taken for a woman enclined to vice
Nothing at all: to vertue giuing hir due price.
Wherfore concerning mariage, ye are thought
Suche a fine Paragon, as nere honest man bought.
And nowe by these presents I doe you aduertise,
That I am minded to marrie you: In no wyse
For your goodes and substance: I can be content
To take you as you are: yf ye will be my wife,
Ye shall be assured for the time of my life,
I wyll keepe you right well: from good raiment and fare,
Ye shall not be kept: but in sorowe and care
Ye shall in no wyse lyue: at your owne libertie,
Doe and say what ye lust: ye shall neuer please me
But when ye are merrie: I will bee all sadde
When ye are sorie: I wyll be very gladde
When ye seeke your heartes ease: I will be vnkinde
At no time: in me shall ye muche gentlenesse finde.
But all things contrary to your will and minde
Shall be done otherwise: I wyll not be behynde
To speake: And as for all they that woulde do you wrong,
(I wyll so helpe and maintayne ye) shall not lyue long.
Nor any foolishe dolte shall cumber you, but I,
I, who ere say nay, wyll sticke by you tyll I die.
Thus good mistresse Custance, the lorde you saue and kepe.
From me Roister Doister, whether I wake or slepe,
Who fauoureth you no lesse, (ye may be bolde)
Than this letter purporteth, which ye haue vnfolde.

See also

Written by S

Tue, 2014-02-25 at 07:30:28 +05:30

Posted in language, literature

Free, defiant, and without a security label

leave a comment »

James Mickens is a CS researcher (“Galactic Viceroy of Research Magnificence”) who among other things writes wrote for the online version of Usenix’s magazine ;login: (called ;login: logout, published every other month). Here are some of his articles:

  1. [May 2013] The Saddest Moment
  2. [July 2013] Mobile Computing Research Is a Hornet’s Nest of Deception and Chicanery
  3. [September 2013] The Slow Winter
  4. [November 2013] The Night Watch
  5. [January 2014] This World of Ours
  6. [March 2014] To Wash It All Away

Reading these is an epiphany akin to one’s first encounter with Dave Barry or Airplane!

(Plug by Raymond Chen too.)

See also this video, where he answers questions like “What’s the best piece of advice you have ever received?” (Answer: “The best piece of advice was probably ‘Stay out of jail’. That came from my dad.”)

Edit [2014-03-13]: Apparently the March 2014 column is his last for the magazine; updated post.

Written by S

Wed, 2014-01-08 at 13:53:11 +05:30

The idea of logarithms, and the first appearance of e

with 2 comments

[Incomplete post: about 10% written, about 90% left.]

The notion of the number e, the exponential function e^x, and logarithms \log x are often conceptual stumbling blocks even to someone who has an otherwise solid understanding of middle-school mathematics.

Just what is the number e? How was it first calculated / where did it first turn up? Premature exposure to its numerical value

\displaystyle e \approx 2.718281828459045\dots

only serves to deepen the mysteriousness and to make it seem arbitrary.

Here a historical perspective helps: as is often the case, here too, the first appearance is simpler and more well-motivated than the accounts in dry textbooks. This is from this account by Matthew P. Wiener (originally posted on USENET somewhere, as quoted by MJD). I’m just going to quote it directly for now, and edit it later:

Napier, who invented logarithms, more or less worked out a table of logarithms to base \frac1e, as follows:

     0  1  2  3   4   5   6    7    8    9    10 ...
     1  2  4  8  16  32  64  128  256  512  1024 ...

The arithmetic progression in the first row is matched by a geometric progression in the second row. If, by any luck, you happen to wish to multiply 16 by 32, that just happen to be in the bottom row, you can look up their “logs” in the first row and add 4+5 to get 9 and then conclude 16·32=512.

For most practical purposes, this is useless. Napier realized that what one needs to multiply in general is 1+\epsilon for a base—the intermediate values will be much more extensive. For example, with base 1.01, we get:

       0 1.00   1 1.01   2 1.02   3 1.03   4 1.04   5 1.05
       6 1.06   7 1.07   8 1.08   9 1.09  10 1.10  11 1.12
      12 1.13  13 1.14  14 1.15  15 1.16  16 1.17  17 1.18
      18 1.20  19 1.21  20 1.22  21 1.23  22 1.24  23 1.26
      24 1.27  25 1.28  26 1.30  27 1.31  28 1.32  29 1.33
      30 1.35  31 1.36  32 1.37  33 1.39  34 1.40  35 1.42
      50 1.64  51 1.66  52 1.68  53 1.69  54 1.71  55 1.73
      94 2.55  95 2.57  96 2.60  97 2.63  98 2.65  99 2.68
     100 2.70 101 2.73 102 2.76 103 2.79 104 2.81 105 2.84

So if you need to multiply 1.27 by 1.33, say, just look up their logs, in this case, 24 and 29, add them, and get 53, so 1.27·1.33=1.69. For two/three digit arithmetic, the table only needs entries up to 9.99.

Note that e is almost there, as the antilogarithm of 100. The natural logarithm of a number can be read off from the above table, as just [approximately] \frac1{100} the corresponding exponent.

What Napier actually did was work with base .9999999. He spent 20 years computing powers of .9999999 by hand, producing a grand version of the above. That’s it. No deep understanding of anything, no calculus, and e pops up anyway—in Napier’s case, \frac1e was the 10 millionth entry. (To be pedantic, Napier did not actually use decimal points, that being a new fangled notion at the time.)

Later, in his historic meeting with Briggs, two changes were made. A switch to a base > 1 was made, so that logarithms would scale in the same direction as the numbers, and the spacing on the logarithm sides was chosen so that \log(10)=1. These two changes were, in effect, just division by -\log_e(10).

In other words, e made its first appearance rather implicitly.

(I had earlier read a book on Napier and come to the same information though a lot less clearly, here.)

I had started writing a series of posts leading up to an understanding of the exponential function e^x (here, here, here), but it seems to have got abandoned. Consider this one a contribution to that series.

Written by S

Wed, 2013-11-27 at 10:52:51 +05:30

Posted in mathematics

Wodehouse on Conan Doyle

with 4 comments

I have noted before, while reading Right Ho, Jeeves, how much it draws from and parodies the Sherlock Holmes stories of Sir Arthur Conan Doyle. In fact, the whole book can be read as if Bertie Wooster is Sherlock Holmes, or at least that he imagines himself to be. Rereading it this way threw up a surprising number of examples (as did Psmith, Journalist), all the way from obvious ones like “You know my methods, Jeeves. Apply them.”, to references so subtle that it’s not clear whether Wodehouse is consciously parodying Sherlock Holmes, or it’s a simple case of one author influencing another. (But perhaps they only seem subtle to those of us who aren’t as steeped in the Holmesverse as the readers of the early 1900s would be.) And of course, when in his stories he directly mentions detectives (such as in The Man With Two Left Feet), it’s laid on thick:

He had never measured a footprint in his life, and what he did not know about bloodstains would have filled a library.


A detective is only human. The less of a detective, the more human he is. Henry was not much of a detective, and his human traits were consequently highly developed.

And I knew, too, (see previous post) that both authors enjoyed cricket, and even turned out occasionally for the same celebrity cricket team.

Despite all the preceding, I still was surprised by the existence of this:


An edition of The Sign of the Four, with introduction by P. G. Wodehouse!

It appears that PGW was a fan of ACD: in 1925, in a letter to his friend William Townend, he wrote:

“Conan Doyle, a few words on the subject of. Don’t you find as you age in the wood, as we are both doing, that the tragedy of your life is that your early heroes lose their glamour? As a lad in the twenties you worship old whoever-it-is, the successful author, and by the time you’re forty you find yourself blushing hotly at the thought that you could ever have admired the bilge he writes.
Now with Doyle I don’t have that feeling. I still revere hls work as much as ever. I used to think it swell, and I still think it swell.
And apart from his work, I admire Doyle so much as a man. I should call him definitely a great man, and I don’t imagine I’m the only one who thinks so.

And the introduction to The Sign of the Four was written in the 1970s, when Wodehouse must have been over 90. He echoes much the same lines. The full introduction is attached, pieced together from some rather excellent sources on the internet.

When I was starting out as a writer—this would be about the time Caxton invented the printing press—Conan Doyle was my hero. Others might revere Hardy and Meredith. I was a Doyle man, and I still am. Usually we tend to discard the idols of our youth as we grow older, but I have not had this experience with A.C.D. I thought him swell then, and I think him swell now.

We were great friends in those days, our friendship only interrupted when I went to live in America. He was an enthusiastic cricketer—he could have played for any first-class country—and he used to have cricket weeks at his place in the country, to which I was almost always invited. And after a day’s cricket and a big dinner he and I would discuss literature.

The odd thing was that though he could be expansive about his least known short stories–those in Round the Red Lamp, for instance—I could never get him to talk of Sherlock Holmes, and I think the legend that he disliked Sherlock must be true. It is with the feeling that he would not object that I have sometimes amused myself by throwing custard pies at that great man.

Recently I have taken up the matter of Holmes’s finances.

Let me go into the matter, in depth, as they say. I find myself arriving at a curious conclusion.

Have you ever considered the matter of Holmes’s financial affairs?

Here we have a man who evidently was obliged to watch the pennies, for when we are introduced to him he is, according to Doctor Watson’s friend Stamford, “bemoaning himself because he could not find someone to go halves in some nice rooms which he had found and which were too much for his purse.” Watson offers himself as a fellow lodger, and they settle down in—I quote—a couple of comfortable bedrooms and a large sitting room at 221B Baker Street.

Now I lived in similar rooms at the turn of the century, and I paid twenty-one shillings a week for bed, breakfast, and dinner. An extra bedroom no doubt made the thing come higher for Holmes and Watson, but thirty shillings must have covered the rent and vittles, and there was never any question of a man as honest as Watson failing to come up with his fifteen bob each Saturday. It follows, then, that allowing for expenditures in the way of Persian slippers, tobacco, disguises, revolver cartridges, cocaine, and spare violin strings Holmes would have been getting by on a couple of pounds or so weekly. And with this modest state of life he appeared to be perfectly content. Let us take a few instances at random and see what he made as a “consulting detective.”

In the very early days of their association, using it as his “place of business,” he interviewed in the sitting room “a grey-headed seedy visitor, who was followed by a slipshod elderly woman, and after that a railway porter in his velveteen uniform.” Not much cash in that lot, and things did not noticably improve later, for we find his services engaged by a stenographer, a city clerk, a Greek interpreter, a landlady, and a Cambridge undergraduate.

So far from making money as a consulting detective, he must have been a good deal out of pocket most of the time. In A Study in Scarlet, Inspector Gregson asks him to come to 3 Lauriston Gardens in the Brixton neighborhood, because there has been “a bad business” there during the night. Off goes Holmes in a hansom cab from Baker Street to Brixton, a fare of several shillings, dispatches a long telegram (another two or three bob to the bad), summons “half a dozen of the dirtiest and most ragged street Arabs I ever clapped eyes on,” gives each of them a shilling, and tips a policeman half a sovereign. The whole affair must have cost him considerably more than a week’s rent at Baker Street, and no hope of getting any of it back from Inspector Gregson, for Gregson, according to Holmes himself, was “one of the smartest of all the Scotland Yarders.”

Inspector Gregson! Inspector Lestrade! Those clients! I found myself thinking a good deal about them, and it was not long before the truth dawned upon me, that they were merely cheap actors, hired to deceive doctor Watson, who had to be deceived because he had the job of writing the stories.

For what would the ordinary private investigator have said to himself when starting out in business? He would have said ‘Before I take on work for a client I must be sure that the client has the stuff. The daily sweetener and the little something down in advance are of the essence,’ and he would have had those landladies and those Greek interpreters out of his sitting room before you could say ‘bloodstain.’ Yet Holmes, who could not afford a pound a week for lodgings, never bothered. Significant!

Later the thing became absolutely farcical, for all pretence that he was engaged in a gainful occupation was dropped by himself and the clients. I quote Doctor Watson.

“He tossed a crumpled letter across the table to me. It was dated from Montague Place upon the preceding evening and ran thus:

Dear Mr. Holmes,
I am anxious to consult you as to whether or not I should accept a situation which has been offered to me as a governess.
I shall call at half-past ten tomorrow, if I do not inconvenience you.
Yours faithfully
Violet Hunter.”

Now, the fee an investigator could expect from a governess, even one in full employment, could scarcely be more than a few shillings, yet when two weeks later Miss Hunter wired “Please be at the Black Swan at Winchester at mid-day tomorrow,” Holmes dropped everything and sprang into the 9:30 train.

It all boils down to one question–Why is a man casual about money?

The answer is–Because he has a lot of it.

Had Holmes?

He pretended he hadn’t, but that was merely the illusion he was trying to create because he needed a front for his true activities. He was pulling the stuff in from another source. Where is the big money? Where it has always been, in crime. Bags of it, and no income tax. If you want to salt away a few million for a rainy day, you don’t spring into 9:30 trains to go and talk to governesses, you become a Master Criminal, sitting like a spider in the center of its web and egging your corps of assistants on to steal jewels and navel treaties. I saw daylight, and all the pieces of the jigsaw puzzle fell into place. Holmes was Professor Moriarty.

What was that name again?

Professor Moriarty.

Do you mean that man who was forever oscillating his face from side to side in a curiously reptilian fashion?

That’s the one.

But Holmes’ face didn’t forever oscillate from side to side in a curiously reptilian fashion.

Nor did Professor Moriarty’s.

Holmes said it did.

And to whom? To Doctor Watson, in order to ensure that the misleading description got publicity. Watson never saw Moriarty. All he knew about him was what Holmes told him on the evening of April 24,1891. And Holmes made a little slip on the occasion. He said that on his way to see Watson he had been attacked by a rough with a bludgeon. A face-oscillating napoleon of Crime, anxious to eliminate someone he disliked, would have thought up something better than roughs with bludgeons. Dropping cobras down the chimney is the mildest thing that would have occurred to him.

P.S. Just kidding, boys. Actually, like all the rest of you, I am never happier than when curled up with Sherlock Holmes, and I hope Messrs Ballantine will sell several million of him. As the fellow said, there’s no police like Holmes.

–P.G. Wodehouse.


Other stuff:

(All written during the time between the publication of Sherlock Holme’s death in FINA published December 1893, and his reapparance in EMPT published September 1903. The Hound of the Baskervilles had been serialized from August 1901 to April 1902. Doyle had announced the impending return of Sherlock Holmes in the Strand, whcih is why Wodehouse wrote “Back to his Native Strand”.)

* Wodehouse wrote (unsigned) a parody called “Dudley Jones, Bore Hunter” (, in Punch on April 29, 1903 ( and May 6, 1903 (

* Wodehouse wrote (unsigned) a poem called “Back to his Native Strand” for Punch on May 27, 1903:

* Wodehouse did an “interview” of ACD in “VC” magazine, July 2, 1903:

* Wodehouse wrote (unsigned) “The Prodigal” for Punch on September 23, 1903:

Written by S

Fri, 2013-10-11 at 08:37:03 +05:30

Posted in literature

Cricket poems

with 3 comments

Arthur Conan Doyle played 10 first-class matches between 1900 (when he was over 40) and 1907, playing for the MCC. He averaged close to 20 with the bat, with a high score of 43. On 25 August 1900, against London County at Crystal Palace, he took his only first-class wicket: that of W. G. Grace, who was batting on 110 at the time (and declared his team’s innings immediately after getting out). He wrote a poem about it.

A Reminiscence of Cricket

Once in my heyday of cricket,
One day I shall ever recall!
I captured that glorious wicket,
The greatest, the grandest of all.

Before me he stands like a vision,
Bearded and burly and brown,
A smile of good humoured derision
As he waits for the first to come down.

A statue from Thebes or from Knossos,
A Hercules shrouded in white,
Assyrian bull-like colossus,
He stands in his might.

With the beard of a Goth or a Vandal,
His bat hanging ready and free,
His great hairy hands on the handle,
And his menacing eyes upon me.

And I – I had tricks for the rabbits,
The feeble of mind or eye,
I could see all the duffer’s bad habits
And where his ruin might lie.

The capture of such might elate one,
But it seemed like one horrible jest
That I should serve tosh to the great one,
Who had broken the hearts of the best.

Well, here goes! Good Lord, what a rotter!
Such a sitter as never was dreamt;
It was clay in the hands of the potter,
But he tapped it with quiet contempt.

The second was better – a leetle;
It was low, but was nearly long-hop;
As the housemaid comes down on the beetle
So down came the bat with a chop.

He was sizing me up with some wonder,
My broken-kneed action and ways;
I could see the grim menace from under
The striped peak that shaded his gaze.

The third was a gift or it looked it—
A foot off the wicket or so;
His huge figure swooped as he hooked it,
His great body swung to the blow.

Still when my dreams are night-marish,
I picture that terrible smite,
It was meant for a neighboring parish,
Or any place out of sight.

But – yes, there’s a but to the story –
The blade swished a trifle too low;
Oh wonder, and vision of glory!
It was up like a shaft from a bow.

Up, up like a towering game bird,
Up, up to a speck in the blue,
And then coming down like the same bird,
Dead straight on the line that it flew.

Good Lord, it was mine! Such a soarer
Would call for a safe pair of hands;
None safer than Derbyshire Storer,
And there, face uplifted, he stands

Wicket keep Storer, the knowing,
Wary and steady of nerve,
Watching it falling and growing
Marking the pace and curve.

I stood with my two eyes fixed on it,
Paralysed, helpless, inert;
There was ‘plunk’ as the gloves shut upon it,
And he cuddled it up to his shirt.

Out – beyond question or wrangle!
Homeward he lurched to his lunch!
His bat was tucked up at an angle,
His great shoulders curved to a hunch.

Walking he rumbled and grumbled,
Scolding himself and not me;
One glove was off, and he fumbled,
Twisting the other hand free

Did I give Storer the credit
The thanks he so splendidly earned?
It was mere empty talk if I said it,
For Grace had already returned.

Incidentally, W. G., like Conan Doyle, was also a doctor with no time for that profession. Here’s another article about Conan Doyle. He also made up a story about a “high dropping full toss” (lob bowling?) that fell on the stumps from the air. (Discussion.)

P. G. Wodehouse wrote a happy little poem about a fielder who misses a catch.


The sun in the heavens was beaming,
The breeze bore an odour of hay,
My flannels were spotless and gleaming,
My heart was unclouded and gay;
The ladies, all gaily apparelled,
Sat round looking on at the match,
In the tree-tops the dicky-birds carolled,
All was peace — till I bungled that catch.

My attention the magic of summer
Had lured from the game — which was wrong.
The bee (that inveterate hummer)
Was droning its favourite song.
I was tenderly dreaming of Clara
(On her not a girl is a patch),
When, ah, horror! there soared through the air a
Decidedly possible catch.

I heard in a stupor the bowler
Emit a self-satisfied ‘Ah!’
The small boys who sat on the roller
Set up an expectant ‘Hurrah!’
The batsman with grief from the wicket
Himself had begun to detach –
And I uttered a groan and turned sick. It
Was over. I’d buttered the catch.

O, ne’er, if I live to a million,
Shall I feel such a terrible pang.
From the seats on the far-off pavilion
A loud yell of ecstasy rang.
By the handful my hair (which is auburn)
I tore with a wrench from my thatch,
And my heart was seared deep with a raw burn
At the thought that I’d foozled that catch.

Ah, the bowler’s low, querulous mutter
Points loud, unforgettable scoff!
Oh, give me my driver and putter!
Henceforward my game shall be golf.
If I’m asked to play cricket hereafter,
I am wholly determined to scratch.
Life’s void of all pleasure and laughter;
I bungled the easiest catch.

Both Conan Doyle and Wodehouse played cricket at one point for J. M. Barrie’s team Allah-akbarries (named in the belief that “Allahu Akbar” meant “God help us!”, but of course probably more for the “barries” in the name), some of whose other players included Rudyard Kipling, H. G. Wells, G. K. Chesterton, Jerome K. Jerome, A. A. Milne.

Here’s another great article about Conan Doyle and Wodehouse.

A. A. Milne wrote some poems about cricket as well.

An article about authors.

Casey at the Bat is the most famous baseball poem. (Wikipedia article)

Written by S

Sun, 2013-09-01 at 14:35:50 +05:30

Posted in literature

Tagged with


Get every new post delivered to your Inbox.

Join 57 other followers