Karatsuba Multiplication

This is a discussion on Karatsuba Multiplication within the C Programming forums, part of the General Programming Boards category; Hi! I am looking for Karatsuba Multiplication Algorithm for large integers, mainly I mean implementation because theory does not help ...

  1. #1
    Registered User
    Join Date
    Apr 2005
    Posts
    6

    Unhappy Karatsuba Multiplication

    Hi! I am looking for Karatsuba Multiplication Algorithm for large integers, mainly I mean implementation because theory does not help me much. I would be much grateful for this. On the Internet I found one on Burch site, but it crashes when numbers get bigger than 10KB. The need is that it should operate on numbers of about 300KB or more.
    Please share your knowledge if you can. Maybe you know how to successfully improve the algorithm here:
    http://ozark.hendrix.edu/~burch/proj/karat/karat.txt
    it's good but like I say it does not operate on really big numbers.

    I am looking forward to your ideas or suggestions.

    Greetings!
    Last edited by author; 04-06-2005 at 02:09 PM.

  2. #2
    Senior Member joshdick's Avatar
    Join Date
    Nov 2002
    Location
    Phildelphia, PA
    Posts
    1,146
    And why can't you just increase the cap you placed on size?

  3. #3
    Registered User
    Join Date
    Apr 2005
    Posts
    6
    'cause there will be an overflow in int cells then, and this is the problem to sort out ...
    Carries should be applied according to the author, butt dunno where is the 'there'

  4. #4
    Tropical Coder Darryl's Avatar
    Join Date
    Mar 2005
    Location
    Cayman Islands
    Posts
    503
    I recently implemted a large integer class, initially I used int, but I ended up switching to long long (_int64) instead, then you can go really high before you overflow depending on your base. Also, what I did was figured out how many digits I could multiply before it overflow (9 in my case using base 1 billion) and during a multiplication operation checked to see what digit I was on, every eighth digit , I just did a carry operation on my total and then kept going instead of doing the carry at the very end.

  5. #5
    Registered User
    Join Date
    Apr 2005
    Posts
    6
    thx for your instructions Darryl!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 9
    Last Post: 05-22-2009, 08:03 AM
  2. Multiplication table
    By freddyvorhees in forum C++ Programming
    Replies: 6
    Last Post: 08-02-2008, 12:09 PM
  3. Help me find a multiplication toy.
    By QuestionC in forum A Brief History of Cprogramming.com
    Replies: 5
    Last Post: 08-24-2007, 01:27 PM
  4. ...multiplication using stacks
    By iiwhitexb0iii in forum C Programming
    Replies: 1
    Last Post: 10-09-2006, 02:28 AM
  5. multiplication table
    By SpEkTrE in forum C Programming
    Replies: 2
    Last Post: 12-09-2003, 04:46 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21