Уточнение нижней оценки сложности возведения в степеньстатья
Статья опубликована в журнале из списка RSCI Web of Science
Информация о цитировании статьи получена из
Web of Science,
Scopus
Статья опубликована в журнале из перечня ВАК
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 22 февраля 2018 г.
Аннотация:В работе для величины $l(x^n)$~--- минимального числа операций умножения, достаточного для вычисления по переменной $x$ степени $x^n$~--- уточнена нижняя оценка.
Установлено, что для любого $\varepsilon >0$ доля чисел $k$, не превосходящих $n$ и удовлетворяющих условию
\begin{equation*}
l(x^k) > \log_2 n + \frac{\log_2 n}{\log_2 \log_2 n} \left( 1-(2+\varepsilon) \frac{\log_2 \log_2 \log_2 n}{\log_2 \log_2 n} \right),
\end{equation*}
стремится к 1 при $n \to \infty$.