```Issue #15233 has been updated by CaryInVictoria (Cary Swoveland).

The O(ln n) method could be written as follows.

def pow1(m, n)
return m if n == 1
p = pow1(m, n/2)
n.even? ? (p*p) : p*p*m
end

t = Time.now
p = (pow(Q,100000000)*r).sum % 1_000_000
#=> 109376
Time.now-t
#=> 53.2

t = Time.now
p1 = (pow1(Q,100000000)*r).sum % 1_000_000
#=> 109376
Time.now-t
#=> 54.4

----------------------------------------
Bug #15233: Speeding Up Matrix Powers
https://bugs.ruby-lang.org/issues/15233#change-74589

* Author: octonion (Christopher Long)
* Status: Assigned
* Priority: Normal
* Assignee: marcandre (Marc-Andre Lafortune)
* Target version:
* ruby -v: ruby 2.5.1p57 (2018-03-29 revision 63029) [x86_64-linux-gnu]
* Backport: 2.3: UNKNOWN, 2.4: UNKNOWN, 2.5: UNKNOWN
----------------------------------------
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:

~~~ ruby
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:

~~~ ruby
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
~~~

--
https://bugs.ruby-lang.org/

Unsubscribe: <mailto:ruby-core-request / ruby-lang.org?subject=unsubscribe>
<http://lists.ruby-lang.org/cgi-bin/mailman/options/ruby-core>
```