on a tail-recursive square-and-multiply

[Greg Ewing]

On 8/11/23 2:26 pm, Julieta Shem wrote:
> 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.

Stepping back a bit, why do you feel the need to write this
tail-recursively? Is it just an exercise?

Note that Python doesn't optimise tail calls, so anything that
can be done tail-recursively is probably better done iteratively.

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

Well, there are inherently two cases, and they're different, so
I don't think you're doing anything wrong here. It was asymmetrical
to begin with. If you were doing it iteratively you would also be
leaving the accumulator alone when the exponent is even.

-- 
Greg