TADM2E 1.7 - Revision history

Matt: Undo revision 842 by Wacko (talk)

2020-07-23T15:55:15Z

Undo revision 842 by Wacko (talk)

Wacko at 07:27, 18 July 2020

2020-07-18T07:27:39Z

Algowikiadmin: Recovering wiki

2014-09-11T18:22:31Z

Recovering wiki

Show changes

Algowikiadmin: Recovering wiki

2014-09-11T18:13:14Z

Recovering wiki

New page

<h2>Base Case</h2>

The base case <math>(z = 0)</math> is true since it returns zero 
:<code>if <math>z = 0</math> then return(0)</code>

<h2>Assumptions</h2> 
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:
* <math>\left \lfloor z / c \right \rfloor c + (z\,\bmod\,c) = z</math>
 

<h2>Proof</h2> 
Where z = n+1, c >= 2, y >= 0 
 
First we break the result of multiply into two parts: 
 
&nbsp;&nbsp;&nbsp;&nbsp;A = <math>multiply(cy, \left \lfloor [n+1]/c \right \rfloor)</math> 
&nbsp;&nbsp;&nbsp;&nbsp;B = <math>y([n+1]\,\bmod\,c)</math> 
 
&nbsp;&nbsp;&nbsp;&nbsp;<math>multiply(y,z) = A + B</math> 
 
 
Now, because c >= 2 we know that <math>\left \lfloor (n+1) / c \right \rfloor < (n+1)</math>. 
Based on that, we know that the call to multiply in "A" returns the correct result. 
 
&nbsp;&nbsp;&nbsp;&nbsp;<math>A = multiply(cy, \left \lfloor [n+1]/c \right \rfloor) = cy * \left \lfloor [n+1] / c \right \rfloor</math> 
 
So now let's transform A into something more useful: 
 
&nbsp;&nbsp;&nbsp;&nbsp;<math>A = cy * \left \lfloor [n+1] / c \right \rfloor = y * \left \lfloor z / c \right \rfloor c</math> 
&nbsp;&nbsp;&nbsp;&nbsp;(Note: We transformed n+1 back into z for simplicity) 
 
Based on our earlier assumption, we can transform this further: 
 
&nbsp;&nbsp;&nbsp;&nbsp;<math> \left \lfloor z / c \right \rfloor c + (z \,\bmod\, c) = z</math> 
&nbsp;&nbsp;&nbsp;&nbsp;<math> \left \lfloor z / c \right \rfloor c = z - (z \,\bmod\, c)</math> 
 
&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> 
 
And now we add B back into the mix: 
 
&nbsp;&nbsp;&nbsp;&nbsp;<math>A + B = yz - y(z \,\bmod\, c) + y(z \,\bmod\, c) = yz</math> 
 
 
<h2>Subproof</h2>
Show that <math>\left \lfloor z/c \right \rfloor c + z\,\bmod\,c = z</math> where c >= 2 
 
We can prove this statement using a general example. 
 
First, assume that <math>z\,\bmod\,c = a.</math> 
 
Now, due to the definition of floor, we know the following: 
 
&nbsp;&nbsp;&nbsp;&nbsp;<math>(z-a) / c = \left \lfloor z / c \right \rfloor</math> 
 
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: 
 
&nbsp;&nbsp;&nbsp;&nbsp;<math>(z-a) / c * c + a = (z - a) + a = z</math> 
 

[[introduction-TADM2E|Back to ''Introduction ...'']]

