| 1 |
From Coq Require Import Qabs. |
| 2 |
Require Import CoRN.util.Qdlog |
| 3 |
CoRN.algebra.RSetoid |
| 4 |
CoRN.model.totalorder.QposMinMax |
| 5 |
CoRN.model.metric2.Qmetric |
| 6 |
CoRN.model.reals.CRreal |
| 7 |
CoRN.metric2.Metric |
| 8 |
CoRN.metric2.UniformContinuity |
| 9 |
CoRN.reals.fast.CRAlternatingSum |
| 10 |
CoRN.reals.fast.CRstreams |
| 11 |
CoRN.reals.faster.ApproximateRationals |
| 12 |
CoRN.reals.faster.ARArith. |
| 13 |
|
| 14 |
|
| 15 |
(** |
| 16 |
The goal of this section is to compute the infinite alternating sum. Since |
| 17 |
we do not have a precise division operation, we want to postpone divisions as |
| 18 |
long as possible. Hence we parametrize our infinite sum by a stream [sN] |
| 19 |
of numerators and a stream [sD] of denominators. |
| 20 |
|
| 21 |
To compute an infinite series at precision epsilon, the finite number n of |
| 22 |
terms to sum can be computed exactly, because sN n / sD n < epsilon/2 is |
| 23 |
equivalent to sN n < (sD n) * epsilon/2, which does not involve the approximate |
| 24 |
division. In the other epsilon/2, we can approximate the n divisions at |
| 25 |
precision 2^k such as n*2^k < epsilon/2. |
| 26 |
*) |
| 27 |
|
| 28 |
Section RationalStreamSum. |
| 29 |
|
| 30 |
Context `{AppRationals AQ}. |
| 31 |
|
| 32 |
(* For exponential, f p n d := (n*a, d*p). |
| 33 |
We might need to generalize positive to a more complicated |
| 34 |
state type later. *) |
| 35 |
Variable f : positive*(AQ*AQ) -> AQ*AQ. |
| 36 |
Definition fS x : positive*(AQ*AQ) := (Pos.succ (fst x), f x). |
| 37 |
Definition fSsum (k:Z) (x : positive*(AQ*AQ)*AQ) : positive*(AQ*AQ)*AQ |
| 38 |
:= let (y,s) := x in |
| 39 |
let (a,b) := fS y in |
| 40 |
(a, b, s + app_div (fst b) (snd b) k). |
| 41 |
|
| 42 |
Hypothesis denomPos : forall x, 0 < snd (snd x) -> 0 < snd (f x). |
| 43 |
|
| 44 |
Lemma denomPos_iter : forall p x, |
| 45 |
0 < snd (snd x) -> |
| 46 |
0 < snd (snd (CRstreams.iterate _ fS p x)). |
| 47 |
Proof. |
| 48 |
apply (Pos.peano_ind (fun p => forall x, |
| 49 |
0 < snd (snd x) -> |
| 50 |
0 < snd (snd (CRstreams.iterate _ fS p x)))). |
| 51 |
- intros. simpl. apply denomPos, H5. |
| 52 |
- intros. rewrite iterate_succ, iterate_shift. |
| 53 |
apply H5. simpl. |
| 54 |
apply denomPos, H6. |
| 55 |
Qed. |
| 56 |
|
| 57 |
(* Find first index where num/denom <= e. *) |
| 58 |
Definition IsStopIndex x (e : AQ) (candidate : positive) : Prop |
| 59 |
:= let (_,v) := CRstreams.iterate _ fS candidate (xH,x) in |
| 60 |
le (abs (fst v)) (snd v * e). |
| 61 |
Definition StopIndex x (e : AQ) (candidate : positive) : positive |
| 62 |
:= Pos.pred (fst (iterate_stop |
| 63 |
_ fS (fun y : positive*(AQ*AQ) |
| 64 |
=> bool_decide_rel le (abs (fst (snd y))) ((snd (snd y))*e)) |
| 65 |
candidate (xH, x))). |
| 66 |
|
| 67 |
Lemma fS_fst : forall (p:positive) x, |
| 68 |
fst (CRstreams.iterate (positive and AQ and AQ) fS p (1%positive, x)) |
| 69 |
≡ Pos.succ p. |
| 70 |
Proof. |
| 71 |
apply (Pos.peano_ind (fun p => forall (x : AQ and AQ), |
| 72 |
fst (CRstreams.iterate (positive and AQ and AQ) fS p (1%positive, x)) ≡ Pos.succ p)). |
| 73 |
- reflexivity. |
| 74 |
- intros. rewrite iterate_succ. simpl. |
| 75 |
apply f_equal, H5. |
| 76 |
Qed. |
| 77 |
|
| 78 |
Lemma StopIndex_correct : forall x (e:AQ) (p r : positive), |
| 79 |
IsStopIndex x e p |
| 80 |
-> (forall q:positive, Pos.lt q p -> ~IsStopIndex x e q) |
| 81 |
-> Pos.le p r |
| 82 |
-> StopIndex x e r ≡ p. |
| 83 |
Proof. |
| 84 |
unfold IsStopIndex. intros. |
| 85 |
unfold StopIndex. |
| 86 |
destruct (iterate_stop_correct |
| 87 |
_ fS (fun y : positive and AQ and AQ => |
| 88 |
bool_decide_rel |
| 89 |
le (abs (fst (snd y))) (snd (snd y) * e0)) |
| 90 |
r (xH,x)) as [s [req [H8 H9]]]. |
| 91 |
rewrite req, fS_fst, Pos.pred_succ. clear req. |
| 92 |
destruct H9. |
| 93 |
- subst r. apply Pos.le_lteq in H7. |
| 94 |
destruct H7. 2: symmetry; exact H7. |
| 95 |
exfalso. specialize (H8 p H7). |
| 96 |
apply bool_decide_rel_false in H8. |
| 97 |
contradict H8. |
| 98 |
destruct (CRstreams.iterate _ fS p (1%positive, x)). |
| 99 |
exact H5. |
| 100 |
- destruct H9. |
| 101 |
apply bool_decide_rel_true in H10. |
| 102 |
clear H7 H9 r. |
| 103 |
destruct (Pos.lt_total s p). |
| 104 |
+ exfalso. specialize (H6 s H7). |
| 105 |
contradict H6. |
| 106 |
destruct (CRstreams.iterate _ fS s (1%positive, x)). |
| 107 |
exact H10. |
| 108 |
+ destruct H7. exact H7. exfalso. |
| 109 |
specialize (H8 p H7). |
| 110 |
apply bool_decide_rel_false in H8. |
| 111 |
contradict H8. |
| 112 |
destruct (CRstreams.iterate _ fS p (1%positive, x)). |
| 113 |
exact H5. |
| 114 |
Qed. |
| 115 |
|
| 116 |
Lemma StopIndex_stop_fuel : forall x (e:AQ) (candidate : positive), |
| 117 |
(forall p:positive, Pos.lt p candidate -> ~IsStopIndex x e p) |
| 118 |
-> StopIndex x e candidate ≡ candidate. |
| 119 |
Proof. |
| 120 |
intros. unfold StopIndex. |
| 121 |
destruct (iterate_stop_correct |
| 122 |
_ fS (fun y : positive and AQ and AQ => |
| 123 |
bool_decide_rel |
| 124 |
le (abs (fst (snd y))) (snd (snd y) * e0)) |
| 125 |
candidate (xH,x)) as [r [req [H6 H7]]]. |
| 126 |
rewrite req, fS_fst, Pos.pred_succ. clear req. |
| 127 |
destruct H7. symmetry. exact H7. |
| 128 |
destruct H7. exfalso. clear H6. |
| 129 |
specialize (H5 r H7). |
| 130 |
apply bool_decide_rel_true in H8. |
| 131 |
contradict H5. |
| 132 |
unfold IsStopIndex. |
| 133 |
destruct (CRstreams.iterate _ fS r (1%positive, x)). |
| 134 |
exact H8. |
| 135 |
Qed. |
| 136 |
|
| 137 |
(* Approximate the infinite series at precision e. |
| 138 |
The precision i:Z in fSum satisfies n*2^i <= e/2. *) |
| 139 |
Definition app_inverse_below (q : Qpos) : AQ |
| 140 |
:= AppInverse0 ((3#4)*proj1_sig q) ((1#4)*q)%Qpos. |
| 141 |
|
| 142 |
Lemma app_inverse_below_pos : forall q:Qpos, 0 < app_inverse_below q. |
| 143 |
Proof. |
| 144 |
intros. unfold app_inverse_below. |
| 145 |
destruct aq_dense_embedding. |
| 146 |
specialize (dense_inverse ((3 # 4) * ` q)%Q ((1#4)*q)%Qpos). |
| 147 |
apply AbsSmall_Qabs, Qabs_Qle_condition in dense_inverse. |
| 148 |
destruct dense_inverse as [H5 _]. |
| 149 |
simpl in H5. |
| 150 |
apply (Qplus_le_r _ _ ((3 # 4) * ` q)) in H5. |
| 151 |
ring_simplify in H5. |
| 152 |
destruct aq_strict_order_embed. |
| 153 |
apply strict_order_embedding_reflecting. |
| 154 |
refine (Qlt_le_trans _ ((8 # 16) * ` q) _ _ H5). |
| 155 |
rewrite rings.preserves_0. |
| 156 |
apply (Qpos_ispos ((8#16)*q)). |
| 157 |
Qed. |
| 158 |
|
| 159 |
Lemma app_inverse_below_correct : forall q:Qpos, |
| 160 |
AQtoQ (app_inverse_below q) <= proj1_sig q. |
| 161 |
Proof. |
| 162 |
intros. unfold app_inverse_below. |
| 163 |
destruct aq_dense_embedding. |
| 164 |
specialize (dense_inverse ((3 # 4) * ` q)%Q ((1#4)*q)%Qpos). |
| 165 |
apply AbsSmall_Qabs, Qabs_Qle_condition in dense_inverse. |
| 166 |
destruct dense_inverse as [_ H5]. |
| 167 |
simpl in H5. |
| 168 |
apply (Qplus_le_r _ _ ((3 # 4) * ` q)) in H5. |
| 169 |
ring_simplify in H5. exact H5. |
| 170 |
Qed. |
| 171 |
|
| 172 |
(* cvmod : AQ->positive would not improve this definition, because an |
| 173 |
AQtoQ would be almost inevitable to produce a boxed positive. |
| 174 |
Besides, Q will allow an easier interaction with fast reals streams. *) |
| 175 |
Definition AltSeries_raw (x : AQ*AQ) (cvmod : Qpos -> positive) (e:QposInf) : AQ |
| 176 |
:= match e with |
| 177 |
| Qpos2QposInf d |
| 178 |
=> let ae := app_inverse_below (d*(1#2)) in |
| 179 |
let n := StopIndex x ae (cvmod (d * (1#2))%Qpos) in |
| 180 |
snd (CRstreams.iterate _ (fSsum (Qdlog2 (proj1_sig d * (1#2*n)))) n (xH,x,0)) |
| 181 |
| QposInfinity => 0 |
| 182 |
end. |
| 183 |
|
| 184 |
(* To prove the correctness of the limit, convert the stream f into |
| 185 |
a stream g of exact rationals. g could be defined as the zip of |
| 186 |
f with the exact divisions, but it's more flexible to take g from |
| 187 |
outside, so that in addition we prove the equality of series. *) |
| 188 |
Variable X : Type. |
| 189 |
Variable g : X*Q -> X*Q. |
| 190 |
Variable fInit : AQ*AQ. |
| 191 |
Variable gInit : X*Q. |
| 192 |
|
| 193 |
Hypothesis g_pth : forall p:positive, |
| 194 |
Str_pth _ g p gInit |
| 195 |
== let (y,r) := CRstreams.iterate _ fS p (xH, fInit) in |
| 196 |
AQtoQ (fst r) / AQtoQ (snd r). |
| 197 |
|
| 198 |
Lemma abs_div_aqtoq_shift : forall (q r s : AQ), |
| 199 |
0 < r -> |
| 200 |
(Qabs (AQtoQ q / AQtoQ r) <= AQtoQ s |
| 201 |
<-> le (abs q) (r * s)). |
| 202 |
Proof. |
| 203 |
assert (forall q:AQ, Qabs (AQtoQ q) == AQtoQ (abs q)) as preserves_abs. |
| 204 |
{ intros. rewrite abs.preserves_abs. reflexivity. } |
| 205 |
assert (forall q r:AQ, AQtoQ (q*r) == AQtoQ q*AQtoQ r) as preserves_mult. |
| 206 |
{ intros. rewrite rings.preserves_mult. reflexivity. } |
| 207 |
intros. |
| 208 |
assert (0 < AQtoQ r). |
| 209 |
{ rewrite <- rings.preserves_0. |
| 210 |
destruct aq_strict_order_embed. |
| 211 |
apply strict_order_embedding_preserving. exact H5. } |
| 212 |
split. |
| 213 |
- intros. unfold Qdiv in H7. |
| 214 |
rewrite Qabs_Qmult, Q.Qabs_Qinv in H7. |
| 215 |
rewrite (Qabs_pos (AQtoQ r)) in H7. |
| 216 |
rewrite preserves_abs, Qmult_comm in H7. |
| 217 |
apply (Qmult_le_l _ _ (AQtoQ r)) in H7. |
| 218 |
2: exact H6. |
| 219 |
rewrite Qmult_assoc, Qmult_inv_r, Qmult_1_l in H7. |
| 220 |
rewrite <- preserves_mult in H7. |
| 221 |
destruct aq_order_embed, order_embedding_reflecting. |
| 222 |
apply order_reflecting in H7. |
| 223 |
exact H7. |
| 224 |
intro abs. rewrite abs in H6. exact (Qlt_irrefl 0 H6). |
| 225 |
apply Qlt_le_weak, H6. |
| 226 |
- intros. unfold Qdiv. |
| 227 |
rewrite Qabs_Qmult, Q.Qabs_Qinv. |
| 228 |
rewrite (Qabs_pos (AQtoQ r)). |
| 229 |
rewrite preserves_abs. |
| 230 |
rewrite Qmult_comm. |
| 231 |
apply (Qmult_le_l _ _ (AQtoQ r)). |
| 232 |
exact H6. |
| 233 |
rewrite Qmult_assoc, Qmult_inv_r, Qmult_1_l. |
| 234 |
rewrite <- preserves_mult. |
| 235 |
destruct aq_order_embed. |
| 236 |
apply order_embedding_preserving. |
| 237 |
exact H7. |
| 238 |
intro abs. rewrite abs in H6. exact (Qlt_irrefl 0 H6). |
| 239 |
apply Qlt_le_weak, H6. |
| 240 |
Qed. |
| 241 |
|
| 242 |
Lemma fSsum_fst : forall p k, |
| 243 |
fst (CRstreams.iterate _ (fSsum k) p (1%positive, fInit, 0)) |
| 244 |
≡ CRstreams.iterate _ fS p (xH,fInit). |
| 245 |
Proof. |
| 246 |
apply (Pos.peano_ind (fun p => forall k, |
| 247 |
fst (CRstreams.iterate _ (fSsum k) p (1%positive, fInit, 0)) |
| 248 |
≡ CRstreams.iterate _ fS p (xH,fInit))). |
| 249 |
- reflexivity. |
| 250 |
- intros. rewrite iterate_succ, iterate_succ. |
| 251 |
rewrite <- (H5 k). unfold fSsum at 1. |
| 252 |
destruct (CRstreams.iterate ((positive and AQ and AQ) and AQ) |
| 253 |
(fSsum k) p (1%positive, fInit, 0)). |
| 254 |
reflexivity. |
| 255 |
Qed. |
| 256 |
|
| 257 |
(* Sum p terms, the error between each is below e. *) |
| 258 |
Lemma div_approx_error : ∀ (p:positive) (e:Qpos), |
| 259 |
Qball (` e * inject_Z (Zpos p)) |
| 260 |
(AQtoQ (snd (CRstreams.iterate |
| 261 |
_ (fSsum (Qdlog2 (` e))) p (1%positive, fInit, 0)))) |
| 262 |
(snd (CRstreams.iterate |
| 263 |
_ (fun y : X*Q*Q => |
| 264 |
let (z, r) := g (fst y) in (z, r, Qred (r + snd y))) p |
| 265 |
(gInit, 0))). |
| 266 |
Proof. |
| 267 |
apply (Pos.peano_ind (fun p => forall (e:Qpos), |
| 268 |
Qball (` e * inject_Z (Zpos p)) |
| 269 |
(AQtoQ (snd (CRstreams.iterate |
| 270 |
_ (fSsum (Qdlog2 (` e))) p (1%positive, fInit, 0)))) |
| 271 |
(snd (CRstreams.iterate |
| 272 |
_ (fun y : X*Q*Q => |
| 273 |
let (z, r) := g (fst y) in (z, r, Qred (r + snd y))) p |
| 274 |
(gInit, 0))))). |
| 275 |
- intros. rewrite iterate_one, iterate_one. |
| 276 |
rewrite Qmult_1_r. |
| 277 |
unfold fSsum, fS. |
| 278 |
unfold snd at 1. unfold fst at 2. |
| 279 |
pose proof (g_pth 1). |
| 280 |
unfold Str_pth in H5. simpl in H5. |
| 281 |
unfold snd at 3. |
| 282 |
replace (snd (let (z, r) := g gInit in (z, r, Qred (r + zero)))) |
| 283 |
with (Qred (snd (g gInit) + 0)) |
| 284 |
by (destruct (g gInit); reflexivity). |
| 285 |
rewrite Qred_correct, Qplus_0_r, H5. |
| 286 |
clear H5. |
| 287 |
destruct (f (1%positive, fInit)) as [u v]. |
| 288 |
unfold snd, fst. |
| 289 |
rewrite rings.plus_0_l. |
| 290 |
apply ball_weak_le with (e:= (2 ^ Qdlog2 (` e0))%Q). |
| 291 |
apply Qdlog2_spec, Qpos_ispos. |
| 292 |
apply aq_div. |
| 293 |
- intros. |
| 294 |
rewrite iterate_succ. |
| 295 |
unfold fSsum at 1. |
| 296 |
specialize (H5 e0). |
| 297 |
pose proof (fSsum_fst p (Qdlog2 (` e0))). |
| 298 |
destruct (CRstreams.iterate _ (fSsum (Qdlog2 (` e0))) p (1%positive, fInit, 0)) |
| 299 |
as [u approx_sum]. |
| 300 |
unfold snd in H5 at 1. |
| 301 |
unfold fst in H6. |
| 302 |
change (snd |
| 303 |
(let (a, b) := fS u in (a, b, approx_sum + app_div (fst b) (snd b) (Qdlog2 (` e0))))) |
| 304 |
with (approx_sum + app_div (fst (snd (fS u))) (snd (snd (fS u))) (Qdlog2 (` e0))). |
| 305 |
rewrite iterate_succ, SumStream_fst_red. |
| 306 |
unfold fst at 2. |
| 307 |
rewrite <- iterate_succ. |
| 308 |
pose proof (g_pth (Pos.succ p)) as H7. |
| 309 |
unfold Str_pth in H7. |
| 310 |
destruct (CRstreams.iterate (X and Q) g (Pos.succ p) gInit). |
| 311 |
unfold snd at 4. unfold snd in H7 at 1. |
| 312 |
rewrite Qred_correct, H7. clear H7 q x. |
| 313 |
rewrite iterate_succ. |
| 314 |
rewrite <- H6. clear H6. |
| 315 |
destruct (fS u) as [v w]. |
| 316 |
change (snd (v,w)) with w. |
| 317 |
clear v. |
| 318 |
destruct (CRstreams.iterate _ |
| 319 |
(fun y : (X and Q) and Q => |
| 320 |
let (z, r) := g (fst y) in (z, r, Qred (r + snd y))) p |
| 321 |
(gInit, 0)) |
| 322 |
as [v exact_sum]. |
| 323 |
unfold snd in H5. |
| 324 |
unfold snd at 3. clear v. |
| 325 |
destruct w as [v w]. |
| 326 |
unfold fst, snd. |
| 327 |
rewrite rings.preserves_plus. |
| 328 |
apply AbsSmall_Qabs. |
| 329 |
apply AbsSmall_Qabs in H5. |
| 330 |
setoid_replace ((AQtoQ approx_sum + AQtoQ (app_div v w (Qdlog2 (` e0)))) - |
| 331 |
(AQtoQ v / AQtoQ w + exact_sum))%Q |
| 332 |
with (AQtoQ approx_sum - exact_sum |
| 333 |
+ (AQtoQ (app_div v w (Qdlog2 (` e0))) - (AQtoQ v / AQtoQ w)))%Q |
| 334 |
by ring. |
| 335 |
apply (Qle_trans _ _ _ (Qabs_triangle _ _)). |
| 336 |
rewrite <- Pos.add_1_r, Pos2Z.inj_add, inject_Z_plus. |
| 337 |
rewrite Qmult_plus_distr_r, Qmult_1_r. |
| 338 |
apply Qplus_le_compat. exact H5. |
| 339 |
apply AbsSmall_Qabs. |
| 340 |
change (Qball (` e0) (AQtoQ (app_div v w (Qdlog2 (` e0)))) (AQtoQ v / AQtoQ w)). |
| 341 |
apply ball_weak_le with (e:= (2 ^ Qdlog2 (` e0))%Q). |
| 342 |
apply Qdlog2_spec, Qpos_ispos. |
| 343 |
apply aq_div. |
| 344 |
Qed. |
| 345 |
|
| 346 |
(* SumStream is the implementation of CRAlternatingSum.AltSeries_raw. |
| 347 |
Errors only come from approximate divisions here. *) |
| 348 |
Lemma AltSeries_raw_correct : forall (e:Qpos) (cvmod : Qpos -> positive), |
| 349 |
0 < snd fInit -> |
| 350 |
Qball (` e * (1 # 2)) |
| 351 |
(AQtoQ (AltSeries_raw fInit cvmod (Qpos2QposInf e))) |
| 352 |
(SumStream |
| 353 |
_ g gInit |
| 354 |
(cvmod (e * (1 # 2))%Qpos) (* fuel *) |
| 355 |
(AQposAsQpos (exist _ _ (app_inverse_below_pos (e * (1 # 2))%Qpos)))). |
| 356 |
Proof. |
| 357 |
intros e0 cvmod xpos. |
| 358 |
unfold SumStream. |
| 359 |
change (` (AQposAsQpos |
| 360 |
(app_inverse_below (e0 * (1 # 2))%Qpos |
| 361 |
↾ app_inverse_below_pos (e0 * (1 # 2))%Qpos))) |
| 362 |
with (AQtoQ (app_inverse_below (e0 * (1 # 2))%Qpos)). |
| 363 |
pose proof (iterate_stop_correct |
| 364 |
_ (fun y : (X and Q) and Q => |
| 365 |
let (z, r) := g (fst y) in (z, r, Qred (r + snd y))) |
| 366 |
(fun y : (X and Q) and Q => |
| 367 |
Qle_bool (Qabs (snd (fst y))) |
| 368 |
(AQtoQ (app_inverse_below (e0 * (1 # 2) ↾ eq_refl)))) |
| 369 |
(cvmod (e0 * (1 # 2))%Qpos) (gInit,0)) |
| 370 |
as [p [qeq [H5 H6]]]. |
| 371 |
rewrite qeq. clear qeq. |
| 372 |
unfold AltSeries_raw. |
| 373 |
replace (StopIndex fInit (app_inverse_below (e0 * (1 # 2) ↾ eq_refl)) |
| 374 |
(cvmod (e0 * (1 # 2))%Qpos)) |
| 375 |
with p. |
| 376 |
setoid_replace (` e0 * (1 # 2))%Q |
| 377 |
with (` e0 * (1 # 2 * p) * inject_Z (Zpos p))%Q. |
| 378 |
apply (div_approx_error p (e0*(1#2*p))). |
| 379 |
rewrite <- Qmult_assoc. apply Qmult_comp. reflexivity. |
| 380 |
unfold Qmult, Qeq; simpl. |
| 381 |
rewrite Pos.mul_1_r, Pos.mul_comm. reflexivity. |
| 382 |
rewrite SumStream_fst_red in H6. |
| 383 |
destruct H6 as [fuel | predicate]. |
| 384 |
- (* The sum consumes all the fuel. *) |
| 385 |
subst p. |
| 386 |
symmetry. apply StopIndex_stop_fuel. |
| 387 |
intros. specialize (H5 p H6). |
| 388 |
rewrite SumStream_fst_red in H5. |
| 389 |
unfold fst in H5. |
| 390 |
unfold IsStopIndex. intro abs. |
| 391 |
pose proof (g_pth p). unfold Str_pth in H7. |
| 392 |
rewrite H7 in H5. clear H7. |
| 393 |
pose proof (denomPos_iter p (xH,fInit) xpos). |
| 394 |
destruct (CRstreams.iterate _ fS p (1%positive, fInit)) |
| 395 |
as [u v]. |
| 396 |
apply abs_div_aqtoq_shift in abs. |
| 397 |
apply Qle_bool_iff in abs. |
| 398 |
rewrite abs in H5. discriminate. |
| 399 |
exact H7. |
| 400 |
- (* The sum stops before the fuel, because of the predicate. *) |
| 401 |
assert (IsStopIndex fInit (app_inverse_below (e0 * (1 # 2))%Qpos) p) as pstop. |
| 402 |
{ destruct predicate as [_ predicate]. unfold IsStopIndex. |
| 403 |
apply Qle_bool_iff in predicate. |
| 404 |
simpl in predicate. |
| 405 |
pose proof (g_pth p). |
| 406 |
unfold Str_pth in H6. rewrite H6 in predicate. clear H6. |
| 407 |
pose proof (denomPos_iter p (xH,fInit) xpos). |
| 408 |
destruct (CRstreams.iterate _ fS p (1%positive, fInit)). |
| 409 |
apply abs_div_aqtoq_shift. exact H6. |
| 410 |
exact predicate. } |
| 411 |
symmetry. apply StopIndex_correct. |
| 412 |
exact pstop. intros. |
| 413 |
unfold IsStopIndex. |
| 414 |
specialize (H5 q H6). |
| 415 |
rewrite SumStream_fst_red in H5. unfold fst in H5. |
| 416 |
pose proof (g_pth q). |
| 417 |
unfold Str_pth in H7. rewrite H7 in H5. clear H7. |
| 418 |
pose proof (denomPos_iter q (xH,fInit) xpos). |
| 419 |
destruct (CRstreams.iterate _ fS q (1%positive, fInit)). |
| 420 |
intro abs. |
| 421 |
apply abs_div_aqtoq_shift in abs. |
| 422 |
apply Qle_bool_iff in abs. |
| 423 |
rewrite abs in H5. discriminate. |
| 424 |
exact H7. apply Pos.lt_le_incl, predicate. |
| 425 |
Qed. |
| 426 |
|
| 427 |
Lemma AltSeries_raw_prf : forall (cvmod : Qpos -> positive), |
| 428 |
Str_alt_decr _ g gInit |
| 429 |
-> 0 < snd fInit |
| 430 |
-> Limit_zero _ g gInit cvmod -> |
| 431 |
is_RegularFunction (@ball AQ_as_MetricSpace) (AltSeries_raw fInit cvmod). |
| 432 |
Proof. |
| 433 |
intros cvmod g_decr xpos lz e1 e2. |
| 434 |
setoid_replace (`e1 + `e2)%Q |
| 435 |
with (`e1*(1#2) + (`e1*(1#2) + `e2*(1#2) + `e2*(1#2)))%Q by ring. |
| 436 |
apply (ball_triangle Q_as_MetricSpace _ _ _ |
| 437 |
(SumStream |
| 438 |
_ g gInit |
| 439 |
(cvmod (e1 * (1 # 2))%Qpos) |
| 440 |
(AQposAsQpos (exist _ _ (app_inverse_below_pos (e1 * (1 # 2))%Qpos))))). |
| 441 |
2: apply (ball_triangle Q_as_MetricSpace _ _ _ |
| 442 |
(SumStream |
| 443 |
_ g gInit |
| 444 |
(cvmod (e2 * (1 # 2))%Qpos) |
| 445 |
(AQposAsQpos (exist _ _ (app_inverse_below_pos (e2 * (1 # 2))%Qpos))))). |
| 446 |
- exact (AltSeries_raw_correct _ _ xpos). |
| 447 |
- apply (AltSeries_further |
| 448 |
_ g gInit _ _ _ _ |
| 449 |
(e1 * (1 # 2))%Qpos (e2 * (1 # 2))%Qpos g_decr). |
| 450 |
apply lz. apply lz. |
| 451 |
apply app_inverse_below_correct. |
| 452 |
apply app_inverse_below_correct. |
| 453 |
- apply ball_sym, (AltSeries_raw_correct _ _ xpos). |
| 454 |
Qed. |
| 455 |
|
| 456 |
Definition AltSeries (cvmod : Qpos -> positive) |
| 457 |
(decr : Str_alt_decr _ g gInit) |
| 458 |
(xpos : 0 < snd fInit) |
| 459 |
(lz : Limit_zero _ g gInit cvmod) : msp_car AR |
| 460 |
:= Build_RegularFunction (AltSeries_raw_prf cvmod decr xpos lz). |
| 461 |
|
| 462 |
Lemma AltSeries_correct : forall (cvmod : Qpos -> positive) |
| 463 |
(decr : Str_alt_decr _ g gInit) |
| 464 |
(xpos : 0 < snd fInit) |
| 465 |
(lz : Limit_zero _ g gInit cvmod), |
| 466 |
(ARtoCR (AltSeries cvmod decr xpos lz) |
| 467 |
== CRAlternatingSum.AltSeries _ g gInit cvmod decr lz)%CR. |
| 468 |
Proof. |
| 469 |
intros. |
| 470 |
apply regFunEq_equiv, regFunEq_e. |
| 471 |
intro d. |
| 472 |
setoid_replace (` d + ` d)%Q with (`d*(1#2) + (`d*(1#2)+` d))%Q by ring. |
| 473 |
apply (ball_triangle _ _ _ _ _ _ (AltSeries_raw_correct d cvmod xpos)). |
| 474 |
apply (AltSeries_further |
| 475 |
_ g gInit |
| 476 |
(cvmod (d * (1 # 2))%Qpos) (cvmod d) |
| 477 |
_ _ (d*(1#2))%Qpos d decr). |
| 478 |
apply lz. apply lz. |
| 479 |
apply app_inverse_below_correct. |
| 480 |
apply Qle_refl. |
| 481 |
Qed. |
| 482 |
|
| 483 |
End RationalStreamSum. |