Chickpea Flour Pancakes

July 17th, 2009

This is not about breakfast. Well, not necessarily about breakfast. Pancakes are things made from batter and fried in a pan. The pancakes I’m talking about here could, I guess, be breakfast fare, but the focus is on (A) dense nutrition and (B) extreme simplicity.

Chickpea flour can be had at your local supermarket in packages from Bob’s Red Mill. That stuff is fine. There’s a variant that involves a blend of chickpea and fava beans, which would also probably be fine. However, if you have a local Indian market like MGM on Burnet in Austin, get your flour there. It’s generally labeled “Besan” or “Channa Dal Flour”. Channa dal are a legume, possibly a cultivar of ordinary garbanzos but I don’t think so. They taste better and are (I think based on thin Internet evidence) that they’re somewhat better for you. Anyway at MGM and similar places you can buy serious quantities of chickpea flour for not too much money.

The pancake recipe – the basic one – is weirdly simple: equal parts, by volume, flour and water. The result is a batter that seems way too thin if you’re used to making ordinary breakfast pancakes. A lot too thin; like, “there’s no way this is going to work” thin. It works.

Chickpea flour isn’t super-fond of being mixed into water, so you can either do it carefully with a whisk, and strain it a couple times, or you can just dump it in your food processor and subject it to several amps of high-speed sharp-bladed turbulence. Also I think that the motorized mixing seems to build up some protein chains to make the final pancakes have a little more structural integrity. Finally, of course, if you’re putting other stuff into your pancakes, the food processor is a big help anyway.

Flavoring possibilities are pretty broad. Go South Asian with coriander, cumin, turmeric, cayenne powder, and salt. I’ve purreed in some blanched spinach to great effect. I have a plan to make some seasoned with basil, chive, garlic, and oregano, and then bake them into a sort of cheesy casserole. The main thing to make sure you do is salt them, or else plan on serving them with some salt-bearing condiment, sauce, topping, or whatever.

Anyway mix up the seasonings of choice, the flour, and the water, all together into your suspiciously runny batter. Get a non-stick pan fairly hot (remember, the batter is really wet), but not so hot as to kill all your birds of course. Spread a little oil in the pan (I use one of those curiously not-as-useful-as-they-look silicone brushes for this) and then pour in a quarter-cup or so of batter. Once it hits the pan, tilt it around to let the stuff spread a little. Making these things thin isn’t super important but it’s aesthetically pleasing.

The first side will cook in a couple minutes, depending on the heat. You’ll notice the top go from wet-looking to a kind of matte sheen. The water content makes these things hard to overcook unless you’ve seriously over-cranked your stove. Flip the pancake with a big spatula (one that won’t ruin your pan of course) and let it cook on the top side for another minute or two.

The texture of these things is somewhat like what you’d imagine a soft plastic tortilla to be like. They’re not quite as bendy as a tortilla, at least a wet one, but they’re floppy and toothsome. They taste pretty much exactly like whatever seasonings you applied, plus a pleasant slight earthy backtone from the flour itself.

If you have a big sack of the flour around, and a good easy-to-wash pan (or, I guess, a plug-in griddle, though that’d make it hard to do the tilt-and-spread part), just flour salt and water are a damn good and very nourishing 5 minute snack preparation. I’m told that they freeze and reheat very well, which makes sense because unlike breakfast pancakes they have no “light and fluffy” phase. Make them spicy. Add spinach in the food processor step. Add some ground flax if you’re one of those flax people. Nutritional yeast. Whey powder. Sesame seeds. Sugar. This stuff is awesome. You won’t believe how filling (in a non-gross way) these pancakes are.

Another “Animal Planet” Experience

June 23rd, 2009

My overall landscaping strategy for my back yard is to allow any plant that decides to live there, live there. This means that parts of it have that “this must be an abandoned building” look. There are a variety of yaupon hollies (including one that we, laughably, paid to have planted), a large mulberry tree, a flourishing pittosporum bush, a poplar scion from a tree next door, and all sorts of other things. There’s also a raised garden with some rose bushes gone wild enough to dabble the imagery of any scene from a Brontë novel. It’s been that way for years. It looks both terrible and beautiful at the same time. The weird gnarled hollies bloom in the spring, and they’re quite pretty. The blossoms ripen into clusters of bright red berries, and they’re nice too. The mulberry makes an awful mess in the spring but it attracts mockingbirds (and probably rats) and my kids make purple mush out of the berries in a long series of annual rituals.

