Je n'ai pas le temps pour une réponse complète, mais voici une réponse partielle. Cette technique utilise les concepts de fractions continues - il y a beaucoup à leur sujet en ligne. Je vais ignorer votre valeur dmin, qui n'est pas utilisée ci-dessous.
Obtenez le continued fraction expansion of pi à autant d'endroits que vous avez besoin. Pour votre limite de Dmax < = 1e15 dont vous avez besoin que les 28 premiers numéros, qui sont
[3, 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, 2, 1, 1, 2, 2, 2, 2, 1, 84, 2, 1, 1, 15, 3, 13]
Utilisez une courte boucle pour trouver les réduites pour pi qui ont dénominateurs juste en dessous et juste au-dessus Dmax. En Python qui serait
pi_cont_frac = [3, 7, 15, 1, 292, 1, 1, 1, 2, 1,
3, 1, 14, 2, 1, 1, 2, 2, 2, 2,
1, 84, 2, 1, 1, 15, 3, 13]
denomlo, denomhi = 1, 0
numlo, numhi = 0, 1
for q in pi_cont_frac:
denomlo, denomhi = denomhi, q * denomhi + denomlo
numlo, numhi = numhi, q * numhi + numlo
if denomhi > dmax:
break
Certains logiciels, tels que Microsoft Excel, utiliserait la fraction numlo/denomlo, mais il peut y avoir une meilleure approximation que cela. Trouvez maintenant la valeur du nombre naturel r qui fait denomhi - r * denomlo juste en dessous (ou égal à) dmax.
Ensuite, soit numlo/denomlo ou (denomhi - r * denomlo)/(denomhi - r * denomlo) est votre fraction la plus proche de pi. Vérifiez juste lequel est le plus proche.
Cet algorithme est d'ordre log (dmax), et en raison des propriétés de pi il est généralement beaucoup plus faible. Pour dmax < = 1e15 il faut 28 boucles mais quelques instructions de nettoyage supplémentaires.
Vous pouvez faire un algorithme plus rapide en pré-calculant et en stockant les convergents (valeurs de numhi et denomhi) et en recherchant la valeur de denomhi juste au-dessus de dmax. Cela ne prend que 28 numéros, mais vous en aurez besoin pour les numérateurs et les dénominateurs. Une recherche binaire prendrait au plus 5 étapes pour la trouver - pratiquement instantanée. Encore une autre possibilité en utilisant plus de stockage et moins de calcul serait de stocker toutes les fractions intermédiaires. Ce stockage irait dans les centaines, au moins trois cents. Si vous n'aimez pas cette liste stockée pour l'expansion de fraction continue de pi, vous pouvez utiliser la valeur de pi pour calculer cela à la volée, mais en utilisant une double précision (en C) vous obtiendriez seulement les 28 numéros que je vous ai montrés .
Pour plus de recherche, rechercher des fractions continues et des fractions intermédiaires.
Est-ce que '44/14' est une réponse acceptable pour' dmin = 13' et 'dmax = 15'? –
Ou, pour le dire autrement: qu'est-ce qui motive la contrainte 'dmin'? Si la seule raison pour cela est de s'assurer que l'approximation est "assez bonne", le problème pourrait être plus facile si elle est reformulée d'une autre manière. par exemple.il existe un algorithme assez simple pour trouver le rationnel le plus simple dans un intervalle rationnel donné qui pourrait être facilement appliqué si la contrainte est en fait que l'approximation et pi diffèrent d'au plus 1/dmin, ce qui est une contrainte légèrement différente. –