Re: [LONG][Solution et programme] solve a + k b ~ entier ( i.e. à moins d'epsilon d'un entier )

comme mon accès usenet s'est stabilisé, je recopie ici l'échange par mail et y répond dans le post précédant.
Le 13/11/2023 à 22:08, Olivier Miakinen a écrit :
 > Le 13/11/2023 10:59, Fabrice NEYRET a écrit :
 >>  Olivier Miakinen a écrit :
 >>> Tout d'abord, je rappelle que si b est entier ou rationnel,
 >>
 >> en pratique b = 2pi ;-)
 >
 > C'est parfait.
 >
 >
 >>> Pour simplifier le problème, je commence par calculer la partie entière et la
 >>> partie fractionnaire de a et de b (respectivement a1 et b1 pour la partie
 >>> entière, a2 et b2 pour la partie fractionnaire). On est bien d'accord que
 >>> si (a2 + k b2) est proche d'un entier, alors il en sera de même pour (a + k b)
 >>> qui est égal à (a1 + k b1) + (a2 + k b2).
 >> astucieux. le genre de manip de théorie des nombres dont je n'ai pas l'habitude :-)
 >>
 >>
 >>
 >>> Je calcule alors la fraction continue (ou continuée) de b2, et ses réduites
 >>> successives, jusqu'à ce que le dénominateur de la réduite soit supérieur ou
 >>> égal à 1/epsilon.
 >>
 >> mon but était d'éviter les boucles, mais comme b est une constante ça va.
 >>
 >>> Je calcule alors la fraction continue (ou continuée) de b2, et ses réduites
 >>> successives, jusqu'à ce que le dénominateur de la réduite soit supérieur ou
 >>> égal à 1/epsilon.
 >>
 >> mon but était d'éviter les boucles, mais comme b est une constante ça va.
 >
 > Oui, tu peux précalculer toutes les réduites pour tout niveau de précision
 > souhaité. En plus, avec 2pi, il te suffit d'une poignée de valeurs à tester
 > pour avoir une très bonne précision.
 >
 >>> a = 2.718281828459045 = 2 + 0.7182818284590451 (a1 + a2)
 >>> b = 3.141592653589793 = 3 + 0.14159265358979312 (b1 + b2)
 >>> profondeur = 3
 >>> Fraction continue de b2 : [0, 7, 15]
 >>> Réduite de b2 : 15/106 = 0.14150943396226415
 >>> Ceci convient pour epsilon ≥ 1/106 = 0.009433962264150943
 >>> delta = 106 × b2 - 15 = 0.008821280518070296
 >>> delta est positif, on calcule incr = (1 − a2)/(delta)
 >>> incr = 31.93619916789386, arrondi à 32
 >>> Le nombre k cherché vaut 32 × 106 = 3392
 >>
 >> et on est alors certain qu'il n'y en a pas de plus petit ?
 >
 > Alors non.
 >
 > D'une part, parce que l'on peut améliorer la précision d'un facteur de 2
 > sans aucun problème. En effet, le calcul que je faisais s'assurait qu'entre
 > deux valeurs successives de k j'obtenais deux résultats successifs espacés
 > d'epsilon. Mais du coup, lorsqu'il y a un entier entre ces deux résultats
 > successifs, cet entier est à une distance inférieure à epsilon/2 de l'un
 > des deux résultats, ce qui est deux fois meilleur que la distance d'epsilon
 > que j'avais envisagée !
 >
 > Et d'autre part parce que les calculs que je fais dépendent essentiellement
 > de la valeur de b et ne peuvent pas vraiment tenir compte de la valeur de a.
 > Par exemple, si tu prends a = 7−2pi et b = 2pi, mon algorithme n'a aucun
 > moyen de trouver que la valeur k = 1 donne exactement a + k b = 7.
 >
 > Chose amusante, avec ces valeurs a = 7−2pi et b = 2pi, le k trouvé pour
 > la réduite 1/3 (k = 15) est plus grand que celui trouvé pour la réduite
 > 1/4 (k = 8).
 >
 >
 >
 >>> C'est très efficace parce que la fraction continue de pi comporte
 >>> plusieurs grands nombres (7, 15, 292) et que donc les approximations
 >>> sont très bonnes.
 >>
 >> j'espere qu'il en va de même de 2pi, alors !
 >
 > Je m'attendais à ce que ce soit vraiment le cas, mais il y a un peu plus
 > de petits nombres au début pour 2pi que pour pi. Curieux. Cela dit c'est
 > quand même bien mieux que e, surtout si tu vas jusqu'à la profondeur 7
 > et le nombre 146.
 >
 > pi : [3, 7, 15, 1, 292, 1, 1, 1, 2, 1, ...]
 > 2pi : [6, 3, 1, 1, 7, 2, 146, 3, 6, 1, ...]
--
Fabrice