encontrar el factor de escala más pequeña para obtener cada número dentro de una décima parte de un número entero de un conjunto de dobles

Question

Supongamos que tenemos un conjunto de dobles s, algo como esto:

1.11, 1.60, 5.30, 4.10, 4.05, 4.90, 4.89 

Ahora queremos encontrar el factor de escala entero positivo más pequeño x que cualquier elemento de s multiplicado por x está dentro de la décima parte de un número entero.

Disculpe si esto no es muy claro, solicite una aclaración si es necesario.

Limite las respuestas a los lenguajes de tipo C o pseudocódigo algorítmico.

Gracias!

Answer 1

Está buscando algo llamado aproximación simultánea a Diofantina. La declaración habitual es que se te dan los números reales a_1, ..., a_n y un positivo real epsilon y deseas encontrar los números enteros P_1, ..., P_n y Q para que |Q*a_j - P_j| < epsilon, con suerte Q lo más pequeño posible.

Este es un problema muy estudiado con algoritmos conocidos. Sin embargo, debe saber que es NP-difícil encontrar la mejor aproximación con Q < q donde q es otra parte de la especificación. Según mi entender, esto no es relevante para su problema porque tiene un epsilon fijo y quiere el Q más pequeño, y no al revés.

Un algoritmo para el problema es (Lenstra-Lenstra) -Lovász algoritmo de reducción de celosía. Me pregunto si puedo encontrar buenas referencias para ti. These class notes mencionan el problema y el algoritmo, pero probablemente no son de ayuda directa. Wikipedia tiene un fairly detailed page en el algoritmo, que incluye una lista bastante grande de implementaciones.

Answer 2

Para responder a la pregunta modificada de Vlad (si desea números enteros exactos después de la multiplicación), la respuesta es conocida. Si sus números son racionales a1/b1, a2/b2, ..., aN/bN, con fracciones reducidas (ai y bi relativamente primo), entonces el número que necesita para multiplicar es el mínimo común múltiplo de b1, ..., bN.

Answer 3

Ésta no es una respuesta completa, pero algunas sugerencias:

Nota: Estoy usando "s" para el factor de escala, y "x" para los dobles.

Antes que nada, pregúntate si la fuerza bruta no funciona. P.ej. intente s = 1, luego s = 2, luego s = 3, etc.

Tenemos una lista de números x [i], y una tolerancia t = 1/10. Queremos encontrar los enteros positivos más pequeños, de modo que para cada x [i], hay un número entero q [i] tal que | s * x [i] - q [i] | < t.

En primer lugar, tenga en cuenta que si podemos producir una lista ordenada para cada x [i], es bastante simple combinarlas para encontrar las más pequeñas que funcionen para todas ellas. En segundo lugar, tenga en cuenta que la respuesta depende solo de la parte fraccional de x [i].

Reorganizando la prueba anterior, tenemos | x - q/s | < t/s. Es decir, queremos encontrar una "buena" aproximación racional para x, en el sentido de que la aproximación debería ser mejor que t/s. Los matemáticos han estudiado una variante de esto donde el criterio para "bueno" es que tiene que ser mejor que cualquiera con un valor de "s" más pequeño, y la mejor manera de encontrarlos es mediante truncamientos del continued fraction expansion.

Desafortunadamente, esto no es exactamente lo que necesita, ya que una vez que se encuentra bajo su tolerancia, no necesariamente tiene que seguir mejorando - la misma tolerancia funcionará. La siguiente cosa obvia es usar esto para saltar al primer número que funcionaría, y hacer fuerza bruta desde allí. Desafortunadamente, para cualquier número, el más grande que el primero puede ser es el 5, por lo que no te compra tanto. Sin embargo, este método te encontrará que funciona, pero no el más pequeño. ¿Podemos usar esto para encontrar uno más pequeño, si existe? No lo sé, pero establecerá un límite superior para el forzamiento bruto.

Además, si necesita que la tolerancia para cada x sea < t, significa que la tolerancia para el producto de todo x debe ser < t^n. Esto podría permitirle adelantarse mucho y establecer un límite inferior razonable para el forzamiento bruto.