Abstract:
Let $l(x^n)$ be the minimal number of multiplications sufficient for computing $x^n$. In the paper, we improve the lower bound of $l(x^n)$. We establish that for all $\varepsilon >0$ the fraction of the numbers $k$, $k\le n$, satisfying the relation
\begin{equation*}
l(x^k)>\log_2n+\frac{\log_2n}{\log_2\log_2n}\left(1-(2+\varepsilon)\frac{\log_2\log_2\log_2n}{\log_2\log_2n}\right),
\end{equation*}
tends to 1 as $n\to\infty$.
Keywords:
addition chains, exponentiation, lower bounds of complexity.
Bibliographic databases:
Document Type:
Article
UDC:
519.714.1
Language: Russian
Citation:
V. V. Kochergin, D. V. Kochergin, “Improvement of the lower bound for the complexity of exponentiation”, Prikl. Diskr. Mat., 2017, no. 38, 119–132
\Bibitem{KocKoc17}
\by V.~V.~Kochergin, D.~V.~Kochergin
\paper Improvement of the lower bound for the complexity of exponentiation
\jour Prikl. Diskr. Mat.
\yr 2017
\issue 38
\pages 119--132
\mathnet{http://mi.mathnet.ru/pdm600}
\crossref{https://doi.org/10.17223/20710410/38/10}
Linking options:
https://www.mathnet.ru/eng/pdm600
https://www.mathnet.ru/eng/pdm/y2017/i4/p119
This publication is cited in the following 3 articles:
Vadim Vasilievich Kochergin, Proceedings of Academician O.B. Lupanov 14th International Scientific Seminar “Discrete Mathematics and Its Applications”, 2022, 4
Vadim Vasil'evich Kochergin, “Bellman's, Knut's, Lupanov's, Pippenger's problems and their variations as generalizations of the addition chain problem”, MVK, 2022, no. 20, 119
S. A. Korneev, “O slozhnosti realizatsii sistemy monomov ot dvukh peremennykh skhemami kompozitsii”, PDM, 2021, no. 53, 103–119
Citation in format AMSBIB
Contact us: