Вот нижняя оценка количества умножений:
Рассмотрим алгоритм, использующий сложения, вычитания и умножения, и вычисляющий

.
Будем считать "правильные" умножения, в которых хотя бы один из сомножителей зависит от каких-то

, и докажем, что их не менее

. По индукции.
База.

. Для вычисления

нужно одно правильное умножение.
Переход.

. Пусть алгоритм имеет сложность(кол-во правильных умножений)

. Рассмотрим первое правильное умножение. Оно вычисляет произведение

. Без ограничения общности

.
Рассмотрим новый алгоритм, который работает так: сначала он вычисляет

, а затем работает так же, как исходный. Так как в этом случае

, первое правильное умножение можно убрать, т.е. мы получили алгоритм вычисления какой-то функции

, имеющий сложность

. По предположению индукции

.
-- Пт сен 11, 2009 19:22:17 --Тут есть неточности, но их в принципе можно устранить (например, надо указать, что

должны быть неконстантными, линейно независимыми и проверить это для

)
Это изложение на основе статьи Винограда "On the Number of Multiplications Required to Compute Certain Functions" и шестой главы "Algebraic Complexity Theory", авторы Burgisser, Clausen, Shokrollahi.
-- Пт сен 11, 2009 19:27:10 --Задачка попроще: за сколько операций сложения можно вычислить сумму вида:
Конкретно для 15 я уже не помню значение. Для

есть оценка
