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

All the Perl that's Practical to Extract and Report

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

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

 Full
 Abbreviated
 Hidden
More | Login | Reply
Loading... please wait.
  • 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 :)

      • 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) it's slower than Miller-Rabin, though.
Stories, comments, journals, and other submissions on use Perl; are Copyright 1998-2006, their respective owners.