Of course, a downside of maintaining a vacant lot in my backyard is that it appeals to members of Kingdom Animalia as well. A wild (or feral) rabbit this year delivered a litter of kits in a superbly-hidden nest under a 1-foot-tall rose mallow plant in a large gravel pit. A small plastic beach ball was the key to secrecy. It took about 3 minutes for my daughter and my rat terrier to find the nest of course, with the ultimate result – after 10 long, long days of bewilderment on the part of the poor rat terrier, restricted from the yard over that time until the kits became at least basically motile – being a large number of new rabbit stamps on the dog’s kill list. (I like rabbits just fine, but if I’m housing and feeding a rat terrier it makes no sense to disallow it from ridding the yard of what it considers “vermin”, as that’s basically the only thing it lives for. It’s pretty bad at hunting, so baby rabbits – who apparently react to a dog in the yard by standing still – are great prey for this animal.)

Back to yard maintenance. A thing I don’t do – though for a short time I tried – is maintain my own lawn. I’d much prefer to have no lawn at all, which is to say that I’d like to have a full-blown impassable Hill Country thicket outside the back door, with (possibly) a couple of semi-maintained paths hacked through for access to some planned areas like the butterfly garden and the herb patches. That would probably bring down the Neighborhood Association storm troopers, however, so we’ve still got grass and we keep it alive. Thus we pay the cheapest, least-competent lawn service in existence to mow the lawn. They come once a week, or once every two weeks, or basically whenever they decide to.

Last week, during the lawn maintenance process, one of the lawn men knocked on the back door with a look of alarm. Elaine answered, and over the noise of his idling weed whacker he told her that he’d just seen a rattlesnake slithering over the rock wall into the middle rose (Brontë) thicket. She pushed him for details, as we’ve learned that lots of people mistake (harmless) rat snakes for rattlesnakes, but the guy said that he’d seen the rattles on the tail.

Well living in this goofy neighborhood, one has to imagine that pretty much anything that might live in the greenbelt around the development has probably strayed into every single backyard at one time or another. The fences are all old and rotting, so there’s nothing but the variously-demented pet dogs to keep vermin out. I’ve seen raccoons and opossums and rat snakes and rats and (of course) squirrels, and I’m sure that ring-tails and foxes are around. I’ve seen armadillo evidence (little holes where they dig for grubs). Oh, and the rabbits of course. Thus the idea that a rattlesnake would pass through seemed totally believable, but we figured that nobody’s backyard – especially ones with yapping idiot dogs and loud kids – would be much of a home for a rattlesnake.

That night, accompanying said idiot dog out for her evening vermin hunt, I was musing to myself that the noise from all the arboreal cicadas was so loud that it probably would be impossible to hear a rattlesnake rattling. I watched the dog sniff along the fence line heading for another raised “garden” in the corner, itself filled with a holly, some volunteer red oaks, random bushes, vines, and other unidentified vegetation. I couldn’t see it at all in the dark. As the dog moved into complete shadow, and as I thought about the noise of all those bugs, Gypsy suddenly jumped back with a “yip” and gave a couple more barks. Concurrently, I heard a very distinct and robust rattle coming from somewhere smack in the middle of the shadows.

I know I’ve probably heard rattlesnakes rattle at reptile shows or whatever, and of course I can’t be positive that that’s what I heard, but it wasn’t a bug or a bird and it was coming from low along the ground (or maybe the garden), and it sure as heck sounded like a rattlesnake. It was very assertive; really, I thought, a pretty useful thing to have as an animal. The dog, thankfully, didn’t think the snake looked like a squirrel, so when I demanded that it go inside immediately it ran up the deck steps right away.

So with a rattlesnake more-or-less definitely hanging around, what do we do? Once again, there’s only one answer: we call Amazon Rodent & Wildlife Control to secure the services of intrepid zoologist Rio Tenango. Of course, in Austin calls for tiger removal are probably pretty rare, but surely rattlesnake removal is a close second. We call and are told that they can treat our yard/house with a repellent mixture that should keep all but the dumbest snakes away. Elaine booked a house call. She asked if I thought we might be buying “snake oil.” Well, in a backwards sort of way, yes.

The Amazon team showed up outfitted with anti-pointy-teeth leggings and heavy boots. Rio got to work going through just about every square foot of vegetation looking for the snake, while his trusty assistant/spouse (I think? sorry if I’m wrong Rio) mixed up the anti-snake powder. I won’t divulge the recipe because you really need to see these people apply it to get the whole Tao of snake-repelling.

So our house is now radiating snake terror waves in all directions. I never really minded the non-venomous snakes like rat snakes, but honestly I don’t think we ever had any permanent residents, and at the rate they eat rats it wouldn’t really ever make a dent in the rat population when it swells up from time to time.


February 5th, 2009

I am not a South Asian person

If this is good at all, it’s because I’ve read some cookbooks and tried a few things. Maybe this stuff shouldn’t be called “dal” because it contains or fails to contain certain key things. Whatever. Cook at your own risk. The end goal is a bowl of mush, more or less, so in my opinion there’s a lot of leeway.


