I learned about probabilistic algorithms yesterday in Structure and Interpretation of Computer Programs. Probabilistic algorithms do not yield the correct answer with 100% certainty, but are designed so that the chance of an incorrect answer is infinitesimal. For example, the Fermat Test for primality yields a nice logarithmic-time (very quick) algorithm which yields the incorrect answer extremely rarely. I came across a nice bit of witticism from the author:
Numbers that fool the Fermat test are called Carmichael numbers, and very little is known about them other than that they are extremely rare…in testing primality of very large numbers chosen at random,the chance of stumbling upon a value that fools the Fermat test is less than the chance that cosmic radiation will cause the computer to make an error in carrying out a “correct” algorithm. Considering an algorithm to be inadequate for the first reason but not for the second illustrates the difference between mathematics and engineering.
– Structure and Interpretation of Computer Programs, 53 n. (emphasis mine)
So…if I’m a computer scientist does that make me an engineer or mathematician? The author seems to have made his own decision.
Of course, Sheldon Cooper has his own, opposing opinion: