Bug #13503
Updated by watson1978 (Shizuo Fujita) almost 7 years ago
Some Time methods will call internal quov() function.
quov() calls Rational#quo -> f_muldiv() -> i_gcd() in rational.c
i_gcd() will calculate GCD using Euclidean's Algorithm and it lose a long time in modulo method (ie "x = y % x;").
This patch will replace i_gcd() with Stein's algorithm which is faster algorithm for GCD.
(https://en.wikipedia.org/wiki/Binary_GCD_algorithm)
Some Rational methods also call i_gcd().
### Before
~~~
Calculating -------------------------------------
Time#subsec 2.017M 1.977M (± 8.6%) 9.0%) i/s - 10.052M 9.816M in 5.020331s 5.003551s
Time#- 4.246M 3.844M (± 1.1%) 4.9%) i/s - 21.259M 19.220M in 5.006968s 5.011682s
Time#round 402.944k (±11.0%) 397.118k (±10.5%) i/s - 1.996M 1.976M in 5.014424s 5.032733s
Time#to_f 5.627M 5.566M (± 1.3%) 1.9%) i/s - 28.195M 27.876M in 5.011366s 5.010230s
Time#to_r 1.927M 1.874M (± 8.2%) 8.7%) i/s - 9.590M 9.339M in 5.009198s 5.018589s
Rational#+ 3.894M 3.889M (± 1.0%) 0.8%) i/s - 19.545M 19.521M in 5.019923s 5.019869s
Rational#- 3.811M 3.684M (± 1.0%) 0.9%) i/s - 19.125M 18.517M in 5.018842s 5.026471s
Rational#* 5.148M 3.681M (± 1.1%) 0.9%) i/s - 25.858M 18.501M in 5.023586s 5.025969s
~~~
### After
~~~
Calculating -------------------------------------
Time#subsec 2.648M 2.640M (± 3.0%) i/s - 13.257M 13.204M in 5.010600s 5.005680s
Time#- 4.265M 4.241M (± 1.4%) 2.1%) i/s - 21.372M 21.225M in 5.012480s 5.006865s
Time#round 393.309k (±12.5%) 404.738k (±10.9%) i/s - 1.934M 2.003M in 5.000319s 5.009187s
Time#to_f 5.638M 5.659M (± 2.0%) 2.1%) i/s - 28.223M 28.297M in 5.008422s 5.002788s
Time#to_r 2.313M 2.263M (± 5.2%) 7.0%) i/s - 11.568M 11.307M in 5.015379s 5.024765s
Rational#+ 4.366M 4.386M (± 1.6%) 0.6%) i/s - 21.846M 22.029M in 5.004487s 5.023014s
Rational#- 4.443M 4.391M (± 1.2%) 0.7%) i/s - 22.255M 22.037M in 5.009509s 5.018534s
Rational#* 5.776M 4.355M (± 1.1%) 1.7%) i/s - 28.888M 21.820M in 5.002322s 5.011914s
~~~
### 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#-" do |t|
time1 = Time.now
time2 = Time.now
t.times { time1 - time2 }
end
x.report "Time#round" do |t|
time = Time.now
t.times { time.round }
end
x.report "Time#to_f" do |t|
time = Time.now
t.times { time.to_f }
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
~~~