Debian Codegraph @

reals/fast/CRsum.v

raw
1 (*
2 Copyright © 2008 Russell O’Connor
3
4 Permission is hereby granted, free of charge, to any person obtaining a copy of
5 this proof and associated documentation files (the "Proof"), to deal in
6 the Proof without restriction, including without limitation the rights to
7 use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
8 the Proof, and to permit persons to whom the Proof is furnished to do so,
9 subject to the following conditions:
10
11 The above copyright notice and this permission notice shall be included in all
12 copies or substantial portions of the Proof.
13
14 THE PROOF IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
16 FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR
17 COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
18 IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
19 CONNECTION WITH THE PROOF OR THE USE OR OTHER DEALINGS IN THE PROOF.
20 *)
21 From Coq Require Import ZArith.
22 Require Import CoRN.metric2.Metric.
23 Require Import CoRN.metric2.UniformContinuity.
24 Require Import CoRN.model.totalorder.QposMinMax.
25 Require Import CoRN.reals.fast.CRArith.
26 Require Import CoRN.stdlib_omissions.List.
27 Require Import CoRN.model.metric2.Qmetric.
28
29 Local Open Scope Q_scope.
30
31 (* Equi-distribute the error e on all terms, which is on average
32 faster than dividing e by 2 for each term. *)
33 Definition CRsum_list_raw (l:list CR) (e:QposInf) : Q :=
34 fold_left Qplus
35 match l with
36 | nil => nil
37 | cons h t =>
38 let e' := QposInf_mult (Qpos2QposInf (1#(P_of_succ_nat (length t))))%Qpos e in
39 (map (fun x => approximate x e') l)
40 end
41 0.
42
43 Lemma CRsum_list_prf : forall l,
44 is_RegularFunction Qball (CRsum_list_raw l).
45 Proof.
46 intros [|a t] e1 e2.
47 apply ball_refl. apply (Qpos_nonneg (e1 + e2)).
48 unfold CRsum_list_raw.
49 simpl.
50 set (p:=P_of_succ_nat (@length (RegularFunction Qball) t)).
51 set (e1':=((1 # p) * e1)%Qpos).
52 set (e2':=((1 # p) * e2)%Qpos).
53 simpl in e1'. fold e1'.
54 simpl in e2'. fold e2'.
55 assert (Qball (proj1_sig e1' + proj1_sig e2')
56 (0 + @approximate Q Qball a e1') (0 + @approximate Q Qball a e2')) as H.
57 { rewrite Qplus_0_l, Qplus_0_l.
58 apply (regFun_prf a). }
59 assert (forall e:Qpos,
60 proj1_sig ((1 # p) * e)%Qpos * inject_Z (Z.of_nat (length t)) +
61 proj1_sig ((1 # p) * e)%Qpos <= proj1_sig e) as X.
62 { intros e.
63 simpl.
64 setoid_replace ((1 # p) * proj1_sig e * (Z.of_nat (length t) # 1) + (1 # p) * proj1_sig e)%Q
65 with ((1#p)*((Z.of_nat (length t) #1) + (1#1))* proj1_sig e)%Q
66 by (unfold canonical_names.equiv, stdlib_rationals.Q_eq; simpl; ring).
67 rewrite <- (Qmult_1_l (proj1_sig e)) at 2.
68 apply Qmult_le_r. apply Qpos_ispos.
69 unfold Qmult, Qplus, Qle, Qnum, Qden.
70 rewrite Z.mul_1_r, Z.mul_1_r, Z.mul_1_r.
71 rewrite Z.mul_1_l, Z.mul_1_l, Pos.mul_1_r.
72 unfold p. rewrite Z.P_of_succ_nat_Zplus.
73 apply Z.le_refl. }
74 generalize (X e1) (X e2).
75 simpl ((1 # p) * e1)%Qpos. simpl ((1 # p) * e2)%Qpos.
76 fold e1' e2'.
77 unfold e1' at 1 3.
78 unfold e2' at 1 3.
79 generalize (Qpos_mult
80 (@exist Q (Qlt {| Qnum := Z0; Qden := xH |})
81 {| Qnum := Zpos xH; Qden := p |} (@eq_refl comparison Lt)) e1)
82 (Qpos_mult
83 (@exist Q (Qlt {| Qnum := Z0; Qden := xH |})
84 {| Qnum := Zpos xH; Qden := p |} (@eq_refl comparison Lt)) e2)
85 e1' e2'
86 (0 + @approximate Q Qball a e1') (0 + @approximate Q Qball a e2') H.
87 clear - t.
88 induction t; intros e1'' e2'' e1' e2' x y Hxy H1 H2.
89 - simpl in *.
90 ring_simplify in H1.
91 ring_simplify in H2.
92 apply (@ball_weak_le Q_as_MetricSpace (proj1_sig e1' + proj1_sig e2')); auto.
93 apply Qplus_le_compat; auto.
94 - simpl in *.
95 change (Zpos (P_of_succ_nat (length t))) with (Z_of_nat (1+(length t))) in H1.
96 change (Zpos (P_of_succ_nat (length t))) with (Z_of_nat (1+(length t))) in H2.
97 rewrite -> inj_plus in *.
98 rewrite -> Q.Zplus_Qplus in *.
99 ring_simplify in H1.
100 ring_simplify in H2.
101 apply (IHt e1'' e2'' (e1'' + e1')%Qpos (e2'' + e2')%Qpos);
102 try (autorewrite with QposElim; ring_simplify; assumption).
103 unfold Qball.
104 autorewrite with QposElim.
105 unfold QAbsSmall.
106 setoid_replace (x + approximate a e1'' - (y + approximate a e2''))%Q
107 with ((x - y) + (approximate a e1'' - approximate a e2''))
108 by (unfold canonical_names.equiv, stdlib_rationals.Q_eq; simpl; ring).
109 simpl.
110 setoid_replace (proj1_sig e1'' + proj1_sig e1' + (proj1_sig e2'' + proj1_sig e2'))%Q
111 with ((proj1_sig e1' + proj1_sig e2') + (proj1_sig e1'' + proj1_sig e2''))%Q
112 by (unfold canonical_names.equiv, stdlib_rationals.Q_eq; simpl; ring).
113 apply QAbsSmall_plus.
114 auto.
115 apply (regFun_prf a).
116 simpl. rewrite Qplus_assoc. assumption.
117 simpl. rewrite Qplus_assoc. assumption.
118 Qed.
119
120 Definition CRsum_list (l:list CR) : CR := Build_RegularFunction (CRsum_list_prf l).
121
122 Lemma CRsum_correct : forall l, (CRsum_list l == fold_right (fun x y => x + y) 0 l)%CR.
123 Proof.
124 induction l.
125 apply regFunEq_equiv, regFunEq_e; intros e.
126 apply ball_refl. apply (Qpos_nonneg (e+e)).
127 simpl (fold_right (fun x y : CR => (x + y)%CR) 0%CR (a :: l)).
128 rewrite <- IHl.
129 clear -l.
130 apply regFunEq_equiv, regFunEq_e; intros e.
131 simpl.
132 unfold Cap_raw.
133 simpl.
134 unfold CRsum_list_raw.
135 simpl.
136 destruct l; simpl.
137 rewrite Qplus_0_l, Qplus_0_r.
138 setoid_replace (proj1_sig e+proj1_sig e)
139 with (proj1_sig ((1 # 1) *e + (1 # 2) * e + (1 # 2) * e))%Qpos
140 by (unfold canonical_names.equiv, stdlib_rationals.Q_eq; simpl; ring).
141 change (Qball (proj1_sig ((1 # 1) * e + (1 # 2) * e + (1 # 2) * e)%Qpos)
142 (approximate a ((1 # 1) * e)%Qpos)
143 (approximate a ((1 # 2) * e)%Qpos)).
144 apply ball_weak. apply Qpos_nonneg.
145 apply regFun_prf.
146 set (n:= (@length (RegularFunction Qball) l)).
147 cut (forall (z1:Q) (e3 e5 e1 e2 e4 e6:Qpos) (z2 z3:Q),
148 ball (proj1_sig e5) z1 z2 ->
149 (z3 == approximate a e3 + z1)
150 -> (proj1_sig e1*(Z.of_nat n#1) + proj1_sig e2*(Z.of_nat n#1) +proj1_sig e3 + proj1_sig e4 + proj1_sig e5 <= proj1_sig e6)
151 -> Qball (proj1_sig e6) (fold_left Qplus
152 (map (fun x : RegularFunction Qball => approximate x e1) l) z3) (approximate a e4 +
153 fold_left Qplus (map (fun x : RegularFunction Qball => approximate x e2) l) z2)).
154 { intros H.
155 apply (H (approximate m ((1 # Pos.succ (P_of_succ_nat n)) * e)%Qpos)
156 ((1 # Pos.succ (P_of_succ_nat n)) * e)%Qpos
157 ((1 # Pos.succ (P_of_succ_nat n)) * e +
158 (1 # P_of_succ_nat n) * ((1 # 2) * e))%Qpos
159 _ _ _ (e+e)%Qpos).
160 2: rewrite Qplus_0_l; reflexivity.
161 pose proof (Qplus_0_l (approximate m ((1 # Pos.of_succ_nat n) * ((1 # 2) * e))%Qpos)).
162 apply Qball_0 in H0. rewrite H0.
163 apply regFun_prf.
164 simpl.
165 apply (Qle_trans _
166 ((1 # Pos.succ (P_of_succ_nat n)) * ((2#1)+(Z.of_nat n#1)) *proj1_sig e +
167 ((1 # P_of_succ_nat n) * ((1#1) + (Z.of_nat n#1)) * ((1 # 2) * proj1_sig e) + (1 # 2) * proj1_sig e))).
168 ring_simplify; apply Qle_refl.
169 setoid_replace ((1 # Pos.succ (Pos.of_succ_nat n)) * ((2#1) + (Z.of_nat n#1)))
170 with (1#1)%Q.
171 setoid_replace ((1 # Pos.of_succ_nat n) * ((1#1) + (Z.of_nat n#1))) with (1#1)%Q.
172 field_simplify.
173 setoid_replace (8 # 4) with (2#1) by reflexivity. apply Qle_refl.
174 unfold Qmult, inject_Z, Qplus, Qeq, Qnum, Qden.
175 ring_simplify. rewrite Pos.mul_1_r.
176 unfold canonical_names.equiv, stdlib_rationals.Q_eq.
177 rewrite Z.mul_1_l, Z.mul_1_l, Z.mul_1_r, Z.add_comm.
178 rewrite <- Z.P_of_succ_nat_Zplus.
179 unfold Qeq; simpl. rewrite Pos.mul_1_r. reflexivity.
180 unfold canonical_names.equiv, stdlib_rationals.Q_eq.
181 unfold Qmult, inject_Z, Qplus, Qeq, Qnum, Qden.
182 ring_simplify. rewrite Pos.mul_1_r.
183 rewrite <- SuccNat2Pos.inj_succ.
184 rewrite Z.P_of_succ_nat_Zplus.
185 replace (S n) with (1+n)%nat by reflexivity.
186 rewrite Nat2Z.inj_add.
187 rewrite (Z.add_comm 1). rewrite <- Z.add_assoc. reflexivity. }
188 unfold n.
189 clear n.
190 induction l; intros z1 e3 e5 e1 e2 e4 e6 z2 z3 Hz H0 H.
191 simpl in *.
192 ring_simplify in H.
193 ring_simplify.
194 apply Qball_0 in H0.
195 rewrite -> H0.
196 unfold Qball.
197 unfold QAbsSmall.
198 setoid_replace (approximate a e3 + z1 - (approximate a e4 + z2))
199 with ((approximate a e3 - approximate a e4) + (z1 - z2))
200 by (unfold canonical_names.equiv, stdlib_rationals.Q_eq; simpl; ring).
201 pose proof (@ball_weak_le Q_as_MetricSpace
202 (proj1_sig e3 + proj1_sig e4 + proj1_sig e5)
203 (proj1_sig e6)
204 (approximate a e3 - approximate a e4 + (z1 - z2)) 0).
205 simpl in H1.
206 unfold Qball, QAbsSmall, Qminus in H1. rewrite Qplus_0_r in H1.
207 apply H1. exact H.
208 apply QAbsSmall_plus; auto.
209 apply (regFun_prf a).
210 simpl.
211 apply (IHl (z1 + approximate a0 e1) e3 (e5 + (e1 + e2))%Qpos).
212 simpl.
213 unfold Qball.
214 unfold QAbsSmall.
215 setoid_replace (z1 + approximate a0 e1 - (z2 + approximate a0 e2))
216 with ((z1 - z2) + (approximate a0 e1 - approximate a0 e2))
217 by (unfold canonical_names.equiv, stdlib_rationals.Q_eq; simpl; ring).
218 apply QAbsSmall_plus.
219 auto.
220 apply (regFun_prf a0).
221 rewrite -> H0.
222 simpl; ring.
223 simpl.
224 simpl in H.
225 set (n:= (@length (RegularFunction Qball) l)) in *.
226 change (Zpos (P_of_succ_nat n)) with (Z_of_nat (1+n)) in H.
227 rewrite inj_plus in H.
228 refine (Qle_trans _ _ _ _ H). clear H.
229 setoid_replace (Z.of_nat 1 + Z.of_nat n # 1)%Q
230 with ((1#1) + (Z.of_nat n # 1)).
231 ring_simplify. apply Qle_refl.
232 unfold canonical_names.equiv, stdlib_rationals.Q_eq.
233 unfold Qeq, Qplus, Qnum, Qden.
234 rewrite Z.mul_1_r, Z.mul_1_r, Z.mul_1_r, Z.mul_1_r.
235 reflexivity.
236 Qed.