Problème! Erreur de compilation Caml.

Version imprimable

Bonjour, j'aurai besoin d'aide sur une fonction Caml que je fais dans le cadre d'un projet informatique.
J'ai une erreur de compilation et je n'arrive pas à déterminé d'où vient mon erreur.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
 let miller_rabin n k =
 if n < 2 then print_string "trop petit"
 else if n != 2 && (n mod 2) = 0 then print_string "pair : non premier"
 else
 (
 let s = n-1 in
 while (s mod 2) = 0 do
	s lsr 1
 done;
 for i = 0 to k do
	 let a = (Random.int (n-1))+1
 	 and temp = s in
	 let mo = (puiss a temp) mod n in
	 while temp != (n-1) && mo != 1 && mo != (n-1) do
		 mo := (puiss mo 2) mod n;
		 temp := temp * 2;
	 done;
	 if mo != (n-1) && (temp mod 2) = 0 then print_string "pseudo";
 done;
 print_string "composé"
 )
 ;;

voici la réponse du compilateur :

Code:

1
2
3
4
5
6
 
File "D:/cours/M1/AC Algo et Complexite/Projet/arithmetique.ml", line 8, characters 1-8:
Warning 10: this expression should have type unit.
File "D:/cours/M1/AC Algo et Complexite/Projet/arithmetique.ml", line 15, characters 2-4:
Error: This expression has type int but an expression was expected of type
         'a ref

Voilà, toute proposition seras la bienvenue.

07/01/2012, 13h51
gasche
Les deux messages du compilateur sont très explicites, ils t'indiquent des problèmes dans ton code.

Citation:

File "D:/cours/M1/AC Algo et Complexite/Projet/arithmetique.ml", line 8, characters 1-8:
Warning 10: this expression should have type unit.

On regarde ce qui se trouve ligne 8 :
Code:

1 2 3 while (s mod 2) = 0 do s lsr 1 done;
`s lsr 1` c'est un entier, cette expression ne fait rien, elle renvoie juste un nombre. `while ... do s lsr 1 done` n'a donc pas de sens. Le compilateur te dit que tu mets un entier (int) à un endroit où une action (type unit) est attendue.

Citation:

File "D:/cours/M1/AC Algo et Complexite/Projet/arithmetique.ml", line 15, characters 2-4:
Error: This expression has type int but an expression was expected of type
'a ref

On regarde ligne 15:

Code:

mo := (puiss mo 2) mod n;

Les caractères 2 à 4 correspondent à `mo`. Comment est défini mo ?

Code:

let mo = (puiss a temp) mod n in

`mo` est un entier (type int) et pas une référence sur un entier (type int ref). C'est bien ce que dit le compilateur.

Dans le second cas, la correction est très simple : `let mo = ref ((puiss mo 2) mod n)`. Dans le premier cas, ça dépend de ce que tu veux faire.

PS: pour calculer (a^b mod n), il y a beaucoup plus efficace que calculer (a^b), qui est un très gros nombre, puis faire modulo n. Tu peux faire un modulo sur chaque multiplication intermédiaire, pour éviter de manipuler des nombres trop gros. C'est ce qu'on appelle l'exponentiation modulaire.

toujours un problème.

salut. Tout d'abord je te remercie de m'avoir répondu.
Sache que j'avais testé plusieurs solutions dont le 'let' dans le while or il m'affiche une erreur sur le 'done'.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 let miller_rabin n k = if n < 2 then print_string "trop petit" else if n != 2 && (n mod 2) = 0 then print_string "pair : non premier" else ( let s = n-1 in while (s mod 2) = 0 do s lsr 1 done; for i = 0 to k do ( let a = (Random.int (n-1))+1 and temp = s in let mo = (puiss a temp) mod n in while temp != (n-1) && mo != 1 && mo != (n-1) do let mo = (puiss mo 2) mod n in let temp = temp * 2 done; if mo != (n-1) && (temp mod 2) = 0 then print_string "pseudo"; ) done; print_string "composé" ) ;;
le compilateur :
Code:

1 2 3 #use "D:/cours/M1/AC Algo et Complexite/Projet/arithmetique.ml";; File "D:/cours/M1/AC Algo et Complexite/Projet/arithmetique.ml", line 18, characters 3-7: Error: Syntax error
Je crois qu'il n'aime pas trop les "let" dans les boucles. Je ne sait plus, je penche dessus depuis pas mal de temps et je n'y arrive pas. Surtout quand le compilateur te marque "Syntax error", ce n'est pas chose aisée de trouver l'erreur.

