Abstract
Various generalizations of the classical problem of the fastest raising to a power (or the so-called problem on addition chains) are studied in the asymptotic sense. Under weak restrictions, we demonstrate asymptotically tight solutions of the two best known generalizations, namely, Bellman’s problem on the computational complexity (on the minimal number of multiplication operations) of a normed monomial of several variables and Knuth’s problem on the computational complexity of a power system of one variable. We also briefly review some results on the computational complexity for three problems, namely, the computation of p-element systems of normed monomials in q variables, additive computations for systems of p integer linear forms over q variables, and the computation of p-element systems of the free Abelian group with q generators.
Similar content being viewed by others
References
A. Arnold and S. Brlek, “Optimal word chains for the Thue–Morse word,” Inform. Comput., 83, No. 2, 140–151 (1989).
R. E. Bellman, “Addition chains of vectors (Advanced problem 5125),” Amer. Math. Mon., 70, 765 (1963).
D. J. Bernstein, “Pippenger’s exponentiation algorithm,” http://cr.yp.to/papers/pippenger.pdf (2002).
A. Brauer, “On addition chains,” Bull. Am. Math. Soc., 45, 736–739 (1939).
D. Dobkin and R. J. Lipton, “Addition chain methods for the evaluation of specific polynomials,” SIAM J. Comput., 9, No. 1, 121–125 (1980).
P. Downey, B. Leong, and R. Sethi, “Computing sequences with addition chains,” SIAM J. Comput., 10, 638–646 (1981).
P. Erdős , “Remarks on number theory. III: On addition chains,” Acta Arith., 6, 77–81 (1960).
S. B. Gashkov and V. V. Kochergin, “On addition chains of vectors, gate circuits, and the complexity of computations of powers,” Sib. Adv. Math., 4, 1–16 (1994).
D. M. Gordon, “A survey of fast exponentiation methods,” J. Algorithms, 27, 129–146 (1998).
R. R. Goundar, K. Shiota, and M. Toyonaga, “New strategy for doubling-free short addition-subtraction chain,” Appl. Math. Inform. Sci., 2, No. 2, 123–133 (2008).
K. R. Hebb, “Some results on addition chains,” Not. Am. Math. Soc., 21, A-294 (1974).
D. E. Knuth, The Art of Computer Programming, Vol. 2, Addison-Wesley, Reading (1969).
D. E. Knuth and C. H. Papadimitriou, “Duality in addition chains,” Bull. European Assoc. Theoret. Comput. Sci., 13, 2–4 (1981).
V. V. Kochergin, “On the complexity of computations in finite Abelian groups,” Sov. Math. Dokl., 43, No. 2, 374–376 (1991).
V. V. Kochergin, “On the complexity of computations in finite Abelian groups,” Mat. Vopr. Kibernet., No. 4, 178–217 (1992).
V. V. Kochergin, “On additive computations of systems of integral linear forms,” Moscow Univ. Math. Bull., 48, No. 6, 62–64 (1993).
V. V. Kochergin, “On the computation of sets of powers,” Discrete Math. Appl., 4, No. 2, 119–128 (1994).
V. V. Kochergin, “On the complexity of computations of monomials and tuples of powers,” Sib. Adv. Math., 6, No. 1, 71–86 (1996).
V. V. Kochergin, “On the multiplicative complexity of binary words with a given number of units,” Mat. Vopr. Kibernet., No. 8, 63–76 (1999).
V. V. Kochergin, “On the complexity of computation of a pair of monomials in two variables,” Discrete Math. Appl., 15, No. 6, 547–572 (2005).
V. V. Kochergin, “On the complexity of computation of three monomials in three variables,” Mat. Vopr. Kibernet., No. 15, 79–155 (2006).
V. V. Kochergin, “On the complexity of joint computation of two elements of a free Abelian group,” in: Proc. XVI Int. Workshop “Synthesis and Complexity of Control Systems,” Saint Petersburg, June 26–30, 2006 [in Russian], Izd. Mekh.-Mat. Fak. Mosk. Univ., Moscow (2006), pp. 54–59.
V. V. Kochergin, “On the computation complexity of monomials systems of two variables,” in: Proc. VII Int. Conf. “Discrete Models in the Theory of Control Systems,” Pokrovskoe, Russia, March 4–6, 2006 [in Russian], MAKS Press, Moscow (2006), pp. 55–59.
V. V. Kochergin, “Asymptotics of the complexity of systems of integer linear forms for additive computations,” J. Appl. Indust. Math., 1, No. 3, 328–342 (2007).
V. V. Kochergin, “On the maximal complexity of calculations of systems of elements of a free Abelian group,” Moscow Univ. Math. Bull., 62, No. 3, 95–100 (2007).
V. V. Kochergin, “On the complexity of joint computation of three elements of free Abelian group with two generators,” Diskret. Anal. Issled. Oper., Ser. 1, 15, No. 2, 23–64 (2008).
V. V. Kochergin, “Relation between two measures of the computation complexity for systems of monomials,” Moscow Univ. Math. Bull., 64, No. 4, 144–150 (2009).
V. V. Kochergin, “Improvement of the estimates of the computational complexity for monomials and sets of powers in Bellman’s and Knuth’s problems,” J. Appl. Indust. Math., 9, No. 1 (2015).
N. Kunihiro and H. Yamamoto, “Window and extended window methods for addition chain and addition-subtraction chain,” IEICE Trans. Fund. Electron. Commun. Comput. Sci., E81-A, No. 1, 72–81 (1998).
O. B. Lupanov, “On the synthesis of certain classes of control systems,” Probl. Kibernet., No. 10, 63–97 (1963).
Yu. V. Merekin, “A lower bound for the complexity of concatenation schemes of words,” Diskret. Anal. Issled. Oper., 3, No. 1, 52–56 (1996).
F. Morain and J. Olivos, “Speeding up the computation on an elliptic curve using addition-subtraction chains,” Inform. Théor. Appl., 24, 531–544 (1990).
J. Morgenstern, “Note on a lower bound of the linear complexity of the fast Fourier transform,” J. Assoc. Comput. Mach., 20, 305–306 (1973).
E. I. Nechiporuk, “On topological principles of selfcorrection,” Probl. Kibernet., No. 21, 5–102 (1969).
N. Nedjah and L. Mourelle, “Minimal addition-subtraction chains using genetic algorithm,” in: Advances in Information Systems, Lect. Notes Comput. Sci., Vol. 2457, Springer, Berlin (2002), pp. 303–313.
J. Olivos, “On vectorial addition chains,” J. Algorithms, 2, No. 1, 13–21 (1981).
N. Pippenger, “The minimum number of edges in graphs with prescribed paths,” Math. Syst. Theor., 12, No. 4, 325–346 (1979).
N. Pippenger, “On evaluation of powers and monomials,” SIAM J. Comput., 9, No. 2, 230–250 (1980).
J. E. Savage, The Complexity of Computing, Wiley-Interscience, New York (1976).
A. Schönhage, “A lower bound for the length of addition chains,” Theor. Comput. Sci., 1, No. 1, 1–12 (1975).
A. F. Sidorenko, “Complexity of additive computations of systems of linear forms,” J. Sov. Math., 22, 1310–1315 (1983).
T. H. Southard, Addition Chains for the First N Squares, Tech. Rep. CNA-84, Univ. of Texas at Austin (1974).
V. Strassen, “Berechnungen in partiellen Algebren endlichen Typs,” Computing, 11, 181–196 (1973).
E. G. Straus, “Addition chains of vectors,” Am. Math. Monthly, 71, 806–808 (1964).
M. V. Subbarao, “Addition chains — some results and problems,” in: R. A. Mollin, ed. Number Theory and Applications, NATO Adv. Sci. Inst. Ser., Ser. C, Vol. 265, Kluwer Academic, Dordrecht (1989), pp. 555–574.
H. Volger, “Some results on addition/subtraction chains,” Inform. Proc. Lett., 20, 155–160 (1985).
A. C.-C. Yao, “On the evaluation of powers,” SIAM J. Comput., 5, 100–103 (1976).
Author information
Authors and Affiliations
Corresponding author
Additional information
Translated from Fundamentalnaya i Prikladnaya Matematika, Vol. 20, No. 6, pp. 159–188, 2015.
Rights and permissions
About this article
Cite this article
Kochergin, V.V. On Bellman’s and Knuth’s Problems and their Generalizations. J Math Sci 233, 103–124 (2018). https://doi.org/10.1007/s10958-018-3928-4
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10958-018-3928-4