In the book Structure and Interpretation of Computer Programs, there is a Scheme implementation of Fermat's test for primality. This is known as Fermat's Little Theorem. In a footnote, it is mentioned that there is a rare category of little understood numbers known as "Carmichael numbers." These obscure little beasts will actually generate false positives for Fermat's test.
From a mathematical standpoint, Carmichael numbers demonstrate that Fermat's test is not sufficient for determining whether or not a number is prime. However, when using a "correct" algorithm, the odds of cosmic radiation causing the computer to generate an incorrect result are less than the odds that the number you're testing for primality is a Carmichael number. Thus, from an engineering standpoint one might argue that the "incorrect" algorithm is the better choice because in the real world, it Gets Things Done.
There's an excellent reason why there are more engineers than mathematicians. We need to Get Things Done. I suspect that many computer programmers would prefer to be the mathematician but are forced to be engineers. Heck, some of us are apprenctice carpenters who aren't qualified to pick up a hammer without guidance.
As for myself, I think I'm an engineer who dabbles in mathematics. I want to know why things work the way they do and what the "correct" way to do things is, but I also have to Get Things Done. If using the "wrong" theorem lets me do that, I'll cheerfully smile and be wrong if the "right" theorem causes more problems than it solves.
Incidentally, this is yet another benefit of testing. Yes, someone else can argue that your code is awful (and you may know your code is awful), but having ugly working code versus their beautiful non-working code is a very strong rebuttal. Then the tests let you turn it into beautiful code.
Two students, a math major and an engineering major, are asked to generate a sequence of prime numbers.The math major draws out a sieve of Eratosthenes and slowly gets the sequence 2 3 5 7...
The engineering major calculates the first few primes and extrapolates the rest: 2 3 5 7 9 11 13 15...
Re:Engineers and Prime Numbers
VSarkiss on 2005-01-05T19:00:25
The way I heard it, there was also a physicist, who piped up between the mathematician and the engineer. Her sequence went:
2 is prime
3 is prime
5 is prime
7 is prime
9 is, erm, an experimental error
11 is prime...
By the way, what you said about cosmic radiation is correct, and probabilistic primality testing algorithms are indeed used in practice. However, I believe there's some refinement of Fermat's theorem that suceeds on Carmichael's - maybe by detecting them, I don't quite remember.
Re:sicp
Ovid on 2005-01-05T17:40:24
You are correct. There is a refinement that handles Carmichaels correctly, but I don't recall what it is and I don't have the book handy. And yes, SICP is fantastic. Fortunately, everyone can visit the link I provided above and download a free copy
:) Re:sicp
ajtaylor on 2005-01-05T20:31:45
And there is also a series of lectures on video based on the first edition of the book. Very interesting stuff. http://swiss.csail.mit.edu/classes/6.001/abelson-sussman-lectures/Re:sicp
ethan on 2005-01-06T07:46:29
There's a number of prime-tests based on Fermat's first theorem. Miller-Rabin test is a Monte Carlo algorithm that has a very high probability of finding the correct answer if you test maybe 10 or so witnesses (which is a fairly cheap operation). But then, for very large numbers this test (AFAIR) assumes that Riemann's assumption, that has been unproved for almost 150 years, is true.
The other one is the Agrawal-Kayal-Saxena test which is deterministic and avoids the Riemann assumption. WithO(log^10.5 n)it's slower than Miller-Rabin, though.Re:sicp
ziggy on 2005-01-05T21:15:14
Speaking of SICP and elements of physics like cosmic radiation, I just have to mention SICM.:-)
The analogy as it is misses a fundamental point: it's not a mathematician's job to get things done. It skips over the fact that without past mathematicians' relentless pursuit for correctness, the engineers of today wouldn't have any better tools than those their ancestors worked with.
There is a divide between those building solutions and those crafting tools. You should know which camp you are in, or you're going to be ineffective. An engineer's methodology is as inappropriate for a mathematician as vice versa.
Re:Goals
drhyde on 2005-01-06T10:14:34
It's also worth noting that good engineers *know* that their solutions may not be perfect, but they still find it useful to have an idea of how imperfect they are. If only to justify their shortcuts to their bosses.
