Difference between revisions of "TADM2E 1.7"

From Algorithm Wiki
Jump to: navigation, search
(Recovering wiki)
 
(Recovering wiki)
 
Line 1: Line 1:
<h2>Base Case</h2>
+
<h2>Base Case</h2>
  
The base case &lt;math&gt;(z = 0)&lt;/math&gt; is true since it returns zero&lt;br&gt;
+
The base case <math>(z = 0)</math> is true since it returns zero<br>
:&lt;code&gt;if &lt;math&gt;z = 0&lt;/math&gt; then return(0)&lt;/code&gt;
+
:<code>if <math>z = 0</math> then return(0)</code>
  
&lt;h2&gt;Assumptions&lt;/h2&gt;&lt;br/&gt;
+
<h2>Assumptions</h2><br/>
 
multiply(y,z) gives the correct answer where:
 
multiply(y,z) gives the correct answer where:
* z &lt;= n
+
* z <= n
* c &gt;= 2
+
* c >= 2
* y &gt;= 0&lt;br /&gt;
+
* y >= 0<br />
&lt;br /&gt;
+
<br />
 
We will also assume the following. A brief proof will follow:
 
We will also assume the following. A brief proof will follow:
* &lt;math&gt;\left \lfloor z / c \right \rfloor c + (z\,\bmod\,c) = z&lt;/math&gt;
+
* <math>\left \lfloor z / c \right \rfloor c + (z\,\bmod\,c) = z</math>
&lt;br/&gt;
+
<br/>
  
