Bonjour,

Tu sais que je n'ai pas appris à programmer ...
Je compense donc avec mon tableur préféré
Je peux te donner en quelques secondes le PGCD de deux nombres
jusqu'à 2^30.

salut

avec des soustractions :

def pgcd(a, b) :
   while a != b :
        if a > b :
            return pgcd (a - b, b)
        else :
            return pgcd (a, b - a)
    return a

def pgcd (a, b) :
   if b = 0 :
       return a
   else :
       return pgcd (b, a%b)

Récursions et pgcd en général ça veut dire perte de performance, mais voici un binary gcd pour changer d'Euclide.

fn binary_gcd(u: u128, v: u128) -> u128 {
    use std::cmp::min;
    use std::mem::swap;

    match (u, v) {
        (0, n) => n,
        (n, 0) => n,
        (mut a, mut b) => {
            // a = 2^i x et b = 2^j y donc gcd(a,b) = 2^k gcd(a>>k, b>>k) où k = min(i,j)
            // mais c'est aussi égal à 2^k gcd(x,y) parce que gcd(2u,v) = gcd(u,v) si v impair
            // enfin, x et y impairs => gcd(x,y) = gcd(|x-y|, min(x,y))
            let i = a.trailing_zeros();
            let j = b.trailing_zeros();
            let k = min(i, j);

            a >>= i;
            b >>= j;

            if a > b {
                swap(&mut a, &mut b);
            }

            binary_gcd(b - a, a) << k
        }
    }
}

fn main() {
    println!("Hello, world!");
    let (u, v): (u128, u128) = (123189451, 152315843152132);
    println!("{}", binary_gcd(u, v))
}

Bonjour,
Que c'est joli comme version Ulmiere, je ne connaissais pas cet algo, si on compare l'efficacité, ça donne quoi par rapport à Euclide ? C'est juste pas curiosité.

Pour mémoire
Voici un exemple de PGCD sur tableur ,(vous pouvez tester...)

Je ne crois pas qu'il y ait de grande différence entre les deux en termes de vitesse, mais je dirais que ça dépend de la taille des données.

La version binary a quand même l'avantage de ne nécessiter aucune division (ni aucun modulo), mais seulement des shifts. Les divisons sont des opérations qui coutent très cher.


A priori, binary_gcd devrait être plus rapide que l'algorithme d'Euclide la plupart du temps. Il faudra au plus O(m) étapes avec m le nombre de bits du plus grand des deux entiers. Sur entiers de 64 bits ou moins tout est très rapide.

Pour les deux algorithmes la complexité est de l'ordre de (à cause de la soustraction et des comparaisons, ou des divisions).
Si tu veux un pcgd pour les très grands entiers, les deux sont adaptables mais pas très efficaces. Ce sera beaucoup mieux de prendre la transformée de Fourier de ton vecteur de bits et de la trafficoter.


Sinon, c'est comme tu préfères, ou bien la simplicité d'Euclide (pas besoin de vérifier si a<=b à chaque tour de boucle, puisque a%b est toujours < b, tient en une ligne, les coefficients de Bézout sont calculablse quasiment de la même façon, etc), ou bien les opérations rapides idéales dans une boucle de l'algoithme binaire.

Merci pour l'info Ulmiere, si j'ai l'occasion, je testerai

Bonjour,

PGCD " moyen"

Sur mon tableur en cherchant des PGCD ,j'ai été surpris de la fréquence des nombres premiers entre eux ou de ceux  (les pairs) qui n'ont que 2 pourPGCD.
Alors j'ai fait une petite étude et j'arrive à 3.6 pour la moyenne des
PGCD sortis.
Existe-t-il une approche mathématique sur ce sujet ?

Oui. Le début est facile à comprendre, mais la fin, pas.

Le but est de calculer avec .

On groupe toutes les paires i<j en fonction de leur pgcd. On cherche le nombre de paires i<j de pgcd d<n (le cas d = n a déjà été traité silencieusement au début, il n'existe que la paire (n,n) et n n'est pas < n)

1) d'abord on ne regarde que les multiples de d
* d et 2d,3d,4d,... E(n/d)d : ça fait au plus E(n/d)-1 cas
* 2d et 3d,4d,5d,..., E(n/d)d : ça fait au plus E(n/d)-2 cas
* ...
* (E(n/d)-1)d et E(n/d)d : au plus 1 cas. On note que E(n/d) ne peut valoir zéro puisque n est > d.

2) A chaque ligne marquée par une étoile, il faut retirer tous les cas où kd et Kd ont un pgcd > d. Par exemple, le pgcd de 2d et 4d est 2d, pas seulement d.
Dit autrement, je veux le nombre de paires k<K telles que k et K sont premiers entre eux et inférieurs à E(n/d). Et ça c'est phi(n/d) = phi(E(n/d)) avec phi la fonction totient d'Euler !


Au final notre somme vaut, sauf erreur de ma part .


A partir de ce point, il y a encore de nombreuses choses à dire. D'abord on peut réécrire la somme de manière un peu différente pour n'avoir qu'à calculer les phi(d) jusqu'à la racine de n et non jusqu'à n (grace aux parties entières de n/d, encore du regroupement de termes et des changements de variable). On peut pour cela couper la somme en deux jusqu'à une borne qui en général est optimale en m = E(sqrt(n)). Ca s'appelle la méthode l'hyperbole de Dirichlet :

Ensuite, on peut introduire les bonnes vieilles méthodes de théorie des nombres/convolution de Dirichlet, etc.



Mais ici plus directement,

.


Le premier terme tendrait vers -1.
Dans l'autre, en majorant phi(d) par d, on a une somme de Riemann, donc la limite est et ça diverge malheureusement grossièrement.

Ceci dit, la même méthode fonctionnera peut-être après avoir essayé l'hyperbole ou en remettant le n/d dans la phi et non dans les parties entières. Ou avec un meilleur majorant de phi, mais ça j'en doute

>Ulmiere

Je te remercie de ton étude ,j'avoue humblement que je ne voyais
pas le niveau de difficulté.
Je pensais que   serait dans le coup.
En testant 1000  PGCD pris au hasard la moyenne baisse encore
j'en suis à  2.6 .
Peut-être qu'un programme test donnera une valeur approchée.

Nota
Pour tester mon tableur (8 à 15h11) ,j'ai volontairement pris
un "gros" PGCD   mais le plus souvent on est à <10 d'où ma moyenne.

Je crois que j'ai dit une petite bêtise, c'est pas (1+2S)/n² mais plutôt (n(n+1)/2 + 2S)/n². Ca change pas le noeud problème qui est de calculer S, cependant.

Sinon on peut plutôt regarder les couples avec i <= j (et non plus i<j) et utiliser ce que je racontais plus haut pour écrire .

La méthode de l'hyperbole me donne, sauf erreur de ma part à nouveau, pour n = 10 puissance 11,12,13,14 (après c'est trop long, flemme d'attendre ) respectivement (après avoir multiplié par 2 et, cette fois, retranché, le n(n+1)/2 en trop) :

156421839935892432276728
17041987867886314510820816
1844179174709569816666409320
198415956294578426990741424464


Pour les moyennes ensuite, c'est facile à calculer, tu rajoutes une virgule après les deux premiers chiffres

Analyse asymptotique peut-être demain si j'ai le temps

Merci à tous pour votre participation ,finalement de très bonnes idées ont pu être échangées dans ce post