Обычна для начинающих программистов: написать программу, "экономно" использующую умножения. Стандартное решение — разложение показателя n по степеням двойки — приводит к верхней оценке 2*lb(n) (битовая длина n).
Можно доказать, что нижняя оценка — lb(n)-1, так что есть "зазор" и естественна задача уменьшить его.

Меня интересует, есть ли вот такой опубликованный результат для верхней оценки: (1 + о(1))*lb(n), или, иначе, двойку в "школьной" оценку можно заменить на единичку с бесконечно малым "гаком".

Ежели нет — то предлагаю как задачку: её решение я получил.
На самом деле это не совсем задача для программистов, но знакомые математики такого решения не знают.