Calcular el número de bits de una gran potencia de entero

10

Dados dos enteros y en representación binaria, ¿cuál es la complejidad de calcular el tamaño de bit de ?n x nXnortexnorte

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 n1+log2(xn)=1+nlog2(x)Iniciar sesión2(X)Iniciar sesión2(X)kO(METRO(k)Iniciar sesiónk)METRO(k)kO(sIniciar sesión2s)sXnorte

¿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 nO(sIniciar sesión2(s))sXnorte

Nota: Estoy interesado en la complejidad de un modelo teórico como las máquinas de Turing.

Bruno
fuente
sugiera migrar / "promocionar" esto a Ciencias de la Computación Teórica
vzn
@vzn: No creo que esto sea útil ...
Bruno
¿Por qué no? Esta pregunta me recuerda los ataques algorítmicos contra la conjetura de Dyson, por ejemplo, según lo cubierto por RJLipton en 1 , 2
vzn
Simplemente porque encontré una respuesta a mi pregunta, así que no necesito preguntarla en otra parte.
Bruno

Respuestas:

1

[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 .Iniciar sesión(X)kX2k

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 |yyy1+Iniciar sesióny

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.El |X2kEl |=1+2kIniciar sesiónX2kIniciar sesión(X)Iniciar sesión(X)kIniciar sesión(X)k1X2kk

Bruno
fuente
1
¿Por qué el número de bits en le permite calcular log x to k bits de precisión? ¿Su reducción realmente funciona? ¿Qué pasaría si el caso especial donde n = 2 k fuera mucho más fácil / difícil que todos los demás valores posibles de n (no potencias de dos)? ¿Tienes alguna forma de descartar esa posibilidad? X2kIniciar sesiónXknorte=2knorte
DW
@DW: vuelvo a esta pregunta, después del comentario de vzn. Mi prueba es la siguiente: el número de bits de un entero es 1 + log y . Por lo tanto, el número de bits en x 2 k es 1 + 2 k log x . Además, 2 k log x es lo mismo que log x pero desplazó k posiciones a la izquierda. Por lo tanto, 2 k log x le da (al menos) los k primeros bits dey1+logyx2k1+2klogx2klogxlogxk2klogxk . Por lo tanto, si puede calcular el número de bits de x 2 k , restando 1 al resultado, obtendrá los primeros k bits de log x . ¿Esto tiene sentido? logxx2k1klogx
Bruno
¡Sí, eso tiene más sentido para mí! Particularmente porque solo estás tratando de mostrar dureza. ¿Puedo animarlo a actualizar su respuesta con esta explicación más detallada? Gracias por volver a esto y documentar la respuesta a su propia pregunta.
DW