Hay un algoritmo que puede decir si el poder de dos números racionales es racional?

Question

Se ha sabido desde Pitágoras que 2^(1/2) es irracional. También es obvio que 4^(1/2) es racional. También hay una divertida prueba de que incluso el poder de dos números irracionales puede ser racional.

Puede que, en general, calcular si el poder de dos números racionales es racional?

La razón por la que estoy pidiendo, además de la curiosidad, es que la Fracción de tipo en Python siempre devuelve un float en la exponenciación. Si hay una manera rápida de saber si podría estar con precisión expresada como una fracción, la función de la energía podría regresar sólo flota cuando tiene que llegar.

EDITAR: Por petición popular, he cambiado de 0.5 a 1/2 para dejar claro que es una fracción y no un float.

Answer 1

Uno puede hacer esto mucho más rápido que usando la factorización prima. A continuación voy a mostrar cómo reducir el problema de la prueba si un número entero es un (específica) de potencia perfecto.

Suponga $\rm\:R,\: K/N\:$$\rm\:R^{K/N} = S\in\mathbb Q$, $\rm\:K/N\:$ de reducción, $\rm\:K,N\in\mathbb Z$. Mostramos $\rm\:R^{1/N}\in \mathbb Q.\:$ Por Bezout, $\rm\:gcd(N,K) = 1\:$ $\Rightarrow$ $\rm\:JN+IK = 1\:$ para algunos $\rm\:I,J\in \mathbb Z.\:$ por lo Tanto

$$\rm 1/N \ =\ J + IK/N\ \Rightarrow\ R^{1/N}\ =\ R^{J+IK/N}\ =\ R^J(R^{K/N})^I = R^J S^I \in \mathbb Q$$

Por el contrario $\rm\:R^{1/N}\in \mathbb Q\ \Rightarrow\ R^{K/N} = (R^{1/N})^K\in \mathbb Q$.

Así que hemos reducido el problema a la determinación de si $\rm\:R^{1/N} = A/B \in \mathbb Q$. Si es así, a continuación, $\rm\: R = A^N/B^N\:$ y $\rm\:gcd(A,B)=1\:$ $\Rightarrow$ $\rm\:gcd(A^n,B^n) = 1,\:$ por única factorización o Euclides del Lexema. Por la singularidad de la reducción de fracciones, esto es cierto si el menor de los términos en el numerador y denominador de $\rm\:R\:$ ambos $\rm\:N'th\:$ potencias de números enteros.

Así reducimos el problema de comprobar si un número entero es un poder perfecto. Esto se puede hacer muy rápidamente, incluso en el caso general, véase D. J. Bernstein, la Detección de poderes casi en tiempo lineal. 1997.

Answer 2

No hay realmente manera fácil para probar si el resultado de a ** b con a y b siendo los números racionales es racional. La forma más fácil es descomponer a en su primer factorización

a = p_0 ** k_0 * p_1 ** k_1 ... p_r ** k_r

con p_i ser números primos y k_i (firmado) enteros. El resultado de a ** b es racional si todos k_i * b son enteros de nuevo.

Answer 3

Yo diría que la verdadera respuesta aquí es la siguiente: Usted no quiere estar recuperándose de precisión una vez que lo has perdido.

Por ejemplo (como senderle) un ejemplo irrational^irrational = rational ejemplo sería e^ln(10) = 10. En tal caso, usted no quiere trabajar con flotadores; desea trabajar con matemática simbólica, como un sistema de álgebra computacional. Usted mira de las reglas para la exponenciación, y hacer una búsqueda para determinar que se simplifica.

---

Si realmente se vieron obligados a perder precisión sin embargo, y tratar de recuperar, y quería en este extraño contexto (irrational^irrational = rational), y no se preocupan por ser 100% correcto, usted puede hacer de la siguiente manera:

1. calcular a**b = c
2. si c es "cerca de un racional", el retorno que racional

Creo que este es utilizado en las calculadoras gráficas. Incluso python Fracción de la biblioteca utiliza esta técnica como .limit_denominator(...). Específicamente usted dice que va a regresar a la "más cercano" racional, pero ligeramente penalizar racionales que son "complicadas" (por ejemplo, el número de dígitos) en comparación con los insumos (base y exponente). Uno de esos algoritmo para la "mejor aproximación racional" sería el uso de fracciones continuas, por ejemplo, http://en.wikipedia.org/wiki/Continued_fraction#Best_rational_approximations (de manera similar a cómo aproximaciones racionales de pi son calculadas); usted puede modificar esto para sancionar las conjeturas de que están complicados con respecto a la base y el exponente.

Por lo tanto, yo personalmente preferiría que tiene el poder de simplificar expresiones matemáticas, en lugar de perder precisión y tiene que recuperarlo. =)