The Quest for an Accelerated Population Count

[[deleted user]]

Ah, back to my kind of chapter. Again, I really enjoy seeing simple problems dissected, beginning with the obvious solution and then stepping through successive refinements with interesting reflections on the associated costs and benefits. I think that the divide and conquer technique is particularly elegant.

As an aside, I am also re-reading the Steven Levy book "Hackers" (now out in the 25th anniversary edition), which brought me back to the days when the primary programming task was to do the kind of machine instruction analysis and optimization described in this chapter. I wonder how few people care about this anymore (and have the skill to do so), given the abundance of CPU power, the state of compiler optimization technology, and the already crowded undergraduate curriculum that increasingly leaves out this kind of analysis.

[Erik]

The code examples between paragraphs are very helpful. I can usually look at the code and find more purpose and meaning than from the paragraphs.

This type of problem makes for a great academic exercise, but most business applications would be satisfied by the obvious solution. I wrote several obvious Block Coding, Hamming Codes, and Checksum functions in my company's applications. When applications get profiled for bottlenecks, these functions never come back as problem areas. Business deadlines seldomly allow for time to research and develop solutions like the divide and conquer technique.

I think undergraduate math classes do a good job of preparing students for traditional sciences like Chemistry and Physics. I don't think math classes do a good job of preparing students for computer science concepts. I think this is why concepts like this chapter and Quicksort are so hard for students to comprehend especially when combined with new programming language syntax and datastructures. That's like trying to learn Physics and French in the same class.