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

Le 24/11/2023 18:55, robby a écrit :

comme mon accès usenet s'est stabilisé, je recopie ici l'échange par
mail et y répond dans le post [suivant, je suppose]

Je ne sais pas si ta recopie de mon message est lisible en format flowed.

Mais, au moins pour moi qui n'acceptes pas ce format, ça ne l'est pas du
tout. Alors je vais recopier moi-même mon message.



Le 13/11/2023 10:59, Fabrice NEYRET a écrit :

>

[...]

sur ce fil j'ai ces réponses de toi. ( mais il ne sais plus m'afficher
les précédentes)

Euh... je ne comprends pas lesquelles, mais bon, tu en as eu. ;-)

s'il en manque un d'important, je dois pouvoir le retouver sur google
groupes, mais ce présent mail me parait clair.

Ok.

Tout d'abord, je rappelle que si b est entier ou rationnel,

>
en pratique b = 2pi ;-)

C'est parfait.

[...]

>

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).

>
le coup du delta était dans ton post rouge dont le contenu ne s'affiche
plus, mais je vois que c'est dans ton python:

Mon post « rouge » (???)

if delta > 0:
         print("delta est positif, on calcule incr = (1 − a2)/(delta)")
         incr = (1 - a2)/delta
     elif delta < 0:
         print("delta est négatif, on calcule incr = (a2)/(− delta)")
         incr = - a2/delta

>

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, ...]


--
Olivier Miakinen