Let \(x,y\) be two non-negative integers. We want to compute \(p\), the product:

Set p=0 While x > 0: if x is odd: p = p + y x = x/2 (Integer Division) y = y + y return p

Mathematically, this is equivalent to:

\begin{equation*}
x \cdot y=\left\{\begin{array}{ll}0 & \text { if } x=0 \\ \lfloor x / 2\rfloor \cdot(y+y) & \text { if } x \text { is even } \\ \lfloor x / 2\rfloor \cdot(y+y)+y & \text { if } x \text { is odd }\end{array}\right.
\end{equation*}

Convince yourself this is true. The even case is trivial. The odd case is true because \(x=2k+1\) and \(\lfloor x / 2\rfloor=k\).