Быстрый алгоритм для "частичного" возведения в степень

+ в цитатник

Cообщение скрыто для удобства комментирования.
Прочитать сообщение

Комментировать

« Пред. запись — К дневнику — След. запись »

Страницы: [1] [Новые]

NemOFF обратиться по имени Re: Быстрый алгоритм для "частичного" возведения в степень Воскресенье, 15 Января 2006 г. 01:33 (ссылка)

Придумать конечно можно... в принципе если числа большие - будет по сложней - используй "длинную арифметику" или к примеру...
году в 2000ом или в 01-ом была задачка такая на районной олимпиаде г. Н. Новгорода (и по некоторым данным ещё в пару городах):
Числа от 1 до n записаны по порядку без знаков препинания. Найдите i-ую цифру в данной записи
Решение примерно таково: Записываем все в файл, потом читаем...

Здесь тоже прокатит этот алгоритм.
Во-вторых, была где-то формула что степень выражаецца черех логарифм (арифметика школьная)...

если будут вопросы по этому поводу - могу ответить

LI 5.09.15

Ответить С цитатой В цитатник

kpt_Petia обратиться по имени Воскресенье, 15 Января 2006 г. 11:45 (ссылка)

что означает сия загадочная запись "загвоздка в том, что все должно работать в o(lg y)" не понял...

формулу такую знаю.. a^b = Exp(b * Ln(a)).. не знаю поможет ли т.к. сути задачи не понял.

Ответить С цитатой В цитатник

lnl122 обратиться по имени Воскресенье, 15 Января 2006 г. 12:38 (ссылка)

во втором томе Кнута где-то была похожая задача, единственно что неудобно, в djvu листать все 600 страниц в ее поиске.. елси Кнута нет, полистай этот блог, там есть ссылки на первые три тома (по 6 Мб) и вьювер (2 Мб)

Ответить С цитатой В цитатник

kpt_Petia обратиться по имени Воскресенье, 15 Января 2006 г. 12:43 (ссылка)

lnl122, те ссылки не работают уже ):
в смысле, пароль какой-то требуют

Ответить С цитатой В цитатник

Килгор_Траут обратиться по имени Воскресенье, 15 Января 2006 г. 22:54 (ссылка)

~~NemOFF~~, kpt_Petia, даю дополнительные спецификации:

1) Это чисто теоретическая задача. Ни о каких реальных компьютерах и языках программирования речь не идет. В условии говорится об "абстрактной машине, оперирующей целыми числами". Разрешаются только 5 операций: сложение, вычитание, умножение, деление целых (например 2/5=0) и нахождение остатка (%). Все эти операции занимают одну единицу времени (вне зависимости от размера чисел!)

2) o(lg y) - это значит, что время выполнения алгоритма должно расти медленнее, чем логарифмическая функция f(y)=lg y. Еще раз обращаю внимание на то, что от x и n время выполнения не зависит, они принимаются за постоянные.

3) Желателен алгоритм, который находит n-ную цифру без возведения в степень x^y. Дело в том, что все алгоритмы возведения в степень, насколько я знаю, занимает lg y времени, а это недопустимо.

Ответить С цитатой В цитатник

LiveInternetLiveInternet

-Рубрики

-Подписка по e-mail

-Поиск по дневнику

-Интересы

-Постоянные читатели

-Статистика

Быстрый алгоритм для "частичного" возведения в степень