A k-rotation (or a k-cyclic shift) of a sequence (a0a2...an-1) is a sequence (aP(1)aP(2)...aP(n-1)), where the index permutation is P(i) = (i + k) % n. The problem is to transform the given sequence into its k-rotation.

There are four well-known algorithms to do it:

1. Dolphin algorithm:

   Compute the number of cycles, nc = gcd(k, n - k); for each cycle (aCi(0)aCi(1)aCi(2)...) with Ci(j) = (i + jk) % n, i = 0, ..., nc - 1, make a cyclic shift of all the elements by one position to obtain (aCi(1)aCi(2)...aCi(0)).

2. Gries–Mills algorithm:. > If k = n - k, swap the subsequences (a0...ak-1) and (ak...an-1); if k < n - k, swap the subsequences (a0...ak-1)

Suppose we have two square NxN matrices A and B of doubles, and we want to perform a copy with a transposition:

A = transpose(B)

Equivalently, we want to copy a row-major matrix to a column-major one or vice versa.

Below are the results of a simple benchmark for 3 ways to accomplish the task:

1. Two nested loops such that reads are contiguous and writes are strided.