Talk:Randomized algorithm

From Wikipedia, the free encyclopedia

	This article is within the scope of WikiProject Computer science, which aims to create a comprehensive computer science reference for Wikipedia. Visit the project page for more information and to join in on related discussions.
Stub	rated as Stub-Class on the assessment scale
High	rated as High-importance on the assessment scale

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)¹⁰⁰ be (1/4)¹⁰⁰, 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)¹⁰⁰. 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.

No, algorithms that do not terminate are still algorithms.