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?

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On Wednesday, 8 November 2023 at 02:26:37 UTC+1, 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.

I am having troubles reading it, too: you are computing b^e I would guess,
but that's about it, essentially you don't say what (variant of the) algorithm you are implementing specifically.

--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 was looking at the Wikipedia article: <https://en.wikipedia.org/wiki/Exponentiation_by_squaring>

Beside that I must admit I do not understand why the very first version
they show, the "Recursive version" exp_by_squaring, they dub *not* tail-recursive (and those else-if's should just be if's...). Can you maybe explain that?

Anyway, if you look past that one at exp_by_squaring_iterative,
there is a patent asymmetry between odd and even cases,
so I wouldn't be too worried by that... :)

Julio

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

Greg Ewing <greg.ewing@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---

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

Julieta Shem <jshem@yaxenu.org> writes:

[...]

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.

It seems everyone refers Guido van Rossum's post at

https://neopythonic.blogspot.com/2009/04/final-words-on-tail-calls.html

From the page, confuse-users is /not/ the only reason. After mentioning
it first, he begins a second paragraph saying ``[t]he main issue here
[...]'' and I wonder if by ``main issue'' he means something like ---
the main /problem/ with tail-call optimization (for me) is [...].

--8<---------------cut here---------------start------------->8---
Personally, I think it is a fine feature for some languages, but I
don't think it fits Python: The elimination of stack traces for some
calls but not others would certainly confuse many users, who have not
been raised with tail call religion but might have learned about call
semantics by tracing through a few calls in a debugger.

The main issue here is that I expect that in many cases tail calls are
not of a recursive nature (neither direct nor indirect), so the
elimination of stack frames doesn't do anything for the algorithmic
complexity of the code, but it does make debugging harder. For
example, if your have a function ending in something like this:

if x > y:
return some_call(z)
else:
return 42

and you end up in the debugger inside some_call() whereas you expected
to have taken the other branch, with TCO as a feature your debugger
can't tell you the value of x and y, because the stack frame has been
eliminated.
--8<---------------cut here---------------end--------------->8---

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

Julieta Shem <jshem@yaxenu.org> writes:

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.

Try first writing a straightforward recursive version without worrying
about tail recursion or an accumulator. Do you understand the
algorithm? Get to that point before trying to add the optimization.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)