algorithm - "Mayor divisor común" "aproximado"

language-agnostic math

Question

Supongamos que tiene una lista de números de coma flotante que son aproximadamente múltiplos de una cantidad común, por ejemplo

2.468, 3.700, 6.1699

que son aproximadamente todos los múltiplos de 1.234. ¿Cómo caracterizarías este "gcd aproximado" y cómo procederías a calcularlo o calcularlo?

Estrictamente relacionado con mi respuesta a esta pregunta .

Answer 1

Encontré esta pregunta buscando respuestas para las mías en MathStackExchange ( here y here ).

Solo he logrado (todavía) medir el atractivo de una frecuencia fundamental dada una lista de frecuencias armónicas (siguiendo la nomenclatura de sonido / música), que puede ser útil si tiene un número reducido de opciones y es factible calcular el atractivo de cada uno y luego elegir el mejor ajuste.

C & P de mi pregunta en MSE (allí el formato es más bonito):

• siendo v la lista {v_1, v_2, ..., v_n}, ordenada de menor a mayor
• mean_sin (v, x) = suma (sin (2 * pi * v_i / x), para i en {1, ..., n}) / n
• mean_cos (v, x) = suma (cos (2 * pi * v_i / x), para i en {1, ..., n}) / n
• gcd_appeal (v, x) = 1 - sqrt (mean_sin (v, x) ^ 2 + (mean_cos (v, x) - 1) ^ 2) / 2, que arroja un número en el intervalo [0,1].

El objetivo es encontrar la x que maximice la apelación . Aquí está el gráfico ( gcd_appeal ) para su ejemplo [2.468, 3.700, 6.1699], donde encuentra que el GCD óptimo está en x = 1.2337899957639993

Answer 2

Esta es una reformulación de la solución de shsmurfy cuando, a priori, eliges 3 tolerancias positivas (e1, e2, e3)
El problema entonces es buscar los enteros positivos más pequeños (n1, n2, n3) y, por lo tanto, la mayor frecuencia de raíz f tal que:

f1 = n1*f +/- e1
f2 = n2*f +/- e2
f3 = n3*f +/- e3

Suponemos 0 <= f1 <= f2 <= f3
Si arreglamos n1, entonces obtenemos estas relaciones:

f  is in interval I1=[(f1-e1)/n1 , (f1+e1)/n1]
n2 is in interval I2=[n1*(f2-e2)/(f1+e1) , n1*(f2+e2)/(f1-e1)]
n3 is in interval I3=[n1*(f3-e3)/(f1+e1) , n1*(f3+e3)/(f1-e1)]

Comenzamos con n1 = 1, luego incrementamos n1 hasta que el intervalo I2 e I3 contengan un entero; es decir, floor(I2min) different from floor(I2max) mismo que I3
Luego elegimos el entero más pequeño n2 en el intervalo I2, y el entero más pequeño n3 en el intervalo I3.

Suponiendo una distribución normal de los errores de punto flotante, la estimación más probable de la frecuencia de raíz f es la que minimiza

J = (f1/n1 - f)^2 + (f2/n2 - f)^2 + (f3/n3 - f)^2

Es decir

f = (f1/n1 + f2/n2 + f3/n3)/3

Si hay varios enteros n2, n3 en intervalos I2, I3 también podríamos elegir el par que minimice el residuo

min(J)*3/2=(f1/n1)^2+(f2/n2)^2+(f3/n3)^2-(f1/n1)*(f2/n2)-(f1/n1)*(f3/n3)-(f2/n2)*(f3/n3)

Otra variante podría ser continuar la iteración e intentar minimizar otro criterio como min (J (n1)) * n1, hasta que f caiga por debajo de cierta frecuencia (n1 alcanza un límite superior) ...

Answer 3

Esto me recuerda el problema de encontrar buenas aproximaciones de números racionales de números reales. La técnica estándar es una expansión de fracción continua:

def rationalizations(x):
    assert 0 <= x
    ix = int(x)
    yield ix, 1
    if x == ix: return
    for numer, denom in rationalizations(1.0/(x-ix)):
        yield denom + ix * numer, numer

Podríamos aplicar esto directamente al enfoque de Jonathan Leffler y Sparr:

>>> a, b, c = 2.468, 3.700, 6.1699
>>> b/a, c/a
(1.4991896272285252, 2.4999594813614263)
>>> list(itertools.islice(rationalizations(b/a), 3))
[(1, 1), (3, 2), (925, 617)]
>>> list(itertools.islice(rationalizations(c/a), 3))
[(2, 1), (5, 2), (30847, 12339)]

seleccionando la primera aproximación suficientemente buena de cada secuencia. (3/2 y 5/2 aquí.) O en lugar de comparar directamente 3.0 / 2.0 a 1.499189 ..., podría notar que 925/617 usa enteros mucho más grandes que 3/2, lo que hace que 3/2 sea un excelente lugar para detenerse .

No debería importar mucho de cuál de los números se divide. (Usando a / byc / b obtienes 2/3 y 5/3, por ejemplo). Una vez que tienes relaciones enteras, puedes refinar la estimación implícita del fundamental usando la regresión lineal de shsmurfy. ¡Todos ganan!

