January 05, 2005
Carmichael Numbers... Mathematicians v. Engineers
This is one of the serendipitous posts I stumble across because I have a “Keyword Search Subscription” set up in my NewsGator Online Services account to continually monitor weblogs and other RSS feeds looking for mention of my last name (narcissistic, I know but to those who know me this is not a surprise.) Usually this search parameter returns articles mentioning a variety of subjects relating to Carmichael California, Ricky Carmichael (the motocross star), Hoagy Carmichael (the famous song writer… not my father who also is named Hoagy) and on occasion Stokely Carmichael (the violent activist of the 60’s). But today I ran across this relating to of all things, “Carmichael Numbers.”
Now I had heard of these somewhere in my distant past in a Cosmology and Gravitational Collapse course I took in college. But until this afternoon I had delegated knowledge of “these obscure little beasts” to what I thought was a brain cell surely destroyed by a Scotch or two. What I love about this post is that many of my engineer friends will no doubt agree that this is an aptly named number, having known me for years. I am notorious for arguing a (in my mind) well constructed point only to look at one of my engineer friends and hear him reply… “And your point is?” And then he proceeds to go on his merry way and succeed in whatever endeavor I was arguing couldn’t be succeeded at doing it “his way.”
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 apprentice 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.
I think I revel a bit in how these numbers are referred to in this post…
· “a rare category of little understood numbers known as "Carmichael numbers,”
· “obscure little beasts,”
· and my favorite “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.”
TrackBack URL for this entry:
Listed below are links to weblogs that reference Carmichael Numbers... Mathematicians v. Engineers:
That's the response I was expecting... sort of... in a Heisenberg-ish kind of way.
Posted by: John | Jan 11, 2005 2:48:38 PM
And your point is?
Seriously, this seems to smell a little fishy...maybe just the way it's written (by an engineer/mathematician):
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
So he's saying that the odds of an incredibly unlikely event are LESS than the odds of finding a Carmichael number? Aren't MOST things better odds than the cosmic radiation interference odds? I need numbers! It's sort of like saying you are more likely to eat lunch today than of you turning into a pumpkin at midnight.
On the bright side, it does seem to be an apt name for a phenomenon that says to make it work do it wrong.
By the way if you convert the entire text of your post into ASCII, and then into Binary, and then back to ASCII, you can regenerate the identical post! But it doesn't Get Anything Done.
(this comment brought to you by the letter Epsilon and the number i, and one ornery engineer)
Posted by: TW | Jan 11, 2005 12:33:30 PM
The comments to this entry are closed.