|
Эта публикация цитируется в 3 научных статьях (всего в 3 статьях)
Вычислительные методы в дискретной математике
Уточнение нижней оценки сложности возведения в степень
В. В. Кочергин, Д. В. Кочергин Московский государственный университет имени М. В. Ломоносова, г. Москва, Россия
Аннотация:
Для величины $l(x^n)$ – минимального числа операций умножения, достаточного для вычисления по переменной $x$ степени $x^n$ – уточнена нижняя оценка. Установлено, что для любого $\varepsilon >0$ доля чисел $k$, не превосходящих $n$ и удовлетворяющих условию
\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*}
стремится к 1 при $n\to\infty$.
Ключевые слова:
аддитивные цепочки, возведение в степень, нижние оценки сложности.
Образец цитирования:
В. В. Кочергин, Д. В. Кочергин, “Уточнение нижней оценки сложности возведения в степень”, ПДМ, 2017, № 38, 119–132
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/pdm600 https://www.mathnet.ru/rus/pdm/y2017/i4/p119
|
Статистика просмотров: |
Страница аннотации: | 210 | PDF полного текста: | 91 | Список литературы: | 40 |
|