https://bugs.ruby-lang.org/https://bugs.ruby-lang.org/favicon.ico?17113305112012-08-11T23:48:07ZRuby Issue Tracking SystemRuby master - Feature #6857: bigdecimal/math BigMath.E/BigMath.exp R. P. Feynman inspired optimizationhttps://bugs.ruby-lang.org/issues/6857?journal_id=287852012-08-11T23:48:07Zroyaltm (Rafał Michalski)
<ul></ul><ul>
<li>algorithms ;)</li>
</ul> Ruby master - Feature #6857: bigdecimal/math BigMath.E/BigMath.exp R. P. Feynman inspired optimizationhttps://bugs.ruby-lang.org/issues/6857?journal_id=288072012-08-13T12:05:46Zsorah (Sorah Fukumori)her@sorah.jp
<ul><li><strong>Assignee</strong> set to <i>mrkn (Kenta Murata)</i></li></ul> Ruby master - Feature #6857: bigdecimal/math BigMath.E/BigMath.exp R. P. Feynman inspired optimizationhttps://bugs.ruby-lang.org/issues/6857?journal_id=288082012-08-13T12:05:57Zsorah (Sorah Fukumori)her@sorah.jp
<ul><li><strong>Tracker</strong> changed from <i>Bug</i> to <i>Feature</i></li></ul> Ruby master - Feature #6857: bigdecimal/math BigMath.E/BigMath.exp R. P. Feynman inspired optimizationhttps://bugs.ruby-lang.org/issues/6857?journal_id=288362012-08-14T02:58:14Zroyaltm (Rafał Michalski)
<ul></ul><p>Having fast exp() allows us to speed up BigMath.log(). Especially for calculations with large precision.</p>
<p>The area hyperbolic tangent power series performs better when the domain (x) of the function is closer to 1.<br>
Additionally for x > 10 there is a significant linear performance degradation proportional to x.</p>
<p>So the first thing would be to narrow "no decimal shift" domain limitation to just 0.1 <= x <= 10.<br>
The current implementation of BigMath.log uses range: 0.1 <= x < 100.</p>
<p>But this is just a prerequisite.</p>
<p>The real performance boost we gain from the following rule:</p>
<p>Let's suppose y ~ log(x) where y is calculated with much lesser precision than we actually need.<br>
We may find then such an A:</p>
<p>A = x / exp(y)</p>
<p>which is very close to 1.</p>
<p>Now we can use it to calculate logarithm with the accurate precision from:</p>
<p>log(x) = y + log(a)</p>
<p>The implementation:</p>
<pre><code> def log(x, prec)
raise ArgumentError, "Zero or negative precision for log" if prec <= 0
raise ArgumentError, "Zero or negative argument for log" if x.round(prec) <= 0
return BigDecimal('0') if x.round(prec) == BigDecimal('1')
return BigDecimal::INFINITY if x.infinite?
n = prec + BigDecimal.double_fig
shift = x.exponent
ten = BigDecimal('10')
if shift < 0 || x > 10
x = x.mult(BigDecimal("1E#{-shift}"), n)
else
shift = 0
end
if prec < 26 # 26 was chosen based on experiments
y = BigMath.log(x, prec)
else
y = log(x, Math.exp(Math.log(prec)/2).round)
a = x.div(exp(y, n), n)
y += BigMath.log(a, prec)
end
y += log(ten, prec).mult(shift, n) unless shift.zero?
y
end
</code></pre>
<p>Get ready for some benchmarks:</p>
<pre><code> require 'benchmark'
require 'bigdecimal/util'
def testlog(p, range=100.0, iter=100, count=1000)
Benchmark.bm(20, 'ext', 'new') do |b|
count.times.map { rand*range }.inject([0,0]) do |(tt1,tt2), n|
nbig = n.to_d
a1 = a2 = nil
GC.disable
t1 = b.report("#{n} ext") { iter.times { a1 = BigMath.log(nbig, p) } }
t2 = b.report("#{n} new") { iter.times { a2 = log(nbig, p) } }
GC.enable
unless a1.round(p - a1.exponent) == a2.round(p - a2.exponent)
raise "bad #{a1.round(p - a1.exponent)} <> #{a2.round(p - a2.exponent)}"
end
[t1/count + tt1, t2/count + tt2]
end
end
nil
end
</code></pre>
<p>To get the idea of speed up factor I'll present some summaries:</p>
<p>testlog(9, 10.0)<br>
ext 0.026100 0.000000 0.026100 ( 0.025777)<br>
new 0.025600 0.000000 0.025600 ( 0.025944)</p>
<p>we didn't optimize anything within the domain range of 0 < x < 10.0 and precision (< 26) so the new implementation performs similarly<br>
(it's slightly slower due to some overhead of wrapper code)</p>
<p>testlog(9, 100.0)<br>
ext 0.236000 0.000000 0.236000 ( 0.235998)<br>
new 0.055900 0.000000 0.055900 ( 0.055529)</p>
<p>just narrowing the domain range calculated wihtout decimal shift to 0.1 <= x <= 10 gives as a significant speed increase.</p>
<p>Now let's try some serious BigDecimal precision:</p>
<p>testlog(99, 10.0)<br>
ext 0.202900 0.000000 0.202900 ( 0.201852)<br>
new 0.075600 0.000000 0.075600 ( 0.076487)</p>
<p>we can now see the effect of approximation algorithm</p>
<p>let's increase the domain range:</p>
<p>testlog(99, 100.0)<br>
ext 2.387300 0.004000 2.391300 ( 2.390849)<br>
new 0.158300 0.001700 0.160000 ( 0.160178)</p>
<p>the combined effect of both approximation and domain decimal shift range limitation gives us more than 10 times performance boost (average)</p>
<p>testlog(999, 10.0, 2)<br>
ext 1.470000 0.000000 1.470000 ( 1.469803)<br>
new 0.031300 0.000000 0.031300 ( 0.031546)</p>
<p>Large mantissa tests:</p>
<p>e = E(10000)<br>
l1 = timer{ BigMath.log(e, 10000) } # -> 318.629882<br>
l2 = timer{ log(e, 10000) } # -> 1.524671<br>
l1.round(10000) == l2.round(10000)<br>
=> true<br>
l1.round(10000) == 1<br>
=> true</p>
<p>pi = BigMath.PI(10000)<br>
l1 = timer{ BigMath.log(pi, 10000) } # -> 371.913958<br>
l2 = timer{ log(pi,10000) } # -> 1.892104</p>
<p>l1.round(10000) == l2.round(10000)<br>
=> true</p> Ruby master - Feature #6857: bigdecimal/math BigMath.E/BigMath.exp R. P. Feynman inspired optimizationhttps://bugs.ruby-lang.org/issues/6857?journal_id=333302012-11-20T23:24:29Zmame (Yusuke Endoh)mame@ruby-lang.org
<ul><li><strong>Status</strong> changed from <i>Open</i> to <i>Assigned</i></li><li><strong>Target version</strong> set to <i>2.6</i></li></ul> Ruby master - Feature #6857: bigdecimal/math BigMath.E/BigMath.exp R. P. Feynman inspired optimizationhttps://bugs.ruby-lang.org/issues/6857?journal_id=431032013-11-23T19:52:41Zmrkn (Kenta Murata)muraken@gmail.com
<ul><li><strong>Status</strong> changed from <i>Assigned</i> to <i>Closed</i></li><li><strong>% Done</strong> changed from <i>0</i> to <i>100</i></li></ul><p>This issue was solved with changeset r43817.<br>
Rafał, thank you for reporting this issue.<br>
Your contribution to Ruby is greatly appreciated.<br>
May Ruby be with you.</p>
<hr>
<ul>
<li>ext/bigdecimal/lib/bigdecimal/math.rb (BigMath.E): Use BigMath.exp.<br>
[Feature <a class="issue tracker-2 status-2 priority-4 priority-default" title="Feature: bigdecimal/math BigMath.E/BigMath.exp R. P. Feynman inspired optimization (Assigned)" href="https://bugs.ruby-lang.org/issues/6857">#6857</a>] <a href="/issues/6857">[ruby-core:47130]</a></li>
</ul> Ruby master - Feature #6857: bigdecimal/math BigMath.E/BigMath.exp R. P. Feynman inspired optimizationhttps://bugs.ruby-lang.org/issues/6857?journal_id=431042013-11-23T19:55:45Zmrkn (Kenta Murata)muraken@gmail.com
<ul><li><strong>Status</strong> changed from <i>Closed</i> to <i>Assigned</i></li><li><strong>% Done</strong> changed from <i>100</i> to <i>50</i></li></ul><p>The optimization of BigMath.log is remaining.</p> Ruby master - Feature #6857: bigdecimal/math BigMath.E/BigMath.exp R. P. Feynman inspired optimizationhttps://bugs.ruby-lang.org/issues/6857?journal_id=688162017-12-25T18:15:07Znaruse (Yui NARUSE)naruse@airemix.jp
<ul><li><strong>Target version</strong> deleted (<del><i>2.6</i></del>)</li></ul>