| 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. |