fact: Definition total_time_of_N_prod_poly_cached {size : has_size (N * N)} {_ : factors_through_prod size} {p : reified (fun x:Z => factor_through_prod size (Z.to_N x))} (cached_table : list Q) : has_total_time (N * N) := fun min max => let deg_series := Nat.max 5 (Z.to_nat (degree p)) in let p' := poly_mul p (poly_mul [(1%Q, 1%Z)] (compose_poly (taylor_series_ln1px deg_series) [(1%Q, (-1)%Z)])) in let '(p_int, ln_coef) := integrate_poly p' in let f_int := if Qeq_bool ln_coef 0 then fun x => eval_poly_cfrac p_int x else fun x => eval_poly_cfrac p_int x + ln_coef * Qln_cfrac x in let minv := (fst min * snd min)%N in let maxv := (fst max * snd max)%N in if (maxv - minv <=? cutoff)%N then @total_time_of_N_prod_exact size min max else if (minv <=? cutoff)%N then total_time_of_cached_table cached_table minv + adjust_time (f_int maxv - f_int cutoff) else adjust_time (f_int maxv - f_int minv).
imports: Coq.Strings.String Coq.Structures.Orders Coq.micromega.Lia Coq.Bool.Bool Coq.Sorting.Mergesort Coq.QArith.QArith Coq.QArith.Qround Coq.QArith.Qabs Coq.QArith.Qminmax Coq.NArith.NArith Coq.ZArith.ZArith Coq.Arith.Arith Coq.Lists.List PerformanceExperiments.LetIn