Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Ruby > BigNum optimizations

Reply
Thread Tools

BigNum optimizations

 
 
Artem Voroztsov
Guest
Posts: n/a
 
      03-16-2009
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.01041
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.00980
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.58733
1600 2.210000 0.000000 2.210000 ( 2.25499
>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/...?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%C3%...ssen_algorithm
or take use of any GPL soft

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

Artem Voroztsov

 
Reply With Quote
 
 
 
 
M. Edward (Ed) Borasky
Guest
Posts: n/a
 
      03-17-2009
On Mon, Mar 16, 2009 at 4:23 PM, Yukihiro Matsumoto <(E-Mail Removed)> wr=
ote:
> Hi,
>
> In message "Re: BigNum optimizations"
> =C2=A0 =C2=A0on Tue, 17 Mar 2009 07:49:20 +0900, Artem Voroztsov <artem.v=

http://www.velocityreviews.com/forums/(E-Mail Removed)> writes:
>
> |+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/...?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=


> 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.

 
Reply With Quote
 
 
 
 
M. Edward (Ed) Borasky
Guest
Posts: n/a
 
      03-18-2009
On Tue, Mar 17, 2009 at 5:56 PM, Yukihiro Matsumoto <(E-Mail Removed)> wr=
ote:
> Hi,
>
> In message "Re: BigNum optimizations"
> =C2=A0 =C2=A0on Wed, 18 Mar 2009 04:11:34 +0900, "M. Edward (Ed) Borasky"=

<(E-Mail Removed)> writes:
>
> |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.

 
Reply With Quote
 
Charles Oliver Nutter
Guest
Posts: n/a
 
      03-18-2009
M. Edward (Ed) Borasky wrote:
> 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

 
Reply With Quote
 
Jeremy Hinegardner
Guest
Posts: n/a
 
      03-20-2009
On Wed, Mar 18, 2009 at 10:10:45AM +0900, Yukihiro Matsumoto wrote:
> Hi,
>
> In message "Re: BigNum optimizations"
> on Wed, 18 Mar 2009 10:01:07 +0900, "M. Edward (Ed) Borasky" <(E-Mail Removed)> writes:
>
> |> 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

--
================================================== ======================
Jeremy Hinegardner (E-Mail Removed)


 
Reply With Quote
 
M. Edward (Ed) Borasky
Guest
Posts: n/a
 
      03-20-2009
On Tue, Mar 17, 2009 at 6:10 PM, Yukihiro Matsumoto <(E-Mail Removed)> wr=
ote:
> |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=

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Webpart optimizations =?Utf-8?B?Sm9obiBHcmFudA==?= ASP .Net 3 05-25-2006 11:12 PM
Optimizations niju ASP .Net 1 08-21-2005 04:57 PM
bitfield optimizations zb32 C++ 1 07-13-2004 05:13 AM
An Evolutionary Analysis of GNU C Optimizations Scott Robert Ladd C++ 2 11-17-2003 11:20 PM
switch statement optimizations Rob Adelberg C++ 5 09-18-2003 06:10 PM



Advertisments