Multiplication of arbitrary large number.

Posted byJeetPosted inAlgorithm Brews..
    • Just as we do by hand.
    • Take an array of size of sum of the given numbers. for ex. 1000, 300 so size 7.
    • Multiply by digit to the number and store it in the array.
    • In short keep doing it just as we do by hand.
    • To optimize ,we can use linked list so as to avoid the extra memory usage due to array.

    Published by Jeet

    A software developer by profession. In spare time, fancy non-fiction mostly, related to history, finance and politics. A self-proclaimed movie buff - genre, time and era is no bar, only a sumptuous movie is!

    One thought on “Multiplication of arbitrary large number.”

    1. Also look for
      http://en.wikipedia.org/wiki/Multiplication_algorithm#Multiplication_algorithms_for_computer_algebra

      Peasant or binary multiplication
      ——————————————
      This example uses peasant multiplication to multiply 11 by 3 to arrive at a result of 33.

      Decimal: Binary:
      11 3 1011 11
      5 6 101 110
      2 12 10 1100
      1 24 1 11000
      — —–
      33 100001

      Describing the steps explicitly:

      * 11 and 3 are written at the top
      * 11 is halved (5.5) and 3 is doubled (6). The fractional portion is discarded (5.5 becomes 5).
      * 5 is halved (2.5) and 6 is doubled (12). The fractional portion is discarded (2.5 becomes 2). The figure in the left column (2) is even, so the figure in the right column (12) is discarded.
      * 2 is halved (1) and 12 is doubled (24).
      * All not-scratched-out values are summed: 3 + 6 + 24 = 33.

      Karatsuba multiplication
      ———————————–
      For systems that need to multiply numbers in the range of several thousand digits, such as computer algebra systems and bignum libraries, long multiplication is too slow. These systems may employ Karatsuba multiplication, which was discovered in 1960 (published in 1962). The heart of Karatsuba’s method lies in the observation that two-digit multiplication can be done with only three rather than the four multiplications classically required. Suppose we want to multiply two 2-digit numbers: x1x2· y1y2:

      1. compute x1 · y1, call the result A
      2. compute x2 · y2, call the result B
      3. compute (x1 + x2) · (y1 + y2), call the result C
      4. compute C − A − B,call the result “K”; this number is equal to x1 · y2 + x2 · y1.
      5. compute A · 100 + K · 10 + B

      Reply

    Leave a comment