Project

General

Profile

Bug #13503

Updated by watson1978 (Shizuo Fujita) over 2 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.977M8.6%) 9.0%) i/s - 10.052M 9.816M in 5.020331s 5.003551s
Time#- 4.246M 3.844M1.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.566M1.3%) 1.9%) i/s - 28.195M 27.876M in 5.011366s 5.010230s
Time#to_r 1.927M 1.874M8.2%) 8.7%) i/s - 9.590M 9.339M in 5.009198s 5.018589s
Rational#+ 3.894M 3.889M1.0%) 0.8%) i/s - 19.545M 19.521M in 5.019923s 5.019869s
Rational#- 3.811M 3.684M1.0%) 0.9%) i/s - 19.125M 18.517M in 5.018842s 5.026471s
Rational#* 5.148M 3.681M1.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.241M1.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.659M2.0%) 2.1%) i/s - 28.223M 28.297M in 5.008422s 5.002788s
Time#to_r 2.313M 2.263M5.2%) 7.0%) i/s - 11.568M 11.307M in 5.015379s 5.024765s
Rational#+ 4.366M 4.386M1.6%) 0.6%) i/s - 21.846M 22.029M in 5.004487s 5.023014s
Rational#- 4.443M 4.391M1.2%) 0.7%) i/s - 22.255M 22.037M in 5.009509s 5.018534s
Rational#* 5.776M 4.355M1.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
~~~

Back