Results 1 to 3 of 3

Math Help - perform basic operations on large numbers algorithm?

  1. #1
    Newbie
    Joined
    Oct 2008
    Posts
    2

    perform basic operations on large numbers algorithm?

    is there such an algorithm for doing something like add a large integral numbers in sections?

    the reason i ask is in computer science numbers can't be bigger than 2^32, so to emulate operations of a number of 2^256 you have to calcuate it doing many smaller calculations.

    now i know that to mulitply two large(positive) numbers you can put them in a box, say 153 * 86 can be represented as (100*80)+(100*6)+(50*80)+(50*6)+(3*80)+(3*6) which is the only idea i have to work this out

    basically the result of a small calcuation can't result in a number −2,147,483,648 to +2,147,483,647 (-2^31 to 2^31)

    so i guess all calcuations should be done with two numbers below 2^16 so that the outcome can't be greater than 2^32

    any help would be apprecitated, this isn't homework or anything just trying to write something?

    thanks for your time
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2008
    From
    Paris, France
    Posts
    1,174
    Quote Originally Posted by i_heart_pandas View Post
    is there such an algorithm for doing something like add a large integral numbers in sections?
    Yes, there is, and this is like how you learnt to add numbers at school: Begin from the right. Add the corresponding sections, this gives you a number that fits in a section plus a carry. Then add the carry to the next section (to the left) of any of the numbers you're adding. And do the same for the next section.
    To do this, you must be sure that the sum of any two sections + a carry (hence 3 times the maximum number in a section) does not exceed the capacity of the type of variable you use.

    For the multiplication, this is the same: like at school, to multiply a by b, first multiply a by the right-most section of b (you do this by multiplying section after section and adding the carries like before), then multiply a by the next section of b, and sum this with the previous result, and so on.
    To do this, you must be sure that the product of any two sections + a carry is not too large (you can use another type of variable to store the product before you compute and substract the carry).

    Multiplying numbers is a long task, that's why people tried to find faster algorithms. The most efficient one relies on FFT (fast fourier transform), it is much more efficient than the "school algorithm" but more complex to implement.

    To take better advantage of the structure of computers, the "sections" are usually defined using the binary expression for a number, and the translation from/to digits (base 10) is done at the beginning/end, once and for all. But it is easier to define sections in base 10 if you want to write a sample program of addition/multiplication of large numbers.

    There must be a lot of ressource on the internet about this, you should look for it.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2008
    Posts
    2
    yes thanks, i've looked into these algorithms and found out that they where easier to find than i thought, thanks
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 4
    Last Post: March 31st 2010, 11:50 AM
  2. Perform the indicated operations and simplify
    Posted in the Algebra Forum
    Replies: 3
    Last Post: December 16th 2009, 08:57 PM
  3. Complex Numbers-basic operations
    Posted in the Pre-Calculus Forum
    Replies: 4
    Last Post: July 26th 2009, 03:05 AM
  4. Perform Indicated Operations and Simplify
    Posted in the Algebra Forum
    Replies: 1
    Last Post: February 17th 2009, 05:26 AM
  5. Perform operations on vectors
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: April 29th 2008, 09:15 PM

Search Tags


/mathhelpforum @mathhelpforum