Dados y ,
Mis preguntas son:
Dado
- Suponiendo que podemos decidir en , ¿hay alguna forma de decidir sin tener que preformar las multiplicaciones (o divisiones), y . ¿O hay algún tipo de prueba de que no hay manera?
- ¿Existe un método más rápido para comparar números racionales que multiplicar los denominadores?
algorithms
integers
Ensalada Realz
fuente
fuente
Respuestas:
Mi investigación actual:
Intento inicial de algunas reglas generales
Uno puede tratar de hacer algunas reglas generales para resolver la comparación racional:
Asumiendo todos los positivos :a,b,c,d
Otra regla:
De ahora en adelante, asumiremos que , porque de lo contrario podemos resolverlo con las reglas anteriores o revertir la pregunta a , y terminamos con esta condición de todos modos.ca<c∧b<d cd<?ab
Reglas : Esto La regla básicamente establece que siempre se pueden restar los numeradores de los denominadores y establecer los resultados como numeradores para obtener un problema equivalente. Dejaré fuera la prueba.
Esta regla le permite restar el numerador y el denominador izquierdos del numerador y el denominador correctos para un problema equivalente.
Y, por supuesto, hay escala:
Usando estas reglas puedes jugar con cosas, aplicarlas repetidamente, en combinaciones inteligentes, pero hay casos en que los números son cercanos y patológicos.
Al aplicar las reglas anteriores, puede reducir todos estos problemas a:
A veces puedes resolver esto directamente ahora, a veces no. Los casos patológicos suelen tener la forma:
Luego lo voltea y da como resultado lo mismo, solo que con un poco menos. Cada aplicación de las reglas + volteo lo reduce en un dígito / bit. AFAICT, no puede resolverlo rápidamente, a menos que aplique las reglas veces (una vez por cada dígito / bit) en el caso patológico, negando su aparente ventaja.O(n)
¿Problema abierto?
Me di cuenta de que este problema parece ser más difícil que algunos problemas abiertos actuales.
Un problema aún más débil es determinar:
Y aún más débil:
Este es el problema abierto de verificar la multiplicación . Es más débil, porque si tuviera una manera de determinar , ¿entonces puede determinar fácilmente el , al probar usando el algoritmo dos veces, , . Iff tampoco es cierto, ya sabes que .ad<?bc ad=?bc ad<?bc bc<?ad ad≠bc
Ahora, ¿ era un problema abierto, al menos en 1986:ad=?c
Muy interesante, también mencionó la cuestión de verificar la multiplicación de matrices :
Esto se ha resuelto desde entonces, y de hecho es posible verificar en tiempo con un algoritmo aleatorio (con siendo el tamaño de las matrices de entrada, por lo que es básicamente un tiempo lineal en el tamaño de la entrada). Me pregunto si es posible reducir la multiplicación de enteros a la multiplicación de matrices, especialmente con sus similitudes, dadas las similitudes de la multiplicación de enteros de Karatsuba con los algoritmos de multiplicación de matrices que siguieron. Entonces, tal vez de alguna manera podamos aprovechar el algoritmo de verificación de multiplicación de matrices para la multiplicación de enteros.O(n2) n×n
De todos modos, dado que esto sigue siendo, que yo sepa, un problema abierto, ¿el problema más fuerte de seguramente está abierto. Tengo curiosidad por saber si resolver el problema de verificación de igualdad tendría alguna relación con el problema de verificación de desigualdad de comparación.ad<?cd
Una ligera variación de nuestro problema sería si se garantiza que las fracciones se reduzcan a los términos más bajos; en este caso es fácil saber si . ¿Puede esto tener alguna relación con la verificación de comparación para fracciones reducidas?ab=?cd
Una pregunta aún más sutil, ¿y si tuviéramos una forma de probar , ¿esto se extendería a probar ? ¿No veo cómo puede usar estas "dos formas" como lo hicimos para .ad<?c ad=?c ad<?cd
Relacionado:
Reconocimiento aproximado de idiomas no regulares por autómatas finitos
Trabajan un poco en la multiplicación aproximada y la verificación aleatoria, que no entiendo completamente.
fuente
Aquí hay un intento muy parcial de refutar. Supongamos que podemos usar solo un (número constante de) sumas y restas en nuestro decisor, así como un número constante de números predefinidos wrt. En otras palabras, podemos hacer un número constante de , , etc. en nuestro decisor. Entonces, las únicas cantidades que podemos calcular son de la forma donde las son constantes predefinidas. Tenga en cuenta que puede calcularse en el tiempo .mod mod 2 mod 3 q=k1a+k2b+k3c+k4d=∑kia k q O(∑|a|)
Editado Este decisor pretende determinar un bit iff . Considere tomar como puntos en . El bit se decide por su posición en la superficie que es un hiperboloide en 4 dimensiones. Si tenemos un punto en el espacio de entrada, el decisor anterior puede calcular puntos dentro de una distancia acotada de este punto de entrada, es decir, esos puntos etc. Esto define un cuboide en 4 d espacio.a d > b c a , b , c , d R 4 B a d = b c ( a , b , c , d ) q : | q - a | =B:B=1 ad>bc a,b,c,d R4 B ad=bc (a,b,c,d) q:|q−a|=k1,
(¿Cómo hacer que esto sea más preciso?) La distancia desde el cuboide hasta la superficie es generalmente ilimitada y, por lo tanto, la superficie no puede ser calculada por el decisor
fuente
Buena pregunta. ¿Aceptarías un nivel de confianza?
Quizás hacer una división aproximada. Es decir
Para calcular los cocientes aproximados delimitadores de a / b, desplace a la derecha a por ceil (log_2 (b)) y también por floor (log_2 (b)). Entonces sabemos que el cociente exacto se encuentra entre estos dos valores.
Luego, dependiendo de los tamaños relativos de los cuatro enteros, uno puede descartar ciertos casos y obtener el 100% de confianza.
Uno puede repetir el procedimiento para radix que no sea 2, y mediante una sucesión de tales operaciones aumentar el nivel de confianza, hasta que se observe de alguna manera un cambio de signo / desempate.
Ese es mi primer borrador de un método.
fuente
Seguro.
Idea: Compara la expansión decimal bit por bit.
Lo único desagradable es que primero tenemos que excluir la igualdad porque de lo contrario no podremos terminar.
Es útil comparar primero las partes enteras porque eso es fácil.
Considera esto:
Tenga en cuenta que el
do-while
ciclo tiene que terminar ya que los números son desiguales. Sin embargo, no sabemos cuánto tiempo dura; Si los números están muy cerca, podría pasar un tiempo.Claramente, no hay multiplicaciones costosas; lo único que necesitamos es multiplicar los nominadores por . En particular, hemos evitado computar y explícitamente.a d c b10 ad cb
¿Esto es rápido? Probablemente no. Hay muchas divisiones enteras, módulos ys
gdc
para calcular, y tenemos un ciclo cuyo número de iteraciones es inversamente proporcional a la distancia entre los números que comparamos.El método auxiliar:
fuente