Stories
Slash Boxes
Comments

All the Perl that's Practical to Extract and Report

use Perl Log In

Log In

[ Create a new account ]

Ovid (2709)

Ovid
  (email not shown publicly)
http://publius-ovidius.livejournal.com/
AOL IM: ovidperl (Add Buddy, Send Message)

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

Journal of Ovid (2709)

Wednesday January 05, 2005
12:46 PM

Mathematicians v. Engineers

[ #22581 ]

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.


List all Journal entries
The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.

Mathematicians v. Engineers 11 Comments More | Login | Reply /

 Full
 Abbreviated
 Hidden
More | Login | Reply
Loading... please wait.
  • There's a very old joke about Mathematicians v. Engineers and prime numbers:
    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...

    :-)

    • 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...
  • SICP is a terrific book - lav it !

    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.

    • 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 :)

      • 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/
        --
        "Perl users are the Greatful Dead fans of computer science." --slashdot comment
      • 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. With O(log^10.5 n) i
    • Speaking of SICP and elements of physics like cosmic radiation, I just have to mention SICM [mit.edu]. :-)
  • Computer Science is about Math and Engineering, but software development is mostly about... Sociology.
  • The probalistic primality tests are more practically useful than the Fermat Small Theorem. They are used to find prime numbers for public-key algorithms like RSA in a reasonable amount of time. One interesting thing about them is that it possible to reduce the probablity of finding a composite as prime by doing more tests.

  • 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

    • 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.
Stories, comments, journals, and other submissions on use Perl; are Copyright 1998-2006, their respective owners.