Parallel and sequential in-place permuting and perfect shuffling using involutions

Details Parallel and sequential in-place permuting and perfect shuffling using involutions Parallel and sequential in-place permuting and perfect shuffling using involutions

2012-04-09

arxiv.org/abs/1204.1958v1

Computer Science

Data Structures and Algorithms

Scientific paper

We show that any permutation of ${1,2,...,N}$ can be written as the product of two involutions. As a consequence, any permutation of the elements of an array can be performed in-place in parallel in time O(1). In the case where the permutation is the $k$-way perfect shuffle we develop two methods for efficiently computing such a pair of involutions. The first method works whenever $N$ is a power of $k$; in this case the time is O(N) and space $O(\log^2 N)$. The second method applies to the general case where $N$ is a multiple of $k$; here the time is $O(N \log N)$ and the space is $O(\log^2 N)$. If $k=2$ the space usage of the first method can be reduced to $O(\log N)$ on a machine that has a SADD (population count) instruction.

Affiliated with

Also associated with

No associations

Rating

Parallel and sequential in-place permuting and perfect shuffling using involutions 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 Parallel and sequential in-place permuting and perfect shuffling using involutions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Parallel and sequential in-place permuting and perfect shuffling using involutions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-652519