Este es un problema de tarea. Dada la clase "Racional" con dos campos enteros, numerador y denominador, escriba una función para comparar dos instancias "Racionales". Deje r1 = a/b
y r2 = c/d
. La solución trivial es comparar a*d
y b*c
. ¿Podemos hacerlo mejor?¿Cómo comparar números racionales?
Respuesta
Por lo general, el costo de una rama es más que el costo de una multiplicación, por lo que no vale la pena tratar de ser inteligente aparte de eso. Si por enteros quieres decir int32, entonces promueve a int64 para realizar la multiplicación; si te refieres a enteros más grandes, entonces necesitas administrar la multiplicación usando los mecanismos habituales, en cuyo punto las suposiciones sobre las ramas pueden ser invalidadas.
-2 (a * d) es igual a -2 (b * c). –
En el caso general, no. Si espera hacer muchas comparaciones, un paso de procesamiento preliminar podría ocuparse de normalizar todo (dividiendo el numerador y el denominador por su gcd, y haciendo que el denominador sea positivo), de modo que las comparaciones de igualdad compararían a = c y b = d, pero calcular a * d = b * c ciertamente no es prohibitivo por ningún medio.
No me gusta a*d b*c
solución porque puede provocar un desbordamiento de número entero innecesario si algunos de los numeradores y denominadores son grandes. Aunque no tengo una mejor solución.
Si está utilizando Java, puede utilizar la clase java.math.BigInteger
en caso de que se produzca un desbordamiento; de lo contrario, puede implementar sus propios arreglos de bytes.
Si desea la solución sofisticada, convierta cada una de las dos fracciones en una fracción continua (utilizando una variante del algoritmo GCD). Este algoritmo simple genera un número entero a la vez. Compara cada par de enteros de las dos fracciones continuas parciales. Si son diferentes, salga. De lo contrario, genere el siguiente par y continúe mientras haya más. Para racionales, la secuencia es finita, por lo que terminará pronto. Creo que este es el mejor método cuando a, b, c, d son grandes.
Se ha demostrado que las continuas expansiones de fracciones para todas las raíces cuadradas irracionales son recurrentes. De modo que puede usar esto también para comparar esos elementos irracionales, incluso si sus representaciones binarias de computadora le darían un resultado incorrecto (debido a un truncamiento). Eso significa que tan pronto como detecte la repetición en el patrón, puede terminar, probando la igualdad de los dos irracionales.
Desde mi punto de vista, la solución trivial es incorrecto en caso de que existan números negativos permitidos:
¿Qué hay de r1=1/3
y b=1/(-3)
que debería ser un tanto números racionales correctas. y, por supuesto matemáticamente se cumple que: 1/(- 3) < 1/3
Sin embargo, los rendimientos de soluciones propuestas 1*3 > 1*(-3)
lo que conduce a la solución incorrecta que 1/3 < 1/(-3)
.
Me encontré con ese problema durante mi curso de Scala :-) Todavía no tengo una buena solución para eso.
Tal vez, como tan a menudo ayuda a mirar hacia el BOOST-Biblioteca: Allí se dice:
La operación de comparación-con-racional hace dos operaciones de tamaño doble GCD, dos adiciones y disminuciones adicionales, y tres comparaciones en el peor de los casos.(Las operaciones GCD son de tamaño doble, ya que se realizan en poco sistemática y los cocientes provisionales se retienen y se comparan, mientras que una función GCD directa sólo conserva y compara los residuos.)
http://www.boost.org/doc/libs/1_55_0/libs/rational/rational.html
Hasta ahora no tuve la oportunidad de investigar ese código.
Cheers, Felix
Mientras tanto yo tuvimos un vistazo en el código Boost y se hace lo mismo como Liberio describe en su respuesta anterior. https://stackoverflow.com/a/4288890/2682209 Así que este es definitivamente el camino "correcto" (pero engorroso) a seguir.
- 1. ¿Hay una biblioteca de números racionales comúnmente utilizada en Java?
- 2. Módulo de números racionales de Pure Python para 2.5
- 3. comparar cadenas como números en SQLite3
- 4. Usar expresiones regulares para comparar números
- 5. Comparar números de teléfono en Android
- 6. ¿Cómo comparar dos números decimales en bash/awk?
- 7. Comparar números de versión sin usar la función de división
- 8. ¿Cómo comparar dos NSInteger?
- 9. Cómo convertir cadenas numéricas racionales y decimales a flotantes en python?
- 10. Comparar los números de punto flotante en Latex
- 11. Comparar versiones como cadenas
- 12. Oracle: ¿Cómo puedo obtener un valor 'VERDADERO' o 'FALSO' al comparar dos NÚMEROS en una consulta?
- 13. Cómo comparar dos fechas
- 14. Cómo comparar archivos XML
- 15. ¿Cómo comparar dos consultas?
- 16. ¿Cómo comparar dos NSIndexPaths?
- 17. Cómo comparar tipos
- 18. ¿Cómo comparar tipos genéricos?
- 19. Cómo comparar máquinas virtuales
- 20. cómo comparar dos NSMutableArray?
- 21. Números binarios en Python
- 22. ¿Cómo mostrar los racionales como largas listas de dígitos en Lisp?
- 23. máximo de 2 números
- 24. ¿Deberíamos comparar los números de coma flotante para la igualdad con un error * relativo *?
- 25. Cómo comparar 2 objetivos Xcode
- 26. ¿Cómo comparar fechas en Java?
- 27. ¿Cómo comparar dos variables CGSize?
- 28. Cómo comparar valores sqlite TIMESTAMP
- 29. ¿Cómo comparar vectores con Boost.Test?
- 30. ¿Cómo comparar e incrementar atómicamente?
¿Cuál es la definición de "mejor"? Me parece bastante óptimo. –