15. Fast Exponentiation(快速冪)

Observe the example:

x^14 = (x^7)^2 = (((x^3)^2)x)^2 =  ((((x^2)x)^2)x)^2

t1 = clock();

for (j = 0; j < repeat; j++)

{   power2 = 1;

    x = k;

    nn = n;

    while (nn>1)

    {   if (nn % 2 == 0)

{   x *= x;

           nn /= 2;

        }

        else

        {   power2 *= x;

            x *= x;

            nn = (nn-1)/2;

        }

    }

    power2 *= x;

}

t2 = (float) (clock()-t1)/CLOCKS_PER_SEC;

Memo1->Lines->Add("     =x^n = "+IntToStr(power2)+"  ["+FloatToStr(t2)+" (sec.)] "+IntToStr(repeat)+" times");

//----------Replace /2  by >>1

t1 = clock();

for (j = 0; j < repeat; j++)

{   power3 = 1;

    x = k;

    nn = n;

    while (nn>1)

    {   if (nn % 2 == 0) nn >>= 1;

        else

        {   power3 *= x;

            nn = (nn-1)>>1;

        }

        x *= x;

    }

    power3 *= x;

}

t2 = (float) (clock()-t1)/CLOCKS_PER_SEC;

Memo1->Lines->Add("   ==x^n = "+IntToStr(power3)+"  ["+FloatToStr(t2)+" (sec.)] "+IntToStr(repeat)+" times");

//----------Simplify  if__else__

t1 = clock();

for (j = 0; j < repeat; j++)

{   power4 = 1;

    x = k;

    nn = n;

    while (nn>1)

    {   if ((nn % 2))

        {   power4 *= x;

            nn = nn-1;

        }

        nn >>= 1;

        x *= x;

    }

    power4 *= x;

}

t2 = (float) (clock()-t1)/CLOCKS_PER_SEC;

Memo1->Lines->Add(" ===x^n = "+IntToStr(power4)+"  ["+FloatToStr(t2)+" (sec.)] "+IntToStr(repeat)+" times");

//------------------

t1 = clock();

for (j = 0; j < repeat; j++)

{   power5 = 1;

   x = k;

   nn = n;

   while (nn>1)

   {   if ((nn & 1)) 

       {   power5 *= x;

            nn = nn-1;

       }

       nn >>= 1;

       x *= x;

   }

   power5 *= x;

}

t2 = (float) (clock()-t1)/CLOCKS_PER_SEC;

Memo1->Lines->Add("====x^n = "+IntToStr(power5)+"  ["+FloatToStr(t2)+" (sec.)] "+IntToStr(repeat)+" times");

//-------------------------

for (power5=1, x=k, nn=n; (nn>1) ; nn>>=1, x*=x)

{   if ((nn & 1))

    {   power5 *= x;

        nn -= 1;

    }

}

power5 *= x;

//----------