My local HEB now carries “channa dal” and “toor dal” dried split beans. I think they’re tasty. They come in 2lb bags. I suspect that at a real South Asian grocery they might be less expensive, but at less than $3 for 2 pounds of dried beans it’s still inexpensive food.

Chickpeas work too, and those are available everywhere. Yellow split peas tend to get a little mushy, but it’s dal so that hardly matters. Green lentils work fine too. Heck I bet pinto beans would be OK though because they’re not split they’re going to require a long soak and more cooking time.


Mr. McGee points out that with dried beans, it takes a lot longer for moisture to get into the bean than for heat. That’s why soaking is helpful. For split beans like the Indian dals or yellow split peas, I’ve found that pouring hot water over them an hour or so before cooking is plenty of soaking time. Chickpeas require a lot more.


This is not so much a recipe as a process description. There are several “parts” to the dal:

  • Spices
  • Aromatics
  • Beans
  • Liquid/stock
  • Finishing Touches

The spices will be the place where you can experiment or guess and develop experience. What I combine in a dry little skillet is a mix of cumin seed, caraway seed, fenugreek seed, ajwain seed, clove, and coriander seed. Cumin and fenugreek and coriander are usually in equal parts, then a little caraway, 2 or 3 cloves, and the ajwain (which is really optional – it tastes like thyme and caraway basically). For a moderately large pot of dal (I think it’s impossible to make less dal than enough to feed four or five people), the total amount of these seeds is about three tablespoons, maybe a bit more depending on how much you like that sort of thing. Fenugreek is pretty important in my opinion, because it really goes well with the taste of the legumes themselves.

So I heat those up in my dry little skillet until they just start to give off some smoke, tossing them around a couple times. Get them off the heat quickly, and then grind them up in a spice grinder or a mortar & pestle (a pain). Set them aside.

In your cooking pot (a big saucepan with a lid), warm up some oil or ghee or a mix of oil and butter; about 3 tablespoons (or more if you like rich dal). When it’s kind-of hot, toss in some brown mustard seeds (maybe a teaspoon). Don’t do it yet however because you need to read the next paragraph.

The “aromatics” are a mix of onion, carrot, garlic, peppers, and (optionally) celery. I don’t know if celery is traditional in India but it’s part of the classic mirepoix so I use it sometimes. Don’t use too much garlic; in fact you can use asafoetida instead if you like. Believe me I love garlic but it just doesn’t balance well in this dish if you use too much. As to peppers, you can use a couple of serranos or jalapenos, or you can add dried cayenne to the dish; it’s not super important. You don’t have to make it spicy at all of course. Whatever you choose, chop it all up in a food processor into little bitty pieces but not a paste.

Now you’ve got a food processor full of dal mirepoix and a hot pan with hot fat and you’ve just tossed in the mustard seeds. Those guys will pop and splatter pretty quickly. Let them roast in the fat for 10 or 15 seconds, then add in the aromatics. Stir those around to let them soften up, like five minutes or so depending on your stove and pan etc.

For a family-sized pot of dal, you’ll want about 1.5 to 2 cups of dried beans. (I should admit that I always make way too much of this stuff but it freezes OK.) Once your aromatics are soft, you can drain your soaked beans and add them to the pot, stirring. An important ingredient to add now also is tomato. You can go with a small (14-16 oz) can of diced tomatoes, or you can add three or so fresh diced tomatoes. They make a big difference, really.

The spices have been waiting patiently in the spice grinder or somewhere. What I like to do is grind them up as finely as I can in the grinder (I have a $10 Proctor-Silex coffee grinder I got at HEB), and then sift them through a fine steel seive. Some of those seeds have crunchy husks that won’t ever soften up in the pot, and they’re unpleasant. Sifting the spices works pretty well – just shake them over the pot and you’ll collect some not-very-fine ground spices in the seive, and the fine powdery stuff will drop through. You can re-grind that if you like but usually I’m sick of dealing with them by this point.

OK now you just need to add some liquid to the pot and let it go. I generally use plain water but you could use vegetable stock I guess. Split beans will take about 30 to 40 minutes to get nicely done, while chickpeas will take considerably longer. Make sure the liquid level stays up. If you like, towards the end of cooking you can add a can of coconut milk (authentic? no clue, but it makes it rich).

Finally the finish. I have gotten really fond of adding spinach to stuff like this – it’s easy and you get a pretty finished product that’s that much better for you. Just slice up some washed spinach into little slivers and dump it in the pot about 5 minutes before you’re ready to serve it. Stir it around and the spinach will cook immediately.

Check for salt and serve with brown rice, or white rice, or anything you want.

Weird Dream

January 23rd, 2009

