While in Russia...

We can analyze the ``while'' version of the Russian Peasant's algorithm the same way.

int Russian(int a, int b)
//  implements Russian Peasant Algorithm
{
   int x = a, y = b, z = 0;
   while (x > 0)
   {
      if ( 1 == x % 2)
         z += y;
      y <<= 1;
      x >>= 1;
   }
   return z;        
}

• Define the ``operations'':

  Only one: the body of the loop.

• Define the potential function: $\Phi(x) = \log(x).$
• Define the amortized costs: $\hat{c}_t = 0$.
• Show that $c_t \le \hat{c}_t + \Phi(x_{t-1}) - \Phi(x_t)$:

  Within the loop, we do constant work, so c_t =1.

  

• Now, the total work in the sequence of operations is bounded by the maximum initial value of the potential function: $\Phi(x_0) = \log(x_0) = \log(a)$.