Results 1 to 2 of 2

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

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by Deadstar View Post
    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
    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: September 19th 2011, 02:51 PM
  2. Computing ROI ?
    Posted in the Business Math Forum
    Replies: 1
    Last Post: May 13th 2009, 03:46 PM
  3. Computing e^A
    Posted in the Advanced Algebra Forum
    Replies: 6
    Last Post: November 27th 2008, 07:49 AM
  4. Replies: 2
    Last Post: August 17th 2008, 01:02 PM
  5. computing
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: April 28th 2007, 01:25 AM

Search Tags


/mathhelpforum @mathhelpforum