From: "M. Edward (Ed) Borasky" <zznmeb@...>
Date: 2009-03-18T04:11:34+09:00
Subject: Re: BigNum optimizations

On Mon, Mar 16, 2009 at 4:23 PM, Yukihiro Matsumoto <matz@ruby-lang.org> wrote:
> Hi,
>
> In message "Re: BigNum optimizations"
>    on Tue, 17 Mar 2009 07:49:20 +0900, Artem Voroztsov <artem.voroztsov@gmail.com> writes:
>
> |+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=Karatsuba), is it
> |true?
>
> True.
>
> % ruby -v a.rb
> ruby 1.8.7 (2008-08-11 patchlevel 72) [i486-linux]
> Rehearsal ----------------------------------------
> 100    0.020000   0.000000   0.020000 (  0.024290)
> 200    0.070000   0.000000   0.070000 (  0.072934)
> 400    0.120000   0.000000   0.120000 (  0.123551)
> 800    0.490000   0.000000   0.490000 (  0.514302)
> 1600   1.900000   0.000000   1.900000 (  1.971061)
> ------------------------------- total: 2.600000sec
>
>           user     system      total        real
> 100    0.010000   0.000000   0.010000 (  0.015825)
> 200    0.030000   0.000000   0.030000 (  0.048896)
> 400    0.120000   0.000000   0.120000 (  0.124947)
> 800    0.480000   0.000000   0.480000 (  0.490557)
> 1600   1.900000   0.000000   1.900000 (  1.905196)
>
> % ruby1.9 -v a.rb
> ruby 1.9.2dev (2009-03-15 trunk 22972) [i686-linux]
> Rehearsal ----------------------------------------
> 100    0.020000   0.000000   0.020000 (  0.030905)
> 200    0.040000   0.000000   0.040000 (  0.045328)
> 400    0.080000   0.000000   0.080000 (  0.084670)
> 800    0.250000   0.000000   0.250000 (  0.275130)
> 1600   0.770000   0.000000   0.770000 (  0.796491)
> ------------------------------- total: 1.160000sec
>
>           user     system      total        real
> 100    0.010000   0.000000   0.010000 (  0.007731)
> 200    0.020000   0.000000   0.020000 (  0.026167)
> 400    0.070000   0.000000   0.070000 (  0.092874)
> 800    0.260000   0.000000   0.260000 (  0.256951)
> 1600   0.770000   0.000000   0.770000 (  0.807816)
>
> |But why Karatsuba? It is only O(N**1.585)  while Schönhage–Strassen is
> |O(N log N).
>
> It's matter of the resource we have.  If some one would volunteer to
> implement it, we'd love to merge.
>
>                                                        matz.

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.



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