[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.ruby

Re: BigNum optimizations

Yukihiro Matsumoto

3/16/2009 11:24:00 PM

Hi,

In message "Re: BigNum optimizations"
on Tue, 17 Mar 2009 07:49:20 +0900, Artem Voroztsov <artem.voroztsov@gm=
ail.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=3...), 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=C3=B6nhage=E2=80=93St=
rassen 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.
4 Answers

A to Z

3/15/2009 2:44:00 PM

0


"A to Z" <REMOVETHESEaddietzCAPS@verizonPLEASE.net> wrote in message
news:724id7Fo2mvkU1@mid.individual.net...
>
> "Ben Lazar" <BLazar70@gmail.com> wrote in message
> news:ebc42f03-feb7-4c4f-a7f0-9a4764934318@v38g2000yqb.googlegroups.com...
> On Mar 15, 10:12 am, "A to Z"
> <REMOVETHESEaddietzC...@verizonPLEASE.net> wrote:
>> IF - since it's still unsettled, IF...
>>
>> then I got a bit of an issue with it:
>>
>> a feeling that bringing the kid in is...
>> a) pandering - I can't put my finger on exactly what, but taking someone
>> because their name is Weinberg (or Clemons or any one else from the band)
>> strikes me as pandering to fans who value name (E Street) over
>> performance.
>> b) making Bruce more of an novelty act - he can't be truly an oldies act
>> since he tours behind new material each time, but choosing the kid does
>> have
>> a certain gimmicky novelty feel to it
>> c) settling - perhaps Jay is great. I don't know, I have never seen him
>> play. I have heard that he did a decent job in his guest shot - maybe
>> even
>> playing faster than his dad, which I would like, since it eliminates the
>> "plod" that is too common nowadays. But that was for a couple of songs at
>> one show. Can he take a few months of a tour? Can he play on anything
>> other
>> than BTR? Does he have pro experience? Is he in a band now, has he been
>> in a
>> band? Is he a professional caliber drummer? The answer to all these
>> questions may be yes. BUt this is Bruce Springsteen and the E Street
>> Band,
>> they could get any drummer that was looking for work and a bunch that
>> aren't. Maybe they know something about Jay that I don't (they must), but
>> unless he is a prodigy waiting to bust out, it seems to me that the
>> selection of Max is settling for less than they could get, and THAT is
>> the
>> real problem. Bruce used not to settle.
>>
>> --
>> It's about hope
>> It's about brains
>> It's about time
>
> Bottom line is none of us have any idea. If Jay is the drummer and
> can bring it, awesome. If he can't, then it's an issue. But I trust
> that Bruce knows what he's doing in the realm of band leader. It
> seems kind of absurd to me to already having "issues" with something
> that you and everyone else have no idea about. You've attached all
> sorts of meaning to what having Jay drum with the band may mean
> (leaving other drummers out of work, "settling," etc.) - and I assert
> that NONE of it is true.
>
> All that matters is if Jay can deliver on every song, every night. If
> not, then by all means hold Bruce accountable.
>
> -----------------
> I think that's pretty much what I just said

except that I did not say anything about leaving other drummers out of
work - I said that they are professional drummers looking for a gig - i.e.,
available - instead of an ingenue with the Weinberg name. I don't care about
the employment situation amongst drummers except for the pbvious platitude
that it would be great if everyone had a job.


likeavision

3/16/2009 2:00:00 AM

0

hey gang. i have seen jay play and he is the real deal. if he has been
growing up by his dad and bruce's side i assume he will be able to
jump in. not to be sacreligious but he is a way better drummer than
his dad. he plays HARD like dave grohl. if anything it might be a bad
move for him to be just a fill in for his dad in the E street band.

znmeb

3/17/2009 7:12:00 PM

0

On Mon, Mar 16, 2009 at 4:23 PM, Yukihiro Matsumoto <matz@ruby-lang.org> wr=
ote:
> Hi,
>
> In message "Re: BigNum optimizations"
> =C2=A0 =C2=A0on Tue, 17 Mar 2009 07:49:20 +0900, Artem Voroztsov <artem.v=
oroztsov@gmail.com> 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=3...), 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://g... and CLN
http://www.gin.... 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...

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

Charles Oliver Nutter

3/18/2009 3:18:00 AM

0

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