The cost of cyclic permutations and remainder sums in the Euclidean algorithm
Abstract
We discuss a modification to the Gries-Mills block swapping scheme for in-place rotation with average costs of 1.85 moves per element and worst case performance still at 3 moves per element. Analysis of the average case relies on the asymptotic behavior of the sum of remainders in the Euclidean algorithm.
Fields of Study & Subjects
VLSI and FPGA Design Techniques
Algorithms and Data Compression
Interconnection Networks and Systems
Publication details
- Journal / source
- arXiv (Cornell University)
- Publication date
- 2 January 2026
- Document type
- Preprint