Talk:Randomized algorithm

From Wikipedia, the free encyclopedia

You have new messages (last change).

Needs to be merged with randomized algorithms. Fredrik 09:33, 10 Mar 2004 (UTC)

[edit] Possible minor mistake in the Miller-Rabin primality test ?

Shouldn't the probability in the article: (3/4)100 be (1/4)100, according to the 3 propositions of the Miller-Rabin test, since the probability of not picking a witness each iteration is 1/4?

  • Yes, it should have been (1/4)100. Corrected now. Andris 15:29, Jun 28, 2004 (UTC)

[edit] Nonterminating "algorithm"?

I am told by my theoretical Computer Science teacher that an algorithm is not an algorithm if it doesn't end (please see the wikipedia page about Algorithm: "given an initial state, will terminate in a corresponding recognizable end-state". So the side-note "(possibly nonterminating) algorithm" doesn't make sense. But I don't know enough about this to make an edit.

Retrieved from "http://en.wikipedia.org../../../r/a/n/Talk%7ERandomized_algorithm_ee4d.html"