Мультипликативная сложность двоичного слова α - это длина m самой короткой цепочки двоичных слов τ₋₁ = 0, τ₀ = 1, τ₁, . . . , τ_m = α, где каждое τ_i может быть представлено в виде конкатенации двух предшествующих слов: τ_i = τ_j τ_k, −1 ≤ j, k < i. Через l(k, n) обозначается максимальная мультипликативная сложность слов длины n с k единицами. Установлены интересные связи между величиной l(k, n) и наименьшим числом операций умножения, достаточным для вычисления набора степеней x^n₁,..., x^n_k. Основным результатом работы является асимптотическое соотношение l(k,n) = (1 + o(1))(log n + log C_n^k / loglog C_n^k) при n→∞.

цепочка слов, схема конкатенации, схемная сложность, функция Шеннона

Математические вопросы и теория численных методов