Учитывая два целых числа и в двоичном представлении, какова сложность вычисления размера битов ?н х н
Один из способов сделать это - вычислить путем вычисления аппроксимации с достаточной точностью. Похоже, что вычисление с битами точности может быть выполнено в где - время, необходимое для вычисления произведения двух целых чисел длины . Это приводит к (не особенно простому) алгоритму сложности приблизительно если является ограничением размера битов как и (если я не сделал ошибку).log 2 ( x ) log 2 ( x ) k O ( M ( k ) log k ) M ( k ) k O ( s log 2 с ) с х н
Можем ли мы победить где - размер и (в случае, когда они имеют сопоставимые размеры)? Есть простой алгоритм, чтобы получить эту сложность или лучше?
Примечание: меня интересует сложность теоретической модели, такой как машины Тьюринга.
Ответы:
[edit] Как предложено, я редактирую свой ответ, чтобы дать больше деталей.
Ответ на мой второй вопрос - нет :
Предложение. Вычислить с точностью до k по меньшей мере так же сложно, как вычислить битовый размер x 2 k .log(x) k x2К
Доказательство. Пусть обозначает размер в битах целого числа у . Сначала обратите внимание, что для неотрицательного целого числа y размер битов y равен 1 + ⌊ log y ⌋ .| Y| Y Y Y 1 + ⌊ журналY⌋
Таким образом, . Теперь 2 k log ( x ) - это log ( x ), сдвинутое на k позиций влево. Таким образом, можно вычислить log ( x ) с точностью до k , просто вычитая 1 в битовый размер x 2 k и сдвигая результирующие позиции k вправо.||Икс2К||= 1 + ⌊ 2Кжурналх ⌋ 2Кжурнал( х ) журнал( х ) К журнал( х ) К 1 Икс2К К
источник