_First Contact_

1987 book I just finished, by Bob Connolly and Robin Anderson. It's about the contact between white Australians and highland New Guinea in the 1930s, mostly done by Australian gold prospector Michael Leahy, with Leahy's 1930s photographs (and some 1980s ones, by the book's authors.) It's main sources are Leahy's diaries and 1980s interviews of both surviving Australians and highlanders. So we get views from both sides, though most of the surviving highlanders were teens or kids at the time, naturally.

First half or so of the book is a step-by-step following of the initial expeditions, but it later pans out to further developments and reactions, closing with independence for Papua New Guinea in 1975.

Notes:

* The highlanders seem to have been extremely isolated from the coast. They can't have been entirely so, because shells filtered up as highly valuable prestige/trade/moka items, but OTOH they hadn't heard of the white men who'd been on the coast for 50 years, and on first viewing thought the whites were relatives returned from the dead. The highlanders themselves say that.

* Pretty isolated from each other, it seems, or more accurately a person's radius of experience was pretty short, hemmed in by hostiles tribes.

* Volatile mix of racism, paternalism, and humanity among the whites. Michael could readily go for a lethal show of force to "kill before we're killed" while objecting to the bloodfeud killing of the natives or gratuitous killing by his own coastal native 'gunbois'. One brother went half native, taking two native wives and never leaving; a friend from the Administration went full native, being accepted by the highlanders he lived among; Michael turned into an Angry Old White Man, disappointed at not getting wealthy and ranting to his grave against the independence movement.

* Both major Out Of Context problems and rapid adaptation by the highlanders. Took them a while to figure out if the whites were human and not spirit, but quickly taking advantage of the wealth they offered and assessing the physical danger they posed.

* Highlanders somewhat balking at independence, as they had less negative experience of colonialism than the coastal New Guineans, and feared being dominated by the coastals. A Liberian UN commissioner was really surprised at the feelings he ran into. "Development, then independence." Of course, most of the Australians had no intention of developing NG into economic independence, that's not what colonies are for.

* Examples of both benign and imperial introductions of money and trade. The early prospectors weren't that violently rapacious, though killing a fair number of people to establish "don't mess with our stuff"; they brought in lots of wealth of shells, axes, and other goods to buy food and labor with, but the workers weren't losing their own land, and had a real choice to work. Administration and the coastal colonists didn't like independent labor though, and instituted poll taxes that had to be paid in Australian money.

(The prospectors might have been worse had they ever found major gold prospects to dredge. Happily they didn't, and coffee plantations ended up the main means of wealth extraction.)

* WWII was a push toward independence. No mention of attitudes wearing off from the Japanese or the fact of their pushing out Australia, but the returning US and Australian soldiers are claimed to have been relatively egalitarian, a shocking contrast with the pre-war colonists.

* Colonialism probably really did bring down the violent death rate, here.

AVL tree

For a long time, self-balancing trees had seemed like magic to me. Earlier this year I put my mind to figuring them out, and on my own came up with the idea of a weight-balanced tree. With a bit of peeking, I then moved on to a height-balanced tree, pretty much an AVL tree. Then I started coding one in pure C, for Real Programmer (TM) cred.

Stage one, achieved some months ago, fulfilled the basic criterion: you could feed it an increasing sequence of keys, and get a beautifully balanced tree back out. Woo! It had problems, though. Most obviously, I concentrated on the balancing part first, so got heights on the fly via a function rather than from cached values. Not exactly computationally efficient. Less obviously, I had a clever-seeming tree-rotation function I'd come up with: "to rotate right: insert root value to the right, copy rightmost left value into root, delete same value from the left tree." Elegant, but O(log(N)), when there are actually O(1) rotations available.

I went back to the project this evening, and got the faster rotations working. It took longer than I expected, because when you do rotations that way, there's complexity: 1->2->3 can be rotated left, but 1->3->2 needs a rotation right (on 3->2) then left, to come out balanced. Turns out that my slower rotation did the correct thing in both cases, so simply replacing my rotate functions wasn't working until I added more logic. Grumble grumble.

I still don't have heights cached, and the whole thing feels like an unholy mess of pointer manipulations (especially with parent points in the tree.) But, progress!

numeric integrals

So there are the left and right Riemann sums, and the much better midpoint Riemann sum. Recently I wondered about integrals that took the average of the endpoint of each strip: (f(x)+f(x+step))/2. The thing is that most of the halves combine, so you can just add up f(x) for each whole step, plus f(start)/2 and f(end)/2. How's that compare?

Much better than the left and right sums, but not quite as good as the standard midpoint one. E.g. the integrals of sin(x) over 0 to pi/2 are

left_: 0.9992143962198378
right: 1.0007851925466327
mid__: 1.0000001028083885
mine_: 0.9999997943832352

All the other integrals I tried show a similar pattern: x, x^2, x^3, 1/x, e(x)... the two are close, but midpoint is just a bit closer to the correct answer. Or looked at another way, has close to 1/2 the error... hmm, that factor is consistent too. I should look into that.

Or: if I just recalled my terminology correctly, midpoint Riemann sums have half the error of trapezoidal Riemann sums. Which is not what I would have expected.