| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 427950 | Information Processing Letters | 2010 | 4 Pages |
Abstract
We present a randomized parallel algorithm that computes the greatest common divisor of two integers of n bits in length with probability 1−o(1) that takes O(nloglogn/logn) time using O(n6+ϵ) processors for any ϵ>0 on the EREW PRAM parallel model of computation. The algorithm either gives a correct answer or reports failure.We believe this to be the first randomized sublinear time algorithm on the EREW PRAM for this problem.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
