{"id":112389,"date":"2026-06-05T07:00:00","date_gmt":"2026-06-05T14:00:00","guid":{"rendered":"https:\/\/devblogs.microsoft.com\/oldnewthing\/?p=112389"},"modified":"2026-06-05T15:39:18","modified_gmt":"2026-06-05T22:39:18","slug":"20260605-00","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20260605-00\/?p=112389","title":{"rendered":"Rotation revisited: Avoiding having to calculate the gcd when doing cycle decomposition"},"content":{"rendered":"<p>Last time, we looked at <a title=\"Rotation revisited: Cycle decomposition in clang's libcxx\" href=\"https:\/\/devblogs.microsoft.com\/oldnewthing\/20260604-00\/?p=112384\"> how clang&#8217;s libcxx implementation of <code>std::<wbr \/>rotate<\/code> uses cycle decomposition<\/a> to minimize the number of swaps. Doing so requires calculating the greatest common divisor, but I noted that the OpenJDK implementation of the java standard library uses a trick to <a href=\"https:\/\/github.com\/openjdk\/jdk\/blob\/f1e0e0c25ec62a543b9cbfabd630fc4ef17a8b5c\/src\/java.base\/share\/classes\/java\/util\/Collections.java#L822\"> avoid doing the gcd calculation<\/a>.<\/p>\n<p>The trick is realizing that the total number of elements is equal to the sum of the lengths of each of its cycles, and each of the initial elements belongs to a different cycle. Therefore, we can just keep rotating elements until the number of elements rotated is equal to the total. We don&#8217;t have to precalculate the number of cycles; we just let the counter tell us when we&#8217;re done.<\/p>\n<pre>auto a = std::distance(first, mid); \/\/ number of \"A\" elements\r\nauto n = std::distance(first, last); \/\/ total elements\r\nauto count = 0;\r\nauto k = 0;\r\n\r\nwhile (count &lt; n) {\r\n    \/\/ Rotate the elements in the cycle starting at k\r\n    auto save = std::move(first[k]);\r\n    auto i, next = k;\r\n    while (i = next, next = (i + a) % n, next != k) {\r\n        first[i] = std::move(first[next]);\r\n        ++count;\r\n    }\r\n    first[i] = std::move(save);\r\n    ++count;\r\n}\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Math is hard. Let&#8217;s go counting!<\/p>\n","protected":false},"author":1069,"featured_media":111744,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[1],"tags":[25],"class_list":["post-112389","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-code"],"acf":[],"blog_post_summary":"<p>Math is hard. Let&#8217;s go counting!<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/112389","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/users\/1069"}],"replies":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/comments?post=112389"}],"version-history":[{"count":1,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/112389\/revisions"}],"predecessor-version":[{"id":112390,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/112389\/revisions\/112390"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media\/111744"}],"wp:attachment":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media?parent=112389"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=112389"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=112389"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}