Algoritmo optimizado para convertir un decimal en una fracción "bonita"

Question

En lugar de convertir un decimal arbitrario en una fracción exacta (algo así como 323527/4362363), trato de convertirlo en algo común fácilmente discernible (en términos humanos) legibilidad) cantidades como 1/2, 1/4, 1/8, etc.

Además de usar una serie de comparaciones if-then, menos que/igual a etc., ¿hay técnicas más optimizadas para hacer esto?

Editar: En mi caso particular, las estimaciones son aceptables. La idea es que 0,251243 ~ 0,25 = 1/4 - en mi caso de uso, eso es "lo suficientemente bueno", siendo este último más preferible para la legibilidad humana en términos de un indicador rápido (no se utiliza para el cálculo, solo se usa como números de visualización).

Answer 1

Puede usar el algoritmo euclidiano para obtener el Divisor común más grande entre el enumerador y el denominador y dividirlo por él.

Answer 2

Buscar "aproximación continua de fracciones". Wikipedia tiene una introducción básica en su artículo de "fracción continua", pero hay algoritmos optimizados que generan el valor aproximado al generar la fracción.

A continuación, elija alguna heurística de detención, una combinación del tamaño del denominador y la cercanía de la aproximación, para cuando esté "lo suficientemente cerca".

Answer 3

A continuación, supongo que nuestros decimales están entre 0 y 1. Debería ser sencillo adaptar esto a números más grandes y números negativos.

Probablemente lo más fácil sería elegir el mayor denominador que encontraría aceptable y luego crear una lista de fracciones entre 0 y 1 que tengan los denominadores inferiores o iguales a ellas. Asegúrese de evitar cualquier fracción que pueda simplificarse. Obviamente, una vez que has enumerado 1/2, no necesitas 2/4. Puede evitar fracciones que pueden simplificarse verificando que el GCD del numerador y el denominador es 1 que demanda el algoritmo de Euclides. Una vez que tengas tu lista. Evalúe estos como números de coma flotante (probablemente se duplique, pero el tipo de datos obviamente depende de su elección de lenguaje de programación). Luego, insértelos en un árbol de búsqueda binaria equilibrado que almacene tanto la fracción original como la evaluación en coma flotante de la fracción. Solo debe hacer esto una vez para configurarlo inicialmente, por lo que el tiempo n * log (n) (donde n es el número de fracciones) no es mucho.

Luego, cada vez que obtenga un número, simplemente busque en el árbol para encontrar el número más cercano que se encuentra en el árbol de búsqueda. Tenga en cuenta que esto es un poco más complicado que buscar una coincidencia exacta porque el nodo que está buscando puede no ser un nodo hoja. Entonces, mientras recorre el árbol, mantenga un registro del nodo valorado más cercano que haya visitado. Una vez que llegue a un nodo hoja y compare ese nodo con el nodo valorado más cercano que haya visitado, habrá terminado. Cualquiera que sea el más cercano, su fracción es su fracción.

Answer 4

Aquí es una sugerencia: Asumiendo que su fracción de partida es p/q

1. Calcular r = p/q como un valor racional (coma flotante) (por ejemplo,r = flotador (p)/flotador (q))

2. Calcular el redondeado decimal x = int (10.000 * r)

3. Calcular GCD (denominador máximo común) de x y 10000: s = GCD (x, 10000)

4. representar el resultado como m/n, donde m = x/s y n =/s y (su ejemplo calcula a 371/5000)

Normalmente, todos los denominadores de 1000 son bastante legibles por humanos

Esto puede no proporcionar el mejor resultado cuando el valor está más cerca de casos más simples como 1/3. Sin embargo, personalmente encuentro que 379/1000 es mucho más legible para humanos que 47/62 (que es la representación fraccional más corta). Sin embargo, puede agregar algunas excepciones para afinar ese proceso (por ejemplo, calcular el p/GCD (p, q), q/GCD (p, q) y aceptarlo si uno de esos valores son de un solo dígito antes de continuar con este método)

Answer 5

solución bastante tonto, sólo por fracción "vista previa":

 
factor = 1/decimal 
result = 1/Round(factor) 
mult = 1 

while (result = 1) { 
    mult = mult * 10 
    result = (1 * mult)/(Round(mult * factor)) 
} 

result = simplify_with_GCD(result) 

buena suerte!