Bignum multiplication

[Harry Ohlsen]

I was just reading about Python 2.3 and they talked about how they've changed their arbitrary-precision integer multiplication to use the Karatsuba multiplication algorithm.

I heard about Karatsuba recently (in a book called Modern Computer Algebra).

That made me wonder whether this is what Ruby uses. Is it Karatsuba or something else?

Harry O.

 

[Yukihiro Matsumoto]

Hi,

In message "Bignum multiplication"

|That made me wonder whether this is what Ruby uses. Is it Karatsuba or something else?

It uses plain multiplication (as humans do). I once tried to
understand Karatsuba algorithm, but failed. Wish I had mathematical
brain.

matz.
p.s.
Karatsuba sounds like Japanese name for me. But I've heard he is
Russian.

 

[nobu.nokada]

Hi,

At Wed, 30 Jul 2003 18:46:10 +0900,

|That made me wonder whether this is what Ruby uses. Is it Karatsuba or something else?

It uses plain multiplication (as humans do). I once tried to
understand Karatsuba algorithm, but failed. Wish I had mathematical
brain.

I've just tested Ikegami's implementation announced at
[ruby-dev:35759], therefore it was nearly 7 times faster.

http://www.aist-nara.ac.jp/~daisu-ik/sources/bignum_mul-0.0.3.tar.gz

The tests seem to work fine.

 

[Harry Ohlsen]

I've just tested Ikegami's implementation announced at
[ruby-dev:35759], therefore it was nearly 7 times faster.

Fantastic! I'm definitely keen to have a play with that. I've been writing
some number theory code recently and the speed improvement would be helpful.

http://www.aist-nara.ac.jp/~daisu-ik/sources/bignum_mul-0.0.3.tar.gz

Unfortunately, that URL doesn't seem to be current. He has moved and there's
no link to this file there that I can see.

I don't suppose you could make your copy available somewhere? If not, I'll
just send him an e-mail.

Harry O.

 

[Harry Ohlsen]

It uses plain multiplication (as humans do). I once tried to
understand Karatsuba algorithm, but failed. Wish I had mathematical
brain.

Me, too . I enjoy mathematics a lot, but am not good enough at it to
implement something like Karatsuba.

p.s.
Karatsuba sounds like Japanese name for me. But I've heard he is
Russian.

Interesting. I'd have sworn it was Japanese, too.

Harry O.

 

[nobu.nokada]

Hi,

At Wed, 30 Jul 2003 19:45:15 +0900,

Unfortunately, that URL doesn't seem to be current. He has moved and there's
no link to this file there that I can see.

Hmmm. It's not found.

I don't suppose you could make your copy available somewhere? If not, I'll
just send him an e-mail.

I have a copy but am not sure if it's allowed. I'll ask him
about it and importing to bignum.c.

 

[Florian Frank]

Does this mean we have increasing likelyhood that the Kamasutra
algorithm will be the one used in 1.8.0 final?

Yeah, Ruby Kamasutra sounds like fun...

 

[Brandon D. Valentine]

Yeah, Ruby Kamasutra sounds like fun...

Everything's an object.

*duck*

Brandon D. Valentine

 

[Robert Feldt]

Hi,

At Wed, 30 Jul 2003 18:46:10 +0900,

|That made me wonder whether this is what Ruby uses. Is it Karatsuba or
something else?

It uses plain multiplication (as humans do). I once tried to
understand Karatsuba algorithm, but failed. Wish I had mathematical
brain.

I've just tested Ikegami's implementation announced at
[ruby-dev:35759], therefore it was nearly 7 times faster.

http://www.aist-nara.ac.jp/~daisu-ik/sources/bignum_mul-0.0.3.tar.gz

The tests seem to work fine.

I would recommend basing future Ruby's Bignum on LibTomMath
(http://math.libtomcrypt.org/). It has very liberal license and these
crypto guys know what they are doing . If you really want performance
Gnu MP is the way to go but its very large and complex to compile etc.
libtommath is ansic and easily packed as a single c file. I have it wrapped
for Ruby as LargeNum for my crypto lib. Its easy, fast and small and has
more functions than todays BigNum (like power modulo which is all over
crypto and which Python has, notch notch... ).

Libtommath's multiplication has heuristics for choosing multiplication and
uses karatsuba when its optimal.

Regards,

 

[Florian Frank]

Everything's an object.

LOL! Everything is a sex object.