## Feature #15233

### Speeding Up Matrix Powers

**Description**

I've been looking at SymPy's slow matrix power speed, and noticed that replacing Ruby's matrix power code with the equivalent code from SymPy makes it significantly faster. As this is a recursively defined function, presumably it can be made even faster with a proper iterative version.

Base:

```
require 'matrix'
Q = Matrix[[0,0,1,0,2,0],
[0,0,0,1,0,0],
[1,0,0,1,0,2],
[0,2,1,0,0,0],
[1,0,0,0,0,0],
[0,0,1,0,0,0]]
r = Vector[1,0,0,0,0,0]
p = (Q**100000000*r).sum
puts p.to_s.size
```

Output:

time ruby main.rb 35950264 real 1m42.250s user 1m41.050s sys 0m1.184s

Modified:

```
require 'matrix'
def pow(a,num)
if (num==1)
return a
end
if (num%2)==1
return a*pow(a,num-1)
end
ret = pow(a,(num/2))
ret*ret
end
Q = Matrix[[0,0,1,0,2,0],
[0,0,0,1,0,0],
[1,0,0,1,0,2],
[0,2,1,0,0,0],
[1,0,0,0,0,0],
[0,0,1,0,0,0]]
r = Vector[1,0,0,0,0,0]
p = (pow(Q,100000000)*r).sum
puts p.to_s.size
```

Output:

time ruby main.rb 35950264 real 1m9.489s user 1m8.661s sys 0m0.828s