BigNum optimizations

[Artem Voroztsov]

Time for multiplication of BigNums grows quadratically with number of
digits (ruby 1.8.7). And in ruby 1.9 is lower than in ruby 1.8:

require 'benchmark'

Benchmark.bmbm do |b|
[100, 200, 400, 800, 1600].each do |n|
num =3D 1123 ** n
b.report "#{n}" do
1000.times{num*num}
end
end
end

ruby -v a.rb

ruby 1.8.7 (2008-08-11 patchlevel 72) [i486-linux]
Rehearsal ----------------------------------------
100 0.010000 0.000000 0.010000 ( 0.010418)
200 0.030000 0.000000 0.030000 ( 0.036871)
400 0.130000 0.000000 0.130000 ( 0.125760)
800 0.460000 0.000000 0.460000 ( 0.482740)
1600 1.810000 0.000000 1.810000 ( 1.903963)
------------------------------- total: 2.440000sec

user system total real
100 0.020000 0.000000 0.020000 ( 0.008206)
200 0.020000 0.000000 0.020000 ( 0.029941)
400 0.120000 0.000000 0.120000 ( 0.115787)
800 0.460000 0.000000 0.460000 ( 0.459517)
1600 1.770000 0.020000 1.790000 ( 1.807655)

Exit code: 0

$ ruby1.9 -v a.rb
ruby 1.9.0 (2008-06-20 revision 17482) [i486-linux]
Rehearsal ----------------------------------------
100 0.020000 0.000000 0.020000 ( 0.013167)
200 0.040000 0.000000 0.040000 ( 0.046076)
400 0.150000 0.000000 0.150000 ( 0.150487)
800 0.540000 0.010000 0.550000 ( 0.589719)
1600 2.200000 0.000000 2.200000 ( 2.258581)
------------------------------- total: 2.960000sec

user system total real
100 0.000000 0.000000 0.000000 ( 0.009808)
200 0.040000 0.000000 0.040000 ( 0.037194)
400 0.140000 0.000000 0.140000 ( 0.144723)
800 0.560000 0.000000 0.560000 ( 0.587338)
1600 2.210000 0.000000 2.210000 ( 2.254998)

Exit code: 0

+1 for making it faster, i.e. N log N.

