biginteger - recta - Detectar eficientemente que los números racionales son iguales.
que son los numeros irracionales (3)
Esto no será muy útil en su caso, si ya calcula previamente la aproximación de punto flotante; Puede que aún ahorre tiempo en la tubería (o algunas aproximaciones).
Examina los valores enteros de a, b, c y d.
Siendo los números racionales iguales , ellos describen la misma línea a través del origen.
Si c> a, entonces también debe ser d> b, de lo contrario estaríamos en el área gris en la parte inferior derecha; si c <a, a la inversa, debe ser que d <b, o estaríamos en la esquina gris superior izquierda. Las áreas grises no tienen posibilidades de igualdad, y si los números fueran aleatorios (es decir, no filtrados por aproximación flotante), habríamos excluido N / 2 de ellos con comparaciones de bigint N 2 .
Del 50% restante, podemos excluir la mitad notando que si a> b, entonces la línea negra está debajo de la bisectriz del primer y tercer cuadrante, y debe ser que c> d, de lo contrario C / D estaría en el otro lado de la bisectriz; Estaríamos en el sector naranja superior sin igualdad posible. El mismo o el caso a <b. Por lo tanto, otras dos comparaciones de bigint reducen los números que deben verificarse a una cuarta parte del original; esos pueden ser aproximados en punto flotante, y si son "casi iguales", estamos en la pequeña zona roja donde se necesitan otras técnicas.
También puede extender este método observando que para cualquier k, la relación de a a k b debe ser la misma que entre c y k d para que a / b y c / d sean iguales; y si k es una potencia entera de 2, eso permite varias optimizaciones posibles.
(En algún momento, por supuesto, el costo de esto superará el de a*d==b*c prueba a*d==b*c ).
Tengo una colección de muchos números racionales, con el numerador y el denominador de cada uno almacenado como un entero sin signo grande (cientos o miles de bits). Me gustaría poder probar de manera eficiente si un número racional dado a/b en el conjunto es igual a cualquier otro número racional c/d en el conjunto.
El método más directo sería probar si a*d == b*c , por supuesto, pero me gustaría algo más eficiente que calcular los productos completos.
Algunas notas sobre mi caso de uso particular:
- Los pares que probaré tienen una alta probabilidad de ser realmente iguales (porque ya los estoy precomputando y comparándolos por sus aproximaciones de punto flotante primero), por lo que la salida temprana si son desiguales no me ahorrará mucho tiempo.
- Estoy de acuerdo con la precomputación de datos adicionales para cada uno de los números, pero cada número solo se usará en un puñado de comparaciones, por lo que la precomputación costosa (como la factorización prima) probablemente no valga la pena.
- Los falsos negativos ocasionales estarían bien, pero los falsos positivos no lo están.
Creo que esto puede ser teóricamente imposible, pero echarlo a la mente de la colmena por si acaso.
Puede filtrar muchos pares de fracciones no iguales comparando las longitudes de bits. Sea l ( a ) = floor (log2 ( a )) + 1 la longitud de bits de a . Si a / b = c / d es mayor que l ( a ) + l ( d ) = l ( c ) + l ( b ).
Puede usar esto para aumentar la velocidad cuando primero compara las longitudes y compara los productos, solo si la suma de las longitudes es igual.
Segundo intento;) Si debe revisar los números nuevos repetidamente para determinar la contención del conjunto, debe almacenar las fracciones relativamente importantes en un conjunto ordenado. La función de comparación del conjunto debe comparar primero los contadores y los denominadores si los contadores son iguales. La comparación se puede hacer en tiempo lineal y, por lo tanto, encontrar un elemento en el conjunto ordenado con elementos M necesita O ( N registro M ) pasos. Reducir una fracción cuesta O (N²). Por lo tanto, probar un número para la contención requiere O (N² + N registro M ) pasos, y calcular el conjunto O ( MN² ).
Edición: en lugar de usar un conjunto ordenado o de árbol, puede usar un conjunto de hash que reduce el número requerido de pasos para buscar a O ( N ² + N ) = O ( N ²).