pase@ogcvax.UUCP (Douglas M. Pase) (07/07/87)
In article <1331@ogcvax.UUCP> pase@ogcvax.UUCP writes: - One such problem (one which is serial) is the calculation of positive integer - powers. The fastest method is as follows (binary decomposition method is - presented): In article <uiucdcsb.165100010> robison@uiucdcsb.cs.uiuc.edu writes: - Look in The Art of Computer Programming, vol. 2, section 4.6.3. The above - binary scheme is not the fastest possible. For example (a counterexample - is presented): Thank you for taking the time to respond to my article. It is interesting to note that the counterexample you presented depends very heavily on the factorization of the integer power. Notice that binary decomposition does not depend on any such additional information. So, although the portion of your example which was shown is actually faster than the b.d. method, you have neglected to include part of your computation in the analysis. The factorization of arbitrary integers is well known to be a difficult problem -- much more difficult than b.d. This suggests that there is a size of integer power beyond which not only will b.d. compute the result faster, but for most powers of that size or larger it will finish before the factorization is complete. Tim Rentsch and I have been having a stimulating discussion on this same topic via e-mail, and he brings up some points I had overlooked. Since he words them better than I could paraphrase them, I include his mail (I hope you don't mind, Tim). From: Tim Rentsch <rentsch%cs.unc.edu@csnet-relay.CSNET> - Basically, you are right. Determining an optimal addition chain - (as they are called in the literature) is a hard problem, maybe - even harder than factorization. Let l(n) denote the least number - of multiplies required to compute x**n; we would like to believe - that - l(n) <= l(m*n) [we know l(m*n) <= l(m) + l(n)] - - but this inequality, although "obvious", has not been proven. The - function l is a quite devious beast -- better to recommend you - read Knuth than to try to summarize myself. - - As to the rest of it, yes, probably in actual runtime the binary - method will run faster. This depends, however, on how fast or slow - the various operations are. If instead we are computing a large - matrix raised to a large power, we might find it worth our - while (for quite a long while, depending on the size of the - matrix) to try to find the optimal chain for multiplying that - matrix. - - Besides correcting a minor inaccuracy, the point I was making - is that whether something is faster depends on how speed is - measured. Your method is probably faster on any real computer. - On a computer where each multiply takes 1 eon, (and additions - take one microsecond :-) searching for a better solution is - better for suitably small powers. - - Overheard at a conference: - - "Interesting solutions to questionable problems" - - cheers, - - Tim -- Doug Pase -- ...ucbvax!tektronix!ogcvax!pase or pase@Oregon-Grad.csnet