# Thread: Computing a^r by the SX method

1. ## Computing a^r by the SX method

Let $a \in \mathbb{Z}$, $r \in \mathbb{N}$. Write $r$ in binary as $r = b_kb_{k-1} \dots b_1b_0$, with all $b_i \in \{0, 1\}$.
From the binary string $b_kb_{k-1} \dots b_1b_0$ produce a string of $S's$ and $X's$ by replacing each 0 by $S$ and each 1 by $SX$.
Now, starting with $A = 1$ and working from left to right, interpret $S$ as $A \to A^2$ (i.e. replace $A$ by $A^2$), and $X$ as $A \to Aa$ (multiply $A$ by $a$).
Prove that the result of this algorithm is indeed $a^r$.

Anyone wanna tackle this? It's a tutorial question I have but you don't need to use it ever in the course, just seems to be stuck in there for anyone interested. I have no idea where to even begin...

Let $a \in \mathbb{Z}$, $r \in \mathbb{N}$. Write $r$ in binary as $r = b_kb_{k-1} \dots b_1b_0$, with all $b_i \in \{0, 1\}$.
From the binary string $b_kb_{k-1} \dots b_1b_0$ produce a string of $S's$ and $X's$ by replacing each 0 by $S$ and each 1 by $SX$.
Now, starting with $A = 1$ and working from left to right, interpret $S$ as $A \to A^2$ (i.e. replace $A$ by $A^2$), and $X$ as $A \to Aa$ (multiply $A$ by $a$).
Prove that the result of this algorithm is indeed $a^r$.

Anyone wanna tackle this? It's a tutorial question I have but you don't need to use it ever in the course, just seems to be stuck in there for anyone interested. I have no idea where to even begin...

Perhaps some induction together with some diving into binary: if $B$ is a string of 1's and 0's, representing the number $x$ in decimal notation, then $B1=2x+1\,,\,\,B0=2x$ This is pretty straightforward, so we can now assume the theorem is true for all binary strings of length n-1, and we shall prove for a string $B$ of length n (of course, for n=0,1 the claim is easily seen to be true). Let $r\in\mathbb{N}$ be the decimal representation of $B$:

First case: $B=B'1$ , with $B'$ a bin. string of length n-1. In this case, $r=2k+1$ , and the ind. hypothesis tells us that the SX method gives us $a^k$ on $B'$.

Since $1\rightarrow SX$, after getting $a^k$ from $B'$ we get $(a^k)^2=a^{2k}$ because of the last S, and from the last X we get $a^{2k}a=a^{2k+1}=a^r$ .

Second case: $B=B'0$ ...I let you this case (as easy as the above one).

Tonio