Computing powers [of numbers]

The method of repeated squaring (also known as the binary power method, Russian peasant method and Pingala's method) computes the quantity m^{t} by performing about Log[t] multiplications and building up the sequence

FoldList[#^{2} m^#2 &, 1, IntegerDigits[t, 2]]

(related to the Horner form for the base 2 representation of t). Given two numbers x and y their product can be computed in base k by (FromDigits does the carries)

FromDigits[ListConvolve[IntegerDigits[x, k], IntegerDigits[y, k], {1, -1}, 0], k]

For numbers with n digits direct evaluation of the convolution would take about n^{2} steps. But FFT-related methods reduce this to about n Log[n] steps (see also page 1142). And this implies that to find a particular digit of m^{t} in base k will take altogether about t Log[t]^{2} steps.

One might think that a more efficient approach would be to start with the trivial length t digit sequence for c^{t} in base c, then to find a particular base k digit just by converting to base k. However, the straightforward method for converting a t-digit number x to base k takes about t divisions, though this can be reduced to around Log[t] by using a recursive method such as

FixedPoint[Flatten[If[# < k, #, With[{e = Ceiling[Log[k, #]/2]}, {Quotient[#, k^{e}], With[{s = Mod[#, k^{e}]}, If[s==0, Table[0, {e}], {Table[0, {e - Floor[Log[k, s]] - 1}], s}]]}]] & /@#] &, {x}]

The pictures below show stages in the computation of 3^{20} (a) by a power tree in base 2 and (b) by conversion from base 3. Both approaches seem to require about the same number of underlying steps. Note that even though one may only want to find a single digit in m^{t}, I know of no way to do this without essentially computing all the other digits in m^{t} as well.