Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Is there any known integer exponentiation algorithm to compute $x^y$ for the special case $x = 3$ which is faster than the general case algorithm found in [1], section 4.6.3?

[1] D. E. Knuth, The Art of Computer Programming. Volume 2: Seminumerical Algorithms, Addison-Wesley, 1981

share|cite|improve this question
Depends. How do you want the result? If trinary notation is acceptable, you can get it in linear time by outputting an 1 followed by $y$ 0s. – Henning Makholm Nov 27 '11 at 15:53
Is Knuth talking about the squaring algorithm in Section 4.6.3 of the Volume 2? – Simone Nov 27 '11 at 17:01
@Henning: That's just silly! Because it works for any $x$, doesn't it? Not just $x=3$. "Give me $x^y$ in base $x$". – TonyK Nov 27 '11 at 17:27
@Simone: I believe so even though I don't have the referenced print physically available. – jnml Nov 27 '11 at 17:54
@TonyK: Yes, it's a bit silly -- but there's a point to the silliness, namely that the achievable efficiency depends on which representation is required for the result, so the OP should not expect a precise answer without specifying a representation first. – Henning Makholm Nov 27 '11 at 21:20

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.