Bignum multiplication

Discussion in 'Ruby' started by Harry Ohlsen, Jul 30, 2003.

  1. Harry Ohlsen

    Harry Ohlsen Guest

    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.
     
    Harry Ohlsen, Jul 30, 2003
    #1
    1. Advertisements

  2. 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.
     
    Yukihiro Matsumoto, Jul 30, 2003
    #2
    1. Advertisements

  3. Harry Ohlsen

    nobu.nokada Guest

    Hi,

    At Wed, 30 Jul 2003 18:46:10 +0900,
    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.
     
    nobu.nokada, Jul 30, 2003
    #3
  4. Harry Ohlsen

    Harry Ohlsen Guest

    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.
    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, Jul 30, 2003
    #4
  5. Harry Ohlsen

    Harry Ohlsen Guest

    Me, too :). I enjoy mathematics a lot, but am not good enough at it to
    implement something like Karatsuba.
    Interesting. I'd have sworn it was Japanese, too.

    Harry O.
     
    Harry Ohlsen, Jul 30, 2003
    #5
  6. Harry Ohlsen

    nobu.nokada Guest

    Hi,

    At Wed, 30 Jul 2003 19:45:15 +0900,
    Hmmm. It's not found.
    I have a copy but am not sure if it's allowed. I'll ask him
    about it and importing to bignum.c.
     
    nobu.nokada, Jul 30, 2003
    #6
  7. Yeah, Ruby Kamasutra sounds like fun...
     
    Florian Frank, Jul 30, 2003
    #7
  8. Everything's an object.

    *duck*

    Brandon D. Valentine
     
    Brandon D. Valentine, Jul 30, 2003
    #8
  9. Harry Ohlsen

    Robert Feldt Guest

    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, Jul 30, 2003
    #9
  10. LOL! Everything is a sex object.
     
    Florian Frank, Jul 31, 2003
    #10
    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.