FSPM2-Kolloquium- The cost of cyclic permutations

by Kai-Uwe Bux (Universität Bielefeld)

Friday Apr 25, 2025, 4:00 PM → 6:00 PM Europe/Berlin

H 10 (UHG)

lnplace rotation of an array involves nothing but moving data around in computer memory. As modern computer architectures involve several layers of caching, it is a surprisingly non­trivial problem. We describe a competitively fast algorithm (as indicated by measurements) and asymptotically count the number of data moves in the best, warst, and average case. lt turns out that this task is equivalent to determining the expected sum of remainders encoun­tered in a run of the Euclidean algorithm, which in turn can be estimated using tools from analytic number theory. 
1 shall motivate, describe and discuss this algorithm in detail an also compare it to several other reasonable choices. 
(Joint werk with Valentin Blomer) 
gez. G. Akemann, E. Baake, M. Wahl