# on a tail-recursive square-and-multiply

Michael Torrie torriem at gmail.com
Tue Nov 7 23:14:57 EST 2023

```On 11/7/23 18:26, Julieta Shem via Python-list 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.
>
> --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---

I don't see any definition of "remainder()"  When you post to the list,
please provide short but complete code, including a demonstration of
using the code provided. That will help others understand what you are
trying to do, and perhaps comment on your concerns.

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

I don't really understand the code either, so I cannot help much.

```

More information about the Python-list mailing list