15. Fast Exponentiation

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;
//----------