A Randomized Sublinear Time Parallel GCD Algorithm for the EREW PRAM

Details A Randomized Sublinear Time Parallel GCD Algorithm for the EREW PRAM A Randomized Sublinear Time Parallel GCD Algorithm for the EREW PRAM

2009-07-03

arxiv.org/abs/0907.0718v2

Information Processing Letters 110 (2010) 198-201

Computer Science

Data Structures and Algorithms

Scientific paper

10.1016/j.ipl.2009.12.008

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(n loglog n / log n) expected time using n^{6+\epsilon} processors on the EREW
PRAM parallel model of computation. We believe this to be the first randomized
sublinear time algorithm on the EREW PRAM for this problem.

Affiliated with

Also associated with

No associations

Rating

A Randomized Sublinear Time Parallel GCD Algorithm for the EREW PRAM does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Randomized Sublinear Time Parallel GCD Algorithm for the EREW PRAM, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Randomized Sublinear Time Parallel GCD Algorithm for the EREW PRAM will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-529733