&lt;h2&gt;Proof&lt;/h2&gt;&lt;br /&gt;
+
<h2>Proof</h2><br />
Where z = n+1, c &gt;= 2, y &gt;= 0&lt;br/&gt;
+
Where z = n+1, c >= 2, y >= 0<br/>
&lt;br /&gt;
+
<br />
First we break the result of multiply into two parts:&lt;br /&gt;
+
First we break the result of multiply into two parts:<br />
&lt;br/&gt;
+
<br/>
&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;A = &lt;math&gt;multiply(cy, \left \lfloor [n+1]/c  \right \rfloor)&lt;/math&gt;&lt;br/&gt;
+
&nbsp;&nbsp;&nbsp;&nbsp;A = <math>multiply(cy, \left \lfloor [n+1]/c  \right \rfloor)</math><br/>
&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;B = &lt;math&gt;y([n+1]\,\bmod\,c)&lt;/math&gt;&lt;br/&gt;
+
&nbsp;&nbsp;&nbsp;&nbsp;B = <math>y([n+1]\,\bmod\,c)</math><br/>
&lt;br/&gt;
+
<br/>
&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&lt;math&gt;multiply(y,z) = A + B&lt;/math&gt;&lt;br/&gt;
+
&nbsp;&nbsp;&nbsp;&nbsp;<math>multiply(y,z) = A + B</math><br/>
&lt;br/&gt;
+
<br/>
&lt;br/&gt;
+
<br/>
Now, because c &gt;= 2 we know that &lt;math&gt;\left \lfloor (n+1) / c \right \rfloor &lt; (n+1)&lt;/math&gt;.&lt;br /&gt;
+
Now, because c >= 2 we know that <math>\left \lfloor (n+1) / c \right \rfloor < (n+1)</math>.<br />
Based on that, we know that the call to multiply in &quot;A&quot; returns the correct result.&lt;br /&gt;
+
Based on that, we know that the call to multiply in "A" returns the correct result.<br />
&lt;br /&gt;
+
<br />
&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&lt;math&gt;A = multiply(cy, \left \lfloor [n+1]/c \right \rfloor) = cy * \left \lfloor [n+1] / c \right \rfloor&lt;/math&gt;&lt;br /&gt;
+
&nbsp;&nbsp;&nbsp;&nbsp;<math>A = multiply(cy, \left \lfloor [n+1]/c \right \rfloor) = cy * \left \lfloor [n+1] / c \right \rfloor</math><br />
&lt;br /&gt;
+
<br />
So now let's transform A into something more useful:&lt;br /&gt;
+
So now let's transform A into something more useful:<br />
&lt;br /&gt;
+
<br />
&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&lt;math&gt;A = cy * \left \lfloor [n+1] / c \right \rfloor = y * \left \lfloor z / c \right \rfloor c&lt;/math&gt; &lt;br/&gt;
+
&nbsp;&nbsp;&nbsp;&nbsp;<math>A = cy * \left \lfloor [n+1] / c \right \rfloor = y * \left \lfloor z / c \right \rfloor c</math> <br/>
&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;(Note: We transformed n+1 back into z for simplicity)&lt;br /&gt;
+
&nbsp;&nbsp;&nbsp;&nbsp;(Note: We transformed n+1 back into z for simplicity)<br />
&lt;br /&gt;
+
<br />
Based on our earlier assumption, we can transform this further:&lt;br /&gt;
+
Based on our earlier assumption, we can transform this further:<br />
&lt;br /&gt;
+
<br />
&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&lt;math&gt; \left \lfloor z / c \right \rfloor c + (z \,\bmod\, c) = z&lt;/math&gt;&lt;br /&gt;
+
&nbsp;&nbsp;&nbsp;&nbsp;<math> \left \lfloor z / c \right \rfloor c + (z \,\bmod\, c) = z</math><br />
&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&lt;math&gt; \left \lfloor z / c \right \rfloor c = z - (z \,\bmod\, c)&lt;/math&gt;&lt;br/&gt;
+
&nbsp;&nbsp;&nbsp;&nbsp;<math> \left \lfloor z / c \right \rfloor c = z - (z \,\bmod\, c)</math><br/>
&lt;br /&gt;
+
<br />
&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&lt;math&gt;A = y *  \left \lfloor z / c \right \rfloor c = y (z - z \,\bmod\, c) = yz - y(z \,\bmod\, c)&lt;/math&gt;&lt;br /&gt;
+
&nbsp;&nbsp;&nbsp;&nbsp;<math>A = y *  \left \lfloor z / c \right \rfloor c = y (z - z \,\bmod\, c) = yz - y(z \,\bmod\, c)</math><br />
&lt;br /&gt;
+
<br />
And now we add B back into the mix:&lt;br /&gt;
+
And now we add B back into the mix:<br />
&lt;br /&gt;
+
<br />
&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&lt;math&gt;A + B = yz - y(z \,\bmod\, c) + y(z \,\bmod\, c) = yz&lt;/math&gt;&lt;br /&gt;
+
&nbsp;&nbsp;&nbsp;&nbsp;<math>A + B = yz - y(z \,\bmod\, c) + y(z \,\bmod\, c) = yz</math><br />
&lt;br /&gt;
+
<br />
&lt;br/&gt;
+
<br/>
&lt;h2&gt;Subproof&lt;/h2&gt;
+
<h2>Subproof</h2>
&lt;b&gt;Show that &lt;math&gt;\left \lfloor z/c \right \rfloor c + z\,\bmod\,c = z&lt;/math&gt; where c &gt;= 2&lt;/b&gt;&lt;br/&gt;
+
<b>Show that <math>\left \lfloor z/c \right \rfloor c + z\,\bmod\,c = z</math> where c >= 2</b><br/>
&lt;br/&gt;
+
<br/>
We can prove this statement using a general example.&lt;br/&gt;
+
We can prove this statement using a general example.<br/>
&lt;br/&gt;
+
<br/>
First, assume that &lt;math&gt;z\,\bmod\,c = a.&lt;/math&gt;&lt;br/&gt;
+
First, assume that <math>z\,\bmod\,c = a.</math><br/>
&lt;br/&gt;
+
<br/>
Now, due to the definition of floor, we know the following:&lt;br/&gt;
+
Now, due to the definition of floor, we know the following:<br/>
&lt;br/&gt;
+
<br/>
&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&lt;math&gt;(z-a) / c = \left \lfloor z / c \right \rfloor&lt;/math&gt;&lt;br/&gt;
+
&nbsp;&nbsp;&nbsp;&nbsp;<math>(z-a) / c = \left \lfloor z / c \right \rfloor</math><br/>
&lt;br/&gt;
+
<br/>
This is because the remainder can't possibly be taken into account during a &quot;floor&quot; operation.&lt;br/&gt;
+
This is because the remainder can't possibly be taken into account during a "floor" operation.<br/>
&lt;br/&gt;
+
<br/>
Based on that, we can restate the equation as:&lt;br/&gt;
+
Based on that, we can restate the equation as:<br/>
&lt;br/&gt;
+
<br/>
&amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;&lt;math&gt;(z-a) / c * c + a  = (z - a) + a = z&lt;/math&gt;&lt;br/&gt;
+
&nbsp;&nbsp;&nbsp;&nbsp;<math>(z-a) / c * c + a  = (z - a) + a = z</math><br/>
&lt;br/&gt;
+
<br/>
  
 
[[introduction-TADM2E|Back to ''Introduction ...'']]
 
[[introduction-TADM2E|Back to ''Introduction ...'']]

Latest 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 ...