https://bugs.ruby-lang.org/https://bugs.ruby-lang.org/favicon.ico?17113305112018-10-18T06:17:56ZRuby Issue Tracking SystemRuby master - Feature #15233: Speeding Up Matrix Powershttps://bugs.ruby-lang.org/issues/15233?journal_id=744962018-10-18T06:17:56Zduerst (Martin Dürst)duerst@it.aoyama.ac.jp
<ul></ul><p>The code doesn't look very Ruby-ish. What about rewriting it as follows:</p>
<pre><code class="ruby syntaxhl" data-language="ruby"><span class="k">def</span> <span class="nf">pow</span><span class="p">(</span><span class="n">a</span><span class="p">,</span> <span class="n">num</span><span class="p">)</span>
<span class="k">if</span> <span class="n">num</span><span class="o">==</span><span class="mi">1</span>
<span class="n">a</span>
<span class="k">elsif</span> <span class="n">num</span><span class="p">.</span><span class="nf">odd?</span>
<span class="n">a</span><span class="o">*</span><span class="n">pow</span><span class="p">(</span><span class="n">a</span><span class="p">,</span> <span class="n">num</span><span class="o">-</span><span class="mi">1</span><span class="p">)</span>
<span class="k">else</span>
<span class="n">ret</span> <span class="o">=</span> <span class="n">pow</span><span class="p">(</span><span class="n">a</span><span class="p">,</span> <span class="n">num</span><span class="o">/</span><span class="mi">2</span><span class="p">)</span>
<span class="n">ret</span><span class="o">*</span><span class="n">ret</span>
<span class="k">end</span>
<span class="k">end</span>
</code></pre> Ruby master - Feature #15233: Speeding Up Matrix Powershttps://bugs.ruby-lang.org/issues/15233?journal_id=745382018-10-20T07:57:22Zmame (Yusuke Endoh)mame@ruby-lang.org
<ul><li><strong>Status</strong> changed from <i>Open</i> to <i>Assigned</i></li><li><strong>Assignee</strong> set to <i>marcandre (Marc-Andre Lafortune)</i></li></ul><p>Interesting. The current implementation accumulates the value in LSB-to-MSB order, and SymPy's implementation does in MSB-to-LSB because. The former is slower than the latter because the latter multiplies the original matrix (which is smaller than an accumulated matrix for each digit).</p>
<p><a class="user active user-mention" href="https://bugs.ruby-lang.org/users/182">@marcandre (Marc-Andre Lafortune)</a>, could you review this?</p>
<pre><code class="diff syntaxhl" data-language="diff"><span class="gh">diff --git a/lib/matrix.rb b/lib/matrix.rb
index 62852bdad0..fd9115cfad 100644
</span><span class="gd">--- a/lib/matrix.rb
</span><span class="gi">+++ b/lib/matrix.rb
</span><span class="p">@@ -1086,12 +1086,12 @@</span> def **(other)
return self.class.identity(self.column_count) if other == 0
other = -other
end
<span class="gd">- z = nil
- loop do
- z = z ? z * x : x if other[0] == 1
- return z if (other >>= 1).zero?
- x *= x
</span><span class="gi">+ z = self
+ (other.bit_length - 2).downto(0) do |i|
+ z *= z
+ z *= self if other[i] == 1
</span> end
<span class="gi">+ return z
</span> when Numeric
v, d, v_inv = eigensystem
v * self.class.diagonal(*d.each(:diagonal).map{|e| e ** other}) * v_inv
</code></pre> Ruby master - Feature #15233: Speeding Up Matrix Powershttps://bugs.ruby-lang.org/issues/15233?journal_id=745892018-10-23T21:28:26ZCaryInVictoria (Cary Swoveland)cary@swoveland.com
<ul></ul><p>The O(ln n) method could be written as follows.</p>
<pre><code>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
</code></pre> Ruby master - Feature #15233: Speeding Up Matrix Powershttps://bugs.ruby-lang.org/issues/15233?journal_id=745902018-10-23T22:44:20Zmarcandre (Marc-Andre Lafortune)marcandre-ruby-core@marc-andre.ca
<ul></ul><p>Cool. I'll definitely have a look, in a few days probably as I'm travelling right now</p> Ruby master - Feature #15233: Speeding Up Matrix Powershttps://bugs.ruby-lang.org/issues/15233?journal_id=812042019-08-27T19:24:47Zjeremyevans0 (Jeremy Evans)merch-redmine@jeremyevans.net
<ul><li><strong>Tracker</strong> changed from <i>Bug</i> to <i>Feature</i></li><li><strong>ruby -v</strong> deleted (<del><i>ruby 2.5.1p57 (2018-03-29 revision 63029) [x86_64-linux-gnu]</i></del>)</li><li><strong>Backport</strong> deleted (<del><i>2.3: UNKNOWN, 2.4: UNKNOWN, 2.5: UNKNOWN</i></del>)</li></ul> Ruby master - Feature #15233: Speeding Up Matrix Powershttps://bugs.ruby-lang.org/issues/15233?journal_id=889272020-12-05T05:57:18ZAnonymous
<ul><li><strong>Status</strong> changed from <i>Assigned</i> to <i>Closed</i></li></ul><p>Applied in changeset <a class="changeset" title="[ruby/matrix] Optimize ** Avoiding recursive call would imply iterating bits starting from most ..." href="https://bugs.ruby-lang.org/projects/ruby-master/repository/git/revisions/a83a51932dbc31b549e11b9da8967f2f52a8b07c">git|a83a51932dbc31b549e11b9da8967f2f52a8b07c</a>.</p>
<hr>
<p>[ruby/matrix] Optimize **</p>
<p>Avoiding recursive call would imply iterating bits starting from<br>
most significant, which is not easy to do efficiently.<br>
Any saving would be dwarfed by the multiplications anyways.<br>
[Feature <a class="issue tracker-2 status-5 priority-4 priority-default closed" title="Feature: Speeding Up Matrix Powers (Closed)" href="https://bugs.ruby-lang.org/issues/15233">#15233</a>]</p>