aboutsummaryrefslogtreecommitdiffstats
path: root/rational.c
diff options
context:
space:
mode:
authorwatson1978 <watson1978@b2dd03c8-39d4-4d8f-98ff-823fe69b080e>2017-05-27 05:41:02 +0000
committerwatson1978 <watson1978@b2dd03c8-39d4-4d8f-98ff-823fe69b080e>2017-05-27 05:41:02 +0000
commitbce9aa330fe1d5492d52009094aeb7841bf9cc5f (patch)
tree7ca68980720c17e4fd7f5efa789fa7240ea22835 /rational.c
parentbbdb3207519f9f999c12e06c063c33cda40abe5f (diff)
downloadruby-bce9aa330fe1d5492d52009094aeb7841bf9cc5f.tar.gz
Improve performance of some Time & Rational methods
rational.c (i_gcd): replace GCD algorithm from Euclidean algorithm to Stein algorithm (https://en.wikipedia.org/wiki/Binary_GCD_algorithm). Some Time methods will call internal quov() function and it calls Rational#quo -> f_muldiv() -> i_gcd() in rational.c And some Rational methods also call i_gcd(). The implementation of Euclidean algorithm spent a long time at modulo operation (ie "x = y % x;"). The Stein algorithm will replace with shift operation which is faster than modulo. Time#subsec -> 36 % up Time#to_r -> 26 % up Rational#+ -> 14 % up Rational#- -> 15 % up Rational#* -> 13 % up [ruby-core:80843] [Bug #13503] [Fix GH-1596] ### Before Time#subsec 2.142M (± 9.8%) i/s - 10.659M in 5.022659s Time#to_r 2.003M (± 9.1%) i/s - 9.959M in 5.012445s Rational#+ 3.843M (± 0.9%) i/s - 19.274M in 5.016254s Rational#- 3.820M (± 1.3%) i/s - 19.149M in 5.014137s Rational#* 5.198M (± 1.4%) i/s - 26.016M in 5.005664s * After Time#subsec 2.902M (± 2.9%) i/s - 14.505M in 5.001815s Time#to_r 2.503M (± 4.8%) i/s - 12.512M in 5.011454s Rational#+ 4.390M (± 1.2%) i/s - 22.001M in 5.012413s Rational#- 4.391M (± 1.2%) i/s - 22.013M in 5.014584s Rational#* 5.872M (± 2.2%) i/s - 29.369M in 5.003666s * Test code require 'benchmark/ips' Benchmark.ips do |x| x.report "Time#subsec" do |t| time = Time.now t.times { time.subsec } end x.report "Time#to_r" do |t| time = Time.now t.times { time.to_r } end x.report "Rational#+" do |t| rat1 = 1/2r rat2 = 1/3r t.times { rat1 + rat2 } end x.report "Rational#-" do |t| rat1 = 1/3r rat2 = 1/2r t.times { rat1 - rat2 } end x.report "Rational#*" do |t| rat1 = 1/3r rat2 = 1/2r t.times { rat1 * rat2 } end end git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@58922 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
Diffstat (limited to 'rational.c')
-rw-r--r--rational.c30
1 files changed, 25 insertions, 5 deletions
diff --git a/rational.c b/rational.c
index 54fac1e5bc..bd32399e79 100644
--- a/rational.c
+++ b/rational.c
@@ -280,6 +280,9 @@ rb_gcd_gmp(VALUE x, VALUE y)
inline static long
i_gcd(long x, long y)
{
+ unsigned long u, v, t;
+ int shift;
+
if (x < 0)
x = -x;
if (y < 0)
@@ -290,12 +293,29 @@ i_gcd(long x, long y)
if (y == 0)
return x;
- while (x > 0) {
- long t = x;
- x = y % x;
- y = t;
+ u = (unsigned long)x;
+ v = (unsigned long)y;
+ for (shift = 0; ((u | v) & 1) == 0; ++shift) {
+ u >>= 1;
+ v >>= 1;
}
- return y;
+
+ while ((u & 1) == 0)
+ u >>= 1;
+
+ do {
+ while ((v & 1) == 0)
+ v >>= 1;
+
+ if (u > v) {
+ t = v;
+ v = u;
+ u = t;
+ }
+ v = v - u;
+ } while (v != 0);
+
+ return (long)(u << shift);
}
inline static VALUE