Note : je vais réutiliser les notation des posts
./2 et
./4, reportez-vous-y donc si besoin est.
Pollux a écrit :
Mais relis ma phrase :Si tu recherches
les valeurs exactes des parties régulières et irrégulières (et pas seulement leur taille), alors tu ne peux pas supposer le numérateur égal à 1
Certes, mais relis ma phrase :
Enfin, une fois que l'on a la position de la limite et la taille du motif, il ne reste plus qu'à faire un 'masquage' sur la valeur réelle approchée de N/D calculée à la fin.
Je ne sais pas si le terme de
masquage et adapté et compréhensible, mais c'est le meilleur que j'aie trouvé, par comparaison avec les masques de bits utilisés en Asm (sauf que là, on masque des digits décimaux).
D'ailleurs, je me suis aperçu bien après avoir écrit ceci que le masquage était inutile, puisqu'il suffit de multiplier le motif de 1/D par N, et de faire la sommation de la partie qui reboucle si ça dépasse.
Euh ... je crois que là, je ne suis pas très clair, je vais reprendre l'exemple de N/D = 11/42 = 0.2 619047 619047 ... = 0.2 M M ... avec M le motif.
On a 1/D = 1/42 = 0.0 238095 238095 ... = 0.0 m m ... soit un motif m de taille 6 chiffres, valant 238095.
Or N*m = 11*238095 = 2619045 = 2 619045 : il y a 7 chiffres, soit 1 de trop, et en découpant à 6, on a les bouts 2 et 619045, d'où M = 2+619045 = 619047.
D'ailleurs, l'irrégularité de 1/D vaut 0.0, et en ajoutant le bout de N*m qui dépasse (soit 2), on retrouve bien une irrégularité de 0.2 (en se calant bien sûr à la limite irrégularité/motif, pas à la virgule).
Maintenant, pour trouver le motif de 1/D sans avoir à calculer la valeur approchée (auquel cas le masquage interviendrait ici), on utilise celui de 1/D'.
1/D' = 1/21 = 0. 047619 047619 ... = 0. m' m' ... il n'y a pas d'irrégularité puisque D' n'est plus divisible par 2 ou 5, soit X' = Y' = 0, et l'irrégularité va jusqu'à S'=sup(X';Y')=0 chiffre après la virgule (j'ai ajouté des primes à X, Y et S, puisque ce ne sont pas exactement les mêmes qu'avant, ce ne sont que les valeurs équivalentes, qui ici valent forcément 0, c'était juste pour rappeler un peu l'utilité de X et Y).
Dans 1/D = 1/42, l'irrégularité va jusqu'à S=sup(X;Y)=sup(1;0)=1 chiffre après la virgule, et il n'y a que des 0 dans cette partie irrégulière.
La taille du motif est de 6 puisque 21 divise 999999 = 10^6 - 1, et on a 999999/21 = (10^6 - 1) * 1/21 = 047619. 047619 047619 ... - 0. 047619 047619 ... = 047619 = m', soit le motif de 1/D'.
Or pour passer de D=42 à D'=21, on a divisé X=1 fois par 2 et Y=0 fois par 5, d'où un décalage de S=sup(X;Y)=1 de la limite pour 1/D = 1/42.
999999/42 * 10^S = 999999/(21*2^X*5^Y) * (2*5) = 999999/21 * 5 = 047619 * 5 = 238095 = m.
Soit m = 047619 * 5 = m' * 10^S / (2^X * 5^Y) = m' * 2^(S-X) * 5^(S-Y), sachant qu'au moins une des valeurs S-X et S-Y est nulle.
Notre vénérable Normalien a écrit :
Si n n'est divisible ni par 2 ni par 5, il n'y a pas d'irrégularité, et la longueur de la période de 1/n est le plus petit entier p tel que n divise 999....9 (p chiffres)
Quand n est en plus divisible par 2 ou 5, une irrégularité est ajoutée.
écrire le nombre rationnel sous la forme D/p, où D est un nombre décimal et p est un nombre premier non multiple de 2 et de 5.
Il semblerait donc que mon intuition sur le décalage valant S=sup(X;Y) se révèle exacte ...
• Ethaniel est tout fier 
!!!Pour ta forme en D/p, c'est exactement ce que je fait avec mon D devenant D', sauf que ça me permet de continuer à travailler avec des valeurs entières.
Pour p, il est vrai que le mot
premier est de trop ...
Il a aussi écrit :
p-1 = 6, dont les diviseurs sont 1, 2, 3 et 6
On teste :
7 ne divise pas 9
7 ne divise pas 99
7 ne divise pas 999 7 divise 999999
Sachant que c'est un algorithme destiné à tourner sur machine, et non à être fait à la main, je pense que la recherche des diviseurs de p-1 pour tester la divisibilité de 9...9 par p (c'est-à-dire mon D') a un coût trop important.
et si ça ne marche pas, faire quelque chose qui en C serait :T ++ ;
T *= 10 ;
T -- ;
Autant commencer à T=9,Certes, on teste pour 9999 et 99999 alors qu'on sait mathématiquement que ça ne peut pas marcher, mais sur machine, le temps perdu sera négligeable par rapport à la recherche des diviseurs de p-1.
0^(E-S) ;
// le motif est M
// l'irrégularité est I
Voici donc quel serait mon algorithme en pseudo-code C : // acquérir la valeur de N
// acquérir la valeur de D
Dp = D ;
E = max ( 0, 1 + floor(log(N/D)) ) ;
X = -1 ;
while ( Dp != floor(Dp) )
{ Dp /= 2 ;
X ++ ;
}
Dp *= 2 ;
Y = -1 ;
while ( Dp != floor(Dp) )
{ Dp /= 5 ;
Y ++ ;
}
Dp *= 5 ;
T = 9 ;
while ( T/Dp != floor(T/Dp) )
{ T ++ ;
T *= 10 ;
T -- ;
}
mp = T/Dp ;
S = max ( X, Y ) ;
m = mp * 2^(S-X) * 5^(S-Y) ;
M = N * m ;
b = floor ( M / (T+1) ) ;
M -= b * (T+1) ;
M += b ;
I = b * 1Je ne sais pas si ceci est du vrai code C, je ne touche plus à ça depuis longtemps, et cet algorithme est de trop haut niveau pour être fait simplement en Asm.
En tout cas, c'est une mise en forme informatique de tout ce que j'ai essayé d'expliquer, avec des variables intermédiaires inutiles mais en rapport avec les étapes que j'ai décrites.
J'espère juste que mon autre intuition (celle sur le décalage de E) est toujours valable, mais j'ai l'impression que la méthode donnée par HIPPOPOTAME utilise le même postulat.
Voilà voilà, j'espère juste ne pas avoir raconté trop n'importe quoi !
@++
), et l'algo de base me semble etre:
). On pose aussi v[n]=E((u[n]*10)/q). Alors il faut trouver les plus petits indices i<j tels que u[i]=u[j], et alors ce que tu recherches c'est v[0 .. i-1] et v[i .. j-1]. En gros, tu peux faire une bonne vieille liste des familles et une recherche brutale pour un truc en O(n^2), ou bien un arbre binaire de recherche en O(n.ln(n)).
Mais relis ma phrase :
!!!
