Feature #8796


Use GMP to accelerate Bignum operations

Added by akr (Akira Tanaka) almost 9 years ago. Updated almost 9 years ago.

Target version:


How about using GMP to accelerate Bignum operations?

GMP: The GNU Multiple Precision Arithmetic Library

I wrote a simple patch to use GMP to accelerate Bignum multiplication.

If a user don't want to use GMP, a configure option, --without-gmp,
disables this feature.
Since GMP is licensed as LGPL, some people would need it.
However I think most people can accept LGPL as Ruby 1.8's regex engine.
So, my patch uses GMP by default, if it is available.

It converts bignums from RBignum to mpz_t and back for each
large Bignum multiplication.
RBignum structure itself is not changed and ABI compatible.
(So, this is different from ko1's idea mentioned in Feature #6083)

The conversion cost is O(n).
It is negligible for operations slower than O(n) with large inputs.
Multiplication is a kind of such operation.

I measured the performance as follows.

% ./ruby -I.ext/x86_64-linux -r-test-/bignum -e '
methods = %i[big_mul_normal big_mul_karatsuba big_mul_toom3 big_mul_gmp]
m = 1000
n1 = 3**60
100.times {
n1 = n1 * (n1 >> (n1.size8/1514))
n2 = n1 + 1
bits = n1.size*8
methods.dup.each {|meth|
t1 = Process.clock_gettime(Process::CLOCK_THREAD_CPUTIME_ID, :nanoseconds)
n1.send(meth, n2) rescue next
(m-1).times { n1.send(meth, n2) }
t2 = Process.clock_gettime(Process::CLOCK_THREAD_CPUTIME_ID, :nanoseconds)
t = (t2 - t1)*1e-9 / m
puts "#{bits},#{t},#{meth.to_s.sub(/big_mul_/, "")}"
methods.delete meth if 1.0/m < t

It seems GMP is faster when multiplication arguments are longer than 1000 bits
on my environment.
See bignum-mul-gmp.png for details.

I guess other operations, division and radix conversion, can also be faster using GMP.

Any comments?


bignum-mul-gmp.patch (5.04 KB) bignum-mul-gmp.patch akr (Akira Tanaka), 08/17/2013 04:10 AM
bignum-mul-gmp.png (22.6 KB) bignum-mul-gmp.png akr (Akira Tanaka), 08/17/2013 04:10 AM

Also available in: Atom PDF