Hey all this talk of The Gaff reminds me that I had a weird dream last night. I dreamed that there’s a tribe, or region of tribes, with a quirky “traditional culture”. I think it’s somewhere in Minnesota where there are lots of primitive natives. These people have a strange relationship with a species of large sea turtle. It seems that the human women of the tribe(s), as a regular cultural activity, surrender their very young female daughters to the male sea turtles, for the turtles to have their way with them. The turtles do their thing, with tongues lolling out, and then subsequently they waddle over to the ceremonially reclining human mothers and cuddle for a while. That ritual complete, the male turtles are sufficiently primed to be willing and able to fertilize the clutches of eggs laid by the females of the species in the meantime. The turtle eggs are watched by the tribespeople, and towards the point of hatching they’re actually played with by the tribal children. Some scientists speculate that this play activity acts to stimulate the still-developing brains of the unhatched turtles, doing them good and readying them for a long journey out to sea.

When hatching time is nigh, the elder men of the tribe(s) carry the eggs carefully over land, clear across Wisconsin to Lake Michigan. The turtle eggs are placed on a particular holy beach and allowed to hatch on a summer night. The baby turtles wiggle their way across the sand, down to the lake water, and begin their voyage out to the cold North Atlantic. Years later, they return to be greeted by tribal elders on another ritual evening, and are carried back to the village for the cycle to begin anew.

This may seem shocking to us, but it is a working symbiotic relationship between man and para-reptile. Both cultures appear to be nourished by their activities.

Port Aransas

January 23rd, 2009

Another winter, another trip to Port Aransas. I accidentally went through Nixon again this time, but a trip to Nixon is always a pleasure anyway.
Nixon, TX mural

The nice thing about Port Aransas at this time of year is that it’s so empty. The beach is huge and surprisingly clean for a place like this (that is, a dump). There are lots of northern-midwesterner old people around for birds and warm weather and all-you-can-eat pizza buffets, but they’re not at the beach much.
Photo of empty beach

Spent five and a half hours on the Lexington with Christopher. While eating lunch (on the ship) we figured that that was probably at least the fifteenth visit. This time was important because they just recently moved a couple of WWII-era 5″ gun turrets from an old destroyer being junked in Brownsville up the intracoastal waterway to Corpus. During the war (in other words, as originally built) the ship had four such turrets on board. They were removed after the war during a major refit in the early 50’s.
Photo of Christopher on the Lex

There’s a restaurant here called “Shells” that’s about the size of a typical garden shed. We went there for dinner on Wednesday, and the food was surprisingly, almost shockingly in fact, great. It’s like somebody who really knows how to cook went slightly crazy and set up shop cooking for retirees and weirdos like us.

The kids can spend arbitrary amounts of time at the beach. Pat and Allie worked hard to rescue a number if imperiled “beach roaches”, which looked like ordinary roaches to me. The built little habitats for them.
Beach roach rescue

We’re headed for The Gaff today, and I’ll report back on how the place is doing. We’re too early in the year for the belt sander races.

The Gaff update

Well The Gaff does not disappoint. We had to park around back because the city had dug a giant trench across the front parking lot. That meant we got to see the famous Pirate Day Gaff float.
Photo of float

It’s a beautiful day and yet nobody’s eating on the outdoor patio. Warm sun, cool breeze.
Photo of The Gaff

Allie and Pat and Christopher all worked on the ceiling tile we bought.
Photo of kids decorating tile

We were lucky to get a table right in front of the racing belt sanders of The Gaff. The sanders won’t be competing again until April.
Photo of racing belt sanders

Hyde Park “Falafel Burger”

August 21st, 2008

Yesterday I lunched with friends (which is to say, with the audience of this site) at Hyde Park in Austin (the old one). It’s required of those living in Austin to like, even adore, Hyde Park, and I do like it. The people there are really nice, at least, and it’s a fun place to meet.

I ordered the “Falafel Burger”, and was rewarded with a beautifully-formed slab of falafel on a bun. The presentation was OK, in the sense that it was interesting to look at, but seriously guys you can’t really think that’s a success. The falafel stuff itself was fine, though not as good as the almost disorientingly fantastic falafel at Sarah’s. The problem is that the material qualities of a block of cooked falafel turn the whole “sandwich theorem” on its head.

You collect food into a (traditional, “western”) sandwich when the foodstuff you want to eat can’t be picked up and held without either falling apart or being a greasy mess. The bread provides a non-gross, grippable container for the internals. The unfortunate bun surrounding my falafel, however, was faced with the serious challenge of containing the fried falafel puck over the lifespan of the meal. It basically failed; it would have fallen apart much sooner had I more liberally applied the yogurty sauce served alongside the sandwich. The falafel itself was so solid and firm that the bread experienced considerable kneading as the sandwich was consumed.

