For the first time I'm trying to write a tail-recursive
square-and-multiply and, even though it /seems/ to work, I'm not happy
with what I wrote and I don't seem to understand it so well.
--8<---------------cut here---------------start------------->8---
def sam(b, e, m, acc = 1):
if e == 0:
return acc
if is_even(e):
return sam(remainder(b * b, m), e//2, m, acc)
else:
return sam(b, e - 1, m, remainder(b * acc, m))
--8<---------------cut here---------------end--------------->8---
You see, I tried to use an accumulator, but I'm only accumulating when
the exponent is odd. When it's even, I feel I'm forced to change the
base into b * b mod m and leave the accumulator alone. This feels so
unnatural to me. I feel I broke some symmetry there. I'm having to
think of two cases --- when I change the accumulator and when I change
the base. That seems too much for my small head. Can you help?
--
https://mail.python.org/mailman/listinfo/python-list
