Repeated Squaring: You will love it

This time I want to write something about the calculation of large powers of any number. For example say we want to calculate 13 to the power 1000. This is indeed a huge number and there is no data type in C/C++ or even in java that can hold such a huge number. So this is a problem unless you are a python user. Well I am not interested in talking about BigInt class but how to perform such calculation efficiently. In a scenario like when you need to find the last digit of the above mentioned number (13^1000) you can use it since you have to save only one digit throughout the calculation ( of the last digit).
More precisely let l(n)=last digit of n
13^1=13 l=3
13^2=13*13=169 l(13*13)=l(3*13)
13^3=169*13=2197 l(169*13)=l(9*13)
13^4=2197*13=28561 l(2197*13)=l(7*13)
means you need not save all the intermediate huge numbers along the way but just their last digit

Now come back to our business of calculation of 13^1000.
There are 2 approaches
1. Naive method
2. Repeated Squaring

1. Naive method is to calculate straight forward 13*13*13.... (1000 timess)13
something like this
a=1;
for(i=0;i<1000;i++)
{
a=a*13;
a=a%10;
}
it requires 1000 multiplications!!

2. Repeated squaring
we will calculate 13 to the power multiples of two...
here we go
a=13*13
b=a*a=(13*13)*(13*13)=13^4
c=b*b=(13*13)*(13*13)*(13*13)*(13*13)=13^8
using a loop we can proceed
13^16, 13^32, 13^64, 13^128, 13^256, 13^512
now just multiply (13^512)*(13^256)*(13^128)*(13^64)*(13^32)*(13^8)=13^1000
512+256+128+64+32+8=1000
so totally 14 multiplications!!!!
So you can check by yourself how beautiful this method is :)