Now, as I said, the falafel itself was fine, and for that matter the bread was fine too. But the architecture of that dish is just wrong. Make the falafel in little chunks like the people who live on the stuff do – they’re the subject matter experts. Wrap it up in something like pita (and by the way I’ve been thinking lately how cool it is that the word “pita”/”pizza” is such a universal accross the Mediterranean) and drop the whole “burger” idea. Try as I might I can’t think of a way to harmonize the structural nature of fried falafel with bun-based delivery systems.

In a way, I think that “veggie burgers” in general suffer from the same problem. However most vegetarian “patties” designed for sandwiches are a lot thinner than the falafel in that Hyde Park sandwich. Cooked ground beef tends to be more pliable than a veggie patty, and of course sliced meat is a whole different story, being very bendy and yet having plenty of tensile strength.

The Hyde Park fries were good. I feel guilty that I consider the fries at the Boat House Grill to be better, though for all I know they’re fried straight out of the commercial wrapper they come frozen in.

Finding primes with Erlang and Clojure

July 1st, 2008

A couple of bogus prime sieves have shown up in the blogorama lately. After reading a very interesting paper about the authentic prime sieve algorithm, I became kind-of hooked on implementing it. The paper is great but the examples are all in Haskell, and I can’t really understand that too well. However I did manage to figure out the basic point.

The “wrong” prime sieve implementations all operate by accumulating a list of known primes, and then testing candidates by seeing whether they’re divisible by any of them. If not, then the candidate must be prime. It’s only necessary to test from 2 through sqrt(candidate) of course. Well maybe not “of course” but that’s the way it is anyway. Thus the time bound on that approach is O(n sqrt(n)), sort-of, since prime numbers are pretty uniformly distributed along the natural number line. (Note: the preceding claim about prime distribution is incorrect, but as the algorithm doesn’t take density of primes into account the time bound (in terms of numbers tested, not number of primes generated) is about right I think. Thanks Cybil!)

The “right” prime sieve is different (duhh). What it does is keep track of the composite numbers implied by each known prime. In other words, once (in the degenerate initial case) you decide that 2 is prime, you know that all multiples of 2 (starting with 4) must not be prime. As you work upwards through candidates, you know a candidate is prime if it is smaller than the smallest composite number you know about so far. This approach is the “right” approach because, if you do the “what’s the smallest composite?” part properly, you end up with an O(n log n) algorithm and that’s a lot better than the wrong way.

The way to do the “what’s the smallest composite” test is to keep the composite lists (that is, one list per known prime) in a priority queue. In this case, it’s possible to cheat a little with adding primes to the queue because it’s going to be the case that the first composite implied by a new known prime is always a bigger number than any other known composite. That’s probably provable but I don’t feel like doing that now.

Implementing the priority queue in a language like Erlang or Clojure (well one could cheat in Clojure but I didn’t want to) requires that it be done with some sort of functional data structure. In Java (and I did do a Java version but it’s ugly and boring) you can use an array list to store a “heap” for the queue, and inserts are super easy because you just drop your new composite stream in the next available slot of an ArrayList. In the trendy functional languages, however, you can’t do that.

What I came up with (probably after several billion other people did) was to use a functional (immutable) tree structure that I could rebuild when doing an “add” operation. The trick is to consider what’s going on with the ArrayList cheater approach. If you’re dropping something into the next available slot at the end of the heap, well what does that look like if you visualize the heap as a tree? You can work your way up the tree by repeatedly dividing that slot index by 2 until you get to the root. Each time, you know that if the remainder is an odd number you’re moving up a right link, and if it’s an even number you’re moving up a lefft link. Thus by looking at the binary representation of the heap slot index (backwards), you have a little “path” descriptor that’ll guide you straight from the top of the heap down to the next empty slot.

So in Erlang I represent the priority queue as a tuple with the current queue size, and the heap. The heap is also a tuple, containing the top node and the left and right children – recursively, also tuples. Each node is a tuple containing the prime number, the current known composite, and a counter to generate the next composite.

-export([add/2, primes/1]).

% Primes
np(Prime) -> {Prime, Prime * Prime}.
next({Prime, M}) -> {Prime, Prime + M}.
cur({_Prime, V}) -> V.

The queue utilities:

% The priority queue
newQ() -> empty.
leaf(P) -> {P, nil, nil}.
sz(empty) -> 0;
sz({Sz, _T}) -> Sz.

% Find where to put a new prime (end of the queue)
path(N) -> path(N, []).
path(1, L) -> L;
path(N, L) -> path(N bsr 1, [N band 1 | L]).

% Add a newly-discovered prime
add(empty, Prime) -> {1, leaf(np(Prime))};
add({Sz, T}, Prime) -> {Sz + 1, add(T, Prime, path(Sz + 1))}.

% ... follow the path to the nil!
add(nil, Prime, []) -> leaf(np(Prime));
add({P, L, R}, Prime, [0 | Path]) -> {P, add(L, Prime, Path), R};
add({P, L, R}, Prime, [1 | Path]) -> {P, L, add(R, Prime, Path)}.

