on a tail-recursive square-and-multiply

[Julieta Shem]

Greg Ewing <greg.ewing at canterbury.ac.nz> writes:

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

Yes --- an exercise.  (It would be relevant if I were in a language that
gives me tail-call optimization.  I'm preparing myself for when that
happens.)

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

I agree.  By the way, I once read or watched an interview with Guido van
Rossum and and he was asked why not to tail-call optimize Python and the
answer he gave --- IIRC --- was that tail-call optimization makes it
harder for a beginner to understand a stack trace.  I'm now interested
in discovering whether that was his sole reason.  Do you (or does
anyone) know of any reference that I could look into?  Thank you.

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

I think you're quite right and that was not clear until now.  Here's my
iterative version of the procedure:

--8<---------------cut here---------------start------------->8---
def isam(b, e, m):
  r = 1
  while e > 0:
    if is_even(e):
      b = remainder(b * b, m)
      e = e // 2
    else:
      r = remainder(r * b, m)
      e = e - 1
  return remainder(r, m)
--8<---------------cut here---------------end--------------->8---

So, indeed, it is asymmetric.  When it's even, I change the base.  When
it's odd, I change the /r/eturning value.  Thank you so much.

(*) The remainder function

--8<---------------cut here---------------start------------->8---
def is_even(n):
  return remainder(n, 2) == 0

def remainder(a, b):
  return a % b
--8<---------------cut here---------------end--------------->8---