@@ Line 1: / Line 1: @@
-Eat bulaga!!!!!!
+<h2>Base Case</h2>
-Eat bulaga!!!!!!
-Eat bulaga!!!!!!
+The base case <math>(z = 0)</math> is true since it returns zero<br>
-Eat bulaga!!!!!!
+:<code>if <math>z = 0</math> then return(0)</code>
-Eat bulaga!!!!!!
-Eat bulaga!!!!!!
+<h2>Assumptions</h2><br/>
-Eat bulaga!!!!!!
+multiply(y,z) gives the correct answer where:
-Eat bulaga!!!!!!
+* z <= n
-Eat bulaga!!!!!!
+* c >= 2
-Eat bulaga!!!!!!
+* y >= 0<br />
-Eat bulaga!!!!!!
+<br />
-Eat bulaga!!!!!!
+We will also assume the following. A brief proof will follow:
-Eat bulaga!!!!!!
+* <math>\left \lfloor z / c \right \rfloor c + (z\,\bmod\,c) = z</math>
-Eat bulaga!!!!!!
+<br/>
-Eat bulaga!!!!!!
-Eat bulaga!!!!!!
+<h2>Proof</h2><br />
-Eat bulaga!!!!!!
+Where z = n+1, c >= 2, y >= 0<br/>
-Eat bulaga!!!!!!
+<br />
-Eat bulaga!!!!!!
+First we break the result of multiply into two parts:<br />
-Eat bulaga!!!!!!
+<br/>
-Eat bulaga!!!!!!
+&nbsp;&nbsp;&nbsp;&nbsp;A = <math>multiply(cy, \left \lfloor [n+1]/c  \right \rfloor)</math><br/>
-Eat bulaga!!!!!!
+&nbsp;&nbsp;&nbsp;&nbsp;B = <math>y([n+1]\,\bmod\,c)</math><br/>
-Eat bulaga!!!!!!
+<br/>
-Eat bulaga!!!!!!
+&nbsp;&nbsp;&nbsp;&nbsp;<math>multiply(y,z) = A + B</math><br/>
-Eat bulaga!!!!!!
+<br/>
-Eat bulaga!!!!!!
+<br/>
-Eat bulaga!!!!!!
+Now, because c >= 2 we know that <math>\left \lfloor (n+1) / c \right \rfloor < (n+1)</math>.<br />
-Eat bulaga!!!!!!
+Based on that, we know that the call to multiply in "A" returns the correct result.<br />
-Eat bulaga!!!!!!
+<br />
-Eat bulaga!!!!!!
+&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 />

@@ Line 1: / Line 1: @@
-<h2>Base Case</h2>
+Eat bulaga!!!!!!
+Eat bulaga!!!!!!
-The base case <math>(z = 0)</math> is true since it returns zero<br>
+Eat bulaga!!!!!!
-:<code>if <math>z = 0</math> then return(0)</code>
+Eat bulaga!!!!!!
+Eat bulaga!!!!!!
-<h2>Assumptions</h2><br/>
+Eat bulaga!!!!!!
-multiply(y,z) gives the correct answer where:
+Eat bulaga!!!!!!
-* z <= n
+Eat bulaga!!!!!!
-* c >= 2
+Eat bulaga!!!!!!
-* y >= 0<br />
+Eat bulaga!!!!!!
-<br />
+Eat bulaga!!!!!!
-We will also assume the following. A brief proof will follow:
+Eat bulaga!!!!!!
-* <math>\left \lfloor z / c \right \rfloor c + (z\,\bmod\,c) = z</math>
+Eat bulaga!!!!!!
-<br/>
+Eat bulaga!!!!!!
+Eat bulaga!!!!!!
-<h2>Proof</h2><br />
+Eat bulaga!!!!!!
-Where z = n+1, c >= 2, y >= 0<br/>
+Eat bulaga!!!!!!
-<br />
+Eat bulaga!!!!!!
-First we break the result of multiply into two parts:<br />
+Eat bulaga!!!!!!
-<br/>
+Eat bulaga!!!!!!
-&nbsp;&nbsp;&nbsp;&nbsp;A = <math>multiply(cy, \left \lfloor [n+1]/c  \right \rfloor)</math><br/>
+Eat bulaga!!!!!!
-&nbsp;&nbsp;&nbsp;&nbsp;B = <math>y([n+1]\,\bmod\,c)</math><br/>
+Eat bulaga!!!!!!
-<br/>
+Eat bulaga!!!!!!
-&nbsp;&nbsp;&nbsp;&nbsp;<math>multiply(y,z) = A + B</math><br/>
+Eat bulaga!!!!!!
-<br/>
+Eat bulaga!!!!!!
-<br/>
+Eat bulaga!!!!!!
-Now, because c >= 2 we know that <math>\left \lfloor (n+1) / c \right \rfloor < (n+1)</math>.<br />
+Eat bulaga!!!!!!
-Based on that, we know that the call to multiply in "A" returns the correct result.<br />
+Eat bulaga!!!!!!
-<br />
+Eat bulaga!!!!!!
-&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 />
+Eat bulaga!!!!!!