NOTE: **use Perl;** is on undef hiatus. You can read content, but you can't post it. More info will be forthcoming forthcomingly.

Ovid

(email not shown publicly)

http://publius-ovidius.livejournal.com/

**AOL IM:** ovidperl (**Add Buddy, Send Message**)

(email not shown publicly)

http://publius-ovidius.livejournal.com/

Stuff with the Perl Foundation. A couple of patches in the Perl core. A few CPAN modules. That about sums it up.

Wednesday January 05, 2005

11:46 AM

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.

Full

Abbreviated

Hidden

Stories, comments, journals, and other submissions on use Perl; are Copyright 1998-2006, their respective owners.

## Engineers and Prime Numbers (Score:2)

## Re:Engineers and Prime Numbers (Score:2)

The way I heard it, there was also a physicist, who piped up between the mathematician and the engineer. Her sequence went:

## sicp (Score:1)

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 (Score:2)

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 (Score:1)

"Perl users are the Greatful Dead fans of computer science." --slashdot comment

## Re:sicp (Score:2)

The other one is the Agrawal-Kayal-Saxena test which is deterministic and avoids the Riemann assumption. With

`O(log^10.5 n)`

i## Re:sicp (Score:2)

haveto mention SICM [mit.edu].## Re: (Score:1)

## Probalistic Primality Tests (Score:1)

## Goals (Score:1)

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

## Re:Goals (Score:2)