08/01/2012, 07h49
Cacophrene

Bonjour,

Citation:

Envoyé par jocven

Je crois qu'il n'aime pas trop les "let" dans les boucles. Je ne sait plus, je penche dessus depuis pas mal de temps et je n'y arrive pas. Surtout quand le compilateur te marque "Syntax error", ce n'est pas chose aisée de trouver l'erreur.

Le compilateur te dit qu'il y a une erreur de syntaxe à la ligne 18, caractères 3-7, ce qui correspond au mot-clef done. En général, cela veut dire qu'il faut chercher l'erreur un peu plus haut dans le code. En l'occurrence, elle se trouve juste au-dessus, ligne 17. En effet, on écrit toujours let foo = bar in quand on est à l'intérieur d'une expression. Or, dans ta boucle while, tu as un let bien écrit suivi d'un second let auquel il manque le in final : c'est ça qui est la cause de l'erreur ! Bref, le message du compilateur me semble ici assez explicite.

Cependant, il me semble que le problème principal est plus profond que ça : tu raisonnes en style impératif et, semble-t-il, en utilisant les variables OCaml d'une façon inappropriée. J'en veux pour preuve ta variable mo. Si tu veux que son contenu soit modifié à l'intérieur de la boucle while, il faut que tu utilises une référence, car en OCaml les variables définies par let ne sont pas mutables (l'expression foo = bar est un booléen, pas une affectation). Or, en l'état actuel, la variable mo n'est en aucun cas modifiée par la boucle while, qui tourne à vide !

Par ailleurs, tu as beaucoup de parenthèses superflues dans ton code, et l'opérateur "différent de" se note <> en OCaml. L'opérateur != fonctionne aussi, mais c'est un test d'égalité physique qui n'a pas vraiment de raison d'être ici. Outre l'exponentiation modulaire indiquée par gasche, tu peux aussi noter que le modulo 2 est efficacement remplacé par opération sur les bits (land 1), et la multiplication par 2 par un shift.

Dernière remarque : dans l'esprit de la programmation OCaml, une fonction ne devrait pas faire un calcul, puis un effet de bord, et renvoyer unit. Il serait sans doute plus proche de l'esprit caml d'écrire une fonction miller_rabin qui renvoie un résultat, et une fonction distincte qui procède à l'affichage.

Cordialement,
Cacophrène
08/01/2012, 18h13
jocven

Merci pour ta réponse.
J'avais déjà essayer avec le 'in' après le deuxième 'let' mais ça ne fonctionne toujours pas. J'ais une fonction qui ne marche pas à cause d'une simple boucle 'while'. Dite moi comment la faire de façon précise pour modifier mes valeurs dans cette boucle svp.

Donner moi un exemple pour ma boucle while svp.
08/01/2012, 18h51
gasche
Il faut soit utiliser une fonction récursive à la place, soit utiliser des références comme je l'avais mentionné dans ma réponse (la fonction "ref", et pour la modification l'opérateur ":=").

À quel cours de Caml as-tu accès ? Les deux méthodes devraient être décrites dans ton cours.

Exemple avec fonction récursive:
Code:

1 2 3 4 5 let retourne li = let rec renverse acc = function | [] -> acc | t::q -> renverse (t::acc) q in renverse [] li
Exemple avec boucle:
Code:

1 2 3 4 5 6 7 8 let retourne li = let acc = ref [] in let curr = ref li in while !curr <> [] do acc := (hd !curr) :: !acc; curr := tl !curr done; !acc

Merci pour tout. J'ai réussi à faire fonctionner ma fonction.

je donne le code quand même.

Code:

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
let rec decalage s =
		if (s mod 2) = 0 then
			decalage (s lsr 1)
		else s
;;
 
let (*miller_rabin*)mr n k =
if n < 2 then print_string "trop petit"
else if n != 2 && (n mod 2) = 0 then print_string "pair : non premier"
	else
	(
		print_int (n-1);
		let s = decalage (n-1) in
		print_int s;
		for i = 1 to k do
			let a = (Random.int (n-1))+1
			and temp = ref s in
			let mo = ref((puiss a !temp) mod n) in
			while !temp <> (n-1) && !mo <> 1 && !mo <> (n-1) do
				mo := (puiss !mo 2) mod n;
				temp := !temp * 2
			done;
			if !mo <> (n-1) && (!temp mod 2) = 0 then 
				print_string "pseudo ";
		done;
		print_string "composé"
	)
;;

voilà merci de m'avoir aidé.

Jonathan.