Вычисление количества бит большой степени целого

10

Учитывая два целых числа и в двоичном представлении, какова сложность вычисления размера битов ?н х нИксNИксN

Один из способов сделать это - вычислить путем вычисления аппроксимации с достаточной точностью. Похоже, что вычисление с битами точности может быть выполнено в где - время, необходимое для вычисления произведения двух целых чисел длины . Это приводит к (не особенно простому) алгоритму сложности приблизительно если является ограничением размера битов как и (если я не сделал ошибку).log 2 ( x ) log 2 ( x ) k O ( M ( k ) log k ) M ( k ) k O ( s log 2 с ) с х н1+журнал2(ИксN)знак равно1+Nжурнал2(Икс)журнал2(Икс)журнал2(Икс)КО(M(К)журналК)M(К)КО(sжурнал2s)sИксN

Можем ли мы победить где - размер и (в случае, когда они имеют сопоставимые размеры)? Есть простой алгоритм, чтобы получить эту сложность или лучше?О(sжурнал2(s))sИксN

Примечание: меня интересует сложность теоретической модели, такой как машины Тьюринга.

Bruno
источник
предложить перенести / «продвинуть» это в Теоретическую Информатику
vzn
@vzn: я не думаю, что это полезно ...
Бруно
почему бы нет? Этот вопрос напоминает мне о алгоритмических атаках на Dysons гипотезы например , как охватывается RJLipton в 1 , 2
ВЗНА
Просто потому, что я нашел ответ на свой вопрос, поэтому нет необходимости задавать его в другом месте, на мой взгляд.
Бруно

Ответы:

1

[edit] Как предложено, я редактирую свой ответ, чтобы дать больше деталей.

Ответ на мой второй вопрос - нет :

Предложение. Вычислить с точностью до k по меньшей мере так же сложно, как вычислить битовый размер x 2 k .журнал(Икс)КИкс2К

Доказательство. Пусть обозначает размер в битах целого числа у . Сначала обратите внимание, что для неотрицательного целого числа y размер битов y равен 1 + log y .|Y|YYY1+журналY

Таким образом, . Теперь 2 k log ( x ) - это log ( x ), сдвинутое на k позиций влево. Таким образом, можно вычислить log ( x ) с точностью до k , просто вычитая 1 в битовый размер x 2 k и сдвигая результирующие позиции k вправо.|Икс2К|знак равно1+2КжурналИкс2Кжурнал(Икс)журнал(Икс)Кжурнал(Икс)К1Икс2КК

Bruno
источник
1
Почему число бит в позволяет вычислить лог х до K битой точности? Ваше сокращение действительно работает? Что, если особый случай, когда n = 2 k, был намного легче / сложнее, чем все другие возможные значения n (не степени двух)? У вас есть способ исключить такую ​​возможность? Икс2КжурналИксКNзнак равно2КN
DW
@DW: Я возвращаюсь к этому вопросу после комментария vzn. Мое доказательство таково: количество бит целого числа равно 1 + log y . Таким образом, число битов в x 2 k равно 1 + k 2 k log x . Кроме того, 2 k log x - это то же самое, что log x, но смещено на k позиций влево. Таким образом, k 2 k log x дает вам (по крайней мере) k первых битовY1+журналYИкс2К1+2КжурналИкс2КжурналИксжурналИксК2КжурналИксК . Таким образом, если вы можете вычислить количество бит x 2 k , вычитая 1 из результата, вы получите первые k бит log x . Имеет ли это смысл? журналИксИкс2К1КжурналИкс
Бруно
Да, это имеет больше смысла для меня! Тем более что ты просто пытаешься показать твердость. Могу ли я призвать вас обновить свой ответ этим более подробным объяснением? Спасибо, что вернулись к этому и задокументировали ответ на свой вопрос.
DW