Des grands entiers et autres questions.

[jpapot]

Bonjour.

J'ai été amené à réaliser un petit programme qui cherche (et normalement devrait trouver) tous les triplets pythagoriciens contenant un entier choisi au départ. Rappel a²+b²=c² avec a, b et c trois entiers naturels > 0.

Après un essai en langage python, puis en langage C, j'ai pu remarquer (sur ma machine) que :
1) Le calcul en C est 20 fois plus rapide (en gros) qu'en python.
2) Le python comme le C finissent par donner des résultats faux quand les entiers deviennent très grands.
En C j'ai typé les entiers en %llu, c'est à dire long long unsigned, mais cette méthode a des limites.

Donc j'ai refait le même programme dans Xcas en me disant qu'il devait être capable de gérer des entiers sans limite de taille préalablement fixée. Il a l'air de bien fonctionner, comme les autres, pour des entiers assez petits, mais pour des plus grands, il semble mouliner sérieusement.

Mes questions un peu en vrac :
- Est-ce normal ou y a-t-il une configuration particulière du CAS pour accélérer ça ?
- Est-ce que comme je le suppose xcas donne les triplets sans erreur ?
- Puis-je utiliser giac dans un programme en C ?
- (aucun rapport) Comment afficher plusieurs choses sur une ligne ? -> voir la fin de mon prg
- (aucun rapport ou presque) Puis-je afficher le temps de calcul ?

Je vous joins le prg xcas (sans doute optimisable):

Code : Tout sélectionner

afficher("Ce programme permet de trouver, si possible, le(s) triplet(s) pythagoricien(s) qui contiennent un nombre choisi au départ.\n");
saisir("Entrez votre nombre : ",n);
compte:=0;
//recherche d'une hypoténuse
deb_j:=ceil(n*sqrt(2)/2);
pour j de deb_j jusque n-1 faire 
  k:=sqrt((n-j)*(n+j));
  si k==floor(k) alors
    afficher(n,j,k);
    compte:=compte+1; 
  fsi;
fpour;
//recherche d'un "moyen côté"
deb_i:=n+1;
fin_i:=ceil(n*sqrt(2));
pour i de deb_i jusque fin_i-1 faire
  k:=sqrt((i-n)*(i+n));
  si k==floor(k) alors
    afficher(i,n,k);
    compte:=compte+1;
  fsi;
fpour;
//recherche d'un petit côté
deb_i:=ceil(n*sqrt(2));
fin_i:=ceil((n*n+1)/2);
pour i de deb_i jusque fin_i faire
  j:=sqrt((i-n)*(i+n));
  si j==floor(j) alors
    afficher(i,j,n);
    compte:=compte+1;
  fsi;
fpour;
afficher("Il y a ",compte," possibilités.")

Merci de vos aides, éclairages, idées, connaissances !

JP

[parisse]

C'est normal que ca prenne du temps, si je ne m'abuse votre algorithme est quadratique en n (petit cote), en langage compile on ne peut donc pas esperer depasser n=10^5 de beaucoup, en Xcas comme le langage est interprete c'est au moins 100 fois plus lent que le C.
Pour la rigueur du resultat, pour des valeurs de n de cette taille, il ne devrait pas y avoir de problemes a condition de prendre une precision en flottants suffisante (au moins autant de chiffres significatifs que n^4). En effet calculer floor(sqrt(...)) necessite une approximation numerique. Pour eviter ce probleme, il faudrait pouvoir utiliser isqrt qui existe dans la librairie giac mais pas en Xcas.
Vous pouvez utiliser giac dans un programme C++. Depuis un programme C, vous pouvez uniquement utiliser la fonction caseval
extern "C" const char * caseval(const char *);
Pour afficher plusieurs choses sur une meme ligne vous pouvez concatener des chaines avec +
La fonction time() permet d'acceder au temps de calcul.

[jpapot]

Merci pour la réponse rapide et précise !

Pour illustration, voici un exemple des limites actuelles du programme (je ne suis même pas à 10^5 !)
Pour n=10000, le programme (C ou Python) trouve 35 triplets, tous exacts.
Pour n=20000, les deux derniers triplets proposés (sur 46 ?) sont incorrects :

Faux triplets.png (9.53 Kio) Consulté 8036 fois

La concanénation, bien sûr !
Pour time, je n'ai pas réussi à l'utiliser (?).

Bonne soirée.
JP

[parisse]

pour eviter d'avoir des faux positifs, vous pouvez faire un test supplementaire avant affichage et incrementation de compteur: i*i+j*j=k*k qui n'utilisera que de l'arithmetique exacte.
pour aller plus vite, il faudrait arriver a ne pas tester tous les i dans la derniere boucle, ca doit etre possible en estimant l'ecart entre 2 valeurs successives quand on a une presque solution.
pour utiliser time, vous pouvez soit faire time(instruction a executer) soit st:=time() avant et time()-st apres.

[jpapot]

Bonjour.
Suite de "L'odyssée des triplets".

Suite à votre remarque :

pour eviter d'avoir des faux positifs, vous pouvez faire un test supplementaire avant affichage et incrementation de compteur: i*i+j*j=k*k qui n'utilisera que de l'arithmetique exacte.
pour aller plus vite, il faudrait arriver a ne pas tester tous les i dans la derniere boucle, ca doit etre possible en estimant l'ecart entre 2 valeurs successives quand on a une presque solution.

j'ai pu modifier le programme dans la 3ème boucle (l'entier n choisi est le plus petit côté), en considérant l'écart entre l'hypoténuse et le moyen côté comme une variable delta, décroissant de floor(n*(sqrt(2)-1)) jusqu'à 1. Il n'y a pas besoin dans ce cas d'estimation. On peut se passer de la racine et ne faire des calculs sur les entiers. Le résultat est proprement stupéfiant : disparition des faux positifs et surtout accélération drastique du temps de calcul. Cette méthode devrait donner des résultats (en C) exacts pour des grands nombres jusqu'à l'ordre de 10^9 minimum.

Le même exemple que précédemment (n=20000) donne cette fois 44 possibilités, mais en 0.001975 secondes au lieu de 11.94 précédemment :

Vrais triplets.png (33.77 Kio) Consulté 8031 fois

Inconvénient, les résultats deviennent faux pour les "grands nombres" pour les boucles 1 (n=hypoténuse) et 2 (n=moyen côté), puisque il y a toujours des k=sqrt((n-j)*(n+j)).
Dans ces deux cas, il faudra sans doute faire une estimation de l'écart entre deux valeurs successives, comme vous dites, et ne tester que des n*n-i*i-j*j==0. A suivre !

Je suis conscient que ce post sort de la rubrique "Xcas", mais comme je parle aux matheux ...

Bon dimanche.
JP