[WD12] Calcul du PGCD de deux nombres

**orditosh** · 13/04/2009, 16h04

Bonjour,
je souhaite calculer le PGCD de deux nombre.
J'ai fait ce code :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
nba est un entier = "60"
nbb est un entier = "168"
nPlusGrand,nPlusPetit est un entier
SI nba > nbb ALORS 
	nPlusGrand=nba 
	nPlusPetit=nbb 
	SINON 
	nPlusGrand=nbb 
	nPlusPetit=nba
FIN
r est un entier = modulo(nPlusGrand,nPlusPetit)
 
 
TANTQUE r <> 0
nPlusGrand = nPlusPetit * Arrondi(nPlusGrand/nPlusPetit) + r
r=modulo(nPlusGrand,nPlusPetit)
FIN
Trace(nPlusGrand)

Mais, il entre dans une boucle infinie ^^
Comment régler ce soucis ?
Merci.

**klbsjpolp** · 13/04/2009, 17h58

Ça ressemble à travail d'école ça! Avec quels nombres il entre dans une boucle infinie? De plus, si je me souvient bien il n'y a qu'un modulo et des substitution dans l'algorithme d'Euclide? Tu es sûr de l'avoir bien codé?

**orditosh** · 13/04/2009, 18h03

Je viens de retranscrire en windev un code PHP, voila ce que ça donne :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
PROCEDURE PGCD(nValA est un entier, nValB est un entier)
 
 
statut,resultat est une chaîne
reste,nNbEntier,petit,grand est un entier
 
SI nValA < nValB ALORS
	petit = nValA
	grand = nValB
SINON
	petit = nValB
	grand = nValA
FIN
 
statut = "1"
 
TANTQUE statut = "1"
	reste = Euclide(grand,petit)
	SI reste = 0 ALORS
		statut = "0"
		resultat = petit	
	SINON
		statut = "1"
		grand = petit
		petit = reste
	FIN
FIN
 
RENVOYER resultat
 
 
PROCEDURE Euclide(nombre est un entier, diviseur est un entier)
 
NbEntier, Reste sont des entiers
 
NbEntier = nombre / diviseur
Reste = modulo(nombre,diviseur)
 
RENVOYER Reste

Pour des nombres "basiques", cela fonctionne
Exemple, je fait un Trace(PGCD(160,68))
Il me rend bien "12"
Mais, lorsque je met des nombres extremements grands (20 chiffres significatifs tel que 69723607025984632587), j'ai un "-1"

D'ou vient le problème ?
Merci
(J'améliorerai la "propreté" du code après ... )

**klbsjpolp** · 13/04/2009, 21h05

Une variable de type "entier" est sur 32 bits (4 octets). Le plus grand nombre que tu peux y stocker est donc 2^32 = 4294967296. Si tu veux gérer des nombres plus grand, tu dois utiliser un type plus grand comme "entier sur 8 octets" (2^64 = 18446744073709551616) ou numérique.

**orditosh** · 13/04/2009, 23h30

Le PGCD renvoyé est 1 alors que, avec une calculatrice, j'ai un PGCD de 6 ...

**klbsjpolp** · 13/04/2009, 23h35

Pour quels nombres?

**orditosh** · 13/04/2009, 23h57

12056543270971033254 et 7964898

Je tiens à rajouter que, par ma calculatrice, le PGCD est 6
par ce site : http://site2wouf.fr/calculator.php#ici1
le PGCD est 2

Par celui-ci :
http://euler.ac-versailles.fr/webMat...e/euclide1.jsp
le PGCD est 6