I did study this algorithm last year when I took my advanced algorithms course but I always missed the forest for the trees.
It is said that left to right binary exponentiation is faster than naive multiplication. For example, x^108 = x*x*x.... (108 times), now, that's 108 multiplications.
A wee bit faster technique is left to right binary exponentiation. x^108 = (x^54)^2 = ((x^27)^2))^2 = ((x* (x^13)^2)^2)^2 and so on. Apparently, this achieves the same result in logN multiplications, more precisely, 5. I wondered what sense it actually made and I was always told that squaring was not to be treated as multiplication. In technical terms, I thought squaring was just as computationally intensive as multiplication. In software terms, I was right but I was wrong otherwise, in hardware respect.
Actually, squaring a number is equivalent to a 1 bit left shift of its binary representation. That can be achieved using bit shifters and that's where the speed up is achieved. This is programming in such a way so as to exploit hardware capacity.
No comments:
Post a Comment