Benchmarking code for ^(p::perm, n::Int)

bench.jl

using Nemo

function power_by_cycles(a::perm, n::Int)
   if n <0
      return inv(a)^-n
   elseif n == 0
      return parent(a)()
   elseif n == 1
      return deepcopy(a)
   elseif n == 2
      return a*a
   elseif n == 3
      return a*a*a  
   else
      new_perm = similar(a.d)
      cyls = cycles(a)
      for cycle in cyls
         k = n % length(cycle)
         shifted = circshift(cycle, -k)
         for (idx,j) in enumerate(cycle)
            new_perm[j] = shifted[idx]
         end
      end
      return parent(a)(new_perm)
   end
end

import Base.copy
copy(a::perm) = deepcopy(a)

function bench(n, powers, tries=100)
    table_by_cycles = zeros(n, powers)
    table_by_squaring = zeros(n, powers)
    for m in 1:n
        G = PermutationGroup(m)
        for k in 1:powers
            by_sqaring_times = 0
            by_cycles_times = 0
            for j in 1:tries
                p = G(randperm(m))
                t1 = @timed a = Base.power_by_squaring(p,k)
                t2 = @timed b = power_by_cycles(p,k)
                by_sqaring_times += t1[2]
                by_cycles_times += t2[2]
            end
            table_by_cycles[m,k] = by_cycles_times/tries 
            table_by_squaring[m,k] =  by_sqaring_times/tries
        end
    end
    return table_by_cycles, table_by_squaring
end

@time t_cycles, t_squaring = bench(100,100);

writecsv("/tmp/time_by_cycles.csv", t_cycles)
writecsv("/tmp/time_by_squaring.csv", t_squaring)

using Plots
plotly()

heatmap(sign.(t_cycles - t_squaring))
yaxis!("length of permutation")
xaxis!("power")

time_by_cycles.csv

time_by_squaring.csv