Facebook Page
Twitter
RSS
+ Reply to Thread
Results 1 to 4 of 4
  1. MHB Master
    MHB Site Helper
    mathmari's Avatar
    Status
    Offline
    Join Date
    Apr 2013
    Posts
    2,711
    Thanks
    2,160 times
    Thanked
    685 times
    Awards
    MHB Chat Room Award (2015)  

MHB Model User Award (2015)  

MHB LaTeX Award (2015)
    #1
    Hey!!

    With the term "elementary operation" we mean to add two digits of the decimal system and to write the result and the carries. How many elementary operations do we need for the addition of two numbers with $n$ digits?
    (we consider that the addition of two digits together with the carry that comes from previous operations is one elementary operation)

    If we add two numbers with $n$ digits, we add at each step two digits, one of each number, and possibly a carry. That means that we need $n$ elementary operations.

    Is this correct?

    How could we show that the addition of any two numbers with $n$ digits each one of them, cannot be done with less than $n$ steps/elementary operations?

  2. MHB Seeker
    MHB Global Moderator
    MHB Math Scholar
    I like Serena's Avatar
    Status
    Offline
    Join Date
    Mar 2012
    Location
    Netherlands
    Posts
    6,226
    Thanks
    4,172 times
    Thanked
    11,678 times
    Thank/Post
    1.876
    Awards
    MHB Model Helper Award (2016)  

MHB Best Ideas (2016)  

MHB LaTeX Award (2016)  

MHB Calculus Award (2014)  

MHB Discrete Mathematics Award (Jul-Dec 2013)
    #2
    Hey!!!

    Yes, that is correct.

    To add two n-digit numbers, each digit will have to be processed.
    So we need at least n operations.

  3. MHB Master
    MHB Site Helper
    mathmari's Avatar
    Status
    Offline
    Join Date
    Apr 2013
    Posts
    2,711
    Thanks
    2,160 times
    Thanked
    685 times
    Awards
    MHB Chat Room Award (2015)  

MHB Model User Award (2015)  

MHB LaTeX Award (2015)
    #3 Thread Author
    Quote Originally Posted by I like Serena View Post
    Yes, that is correct.



    Quote Originally Posted by I like Serena View Post
    To add two n-digit numbers, each digit will have to be processed.
    So we need at least n operations.
    I see...


    What about the multiplication? In this case we have to count separately the number of elementary additions and elementary multiplications (i.e., multiplications of two digits and writing the carries).
    Can the multiplication of two $n$-digit numbers be done in less than $n$ elementary multiplications?
    (we have to notice that the answer is not obvious as in the case of the addition. It can be done in about $cn \ln n$ elementary multiplications, for a constant $c$. This can be achieved using the Fast Fourier Transform. It is not known if this bound is optimal.)


    To multiplicate two $n$-digit numbers, do we not have to execute $n^2$ elementary multiplications and $2n-1$ elementary additions?

    Could you explain to me how the Fast Fourier Transform is related to the multiplications of two numbers?

  4. MHB Seeker
    MHB Global Moderator
    MHB Math Scholar
    I like Serena's Avatar
    Status
    Offline
    Join Date
    Mar 2012
    Location
    Netherlands
    Posts
    6,226
    Thanks
    4,172 times
    Thanked
    11,678 times
    Thank/Post
    1.876
    Awards
    MHB Model Helper Award (2016)  

MHB Best Ideas (2016)  

MHB LaTeX Award (2016)  

MHB Calculus Award (2014)  

MHB Discrete Mathematics Award (Jul-Dec 2013)
    #4
    Quote Originally Posted by mathmari View Post
    To multiplicate two $n$-digit numbers, do we not have to execute $n^2$ elementary multiplications and $2n-1$ elementary additions?
    The straight forward way to multiply requires indeed $n^2$ elementary multiplications.
    After that, I think it takes $n^2-1$ elementary additions though.

    Quote Quote:
    Could you explain to me how the Fast Fourier Transform is related to the multiplications of two numbers?
    Well, this is the first time I hear about it.
    Let me see...

    If we multiply $\sum a_i 10^i$ with $\sum b_j 10^j$, we get:
    $$\sum_i a_i 10^i \cdot \sum_j b_j 10^j
    = \sum_i\sum_j (a_i 10^i) \cdot (b_j 10^j)
    = \sum_m\sum_i (a_i 10^i) \cdot (b_{m-i} 10^{m-i})
    = \sum_m c_m
    $$
    This is the sum of a sequence of convolutions, meaning we can apply the :
    $$
    c_m = \mathscr F^{-1}\{\mathscr F\{a_m10^m\} \cdot \mathscr F\{b_m10^m\}\}
    $$

    Since the FFT takes $O(n\log n)$ operations, evaluating all $c_m$ also takes $O(n\log n)$ operations.
    After that they only need to be summed.

    To be honest, I'm still not clear how it would work exactly, but I suspect it works something like this.

Similar Threads

  1. Result of operations
    By evinda in forum Computer Science
    Replies: 1
    Last Post: May 17th, 2015, 15:43
  2. Bit Operations
    By HELPMEHELPME in forum Computer Science
    Replies: 4
    Last Post: April 26th, 2015, 14:53
  3. Order of Operations
    By Marvin Kalngan in forum Pre-Algebra and Algebra
    Replies: 1
    Last Post: April 19th, 2014, 21:48
  4. operations on sets
    By bergausstein in forum Discrete Mathematics, Set Theory, and Logic
    Replies: 1
    Last Post: August 5th, 2013, 09:56
  5. Operations on sets II
    By bergausstein in forum Pre-Algebra and Algebra
    Replies: 1
    Last Post: August 2nd, 2013, 21:54

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
Math Help Boards