# Thread: Computing a^r by the SX method

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

Let $\displaystyle a \in \mathbb{Z}$, $\displaystyle r \in \mathbb{N}$. Write $\displaystyle r$ in binary as $\displaystyle r = b_kb_{k-1} \dots b_1b_0$, with all $\displaystyle b_i \in \{0, 1\}$.
From the binary string $\displaystyle b_kb_{k-1} \dots b_1b_0$ produce a string of $\displaystyle S's$ and $\displaystyle X's$ by replacing each 0 by $\displaystyle S$ and each 1 by $\displaystyle SX$.
Now, starting with $\displaystyle A = 1$ and working from left to right, interpret $\displaystyle S$ as $\displaystyle A \to A^2$ (i.e. replace $\displaystyle A$ by $\displaystyle A^2$), and $\displaystyle X$ as $\displaystyle A \to Aa$ (multiply $\displaystyle A$ by $\displaystyle a$).
Prove that the result of this algorithm is indeed $\displaystyle 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 $\displaystyle a \in \mathbb{Z}$, $\displaystyle r \in \mathbb{N}$. Write $\displaystyle r$ in binary as $\displaystyle r = b_kb_{k-1} \dots b_1b_0$, with all $\displaystyle b_i \in \{0, 1\}$.
From the binary string $\displaystyle b_kb_{k-1} \dots b_1b_0$ produce a string of $\displaystyle S's$ and $\displaystyle X's$ by replacing each 0 by $\displaystyle S$ and each 1 by $\displaystyle SX$.
Now, starting with $\displaystyle A = 1$ and working from left to right, interpret $\displaystyle S$ as $\displaystyle A \to A^2$ (i.e. replace $\displaystyle A$ by $\displaystyle A^2$), and $\displaystyle X$ as $\displaystyle A \to Aa$ (multiply $\displaystyle A$ by $\displaystyle a$).
Prove that the result of this algorithm is indeed $\displaystyle 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 $\displaystyle B$ is a string of 1's and 0's, representing the number $\displaystyle x$ in decimal notation, then $\displaystyle 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 $\displaystyle B$ of length n (of course, for n=0,1 the claim is easily seen to be true). Let $\displaystyle r\in\mathbb{N}$ be the decimal representation of $\displaystyle B$:

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

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

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

Tonio