Dados dos enteros y en representación binaria, ¿cuál es la complejidad de calcular el tamaño de bit de ?n x n
Una forma de hacerlo es calcular calculando una aproximación de con suficiente precisión. Parece que calcular con bits de precisiones se puede hacer en donde es el tiempo necesario para calcular el producto de dos enteros de longitud . Esto produce un algoritmo de complejidad (no especialmente simple) aproximadamente si está vinculado en el tamaño de bits de y (si no cometí ningún error).log 2 ( x ) log 2 ( x ) k O ( M ( k ) log k ) M ( k ) k O ( s log 2 s ) s x n
¿Podemos vencer a donde es el tamaño de y (en el caso de que tengan tamaños comparables)? ¿Existe un algoritmo simple para obtener esta complejidad o mejor?s x n
Nota: Estoy interesado en la complejidad de un modelo teórico como las máquinas de Turing.
Respuestas:
[editar] Según lo sugerido, edito mi respuesta para dar más detalles.
La respuesta a mi segunda pregunta es no :
Proposición. Calcular el hasta la precisión k es al menos tan difícil como calcular el tamaño de bit de x 2 k .log(x) k x2k
Prueba. Dejar denota el tamaño de bit de un entero y . Primero observe que para un entero no negativo y , el tamaño de bit de y es 1 + ⌊ log y ⌋ .El | yEl | y y y 1 + ⌊ logy⌋
Por lo tanto, . Ahora 2 k log ( x ) es log ( x ) desplazado k posiciones a la izquierda. Por lo tanto, se puede calcular log ( x ) con precisión k simplemente restando 1 al tamaño de bit de x 2 k y desplazando el resultado k posiciones hacia la derecha.∣∣X2k∣∣= 1 + ⌊ 2kIniciar sesiónx ⌋ 2kIniciar sesión( x ) Iniciar sesión( x ) k Iniciar sesión( x ) k 1 X2k k
fuente