val(empty) -> nothing;
val({P, _L, _R}) -> cur(P);
val({_Sz, {P, _L, _R}}) -> cur(P).

Now there are two things to do when cranking through candidate primes. If your candidate is in fact a prime, you need to add it to the queue (in the form of one of those tuples). If it’s not a prime, you’ve “used up” the minimum known composite number so you need to get a new one. Well it turns out that of course your primes will sometimes generate overlapping composite numbers – both 2 and 3 will give you 12, for example. Thus when you need to “bump” the prime queue up to the next useful value, you need to keep working until the new minimum composite number is bigger than the one you just threw away.

To “bump” the queue, then, we’ll roll to the next composite provided by the prime at the top of the queue. But now of course the heap may not be a heap, so we need to “fix” it. The “bump-fix” needs to repeat until we’ve got a good new minimum.

Thus, the “bump” code:

% Gen next composite number from topmost prime, adjust heap
bump({Sz, T}, N) -> {Sz, bumpt(T, N)}.
bumpt({P, L, R} = T, V) ->
  case cur(P) of
    Vp when Vp =< V -> bumpt(fix({next(P), L, R}), V);
    _ -> T

% adjust heap by swapping primes down until it's a heap again
fix({_P, nil, nil} = T) -> T;
fix({P, {Pl, nil, nil}, nil} = T) ->
  case {cur(P), cur(Pl)} of
    {V, Vl} when V < Vl -> T;
    _ -> {Pl, {P, nil, nil}, nil}
fix({P, {Pl, Ll, Rl} = L, {Pr, Lr, Rr} = R} = T) ->
  case {cur(P), cur(Pl), cur(Pr)} of
    {V, Vl, Vr} when V < Vl, V < Vr -> T;
    {_V, Vl, Vr} when Vl < Vr ->
      {Pl, fix({P, Ll, Rl}), R};
    _ ->
      {Pr, L, fix({P, Lr, Rr})}

The main “primes” routine (which just counts primes up to some limit) is therefore:

primes(Max) -> primes(newQ(), 2, Max).
primes(Q, N, Max) when N >= Max -> sz(Q);
primes(Q, N, Max) ->
  primes(case val(Q) of N -> bump(Q, N); _ -> add(Q, N) end, N + 1, Max).

I did this up in Scheme, and it was kind-of messy and gross. Of course I don’t really know much Scheme, but the hurdle was the representation of the prime tuples and stuff like that. It took a lot of ugly little “(caddr foo)” functions.

Then I moved on to Clojure. Clojure is a neat-o Lisp dialect that runs on the Java VM. Here I’m not really exploting any Java stuff. I did however exploit some of the useful built-in “lazy” features:

