Difference between revisions of "TADM2E 1.7"

Revision as of 18:22, 11 September 2014

Base Case

The base case $ (z = 0) $ is true since it returns zero

if $ z = 0 $ then return(0)

Assumptions

multiply(y,z) gives the correct answer where:

• z <= n
• c >= 2
• y >= 0
  

We will also assume the following. A brief proof will follow:

• $ \left \lfloor z / c \right \rfloor c + (z\,\bmod\,c) = z $

Proof

Where z = n+1, c >= 2, y >= 0

First we break the result of multiply into two parts:

    A = $ multiply(cy, \left \lfloor [n+1]/c \right \rfloor) $
    B = $ y([n+1]\,\bmod\,c) $

    $ multiply(y,z) = A + B $


Now, because c >= 2 we know that $ \left \lfloor (n+1) / c \right \rfloor < (n+1) $.
Based on that, we know that the call to multiply in "A" returns the correct result.

    $ A = multiply(cy, \left \lfloor [n+1]/c \right \rfloor) = cy * \left \lfloor [n+1] / c \right \rfloor $

So now let's transform A into something more useful:

    $ A = cy * \left \lfloor [n+1] / c \right \rfloor = y * \left \lfloor z / c \right \rfloor c $
    (Note: We transformed n+1 back into z for simplicity)

Based on our earlier assumption, we can transform this further:

    $ \left \lfloor z / c \right \rfloor c + (z \,\bmod\, c) = z $
    $ \left \lfloor z / c \right \rfloor c = z - (z \,\bmod\, c) $

    $ A = y * \left \lfloor z / c \right \rfloor c = y (z - z \,\bmod\, c) = yz - y(z \,\bmod\, c) $

And now we add B back into the mix:

    $ A + B = yz - y(z \,\bmod\, c) + y(z \,\bmod\, c) = yz $

Subproof

Show that $ \left \lfloor z/c \right \rfloor c + z\,\bmod\,c = z $ where c >= 2

We can prove this statement using a general example.

First, assume that $ z\,\bmod\,c = a. $

Now, due to the definition of floor, we know the following:

    $ (z-a) / c = \left \lfloor z / c \right \rfloor $

This is because the remainder can't possibly be taken into account during a "floor" operation.

Based on that, we can restate the equation as:

    $ (z-a) / c * c + a = (z - a) + a = z $

Back to Introduction ...