Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proof for operations algorithms

  1. Feb 23, 2005 #1
    Hi everybody,
    I would like to find proofs for the algorithms that we use to calculate sums,products,quotients... For example I would like to see how the long division algorithm is proved. Do you know any sites that have such proofs? Any help would be appreciated
    Thanks
     
  2. jcsd
  3. Feb 23, 2005 #2

    Galileo

    User Avatar
    Science Advisor
    Homework Helper

  4. Mar 1, 2005 #3
    Thanks for your answer, but i didn't actually find any answer to my question
     
  5. Mar 2, 2005 #4

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Work it out for yourself - the long division on is very easy, the others even easier and all rely, essentially, on the distributive nature of arithmetical operations - there really is nothing to "prove".
     
  6. Mar 2, 2005 #5

    arildno

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    Dearly Missed

    It can be relevant to remember that what we call a "division" algorithm, is a way to rewrite a
    fraction a/b into its equivalent decimal representation.

    On way of doing this, is by "guessing" the coefficients [tex]c_{n}[/tex] in the problem:
    [tex]a=b*\sum_{i=-\infty}^{M}c_{i}10^{i}[/tex]
    Be observant of how the different steps in this guessing procedure occurs in a systematic manner in the ordinary algorithm.
     
  7. Mar 2, 2005 #6
    Thanks for your answer. I think ,as matt grime mentioned, they are mostly based on the distributive property. I will also check your method arildno
     
  8. Dec 27, 2007 #7
    Division Theorem and Proof of Long Division Algorithm

    This theorem was discovered for division involving integers in the form a/b where a is greater than b. The cases where a = b or a < b are uninteresting.

    Many do not understand this simple theorem and it can be seen masquerading as the division algorithm in almost every learning institute. In truth, this has nothing to do with radix systems, nor does it define long division.

    I am going to illustrate why the long division algorithm works for the number abc/d where a,b,c and d are single digit integers and d is not zero. Assume that abc is represented in base 10.

    abc/d = (10ab + c)/d = 10ab/d + c/d


    Now let ab/d = q + r/d so that 10(ab/d) = 10(q+r/d)
    where r is a remainder. Note that q and r will always be single digits.

    Then we have:
    abc/d = 10(q + r/d) + c/d
    = 10q + 10r/d + c/d

    but 10r/d+ c/d = rc/d (since both r and c are single digits)

    So abc/d = 10q + rc/d

    This explains why we use the remainder of division as the significant digit for the next quotient in our long division process. For example, 120/8: 12 divided by 8 is 1 remainder 4. Then 40/8 = 5.

    Now let rc/d = k + t/d where t is a remainder. Note that k will always be a single digit.

    To see how this works, try 120/8 by substituting a=1 b =2 c=0 and d=8.

    120/8 = (10(12) + 0)/8 = 10(12)/8 + 0/8

    but 12/8 = 1 + 4/8 => 10(12/8) = 10(1+4/8)

    120/8 = 10(1+4/8) + 0/8
    = 10 + 40/8 + 0/8

    but 40/8 + 0/8 = 40/8

    So 120/8 = 10 + 40/8 = 10 + 5 = 15

    Now back to the division theorem. What does it say exactly?

    Given a/b, we can find unique integers q and r such that a = bq + r where r is the remainder of division. It is redundant to state that r < b but greater than or equal to 0. Since r is a remainder of the quotient a/b, it follows that it must be less than b.

    Similar logic is used in defining an alogorithm for division of abcd/ef or other quotients.
     
  9. Dec 29, 2007 #8
    Long Division Algorithm

    The following is a revision of the previous post:

    This theorem was discovered for division involving integers in the form a/b where a is greater than b. The cases where a = b or a < b are uninteresting.

    Many do not understand this simple theorem and it can be seen masquerading as the division algorithm in almost every learning institute. In truth, this does not rely only on the properties of radix systems, nor does it define long division.

    I am going to illustrate why the long division algorithm works for the number abc/d where a,b,c and d are single digit integers and d is not zero. Assume that abc is represented in base 10.

    abc/d = (10ab + c)/d = 10ab/d + c/d

    Now let ab/d = q + r/d so that 10(ab/d) = 10(q+r/d)
    where r is a remainder.

    Then we have:
    abc/d = 10(q + r/d) + c/d
    = 10q + 10r/d + c/d

    but 10r/d+ c/d = rc/d

    since r is shifted left through multiplication by 10

    So abc/d = 10q + rc/d

    This explains why we use the remainder of division as the significant digit for the next quotient in our long division process. For example, 120/8: 12 divided by 8 is 1 remainder 4. Then 40/8 = 5.

    Now let rc/d = k + t/d where t is a remainder. Note that k will always be a single digit.

    To see how this works, try 120/8 by substituting a=1 b =2 c=0 and d=8.

    120/8 = (10(12) + 0)/8 = 10(12)/8 + 0/8

    but 12/8 = 1 + 4/8 => 10(12/8) = 10(1+4/8)

    120/8 = 10(1+4/8) + 0/8
    = 10 + 40/8 + 0/8

    but 40/8 + 0/8 = 40/8

    So 120/8 = 10 + 40/8 = 10 + 5 = 15

    Now back to the division theorem. What does it say exactly?

    Given a/b, we can find unique integers q and r such that a = bq + r where r is the remainder of division. It is redundant to state that r < b but greater than or equal to 0. Since r is a remainder of the quotient a/b, it follows that it must be less than b.

    Similar logic is used in defining an alogorithm for division of abcd/ef or other quotients. The basic idea is to remember that when the product of the remainder by a multiple of 10 is added to the remaining digits, the multiple of 10 disappears, e.g.

    10a + c = ac
    10ab + c = abc
    100a + c = a0c
    100ab + c = ab0c

    This is the reason why we simply prefix the remaining quotient digits by the remainder and repeat the process. This is the essence of the long division algorithm. The algorithm is altered slightly in the following examples:

    12564/20 and 12564/11

    In the first example, we start with 100abc and in the second example, we start with 1000ab, since 125 > 20 and 12 > 11. Thus, it can be seen that the algorithm changes slightly but the basic idea is the same.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?