BigNum optimizations

Discussion in 'Ruby' started by Artem Voroztsov, Mar 16, 2009.

  1. 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
    Artem Voroztsov, Mar 16, 2009
    #1
    1. Advertising

  2. On Mon, Mar 16, 2009 at 4:23 PM, Yukihiro Matsumoto <> wr=
    ote:
    > Hi,
    >
    > In message "Re: BigNum optimizations"
    > =C2=A0 =C2=A0on Tue, 17 Mar 2009 07:49:20 +0900, Artem Voroztsov <artem.v=

    > 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/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, Mar 17, 2009
    #2
    1. Advertising

  3. On Tue, Mar 17, 2009 at 5:56 PM, Yukihiro Matsumoto <> wr=
    ote:
    > Hi,
    >
    > In message "Re: BigNum optimizations"
    > =C2=A0 =C2=A0on Wed, 18 Mar 2009 04:11:34 +0900, "M. Edward (Ed) Borasky"=

    <> 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.
    M. Edward (Ed) Borasky, Mar 18, 2009
    #3
  4. 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
    Charles Oliver Nutter, Mar 18, 2009
    #4
  5. 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" <> 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
    Jeremy Hinegardner, Mar 20, 2009
    #5
  6. On Tue, Mar 17, 2009 at 6:10 PM, Yukihiro Matsumoto <> 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=
    M. Edward (Ed) Borasky, Mar 20, 2009
    #6
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. niju

    Optimizations

    niju, Aug 21, 2005, in forum: ASP .Net
    Replies:
    1
    Views:
    386
    tom pester
    Aug 21, 2005
  2. =?Utf-8?B?Sm9obiBHcmFudA==?=

    Webpart optimizations

    =?Utf-8?B?Sm9obiBHcmFudA==?=, May 2, 2006, in forum: ASP .Net
    Replies:
    3
    Views:
    1,655
    Robert Bogue [MVP]
    May 26, 2006
  3. Rob Adelberg

    switch statement optimizations

    Rob Adelberg, Sep 18, 2003, in forum: C++
    Replies:
    5
    Views:
    375
    Ron Natalie
    Sep 18, 2003
  4. Scott Robert Ladd
    Replies:
    2
    Views:
    349
    Gianni Mariani
    Nov 17, 2003
  5. zb32

    bitfield optimizations

    zb32, Jul 13, 2004, in forum: C++
    Replies:
    1
    Views:
    1,052
    David Harmon
    Jul 13, 2004
Loading...

Share This Page