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