on a tail-recursive square-and-multiply

Julieta Shem jshem at yaxenu.org
Tue Nov 7 20:26:13 EST 2023

```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?
```