Dados dos números decimales, ¿es posible estimar la cantidad de lugares decimales necesarios para ajustar el resultado de su división? Siempre y cuando la división resulte en un número finito de decimales, por supuesto.
Por ejemplo:
1234.5678/2=617.2839, se requieren 4 lugares decimales1234.5678/4=308.64195, se requieren 5 lugares decimales1234.5678/8=154.320975, se requieren 6 lugares decimales1234.5678/6.4=192.90121875, se requieren 8 lugares decimales
Por estimar, no necesariamente necesito el número exacto de decimales en el resultado, sino una cantidad de decimales igual o mayor a la cantidad requerida, para garantizar que el resultado encaje.
Lo que he intentado
Logré resolver mi problema de forma aproximada utilizando números racionales y factorización prima, pero es muy costoso en términos de cálculo. Estos son los pasos:
- Tomar la división original:
1234.5678 / 6.4 - Convertirlo a un número racional:
12345678 / 64000 - Simplificar esta fracción usando el MCD de los dos números:
6172839 / 32000 - Tomar el denominador:
32000 - Calcular los factores de
2y5dividiendo sucesivamente por estos dos números:
32000\= 28 * 53 - (si se encuentra en este paso que el número tiene otros factores además de
2y5, entonces detenerse aquí: la división resulta en un número infinito de dígitos) - Tomar el máximo de los dos exponentes:
max(8,3) = 8 - 8 lugares decimales son suficientes para que el resultado de la división encaje.
Cómo llegué a la conclusión anterior
De todos los números primos, solo dividir por 2 y 5 resulta en un número finito de dígitos.
Cada división por 10 añade una cifra más al número decimal. Cada combinación de 2 y 5 resulta en un 10, por lo tanto, un dígito adicional.
En 2x * 5y, hay min(x,y) veces 10.
Ahora cada división por 2 o 5 puede potencialmente (aunque no siempre) requerir un dígito extra. Por lo tanto, agregaré cuidadosamente un dígito extra por cada factor restante de 2 o 5:
Número máximo de dígitos requeridos = min(x,y) + (x - min(x,y)) + (y - min(x,y))
Lo cual se simplifica a: x + y - min(x,y)
Lo cual se puede simplificar más a max(x,y).
Siento que mi enfoque, aunque funciona, es demasiado complejo. La consecuencia directa en mi software es la lentitud del algoritmo.
¿Existe un enfoque más directo para estimar la cantidad de lugares decimales necesarios para que el resultado de la división encaje?
Tenga en cuenta que he leído esta pregunta: Número de lugares decimales a considerar en una división pero no me ha ayudado.
2 votos
No creo que haya una forma más sencilla. Buen trabajo sin embargo.
0 votos
No veo por qué piensas que tu algoritmo es demasiado complejo. ¿En qué contexto es demasiado lento?
0 votos
@RobArthan Involucra calcular el MCD, lo cual es un algoritmo recursivo que requiere calcular varias veces el resto de una división; luego descomponer en factores 2 y 5, lo cual requiere nuevamente un número de divisiones que depende del tamaño del número. ¡Esas son muchas divisiones para calcular la escala del resultado de una sola división! Especialmente para una biblioteca de números de tamaño arbitrario.
0 votos
Entonces, ¿esto se trata de gestión de la memoria en una biblioteca de aritmética de tamaño arbitrario que estás diseñando? ¿Por qué no puedes asignar memoria como lo haces con la división? En cualquier caso, necesitas cuantificar los problemas de tiempo y espacio que te preocupan. Simplemente decir "muchas divisiones" no ayuda a nadie a entender tu problema. El MCD se calcula fácilmente usando un bucle si encuentras preocupante el rendimiento de la recursión, pero si ese es el caso, entonces tu problema es un problema de ciencias de la computación y no matemático. ¿Por qué no usar GMP? ¿O ver cómo lo hace GMP?
0 votos
@RobArthan Mi biblioteca sí utiliza GMP cuando está disponible. Esto no se trata de gestión de memoria, sino más bien de los ciclos de reloj necesarios para calcular el resultado. Cada división requiere muchos cálculos, por lo que si hay una manera más inteligente de lograr el mismo resultado con menos divisiones, ¡la tomaré! Si no hay ninguna, entonces supongo que mi enfoque será lo suficientemente bueno.
0 votos
Pero tu pregunta es sobre la cantidad de lugares decimales requeridos para el resultado de la división. ¿Por qué necesitas saber eso de antemano para lograr un algoritmo rápido?
0 votos
Ah, has entendido mal la pregunta, creo. No necesito la escala para hacer la división más rápida. Necesito la escala para poder asignar el número de dígitos del resultado decimal antes de hacer la división. Al dividir
1234.5678 / 6.4, que es12345678 / 64000, en realidad dividiré1234567800000000 / 64000(agregando8ceros al numerador), así que puedo estar seguro de que esta división no tendrá ningún resto. El resultado,19290121875, se asociará con la escala8para formar el decimal192.90121875. Necesito calcular esta escala antes de la división, lo más rápido posible.0 votos
Pido disculpas por mi malentendido de tu pregunta. Mi lectura de tu pregunta me llevó a pensar que querías saber cuántos dígitos asignar al resultado de un problema de división. Sin embargo, tu último comentario me dice que lo que realmente querías saber era cuántos dígitos asignar al resultado de un problema de división. Me temo que esta distinción es demasiado sutil para mí.
0 votos
No estoy seguro de cómo debería entender tu comentario?
0 votos
No estoy seguro de cómo hacerlo más claro. Si me pides que divida
1234.5678entre6.4redondeado a 2 decimales, entonces fácil, dividiré internamente1234567800 / 64000y retendré el cociente. Si no me das una pista sobre la escala del resultado, entonces necesito hacer algunos cálculos adicionales para pre-calcular cuántos ceros debo agregar al numerador antes de hacer la división. Y estoy tratando de hacer este cálculo más rápido, asumiendo que podría haber un método más inteligente que el mío. Por eso esta pregunta.0 votos
Nota: Mi implementación final está aquí.