Boris is right in that what his algorithm does is not the same as the original one. But here is how you can reproduce it, if you really want to:
Observe that you can determine the order of the operations from the binary representation of the number. Let N=7
, then binary N=111
, denoted as N=7~111
.
Now you see the scheme in your original algorithm:
N Op N'
7~111 Mul 6~110 (= zero last bit)
6~110 Squ 3~011 (= shift right)
3~011 Mul 2~010
2~010 Squ 1~001
1~001 Base
Considering that due to the recursive nature of the algorithm, these steps are carried out top-to-bottom, you get Base - Squ - Mul - Squ - Mul = ((A*A)*A)*((A*A)*A))*A = A**7
Contrast this to Boris' algorithm:
N Op N'
1~001 Squ 2~010 (=shift left)
2~010 Squ 4~100 (=shift left)
4~100 Mul 5~101 (=add one)
5~101 Mul 6~110 (=add one)
6~110 Mul 7~111 (=add one)
So this one does all the shifting first, while the original considers each bit except for the first of N, right to left, in turn, "queuing" (because of bottom-up) Mul, Squ
if the bit is set or just Squ
if it is unset.
To reproduce this behavior (which is more efficient, as you will never do more simple multiplications than squares), you could start with N
in binary and do the following (here in general pseudocode, easy for you to translate into prolog):
Acc=A
for i in (reverse(tail(bits(N)))):
Acc*=Acc
if i==1:
Acc*=A
This is for N>=1
. N=0
is a special case and must be treated separately.
I'm pretty sure this is correct. If you have doubts, then just think about your original algorithm: testing for mod 2 == 0
is the same as testing if the last bit is zero. And if it is not, then substracting one is the same as zeroing out the last bit while doubling and halving is just shifting left or right in binary.