Answer 4

Exprese sus medidas como múltiplos de la más baja. Por lo tanto, su lista se convierte en 1.00000, 1.49919, 2.49996. Las partes fraccionarias de estos valores estarán muy cerca de 1 / Nths, para algún valor de N dictado por cuán cerca está tu valor más bajo de la frecuencia fundamental. Sugeriría un bucle al aumentar N hasta que encuentre una coincidencia lo suficientemente refinada. En este caso, para N = 1 (es decir, asumiendo que X = 2.468 es su frecuencia fundamental), encontraría una desviación estándar de 0.3333 (dos de los tres valores son .5 de X * 1), que es inaceptablemente alto. Para N = 2 (es decir, asumiendo que 2.468 / 2 es su frecuencia fundamental), encontraría una desviación estándar de prácticamente cero (los tres valores están dentro de .001 de un múltiplo de X / 2), por lo tanto, 2.468 / 2 es su aproximación GCD.

El mayor defecto en mi plan es que funciona mejor cuando la medición más baja es la más precisa, lo que probablemente no sea el caso. Esto podría mitigarse realizando la operación completa varias veces, descartando el valor más bajo en la lista de mediciones cada vez, luego use la lista de resultados de cada pasada para determinar un resultado más preciso. Otra forma de refinar los resultados sería ajustar el GCD para minimizar la desviación estándar entre los múltiplos enteros del GCD y los valores medidos.

Answer 5

La solución que he visto y usado yo mismo es elegir una constante, digamos 1000, multiplicar todos los números por esta constante, redondearlos a enteros, encontrar el GCD de estos enteros usando el algoritmo estándar y luego dividir el resultado entre dicha constante (1000) Cuanto mayor es la constante, mayor es la precisión.

Answer 6

Pregunta interesante ... no es fácil.

Supongo que miraría las proporciones de los valores de muestra:

• 3.700 / 2.468 = 1.499 ...
• 6.1699 / 2.468 = 2.4999 ...
• 6.1699 / 3.700 = 1.6675 ...

Y luego buscaría una proporción simple de enteros en esos resultados.

• 1.499 ~ = 3/2
• 2.4999 ~ = 5/2
• 1.6675 ~ = 5/3

No lo he perseguido, pero en algún punto de la línea, usted decide que un error de 1: 1000 o algo es lo suficientemente bueno, y retrocede para encontrar la base aproximada de GCD.

Answer 7

Puede ejecutar el algoritmo gcd de Euclid con algo menor que 0.01 (o un número pequeño de su elección) siendo un pseudo 0. Con sus números:

3.700 = 1 * 2.468 + 1.232,
2.468 = 2 * 1.232 + 0.004. 

Entonces, el pseudo gcd de los dos primeros números es 1.232. Ahora toma el gcd de esto con tu último número:

6.1699 = 5 * 1.232 + 0.0099.

Entonces 1.232 es el pseudo gcd, y los mutiples son 2,3,5. Para mejorar este resultado, puede tomar la regresión lineal en los puntos de datos:

(2,2.468), (3,3.7), (5,6.1699).

La pendiente es el pseudo gcd mejorado.

Advertencia: la primera parte de este algoritmo es numéricamente inestable: si comienzas con datos muy sucios, estás en problemas.

Answer 8

Supongo que todos sus números son múltiplos de valores enteros . Para el resto de mi explicación, A indicará la frecuencia "raíz" que está tratando de encontrar y B será una matriz de los números con los que debe comenzar.

Lo que estás tratando de hacer es superficialmente similar a la regresión lineal . Está tratando de encontrar un modelo lineal y = mx + b que minimice la distancia promedio entre un modelo lineal y un conjunto de datos. En su caso, b = 0, m es la frecuencia raíz, e y representa los valores dados. El mayor problema es que las variables independientes X no se dan explícitamente. Lo único que sabemos sobre X es que todos sus miembros deben ser enteros.

Su primera tarea es tratar de determinar estas variables independientes. El mejor método que se me ocurre en este momento supone que las frecuencias dadas tienen índices casi consecutivos ( x_1=x_0+n ). Así que B_0/B_1=(x_0)/(x_0+n) dado un entero pequeño (con suerte) n. A continuación, puede aprovechar el hecho de que x_0 = n/(B_1-B_0) , comience con n = 1 y continúe subiendo hasta que k-rnd (k) se encuentre dentro de un cierto umbral. Después de tener x_0 (el índice inicial), puede aproximar la frecuencia raíz ( A = B_0/x_0 ). Luego puede aproximar los otros índices encontrando x_n = rnd(B_n/A) . Este método no es muy robusto y probablemente fallará si el error en los datos es grande.

Si desea una mejor aproximación de la frecuencia raíz A, puede usar la regresión lineal para minimizar el error del modelo lineal ahora que tiene las variables dependientes correspondientes. El método más fácil de hacerlo es el ajuste por mínimos cuadrados. Wolfram''s Mathworld tiene un tratamiento matemático profundo del tema, pero se puede encontrar una explicación bastante simple con algunos de Google.