It looks like BigNum will be faster in next release
(http://redmine.ruby-lang.org/search/index/ruby-19?q=3DKaratsuba), is it
true?
But why Karatsuba? It is only O(N**1.585) while Sch=F6nhage=96Strassen is
O(N log N).

I guess it is more reasonable to implement
http://en.wikipedia.org/wiki/Schönhage–Strassen_algorithm
or take use of any GPL soft

See also talk http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/7=
7470
dated 30 Jul 2003

Artem Voroztsov

 

[M. Edward (Ed) Borasky]

Hi,

In message "Re: BigNum optimizations"
=C2=A0 =C2=A0on Tue, 17 Mar 2009 07:49:20 +0900, Artem Voroztsov <artem.v=

|+1 for making it faster, =C2=A0i.e. =C2=A0N log N.
|
|It looks like BigNum will be faster in next release
|(http://redmine.ruby-lang.org/search/index/ruby-19?q=3DKaratsuba), is it
|true?

True.

% ruby -v a.rb
ruby 1.8.7 (2008-08-11 patchlevel 72) [i486-linux]
Rehearsal ----------------------------------------
100 =C2=A0 =C2=A00.020000 =C2=A0 0.000000 =C2=A0 0.020000 ( =C2=A00.02429= 0)
200 =C2=A0 =C2=A00.070000 =C2=A0 0.000000 =C2=A0 0.070000 ( =C2=A00.07293= 4)
400 =C2=A0 =C2=A00.120000 =C2=A0 0.000000 =C2=A0 0.120000 ( =C2=A00.12355= 1)
800 =C2=A0 =C2=A00.490000 =C2=A0 0.000000 =C2=A0 0.490000 ( =C2=A00.51430= 2)
1600 =C2=A0 1.900000 =C2=A0 0.000000 =C2=A0 1.900000 ( =C2=A01.971061)
------------------------------- total: 2.600000sec

=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 user =C2=A0 =C2=A0 system =C2=A0 =C2=

=A0 =C2=A0total =C2=A0 =C2=A0 =C2=A0 =C2=A0real

100 =C2=A0 =C2=A00.010000 =C2=A0 0.000000 =C2=A0 0.010000 ( =C2=A00.01582= 5)
200 =C2=A0 =C2=A00.030000 =C2=A0 0.000000 =C2=A0 0.030000 ( =C2=A00.04889= 6)
400 =C2=A0 =C2=A00.120000 =C2=A0 0.000000 =C2=A0 0.120000 ( =C2=A00.12494= 7)
800 =C2=A0 =C2=A00.480000 =C2=A0 0.000000 =C2=A0 0.480000 ( =C2=A00.49055= 7)
1600 =C2=A0 1.900000 =C2=A0 0.000000 =C2=A0 1.900000 ( =C2=A01.905196)

% ruby1.9 -v a.rb
ruby 1.9.2dev (2009-03-15 trunk 22972) [i686-linux]
Rehearsal ----------------------------------------
100 =C2=A0 =C2=A00.020000 =C2=A0 0.000000 =C2=A0 0.020000 ( =C2=A00.03090= 5)
200 =C2=A0 =C2=A00.040000 =C2=A0 0.000000 =C2=A0 0.040000 ( =C2=A00.04532= 8)
400 =C2=A0 =C2=A00.080000 =C2=A0 0.000000 =C2=A0 0.080000 ( =C2=A00.08467= 0)
800 =C2=A0 =C2=A00.250000 =C2=A0 0.000000 =C2=A0 0.250000 ( =C2=A00.27513= 0)
1600 =C2=A0 0.770000 =C2=A0 0.000000 =C2=A0 0.770000 ( =C2=A00.796491)
------------------------------- total: 1.160000sec

=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 user =C2=A0 =C2=A0 system =C2=A0 =C2=

=A0 =C2=A0total =C2=A0 =C2=A0 =C2=A0 =C2=A0real

100 =C2=A0 =C2=A00.010000 =C2=A0 0.000000 =C2=A0 0.010000 ( =C2=A00.00773= 1)
200 =C2=A0 =C2=A00.020000 =C2=A0 0.000000 =C2=A0 0.020000 ( =C2=A00.02616= 7)
400 =C2=A0 =C2=A00.070000 =C2=A0 0.000000 =C2=A0 0.070000 ( =C2=A00.09287= 4)
800 =C2=A0 =C2=A00.260000 =C2=A0 0.000000 =C2=A0 0.260000 ( =C2=A00.25695= 1)
1600 =C2=A0 0.770000 =C2=A0 0.000000 =C2=A0 0.770000 ( =C2=A00.807816)

|But why Karatsuba? It is only O(N**1.585) =C2=A0while Sch=C3=B6nhage=E2= =80=93Strassen is
|O(N log N).

It's matter of the resource we have. =C2=A0If some one would volunteer to
implement it, we'd love to merge.

=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=

=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0matz.

It might be easier to link to a standard open-source multi-precision
library that it would be to revise the one that's built into the Ruby
interpreters. I haven't benchmarked these against each other, but the
two I know about are GMP http://gmplib.org/ and CLN
http://www.ginac.de/CLN/. Both are GPL. GMP is available in just about
every Linux distro I know about; CLN may be a little harder to find,
but it's in Debian and Gentoo. I don't know about other platforms, but
at least GMP is "pure-enough" GNU that it should compile on Windows
and Macs and Solaris.

Ezra ... is this something Engine Yard could do for 1.8.6 / Rubinius?
I think the jRuby people are working on their Bignum performance too.



--=20
M. Edward (Ed) Borasky
http://www.linkedin.com/in/edborasky

I've never met a happy clam. In fact, most of them were pretty steamed.

 

[M. Edward (Ed) Borasky]

Hi,

In message "Re: BigNum optimizations"
=C2=A0 =C2=A0on Wed, 18 Mar 2009 04:11:34 +0900, "M. Edward (Ed) Borasky"=

|It might be easier to link to a standard open-source multi-precision
|library that it would be to revise the one that's built into the Ruby
|interpreters. I haven't benchmarked these against each other, but the
|two I know about are GMP http://gmplib.org/ and CLN
|http://www.ginac.de/CLN/. Both are GPL.

We cannot link pure GPLed library to Ruby for licensing issue. =C2=A0Last
time I checked none of these multi precision numeric libraries
satisfied our criteria (license, portability, etc). =C2=A0GMP (or CLN or
whatever) can be used via extension, and we are happy to offer help if
required.

I just checked ... GMP is LGPL. Would that work?

=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=

=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0matz.


--=20
M. Edward (Ed) Borasky
http://www.linkedin.com/in/edborasky

I've never met a happy clam. In fact, most of them were pretty steamed.

 

[Charles Oliver Nutter]

Ezra ... is this something Engine Yard could do for 1.8.6 / Rubinius?
I think the jRuby people are working on their Bignum performance too.

We're mostly just wrapping the JDK's builtin BigInteger class, which is
not known for its scorching performance. BigInteger.doubleValue actually
passes the number through a a String and re-parses it (a contributor
implemented a replacement, for obvious reasons). There are alternative
libraries, but we have not merged them in to avoid bloating the size of
JRuby's distribution.

Of course almost all of them can be called directly through our Java
integration layer, so if people need the performance they can do that.
Java 7 is supposed to include a number of performance improvements for
BigInteger as well.

We would not decline a clean-room implementation of Bignum that uses the
latest and greatest algorithms It would probably be easier in Java
than in C.

- Charlie

 

[Jeremy Hinegardner]

Hi,

In message "Re: BigNum optimizations"

|> We cannot link pure GPLed library to Ruby for licensing issue. ?Last
|> time I checked none of these multi precision numeric libraries
|> satisfied our criteria (license, portability, etc). ?GMP (or CLN or
|> whatever) can be used via extension, and we are happy to offer help if
|> required.
|
|I just checked ... GMP is LGPL. Would that work?

Well, it's not impossible (i.e. 1.8 regex was LGPL), but not ideal.
Some commercial Ruby users had to replace 1.8 regex by Oniguruma only
for a license issue. I don't want to see same situation for bignums.

How about libtommath/libtomfastmath ? there is a gem of it available:

http://math.libtomcrypt.com/

enjoy,

-jeremy

 

[M. Edward (Ed) Borasky]

|I just checked ... GMP is LGPL. Would that work?

Well, it's not impossible (i.e. 1.8 regex was LGPL), but not ideal.
Some commercial Ruby users had to replace 1.8 regex by Oniguruma only
for a license issue. =C2=A0I don't want to see same situation for bignums=