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

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

Ежели нет — то предлагаю как задачку: её решение я получил.
На самом деле это не совсем задача для программистов, но знакомые математики такого решения не знают.
Re: Хорошо известная задача - возведение в степень.
От: vnp  
Дата: 23.04.08 17:55
Оценка:
Здравствуйте, nikvic, Вы писали:

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

N>Можно доказать, что нижняя оценка — lb(n)-1, так что есть "зазор" и естественна задача уменьшить его.

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


Я знаю верхнюю оценку log(n) + log(n)/log(log(n)) + o(log(n)/log(log(n)))
По ключевым словам additive chain, Scholz и Bauer (а также Bauer conjecture) можно найти много интересного.

N>Ежели нет — то предлагаю как задачку: её решение я получил.

N>На самом деле это не совсем задача для программистов, но знакомые математики такого решения не знают.
Re[2]: Хорошо известная задача - возведение в степень.
От: nikvic  
Дата: 23.04.08 18:18
Оценка:
Здравствуйте, vnp, Вы писали:

vnp>Здравствуйте, nikvic, Вы писали:


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

N>>Можно доказать, что нижняя оценка — lb(n)-1, так что есть "зазор" и естественна задача уменьшить его.

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


vnp>Я знаю верхнюю оценку log(n) + log(n)/log(log(n)) + o(log(n)/log(log(n)))

vnp>По ключевым словам additive chain, Scholz и Bauer (а также Bauer conjecture) можно найти много интересного.

N>>Ежели нет — то предлагаю как задачку: её решение я получил.

N>>На самом деле это не совсем задача для программистов, но знакомые математики такого решения не знают.

Ок, вполне сходится, спасибо. Примерно так Лупанов доказывал асимптотику для сложности реализации булевских функций схемами из функциональных элементов, не так ли?
Впрочем, там остаётся ещё один "академический" вопрос — является ли поиск "чемпионов" универсальной переборной задачей?
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.