From: cary@... Date: 2018-10-23T21:28:29+00:00 Subject: [ruby-core:89541] [Ruby trunk Bug#15233] Speeding Up Matrix Powers 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: