Talk:Randomized algorithm

From Wikipedia, the free encyclopedia

This article is within the scope of Computing WikiProject, an attempt to build a comprehensive and detailed guide to computers and computing. If you would like to participate, you can edit the article attached to this page, or visit the project page, where you can join the project and/or contribute to the discussion.

Stub This article has been rated as Stub-Class on the quality scale

??? This article has not yet received a rating on the importance scale.

WikiProject Computer science      (Rated Stub-Class)

Computer science portal

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 This article has been rated as Stub-Class on the quality scale.

High This article has been rated as High-importance on the importance 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?

[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.

[edit] pseudorandom number generator?

In the first paragraph, the sentence: this means that the machine implementing the algorithm has access to a pseudorandom number generator. - does it really matter if the random number generator is pseodorandom? Would an algorithm which used a Hardware random number generator, not be classed as a randomized algorithm? If so, then this line should be changed to ' a source of random numbers'...