En ocaml peux tu m'écrire une fonction d'évaluation rapide de polynome basée sur l'algo…
- User
En ocaml peux tu m'écrire une fonction d'évaluation rapide de polynome basée sur l'algo fft (Fourier) avec, pour argument, une liste de longueur une puissnace de 2 representant le polynome à évaluer sous sa forme de Horner sans employer de variable de type reference.
- Assistant
Voici une fonction en OCaml qui utilise l'algorithme FFT (Fast Fourier Transform) pour évaluer rapidement un polynôme représenté sous sa forme de Horner :
let eval_poly_fft coeffs x = let n = List.length coeffs in let rec fft coeffs = match coeffs with | [] -> [] | [_] -> coeffs | _ -> let even, odd = List.partition (fun (i, _) -> i mod 2 = 0) (List.mapi (fun i c -> (i, c)) coeffs) in let even_coeffs, odd_coeffs = List.map snd even, List.map snd odd in let even_eval = fft even_coeffs in let odd_eval = fft odd_coeffs in let size = n / 2 in let twiddles = List.init size (fun k -> Complex.polar 1. (-2. *. 3.14159265359 *. float_of_int k /. float_of_int n)) in let combine tw (a, b) = a +. tw *. b, a -. tw *. b in let folded = List.fold_right2 combine twiddles even_eval odd_eval in let even_res = List.map (fun (i, x) -> (i, x /. 2.)) (List.combine (List.init size (fun i -> i * 2)) (List.map fst folded)) in let odd_res = List.map (fun (i, x) -> (i, x /. 2.)) (List.combine (List.init size (fun i -> i * 2 + 1)) (List.map snd folded)) in even_res @ odd_res in let coef_eval = fft coeffs in let rec horner_eval x i = match coef_eval with | [] -> 0. | (j, c) :: rest -> if j = i then c +. x *. horner_eval x (i + 1) else horner_eval x (i + 1) in horner_eval x 0La fonction
eval_poly_fftprend en argument une liste de coefficients représentant le polynôme à évaluer sous sa forme de Horner, ainsi que la valeurxà laquelle on souhaite évaluer le polynôme. La liste de coefficients doit être de longueur une puissance de 2.La fonction utilise la fonction récursive
fftpour calculer la transformée de Fourier du polynôme. La transformée de Fourier est calculée récursivement en divisant la liste de coefficients en sous-listes de taille pair et impaire, puis en combinant les résultats en utilisant des pulsations complexes. La fonctionhorner_evalest utilisée pour évaluer le polynôme en utilisant la liste des coefficients transformés.Notez que la précision des calculs est limitée par la précision des nombres flottants en OCaml. Si vous souhaitez obtenir une précision plus élevée, vous pouvez utiliser des bibliothèques pour les calculs en nombres flottants de précision arbitraire, comme
mpfrpar exemple. - User
Hier tu as généré un programme pour évaluer un polynome sur les racines de l'unite en utilisant fft mais j'ai effacé la dernier instruction .
- Assistant
Bien sûr, voici le programme complet avec la dernière instruction manquante :
let eval_poly_fft coeffs x = let n = List.length coeffs in let rec fft coeffs = match coeffs with | [] -> [] | [_] -> coeffs | _ -> let even, odd = List.partition (fun (i, _) -> i mod 2 = 0) (List.mapi (fun i c -> (i, c)) coeffs) in let even_coeffs, odd_coeffs = List.map snd even, List.map snd odd in let even_eval = fft even_coeffs in let odd_eval = fft odd_coeffs in let size = n / 2 in let twiddles = List.init size (fun k -> Complex.polar 1. (-2. *. 3.14159265359 *. float_of_int k /. float_of_int n)) in let combine tw (a, b) = a +. tw *. b, a -. tw *. b in let folded = List.fold_right2 combine twiddles even_eval odd_eval in let even_res = List.map (fun (i, x) -> (i, x /. 2.)) (List.combine (List.init size (fun i -> i * 2)) (List.map fst folded)) in let odd_res = List.map (fun (i, x) -> (i, x /. 2.)) (List.combine (List.init size (fun i -> i * 2 + 1)) (List.map snd folded)) in even_res @ odd_res in let coef_eval = fft coeffs in let rec horner_eval x i = match coef_eval with | [] -> 0. | (j, c) :: rest -> if j = i then c +. x *. horner_eval x (i + 1) else horner_eval x (i + 1) in horner_eval x 0 let coeffs = [1.; 2.; 3.; 4.] (* coeffs du polynome *) let n = List.length coeffs let roots = List.init n (fun k -> Complex.polar 1. (2. *. 3.14159265359 *. float_of_int k /. float_of_int n)) let evals = List.map (fun r -> eval_poly_fft coeffs r) roots (* Affichage des évaluations sur les racines de l'unité *) List.iteri (fun i ev -> Printf.printf "P(%d) = %f\n" i ev) evalsIci, j'ai ajouté la dernière instruction manquante qui utilise la fonction
List.iteripour afficher les évaluations du polynôme sur les racines de l'unité. La variableevalscontient la liste des évaluations et chaque évaluation est affichée avec son indice correspondant.