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

    $ 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)

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

  2. =A0 =C2=A0total =C2=A0 =C2=A0 =C2=A0 =C2=A0real
    =A0 =C2=A0total =C2=A0 =C2=A0 =C2=A0 =C2=A0real
    =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. Advertisements

  3. I just checked ... GMP is LGPL. Would that work?
    =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. 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. How about libtommath/libtomfastmath ? there is a gem of it available:

    http://math.libtomcrypt.com/

    enjoy,

    -jeremy
     
    Jeremy Hinegardner, Mar 20, 2009
    #5
  6.  
    M. Edward (Ed) Borasky, Mar 20, 2009
    #6
    1. Advertisements

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.