Por el título, ¿cuál es la forma más rápida de calcular exactamente el exponente $m$ de la mayor potencia de 2 que $2^m < 3^n$? Es posible hacer esto en el tiempo que es sub-lineal en el valor de $n$?
Me pregunto si hay una manera que es mejor que simplemente computing $3^n$ y contando el número de bits en el número resultante.
Como otros han señalado que el problema es equivalente a calcular el $\log_23=1/\log_32$ con la suficiente precisión. Un caso problemático puede producirse cuando $n\log_23$ está muy cerca de un entero, porque entonces puede que necesite aumentar la precisión a alturas inesperadas. No sé cómo hacerlo, pero uno de los autores de
"Hirvensalo y Karhumäki. Computación en la información parcial de intratable uno - el primero (ternario) dígitos de $2^n$ base $3$ como un ejemplo. En los fundamentos Matemáticos de la informática de 2002, el volumen de 2420 de Lecture Notes in Computer Science, pp 319-327"
me confió que se las arreglaron para hacer exactamente esto con el fin de resolver su problema (que se describe en el título de la ponencia). Puede ser que su técnica le ayudará también?
En primer lugar, tenga en cuenta que $m=\lfloor\frac{\log_e{3}}{\log_e{2}}n\rfloor$ @anon estados.
Así que si calculamos estos dos logaritmos y aplicar la función de arriba, hemos terminado.
La expansión de la serie de los logaritmos pueden ser obtenidos mediante
$\log_e{\frac{1+x}{1-x}}$ = $2\left(x + \frac{x^3}{3} + \frac{x^5}{5} + \dots + \frac{x^{2n+1}}{2n+1} + \dots\right)$ $, |x| < 1$
Observar (tal vez de nuevo) que estamos buscando $\log_e{3}$$\log_e{2}$. Podemos estimar que estas usando la primera $O(\log n)$ términos de cada serie. Hay en la mayoría de las $O(\log n)$ se multiplica por cada elemento de la serie. Decir que las operaciones aritméticas como la multiplicación y la división de tomar el tiempo de $f(n)$. Entonces se puede calcular cada logaritmo en el tiempo $O(\log{n}\log{n}f(x))$.
Vamos a observar ahora que es el tiempo de ejecución. Debemos primero calcular el $x$ con el fin de obtener los algoritmos de resolución de problemas:
$\frac{1+x}{1-x}=c$ donde $c$ es de dos o tres. Esto, obviamente, puede ser de hecho más rápido de lo que en realidad tomar el logaritmo, y la solución es $x = \frac{c-1}{1+c}$. Ahora podemos conectar el valor en el logaritmo de ecuaciones, que es la que más tiempo consume parte del algoritmo. Finalmente, se resuelve el original de la ecuación logarítmica para $m$. Es obvio que esto no lleve la mayor parte del tiempo. Así que hemos terminado.
Este debe ser precisa, y por lo tanto, una vez más, se toma su tiempo $O(\log{n}\log{n}f(x))$ donde $f(x)$ es el momento para que las operaciones aritméticas en un $x$ el número de bits.
Para números pequeños, se puede utilizar una tabla de búsqueda, y esto va a garantizar más rápido que $O(n)$ del tiempo.
Hmm, mientras estoy escribiendo Matt le da la misma idea. Sin embargo, yo no quiero perder el trabajo de haber escrito todo esto, y al menos aquí, es con un ejemplo concreto.
Hay una muy sencilla. Se hace uso de las sumas parciales de la logarítmica de la serie.
decir, que he n=53 y buscar m, tal que $ \small 2^m<3^n<2*2^m $ . A continuación, $ \small m = floor(n*log(3)/log(2)) $
Por lo que si utilizamos una adecuada alimentación de la serie para log(3) y el registro(2), y evaluar sucesivamente a órdenes superiores llegaremos a un valor, donde el suelo-la función no hace más que aumentar.
El ejemplo funciona rápido porque los parciales de las evaluaciones que convergen geométricamente con el índice de
Hay un powerseries para el logaritmo, que también converge para x>2. Este $$ \pequeño f(x,k) = 2 \cdot ( {x-1\over x+1} + ({x-1\over x+1})^3{1 \over 3} + ({x-1\over x+1})^5 {1 \over 5} + \ldots +({x-1\over x+1})^{2 k+1} {1 \over 2*k+1 } ) $$ Así tenemos por parciales de las evaluaciones
$$ \pequeño \lim_{ k \to \infty} ps(k) = floor ( {f(3,k) \más de f(2,k)} ) \text{ y } m(k)=n \cdot ps(k) $$ Llegamos a m=84 k=6
La evaluación de la powerseries con los términos para x=3:
$ \small {x-1\over x+1} = {1 \over 2} \text{ and } ({x-1\over x+1})^2= {1 \over 4} $
y con los términos para x=2:
$ \small {x-1\over x+1} = { 1 \over 3} \text{ and } ({x-1\over x+1})^2= {1 \over 9} $
entonces
$$ \pequeño \begin{array} {rllll}
ps(1) &=& { 1/2 \over 1/3 } &=& {3 \over 2} = 1.5 \\
ps(2) &=& { 1/2 + 1/8/3 \over 1/3+1/27/3 } &=& { 13*81 \over 24*28 } \\
ps(3) &=& { 1/2 + 1/8/3 + 1/32/5 \over 1/3+1/27/3 +1/243/5 } &=& { \cdots \over \cdots } \\
\cdots& & \cdots
\end{array}
$$
Aquí hay algunos Pari/GP-código:
m_by_n(n)=floor(log(3)/log(2)*n) [n=53,m_by_n(n)] \\ tengo un cheque para el verdadero resultado \\ inicializar bucle: k = 1 f3 = 1/2 f2 = 1/3 s3 = f3 s2 = f2 ps = 1.0*s3/s2 \\ este es el menor aproximado de registro(3)/log(2) m_k = n * ps \\ este es nuestro aproximado de n* log(3)/log(2) \\ bucle a través de la siguiente hasta que la convergencia k++ f3 /= 4 f2 /= 9 s3 += f3/(2*k1-1) s2 += f2/(2*k1-1) ps = 1.0*s3/s2 m_k = n*ps change_k = m_k -m_k1 m_k1 = m_k k ps m_k change_k ------------------------------------------------------------ %211 = [1, 1.5000000, 79.500000] %212 = [2, 1.5669643, 83.049107, 3.5491071] %213 = [3, 1.5812797, 83.807824, 0.75871649] %214 = [4, 1.5842020, 83.962707, 0.15488293] %215 = [5, 1.5848024, 83.994526, 0.031819453] %216 = [6, 1.5849281, 84.001190, 0.0066638762] %217 = [7, 1.5849550, 84.002614, 0.0014242816] %218 = [8, 1.5849608, 84.002924, 0.00031000195] %219 = [9, 1.5849621, 84.002993, 0.000068520789]
podríamos parar en k=6, porque el cambio es menor que la distancia a la siguiente mayor entero pero su tasa de disminución es más fuerte que 1/2
Sería incluso más elegante si tuviéramos una segunda powerseries que se aproxima desde arriba, y luego se detiene la iteración cuando sólo hay un número entero comprendido entre (pero no me da tanto el pensamiento).
[actualización]
Para n que proporcionan m con una muy buena aproximación (que significa que el uso de convergents de la continuación de la fracción de $ \small \log(3)/ \log(2)) $ ) necesitamos siempre la mayoría de las series de términos. En http://go.helms-net.de/math/collatz/2hochS_3hochN_V2.htm tengo una tabla con convergents. Para el mayor n documentado ( n=22431534635635487631007267235817836787 ( 38 dígitos), log(n)~86.0035311129 ), el algoritmo necesita 120 serie de términos, mientras que para un "promedio" en el número de cerca de ese número, algo necesario a la mitad del número de serie de términos. Es tal vez de interés, que los coeficientes de la serie de términos/log(n) son relativamente constantes a lo largo de las secuencias de las mejores aproximaciones (por fracciones continuas) así como para las secuencias de "promedio" aproximaciones, si he de elegir un número aleatorio n . Para los mejores aproximaciones esto es en la cerca de 1.4 (en el ejemplo 120/86.0 ) y por el promedio de las aproximaciones es en la cerca de 0.7 (o la mitad de la serie de términos que son necesarios).
[actualización 2] Esta actualización se produce mucho después de que se responda a la pregunta sólo para el lector superficial. Me dan una mejor Pari/GP-implementación de modo que usted puede tratar de inmediato con diferentes valores. También he adaptado la notación a mi habitual de los convenios.
\\ code for Pari/GP
SbyN(N)=floor(log(3)/log(2)*N) \\ the reference value
{SbyN_part(N,maxit=150)=local(f3,f2,s3,s2,ps,m_k,change_k,m_k_prev);
print(" "); \\ print-cmds only for demo
f3 = 1/2 ; f2 = 1/3 ;
s3 = f3 ; s2 = f2;
ps = 1.0*s3/s2 ; \\ this is the lower approximate of log(3)/log(2)
m_k = N * ps ; \\ this is our approximate of n* log(3)/log(2)
\\ loop through the following until convergence
for(k=1,maxit,
f3 /= 4 ; f2 /= 9;
s3 += f3/(2*k+1); s2 += f2/(2*k+1);
ps = 1.0*s3/s2 ;
m_k_prev = m_k;
m_k = N*ps ;
change_k = m_k -m_k_prev ;
print([k, s2*1.0, s3*1.0, ps,
floor(m_k),min(frac(m_k),frac(m_k)-1),change_k]);
if( frac(m_k) + change_k < 1,break());
);
return(floor(m_k)); }
Pruebe algunos valores interesantes que tienen muchas o pocas iteraciones:
\p 200 \\ I work with 200 digits prec by default
[N1=41,m_by_n(N1),SbyN_part(N1)]
[N1=94,m_by_n(N1),SbyN_part(N1)]
[N1=253,m_by_n(N1),SbyN_part(N1)]
[N1=253+1,m_by_n(N1),SbyN_part(N1)]
[N1=190537,m_by_n(N1),SbyN_part(N1)]
[N1=190537+1,m_by_n(N1),SbyN_part(N1)]
[N1=22431534635635487631007267235817836787;m_by_n(N1);SbyN_part(N1)]
[N1=22431534635635487631007267235817836787+1;m_by_n(N1);SbyN_part(N1)]
[N1=22431534635635487631007267235817836787+2;m_by_n(N1);SbyN_part(N1)]
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
