From: Robert Feldt <feldt@...>
Date: 2003-07-31T06:44:43+09:00
Subject: Re: Bignum multiplication

<nobu.nokada@softhome.net> skrev den Wed, 30 Jul 2003 19:19:40 +0900:

> Hi,
>
> At Wed, 30 Jul 2003 18:46:10 +0900,
> Yukihiro Matsumoto wrote:
>> |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,

-- 
Robert Feldt