¿Cómo puedo escribir un algoritmo para realizar el siguiente cálculo exactamente? (referencias aceptadas)

Question

Dado números naturales $N, K, m, C$,$3^{m/3}K>C$, quiero ser capaz de escribir un algoritmo para calcular exactamente el número de

$$ \left\lceil \log_3 \left(\frac{N}{3^{m/3}K-C}\right) \right\rceil $$

Ya que creo que la vea cómo exactamente comparar un número entero en contra de este número, no es la trivial método de "prueba números más grandes, hasta que uno trabaja" (tal vez esto podría ser acelerado por duplicar el número de cada vez, y haciendo una búsqueda binaria una vez que el límite superior se encuentra?).

Sin embargo, creo que hay mejores métodos. Puede alguien que me señale una referencia en hacer este tipo de cálculo numérico exacto, o al menos dime cómo resolver este problema en particular en una no-forma terrible?

EDIT: Pues parece que un número de personas que han perdido el punto, quiero calcular este número exactamente, y quiero que la salida sea demostrablemente correcta. Sí, en la práctica, hacerlo con dobles obtendrá la respuesta correcta; ya tengo una versión del programa que hace eso. Pero quiero escribir una versión que es seguramente correcto, y, dado el suficiente memoria, el trabajo, incluso si el número de entrada que superan en el rango de un doble (aunque espero que nadie lo hace). En definitiva, cualquier posible falla que no sea de mi equipo que ejecuta fuera de la memoria es inaceptable.

Ya que el programa está escrito en Haskell, me apunta a una aritmética exacta de la biblioteca en Haskell que realmente funciona y es seguramente correcto, será suficiente para una respuesta. Pero, por favor, hacer algún tipo de comprobación que esto es en realidad o al menos probable que sea cierto de la biblioteca que usted está proponiendo que yo uso; por ejemplo, el último en el que he intentado, ERA, me dijo que $\lfloor 3-3^{-128}\rfloor=3$.

EDITAR de nuevo: un poco de experimentación con lo que pensé que sería un mejor método sugiere que tal vez la fuerza bruta/binario de búsqueda es el camino a seguir, después de todo. Oops? Bueno, no estoy seguro aún, pero mi punto es, si la respuesta es "Sí, binario de búsqueda que realmente es una buena manera de hacer esto, sin más elegante manera es necesario," voy a aceptar eso como una respuesta, no de la demanda de algunos de los mejores.

Answer 1

No tengo absolutamente ninguna experiencia en el uso de Haskell, pero dado una biblioteca de apoyo de precisión arbitraria de números de punto flotante y de tamaño arbitrario enteros yo haría lo siguiente:

• Definir una función $\tt{check}$ que toma un entero como entrada y un bool, como la producción con $$ {\tt de verificación}(r) = {\tt true} ~~~ \Leftrightarrow ~~~ 3^{3r+m} K^3 \ge (N + 3^r)^3, $$ es decir, una función que, como usted ha dicho, exactamente compara el número entero a la salida deseada.
• Calcular la expresión en aritmética de punto flotante con algunos de partida de precisión, almacenar el resultado en forma de un arbitrariamente grandes entero $r$.
• Compruebe si ${\tt check}(r) = {\tt true}$${\tt check}(r-1) = {\tt false}$. Si ese es el caso, $r$ ha probado ser el resultado correcto. Si no, el doble de la precisión y de la repetición.

No estoy seguro de si eso cuenta como un no-terrible solución, pero creo que debería terminar relativamente rápido. De hecho, en la mayoría de los casos se debe cancelar en su primer intento, dada la sensible partida de precisión. (También asumo que $3^{m/3}K-C > 0$, de lo contrario $\text{log}$ no está bien definido, de todos modos.)

Si desea evitar que la aritmética de punto flotante por completo, la idea de duplicar los números enteros y, a continuación, utilizando binario de búsqueda debe ser lo suficientemente rápido. Sólo se necesita algo como $4 \text{log}( <result> )$ cheques para ello. Espero un punto flotante de adivinar, entero-método de verificación a ser un poco más rápido, sin embargo.

Answer 2

Bueno, resulta que binario búsqueda era más rápida que los cálculos de punto flotante de alta precisión. No una muy interesante respuesta o respuesta matemática, pero que de lo que sucedió, así que voy a marcar esta cerrado.