using LinearAlgebra, Test function multiplica(a, b) dima = size(a) dimb = size(b) if dima[2] != dimb[1] return -1 end c = zeros(dima[1], dimb[2]) for i in 1:dima[1] for j in 1:dimb[2] for k in 1:dima[2] c[i, j] = c[i, j] + a[i, k] * b[k, j] end end end return c end function matrix_pot(M, p) matriz = M for i in 1:(p-1) matriz = multiplica(matriz, M) end return matriz end function matrix_pot_by_squaring(x, n) if n == 1 return x elseif n % 2 == 0 return matrix_pot_by_squaring(x * x, n / 2) elseif n % 2 == 1 return x * matrix_pot_by_squaring(x * x, (n - 1) / 2) end end function compare_times() a = Matrix(LinearAlgebra.I, 30, 30) @time matrix_pot(a, 10) @time matrix_pot_by_squaring(a, 10) end function extra_test() @testset "Tests for MiniEP9" begin @testset "matrix_pot" begin @test matrix_pot([1 0 0; 0 1 0; 0 0 1], 10) == [1 0 0; 0 1 0; 0 0 1] @test matrix_pot([1 2 3; 4 5 6; 7 8 9], 3) == [468 576 684; 1062 1305 1548; 1656 2034 2412] @test matrix_pot([12 7 4 0; 9 1 2 6; 7 9 3 4; 14 6 0 10], 2) == [235 127 74 58; 215 118 44 74; 242 109 55 106; 362 164 68 136] @test matrix_pot([4 4; 4 4], 4) == [2048 2048; 2048 2048] end @testset "matrix_pot_by_squaring" begin @test matrix_pot_by_squaring([1 0 0; 0 1 0; 0 0 1], 10) == [1 0 0; 0 1 0; 0 0 1] @test matrix_pot_by_squaring([1 2 3; 4 5 6; 7 8 9], 3) == [468 576 684; 1062 1305 1548; 1656 2034 2412] @test matrix_pot_by_squaring([12 7 4 0; 9 1 2 6; 7 9 3 4; 14 6 0 10], 2) == [235 127 74 58; 215 118 44 74; 242 109 55 106; 362 164 68 136] @test matrix_pot_by_squaring([4 4; 4 4], 4) == [2048 2048; 2048 2048] end end end