(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

<h2>Base Case</h2>

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

<code>if $z = 0$ then return(0)</code>

<h2>Assumptions</h2><br/> multiply(y,z) gives the correct answer where:

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

<br /> We will also assume the following. A brief proof will follow:

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

<br/>

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