Discussion :

[elishac]

Bonjour, pouvez-vous me dire comment améliorer/corriger/simplifier/, etc., les programmes suivants (écrits en Caml light):

1) Suppression de tous les zéros à la fin d'un vecteur (si le vecteur ne contient que des zéros, en laisser quand même un).

2) Egaliser la longueur de 2 vecteurs en complétant par des zéros à la fin.


1)

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
let kill_zeros v =
	let n=vect_length v and p=ref 0 in
	while !p<n & v.(n- !p-1) =0  do p:= !p+1 done;
	if !p=n then [|0|] else
		begin
			let res=make_vect (n- !p) 0 in
				for k=0 to (n- !p-1) do
					res.(k) <- v.(k)
				done;
			res
		end
;;

2)

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
let mmlong u v=
(*complete u ou v par des zéros à droite pour qu'ils aient la même longueur, et renvoie (u,v) *)
	let aux u1 u2 p q= (* p=vect_length u1, q=vect_length u2, p<q *)
		let res=make_vect q 0 in
			for k=0 to p do
				res.(k)<-u1.(k)
			done;
		(res,u2)
	in
	let m=vect_length u and n=vect_length v in
	if m<n then aux u v m n
	else if m>n then aux v u n m
	else (*m=n*) (u,v)
;;

[gorgonite]

1) ton code ne marchera pas si tu oublies les déréférencements

tu aurais du utiliser cette fonction

Code :

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

1
2
3
(* sub_vect : 'a vect -> int -> int -> 'a vect *)
 
sub_vect v 0 (n-(!p)+1)

2) utilises concat_vect

Code :

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

1
2
3
4
5
6
7
8
9
10
 (* concat_vect : 'a vect -> 'a vect -> 'a vect *)
let mmlong u v =
  let n = vect_length u in 
  let m = vect_length v in
  if n=m 
  then (u,v)
  else
    if n<m then (concat_vect u (make_vect (m-n) 0),v) 
             else (u,concat_vect v (make_vect (n-m) 0))
;;

au passage, n'hésites pas à lire ceci : http://caml.inria.fr/pub/distrib/cam...cl74refman.pdf

[SpiceGuid]

C'est pour faire une multiplication Karatsuba ?

[elishac]

1) Je n'ai pas compris :
Qu'est-ce qu'un déférencement ?
Pourquoi utiliser la fonction sub_vect ?
Qu'est-ce qui ne marche pas ?

2) ok, je ne connaissais pas cette fonction, il est vrai que c'est plus élégant.


Non ce n'est pas pour faire une multiplication rapide, c'est pour faire des multiplications (et opérations en général) sur des nombres dits p-adiques (en gros, ce sont un peu des entiers, voir par exemple wikipedia pour plus de détails).

Par ailleurs, que pensez-vous des deux "programmes" suivants :

un type produit pour les adique (notamment, pensez-vous le choix d'un vecteur approprié pour sauvegarder un nombre p-adique, ou une liste serait-elle mieux ?) :

Code :

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

type adique={mantisse : int vect ; base : int};;

la fonction d'affichage, qui va afficher un nombre sous la forme (312)_5, où 5 est la base.

Code :

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

1
2
3
4
5
6
7
8
 
let affichage a=
 let rec concat_elements v n acc=
  if acc=n then "" else (string_of_int v.(acc)) ^ (concat_elements v n (acc+1))
 in
 let affiche_mantisse vect = concat_elements vect (vect_length vect) 0
 in
 "(" ^ (affiche_mantisse a.mantisse) ^ ")_" ^ (string_of_int a.base) ;;

[SpiceGuid]

Le déréferencement c'est l'opérateur ! qui le réalise:

Code :

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

1
2
# (!);;
- : 'a ref -> 'a = <fun>

Pour l'addition on veut d'abord traiter les digits de poids faible.
Pour la comparaison on veut d'abord traiter les digits de poids fort.
Par conséquent un vecteur est plus approprié qu'une liste parce que moins orienté.

Je vois bien l'utilité d'enlever les zéros non significatifs, par contre j'avoue ne pas voir l'intérêt d'en ajouter, ni même d'avoir deux vecteurs de même longueurs.
Tu dois pouvoir appliquer Karatsuba si la multiplication est distributive dans Qp.

[gasche]

Si tu as besoin de redimensionner tes tableaux sans cesse, c'est sans doute qu'il y a un problème. Peut-être qu'une liste est alors plus adaptée. As-tu vraiment besoin de l'accès à une position arbitraire ?