V🇺
Это не синоним в данном случае?
Быстрое возведение в степень быстро, но не оптимально
Size: a a a
2020 May 04
JJ
Извиняйте, ссылку кинул
JJ
Меня чистая теория интересует
JJ
Оптимальный вариант в таком случае
lg
А большие числа в квадрат, наверное, возводить проще, чем маленькие в большую степень? Тогда бессодержательное замечание от человека не имеющего отношения к программированию: 9^n=(3^n)^2, но мб возвести в n-ую степень числа 3 и 9 одинаковая по сложности задача
MT
я бы пошагово возводил в квадрат
MT
типа f(n) == f(n/2)*f(n/2+ n mod 2)
🎄T
Быстрое возведение в степень быстро, но не оптимально
А что оптимально тогда?
JJ
Я в основном интересуюсь, есть ли какие-то свойства хитрые?
Все алгоритмы какие описал (как вам ссылку на вики кинуть, бот ссылки режет) не учитывают тот факт, что основание степени - константа
Все алгоритмы какие описал (как вам ссылку на вики кинуть, бот ссылки режет) не учитывают тот факт, что основание степени - константа
MT
скорее нет, чем да
EZ
типа f(n) == f(n/2)*f(n/2+ n mod 2)
Ну это бинарное возведение
MT
Ну это бинарное возведение
я же не программист
MT
придумал - сказал
MT
за логарифм должно работать
JJ
Вот так скину описание :)
JJ
Да, там все адекватные способы работают за логарифм
JJ
Просто где-то константа чуть меньше
V🇺
Оптимальный вариант в таком случае
а конечная цель какая?
JJ
Победа в споре :)
JJ
Если интересно, изначальная цель - определить сколько чисел на промежутке [1, 10^n) не имеют в своей записи идущих подряд цифр