Re^2: Problem Domains and Multiple Disciplines

[danderson]

First things first: the story about Gauss and the schoolteacher was in my high school math textbook, so I'm inclined to believe it. On a nifty note, while he recieved it at age 10, I recieved it on a Math entrance exam in grade 8 at age 13 - and came up with the same algorithm. Of course, I also confirmed it with my calculator afterwards (I thought I was smart, but I also didn't trust myself). A couple of years later I read the story of him coming up with it (and getting whacked because the teacher didn't believe he'd summed them), and I've been unneccesarily proud since.

On a more on-topic note, there's a sig I see quite often that says "algorithm, algorithm, algorithm." I fully agree; this is not a "how do you approach it" question, but a "how well do you approach it" question. Analysing the problem and finding the best solution is part of writing good code, whether you call yourself a coder, a programmer, or a computer scientist.

As for mathematicians with lovely O(N) solutions - a bigger problem is not size of N but size of constants. As an example, primality testing can now be done in polynomial time - a huge breakthrough for mathematicians - but in practice number sieves that give ~99.999% accuracy in constant time are used. There are great (in terms of O())solutions for lots of problems that have constants in over ten digits, but worse solutions with constants under a hundred that are used almost exclusively in practice. (It's been a while since I took an algorithms course, but I remember there were a couple of really good examples, even if I can't remember what they were.)

I think Thompson's "when in doubt, use brute force" quote is fine - when making the first iteration of something. After all, it'll work. If anyone's tried using MS's Indexed Search and had it fail with a false negative, this is familiar - better traditional but correct than convoluted and fancy and purportedly better, especially when building small 'blocks,' since then when the blocks are weaved/welded together to make a complex whole, the interesting behaviour is where it should be - in the weaving/welding code, not in the basic blocks.

As for mathematicians and their ilk being poor programmers - sure, quite often, but at the same time it's normally fixable. Eg, they'll have something written inefficiently, but it'll be something like not freeing memory when they're done with it, or recursing but not tail recursing, or the like. Easily fixable. They rarely make fundamental mistakes - writing code that does it, but does it in a way that no matter what cannot be efficient.

And - known facts? If told, using basic integer math, to find all divisors of a number N, what would you do? Loop through 1 to N, finding the remainder, and whenever it's 0 saving the result? No, you'd save the result at 0 and then divide by that number to get a second divisor, and stop at sqrt(N). It's reasonably obvious. Now, if he was asking for something truly from another field, for instance the surface area to volume ratio of a strange solid, then sure. But we, as programmers, don't get that every day. We do, quite frequently, get "from i to n, do X" - even if X is a simple sum - and we should be able to handle slightly offbeat questions along those lines without any difficulty.

[hardburn]

As an example, primality testing can now be done in polynomial time - a huge breakthrough for mathematicians - but in practice number sieves that give ~99.999% accuracy in constant time are used.

This reminds me of a recent post on http://lambda-the-ultimate.org where (twards the end) the author makes a comment on "Physics vs. Mathematics" (the thread it's attached to is a rather interesting debate on modern type systems). Math majors would rather have their toenails chewed off by chipmunks than use a theorum that wasn't completely true for every little edge case. But a Physics major (and Engineering majors, too) almost have to in order to get work done.

Orbits of planetary bodies comes to mind. Newton presented some simple equations that almost, but not quite, fit the data (he passed this off as God fiddling with the universe). Einstein gave a much more complex equation that perfectly fit the data. However, Newton's equation is still prefered by Physicists because it's easier to work with, and the minor differences in the outcome usually don't matter.

As programming is more or less an Engineering discipline, we can often get away with things that aren't mathmatically pure. I suspect that good programers know their math, but also know when to throw it away.