(def countprimes (fn [Max] (let
    ; The representation of "composites from prime P" is a
    ; Clojure lazy sequence, made by mapping a function to
    ; multiply the prime by each of a lazy sequence, counting
    ; up from the prime.
    countFrom (fn [Start] (iterate #(+ 1 %) Start))
    composites (fn [Prime] (iterate #(+ Prime %) (* Prime Prime)))
    ; Tools for manipulating the queue
    newQ #^{:size 0} [nil nil nil]
    szQ (fn [Q] (get ^Q :size))
    curMin (fn [[Top Left Right]] (if (nil? Top) nil (first Top)))

    ; Add a newly-discovered prime to the queue. This entails making
    ; a new "composites" sequence and dropping into a new leaf node
    ; at the end of the queue.
    addPrime (let
        ; Binary representation of N, backwards
        path (fn [N]
          (reduce #(list* %2 %1) ()
            (for [n (iterate #(quot % 2) N) :while (> n 1)] (rem n 2))
        ; Follow the path to the leaf
        addr (fn addr [Np [Top Left Right] [LR & Rest]]
          (if (nil? LR)
            [Np nil nil]
            (if (== 0 LR)
              [Top (addr Np Left Rest) Right]
              [Top Left (addr Np Right Rest)]
      (fn [Prime Q] (let [newSz (+ 1 (szQ Q))]
        (with-meta (addr (composites Prime) Q (path newSz)) {:size newSz})

    ; Get a new minimum composite, after detecting a non-prime
    bumpUp (let
        ; Make sure the heap really is a heap. Note that there'll
        ; never be a node with nil on the left and non-nil on the
        ; right.
        fix (fn fix [[Top Left Right :as Qfixed]]
          (let [[LTop LLeft LRight] Left [RTop RLeft RRight] Right]
            (if (and (nil? LTop) (nil? RTop))
              (if (nil? RTop)
                (if (<= (first Top) (first LTop))
                  [LTop (fix [Top LLeft LRight]) Right]
                (if (and (<= (first Top) (first LTop)) (<= (first Top) (first RTop)))
                  (if (<= (first LTop) (first RTop))
                    [LTop (fix [Top LLeft LRight]) Right]
                    [RTop Left (fix [Top RLeft RRight])]
      (fn [Comp Q] (let [sz (szQ Q)]
        (with-meta (loop [[Top Left Right :as Qbumped] Q]
          (if (< Comp (first Top))
            (recur (fix [(rest Top) Left Right]))
        ) {:size sz})

    ; It's either a new prime, or it isn't.
    tryNumber (fn [Q Candidate] (let [min (curMin Q)]
      (if (nil? min)
        (addPrime Candidate Q)
        (if (< Candidate min)
          (addPrime Candidate Q)
          (bumpUp Candidate Q)
  (get ^(reduce tryNumber newQ (range 2 Max)) :size)

Because Clojure supports some "decomposition" forms that make it easy to chop arguments up (though not quite as easy as in Erlang), it's somewhat neater and less noisy than my amateur Scheme version. Also in Clojure I can carry the queue size around as a meta property of the queue heap, though there's some weirdness about that which I don't completely understand. (Note - I cleaned up the Clojure source a little bit just now, and added some comments.)

The Erlang version is faster than the Clojure version, if anybody cares. I strongly suspect that both are much faster than the "check for prime factors" wrong sieve implementations. Note that in these the operations are all adds, compares, and multiplies - there are no divisions or square roots to compute.

Update: Thanks, qebab, for the hint, and I've now gotten rid of the useless multiplications in the composite iterations.

Median of 2 sorted arrays

May 4th, 2008

A nice young man wrote about working on an algorithm problem after being inspired to think thusly by his new copy of The Algorithm Design Manual. Coincidentally, I recently received my copy of the book as well. I was less inspired than Mr. Torreborre, probably because I’m very lazy. I thank him for presenting his interview question, because that got me to thinking yesterday morning. How would I find the median element of the merger of two sorted lists without actually doing a (linear) merge?

I’m now typing in what’s been going through my head, mostly while cooking breakfast for my kids. I contemplated trying to explain it to them, but I decided against it. Over the course of the explanation they would certainly concoct a variety of theories about why I was trying to punish them in such a strange and tedious way. I haven’t gone to search for a result in the book or on the web; maybe that’ll be obvious after you read this. I’ll check later.

First, I’ll say the median element of a sorted list afirst … alast is afloor((last-first+1)/2). In other words, it’s the element right in the middle (rounding down – arbitrarily – if the list has an even number of elements). So for this problem, I’ve got two lists, a and b, and I want to know what element would be smack in the middle of the list resulting from their merger.

I went around in confused circles for a while before hitting upon (what I think to be) a good way to view the problem. I know what the size of the merged list would be – it’s the sum of the sizes of a and b. Thus I know exactly where the median value will be in the result. However, all I know about the result list is that it’s a muddle of values from the two original lists. For any index i in the merged list, all I can say is that the value will be from either a or b.

Now, there are a few cheap things I can do to examine my lists. Looking at an element at a given position is cheap – well, at least, I’m going to declare it to be cheap. So, for example, I can look at the median of either source list, or at the first element, or the last. Another thing I can do, less cheaply, is to find where a number would go in one of the source lists. That’s an O(log2 n) operation (with n being the list length).

If I think about a couple of ordered lists of numbers (with no known bounds on the values in the lists), it’s clear that one list may have values larger than any value in the other, or smaller than any value in the other. If I take at the smaller of the two last values in my source lists (that is, alast and blast), and then find where it would go in the other list, I now know something really interesting: I know exactly what values occupy the positions at the end of the merged list! That is, if alast is smaller than blast, and I find that it would 100 numbers down from the last element of b, then I know that the last 100 elements of the merged array have to be the last 100 elements of b. Of course I can make the same discovery at the bottom ends of the lists.

In the degenerate case, one list might contain nothing but values completely beyond the end of the other list. In that case, I can immediately find the median of the combined lists because the merge is easy. If it’s not, then with 2 log n operations I can snip off some of both lists. Now, some portion of the low and high ends of my hypothetical merged lists are no longer muddled – I know that those portions contain values from one of the two lists. In fact, I can now see what my goal is: I need to get to the point where the median slot – the position smack in the middle of the hypothetical merged list – is not muddled.

So now I have two sublists of the original lists, which represent the “muddled middle” of the hypothetical merged result. Hmm. I’m not liking this approach, because I’m not lopping off sufficiently big chunks of the problem. Well, they might be big, but I’m not forcing any bigness; I’m just whittling the ends of the lists down, and the rapidity with which the lists get smaller is entirely dependent on the values in the lists. I need to get a little more radical. (I do still like checking to see whether one list lies completely beyond the other, however, at least for now. It’s cheap to do.)

Another thing I can do cheaply is look at the median of one of my lists, and then I can see where it’d go in the other list. If I do that, then I will definitely lop off half of one list. I’ll still have a muddled result, except now I know a little bit more: I now have four lists, not two, and by looking at the combined sizes I’ll know that two of those can be forgotten. Now that’s looking good, because on every iteration I’m throwing away half of one list and at least some of the other. I’ll always pick the larger list to be the one I cut in half of course. Eventually, I’ll get to the point where one of the two lists lies completely beyond the other, and then I’m home free.

Coding up something like this makes me feel uncomfortable. I fear “off by one” errors the way some people fear spiders. Sitting here now I can conjure up a vision of working through the day on this stupid thing. I know that I really should try. One thing that’s clear is that it’d be silly to do it in a fun language like Erlang, because it all depends on it being O(1) to look at values in the lists. (Well I guess I could merge two Erlang binaries, treating them as arrays of integers, but compounding my off-by-one fears with the need to essentially code up my own array indexing routines really freaks me out.) I’ll try not to be lazy and do this in Java or something boring like that, at least.

Well I just checked this blog by a smart person and he does this a totally ‘nuther way. I don’t have enough glucose left in my blood right now to figure out which is better, but I bet his is because he doesn’t have to do any searches. He has a weird definition of the median though in the case of lists with an even number of elements. I’ve always thought that the median value has to actually be in the data set, because otherwise there can be an arbitrary number of median values. I’m no statistician however. It probably makes no difference at all for this problem.

Later still…
I’ve been putting together a model cannon kit whose instructions are basically “glue it together”. My eyes are sore. Anyway, to the extent that I can get a lame approximation to the stuff I wrote above working, I think it’s still interesting. In the case of a significant disparity in list sizes, mine converges really quickly on the median because it chews up the shorter list very quickly. When the lists are pretty dense and about the same size, it takes about log n iterations. I’m not sure how to figure the bounding function – maybe it’s log n but maybe not (I suspect the later but I’m dumb).

Quote your angle brackets

April 29th, 2008

Here’s a neat fact: both IE and Firefox will find a </script> tag in the middle of a Javascript string constant. Now that’s probably not too surprising; the browser sort-of has to do that, or else a missing quote in a script block would eat the whole page. This came up in my universe however when I was doing some testing on a page I suspected wasn’t quoting stuff properly.

Any web-oriented templating mechanism (or, more generally, anything spewing out HTML programmatically) will have to worry about what to do with external data that needs to be dropped into the HTML. When it’s going into HTML code, like this:

  <label>Name:</label> ${}

then you’ve got to translate angle brackets and ampersands to HTML entities “&lt;”, “&gt;”, and “&amp;”. However, when you’re dropping stuff into portions of the HTML document that are actually Javascript blocks (for example, when populating a data structure), you don’t do that. Instead, you have to massage the value so that it works inside a Javascript string constant (well, that’s what you do if you want to put it in a string constant, at least).

Our library has an “escapeJS” routine that does that sort of quoting. What it worried about (up until about 30 minutes ago) was quote characters, backslashes, and characters outside the old 7-bit printable ASCII range. Of note, it did not worry about less-than characters (left angle bracket, that is). I stumbled over this because I was getting a weird complaint from Firefox:

  whatever = "${mylib:escapeJS(whatever)}";

The error seemed strange because it was about the string being unterminated. When I brought up the source, however, the whole thing was there (including an embedded “</script>” in the string – remember, I was doing XSS testing). “Durrr,” I thought to myself. “What’s Firefox doing?” Embarrassingly it took me some time to get it. I thought that maybe it was a Firefox 3 thing, but no. When I saw that IE did it too, the feeble 20-watt light bulb went on.

I updated the “escapeJS” routine so that it treats less-than characters the same as control characters, encoding them with the Javascript “\u” notation. Probably everybody else in the world is less dumb than me, but nevertheless I figured I’d write this up.

PS: Ha ha I just realized that this is another “spring bug.”

Spring Bugs

April 14th, 2008

Yesterday was very pleasant, so I got out the Sigma macro lens and the “ring flash” and started looking for bugs. The first thing I found was a small spider on some big rosemary plants. He seemed to be repairing a web.

As usual I have no idea what sort of spider that is. The bright orange mark is what caught my eye. I think I’m going to send the photo in to What’s That Bug to see if they know. (Well now I know: it’s a Leucauge venusta, an “orchard spider”. This morning the web is looking very nice and neat.)

The Monarch Butterfly thing this year is weird. They’ve been all over the place, and in particular they found the newly-emerging milkweed in our back yard.

This one is getting started on a whole new milkweed plant, since he and his friends ate the leaves completely off the other plant. They and the black swallowtails are pigs.

Green beetle in a rose:

Bee on some marjoram: