Motivation:
While studying about randomized algorithms in wikipedia, one of the very first algorithms in this context is the Miller-Rabin primality test and an important statement in their algorithm is that:
"If n is composite then at least three-fourths of the natural numbers less than n are witnesses to its compositeness."[1,2]
But a number like 22 has only two numbers are witnesses of its compositeness (2 and 11). So what does that mean. I thought that it could be true for most numbers if we get to infinity, therefore I counted the number of factors (witness of compisiteness) of the numbers from two to one million. And as the mubers grow their factor count become less comparable to their magnitude. So what does that quote mean?[1] . http://en.wikipedia.org/wiki/Randomized_algorithm
[2]. Dietzfelbinger, M. and Hagerup, T. and Katajainen, J. and Penttonen, M. "A Reliable Randomized Algorithm for the Closest-Pair Problem", Journal of Algorithms, Vol 25, Issue 1, 1997.
No comments:
Post a Comment