Notes

Chapter 10: Processes of Perception and Analysis

Section 11: Traditional Mathematics and Mathematical Formulas


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.


From Stephen Wolfram: A New Kind of Science [citation]