Results 1 to 2 of 2

Thread: Computing a^r by the SX method

  1. #1
    Super Member Deadstar's Avatar
    Joined
    Oct 2007
    Posts
    722

    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...
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    3
    Quote Originally Posted by Deadstar View Post
    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
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Computing A^k
    Posted in the Advanced Algebra Forum
    Replies: 7
    Last Post: Sep 19th 2011, 01:51 PM
  2. Computing ROI ?
    Posted in the Business Math Forum
    Replies: 1
    Last Post: May 13th 2009, 02:46 PM
  3. Computing e^A
    Posted in the Advanced Algebra Forum
    Replies: 6
    Last Post: Nov 27th 2008, 06:49 AM
  4. Replies: 2
    Last Post: Aug 17th 2008, 12:02 PM
  5. computing
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: Apr 28th 2007, 12:25 AM

Search Tags


/mathhelpforum @mathhelpforum