MBignum in the core (was: Fwd: Re: GMP)

Just to chime in quickly. I have done another implementation of Bignums
called MBignum which uses libtommath for all the operations. I've found
it to be very fast but I have not yet done a formal speed test. In
addition, MBignum supports the number theory functions that libtommath
makes available, such as mod-exponent and such. The libtommath code has
proved to be very solid also. At some point in the past (This past June
I want to say), I emailed ruby-core concerning the integration of
MBignum into the distro based on the fact that libtommath has no
licenses restrictions upon it. After brief conversation, my normal work
load went up too much for me to continue working on a patch that would
replace Bignum with MBignum in the core. At any rate, as MBignum is
already available, and the patch is about 35% done, what do you (Matz)
and the rest of the core group thing about pushing forward with
integrating MBignum? MBignum is available at http://dark-ruby.org.
You'll see my crypt::random and crypt::rsa on there as well. Crypt::RSA
should be considered primary testcase for MBignum as it uses it for it's
number theory methods to implement RSA directly in ruby space which
still being considerably fast.

Evan Webb // [e-mail]

On Sat, 2004-10-30 at 03:05 +0900, trans. (T. Onoma) wrote:
> Hi ---
> 
> I contacted Tomasz Wegrzanowski <[e-mail]> concerning is work with 
> Ruby bindings for GMP, to see what insights he could provide. Very 
> enlightenting.
> 
> ---- Extracted reply of Tomasz Wegrzanowski:
> 
> I included some benchmarks with Ruby GMP, which compare the performance
>  against Ruby Bignum and against C GMP.
> 
> The numbers I got are here:
> http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/29707
> 
> Ruby BigNum was faster than Ruby GMP for small bignums, probably because the
>  cost of all the method calls was a lot greater than the actual bignum
>  computation (bmark3.rb and bmark4.rb try to compute the point at which it's
>  better to use GMP::Z than Ruby Bignum)
> 
> I don't know how much this overhead could be reduced by putting GMP closer to
>  Ruby core.
> 
> Ruby Bignum also has some kind of optimization for numbers ending with
> long strings of 0s. GMP doesn't have such thing. I don't think such
>  optimization is important for real computations, just don't make benchmark
>  testing performance of (2**n) * (2**m) multiplication.
> 
> The performance I expect:
> * For "small" bignums, like 128 or even 1024 bit, using GMP::Z is going to be
>  slower, unless the object overhead is seriously reduced
> * GMP::Z will be much (like 10:1) faster for larger bignums, like 16k-1M
>  bits, and even faster for extremely large bignums, but such bignums rarely
>  occur in normal software
> * If you want to do performance-sensitive computations, you need modifiable
>  objects. Because Ruby numbers are all const, "natural" Ruby way of using
>  GMP::Z is going to be slow. That is, a.add!(b) is much faster than a+=b
>   (it's tested by bmark2-gmp.rb vs bmark2-gmp_self.rb)
> * Therefore I think it wouldn't be wise to replace BigNum with GMP::Z unless
>  you can greatly reduce the overhead. Even in that case, don't expect
>  performance like C GMP with naive code. C++ GMP on the other hand compiles
>  naive code to something almost as fast as hand-coded C library calls, by
>  using template magic.
> * There is no equivalent of GMP::F and GMP::Q in Ruby.
>   GMP::Z also has some extra features not available for Ruby Bignums.
>   Newer version of GMP library have even more such features, but I haven't
>  included support for them in Ruby GMP.
>   Because of this, it might be useful to include GMP::F support in Ruby core,
>  whether or not GMP::Z is going to replace Bignum.
> 
> ----
> 
> T.
> 
-- 
Evan M. Webb <[e-mail]>