2
$\begingroup$

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

  • 1
    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$ `0`s.2011-11-27
  • 0
    Is Knuth talking about the squaring algorithm in Section 4.6.3 of the Volume 2?2011-11-27
  • 0
    @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$".2011-11-27
  • 0
    @Simone: I believe so even though I don't have the referenced print physically available.2011-11-27
  • 0
    @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.2011-11-27
  • 0
    @HenningMakholm: That's correct. The referenced Knuth's algorithm exploits the binary representation of the exponent, so let me clarify - I need the binary result to work with it in an ordinary binary computer.2011-11-27

0 Answers 0