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\).