## Feature #8796

### Use GMP to accelerate Bignum operations

Status: | Closed | ||
---|---|---|---|

Priority: | Normal | ||

Assignee: | Akira Tanaka | ||

Category: | - | ||

Target version: | 2.1.0 |

**Description**

How about using GMP to accelerate Bignum operations?

GMP: The GNU Multiple Precision Arithmetic Library

http://gmplib.org/

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*

methods.dup.each {|meth|

t1 = Process.clockgettime(Process::CLOCK

m = 1000

n1 = 3*

*60*

100.times {

n1 = n1 * (n1 >> (n1.size8/15100.times {

n1 = n1 * (n1 >> (n1.size

*14))*

n2 = n1 + 1

bits = n1.size8n2 = n1 + 1

bits = n1.size

methods.dup.each {|meth|

t1 = Process.clock

*THREAD*CPUTIME

*ID, :nanoseconds)*

n1.send(meth, n2) rescue next

(m-1).times { n1.send(meth, n2) }

t2 = Process.clockgettime(Process::CLOCK

n1.send(meth, n2) rescue next

(m-1).times { n1.send(meth, n2) }

t2 = Process.clock

*THREAD*CPUTIME

*ID, :nanoseconds)*

t = (t2 - t1)*1e-9 / m

puts "#{bits},#{t},#{meth.tos.sub(/big

t = (t2 - t1)*1e-9 / m

puts "#{bits},#{t},#{meth.to

*mul*/, "")}"

methods.delete meth if 1.0/m < t

}

STDOUT.flush

}

'

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?

### History

#### #1 Updated by Eric Wong 8 months ago

"akr (Akira Tanaka)" akr@fsij.org wrote:

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.

I'm happy with LGPL :)

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.

Is there more performance improvement without the conversion?

How about push the conversion cost to legacy C API users to make

Bignum faster for pure-Ruby use in a future patch?

I'm mainly curious about "smaller" Bignums for users on 32-bit systems,

but I suspect much of that cost is object allocation.

#### #2 Updated by Akira Tanaka 8 months ago

2013/8/17 Eric Wong normalperson@yhbt.net:

Is there more performance improvement without the conversion?

How about push the conversion cost to legacy C API users to make

Bignum faster for pure-Ruby use in a future patch?

It is same as ko1's idea.

I don't against it.

Feel free to implement and propose it.

However it has several difficulties.

It is a big task.

It need to implement all methods, not just slow methods.ABI incompatibility.

ko1 tackles this in Feature #6083.LGPL

It is no problem for me but I guess some people don't accept it.

So we need to maintain non-GMP implementation anyway.

Maintaining two implementations is troublesome.We cannot access internal of mpz

*t.*getlimbn and mpz_size may be enough?)

We may be limited to add new feature with optimal performance.

(mpzIt cannot embed small bignums.

So it needs more memory allocation.## (mpz

*array*init may solve this problem?)¶Tanaka Akira

#### #3 Updated by Yukihiro Matsumoto 8 months ago

**Assignee**set to*Akira Tanaka*

This is internal. So go ahead and experiment.

Matz.

#### #4 Updated by Yui NARUSE 7 months ago

**Status**changed from*Open*to*Closed***Target version**set to*2.1.0*

Introduced on r42743.