Le plus grand diviseur commun "approximatif".

Question

Supposons que vous ayez une liste de nombres à virgule flottante qui sont environ les multiples d'une quantité commune, par exemple

2.468, 3.700, 6.1699

qui sont approximativement tous des multiples de 1,234. Comment caractériseriez-vous ce "pgcd approximatif", et comment procéderiez-vous pour le calculer ou l'estimer ?

Strictement lié à ma réponse à cette question .

Answer 1

Vous pouvez exécuter l'algorithme pgcd d'Euclide avec tout ce qui est inférieur à 0,01 (ou un petit nombre de votre choix) étant un pseudo 0. Avec vos chiffres :

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

Donc le pseudo pgcd des deux premiers nombres est 1,232. Maintenant vous prenez le pgcd de ceci avec votre dernier nombre :

6.1699 = 5 * 1.232 + 0.0099.

Donc 1.232 est le pseudo pgcd, et les mutiples sont 2,3,5. Pour améliorer ce résultat, vous pouvez prendre la régression linéaire sur les points de données :

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

La pente est le pseudo pgcd amélioré.

Attention : la première partie de cet algorithme est numériquement instable - si vous commencez avec des données très sales, vous avez des problèmes.

Answer 2

Exprimez vos mesures en multiples de la plus petite. Ainsi, votre liste devient 1,00000, 1,49919, 2,49996. Les parties fractionnaires de ces valeurs seront très proches de 1/Neuros, pour une certaine valeur de N dictée par la proximité de votre valeur la plus basse avec la fréquence fondamentale. Je vous suggère de faire une boucle en augmentant N jusqu'à ce que vous trouviez une correspondance suffisamment fine. Dans ce cas, pour N=1 (c'est-à-dire en supposant que X=2,468 est votre fréquence fondamentale), vous trouverez un écart type de 0,3333 (deux des trois valeurs sont à 0,5 de X * 1), ce qui est inacceptable. Pour N=2 (c'est-à-dire en supposant que 2,468/2 est votre fréquence fondamentale), vous trouveriez un écart type de pratiquement zéro (les trois valeurs sont à 0,001 d'un multiple de X/2), donc 2,468/2 est votre PGCD approximatif.

Le principal défaut de mon plan est qu'il fonctionne mieux lorsque la mesure la plus basse est la plus précise, ce qui n'est probablement pas le cas. On pourrait atténuer ce problème en effectuant l'opération entière plusieurs fois, en écartant à chaque fois la valeur la plus basse de la liste des mesures, puis en utilisant la liste des résultats de chaque passage pour déterminer un résultat plus précis. Une autre façon d'affiner les résultats serait d'ajuster le DCG pour minimiser l'écart type entre les multiples entiers du DCG et les valeurs mesurées.

Answer 3

Cela me rappelle le problème de la recherche de bonnes approximations rationnelles des nombres réels. La technique standard est une expansion en fractions continues :

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

Nous pourrions appliquer cela directement à l'approche de Jonathan Leffler et 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)]

en choisissant la première approximation suffisamment bonne dans chaque séquence. (3/2 et 5/2 ici.) Ou, au lieu de comparer directement 3.0/2.0 à 1.499189..., vous pourriez remarquer que 925/617 utilisent beaucoup plus grande entiers que 3/2, ce qui fait de 3/2 un excellent endroit pour s'arrêter.

Le nombre par lequel vous divisez ne devrait pas avoir beaucoup d'importance. (En utilisant a/b et c/b, vous obtenez 2/3 et 5/3, par exemple.) Une fois que vous avez des rapports entiers, vous pouvez affiner l'estimation implicite de la fondamentale en utilisant la régression linéaire de shsmurfy. Tout le monde y gagne !

Answer 4

Je suppose que tous vos chiffres sont des multiples de entier valeurs. Pour le reste de mon explication, A désignera la fréquence "racine" que vous essayez de trouver et B sera un tableau des nombres avec lesquels vous devez commencer.

Ce que vous essayez de faire est superficiellement similaire à régression linéaire . Vous essayez de trouver un modèle linéaire y=mx+b qui minimise la distance moyenne entre un modèle linéaire et un ensemble de données. Dans votre cas, b=0, m est la fréquence de racine, et y représente les valeurs données. Le plus gros problème est que les variables indépendantes X ne sont pas explicitement données. La seule chose que nous savons de X est que tous ses membres doivent être des entiers.

Votre première tâche consiste à essayer de déterminer ces variables indépendantes. La meilleure méthode à laquelle je peux penser pour le moment suppose que les fréquences données ont des indices presque consécutifs ( x_1=x_0+n ). Ainsi, B_0/B_1=(x_0)/(x_0+n) étant donné un petit nombre entier n (espérons-le). Vous pouvez alors tirer parti du fait que x_0 = n/(B_1-B_0) commencez avec n=1 et augmentez-le jusqu'à ce que k-rnd(k) se situe dans un certain seuil. Une fois que vous avez x_0 (l'indice initial), vous pouvez approximer la fréquence de racine ( A = B_0/x_0 ). Ensuite, vous pouvez approximer les autres indices en trouvant x_n = rnd(B_n/A) . Cette méthode n'est pas très robuste et échouera probablement si l'erreur dans les données est importante.

Si vous voulez une meilleure approximation de la fréquence de racine A, vous pouvez utiliser la régression linéaire pour minimiser l'erreur du modèle linéaire maintenant que vous avez les variables dépendantes correspondantes. La méthode la plus simple pour ce faire utilise l'ajustement des moindres carrés. Le monde des mathématiques de Wolfram a un traitement mathématique approfondi de la question, mais un explication assez simple peut être trouvé avec un peu de google.

Answer 5

Question intéressante... pas facile.

Je suppose que je regarderais les ratios des valeurs de l'échantillon :

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

Et je chercherais alors un simple ratio d'entiers dans ces résultats.

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

Je ne l'ai pas encore fait, mais à un moment donné, vous décidez qu'une erreur de 1:1000 ou autre est suffisante et vous revenez en arrière pour trouver le PGCD approximatif de base.