Debian Codegraph @

reals/fast/CRstreams.v

raw
1 (*
2 Copyright © 2006-2008 Russell O’Connor
3 Copyright © 2020 Vincent Semeria
4
5 Permission is hereby granted, free of charge, to any person obtaining a copy of
6 this proof and associated documentation files (the "Proof"), to deal in
7 the Proof without restriction, including without limitation the rights to
8 use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
9 the Proof, and to permit persons to whom the Proof is furnished to do so,
10 subject to the following conditions:
11
12 The above copyright notice and this permission notice shall be included in all
13 copies or substantial portions of the Proof.
14
15 THE PROOF IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
17 FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR
18 COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
19 IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
20 CONNECTION WITH THE PROOF OR THE USE OR OTHER DEALINGS IN THE PROOF.
21 *)
22
23 From Coq Require Import ZArith.
24 Require Import CoRN.algebra.RSetoid.
25 Require Import CoRN.model.totalorder.QposMinMax.
26 Require Import CoRN.model.metric2.Qmetric.
27 Require Import CoRN.metric2.Limit.
28 From Coq Require Import Qabs.
29 From Coq Require Import Arith.
30 From Coq Require Import Qpower.
31 Require Import CoRN.reals.fast.LazyNat.
32 From Coq Require Import Ring.
33 Require Import MathClasses.interfaces.abstract_algebra MathClasses.theory.streams.
34 Require Export MathClasses.theory.series.
35 Require Import MathClasses.interfaces.abstract_algebra MathClasses.theory.streams.
36
37 Opaque Qabs.
38 Local Open Scope Q_scope.
39
40 (**
41 ** Specific results for streams on [Q]
42 *)
43
44 (** [everyOther] preserves limits. *)
45 Lemma everyOther_nbz : forall (s : Stream Q) (e : QposInf),
46 (NearBy 0 e s) -> NearBy 0 e (everyOther s).
47 Proof.
48 cofix everyOther_nbz.
49 intros [s [b r]] x [H [_ Hs]].
50 constructor;[|apply everyOther_nbz];assumption.
51 Qed.
52
53 #[global]
54 Instance everyOther_zl `{Hx : !Limit s 0} : Limit (everyOther s) 0.
55 Proof.
56 intros e.
57 assert (H:=Hx e). clear Hx.
58 revert s H.
59 fix everyOther_zl 2.
60 intros x [H|H].
61 left.
62 apply everyOther_nbz.
63 assumption.
64 case (H tt);[intros X |intros X].
65 right; left.
66 clear - x X.
67 abstract ( destruct x as [a [b x]]; destruct X; apply everyOther_nbz; assumption).
68 right; intros _.
69 apply everyOther_zl.
70 apply X.
71 constructor.
72 Defined.
73
74 (** [mult_Streams] preserves convergeing to 0. *)
75 Lemma mult_Streams_nbz : forall {s1 s2 : Stream Q} {x : QposInf},
76 (NearBy 0 x s1)
77 -> forall {y : QposInf}, NearBy 0 y s2
78 -> NearBy 0 (x*y) (mult_Streams s1 s2).
79 Proof.
80 unfold NearBy.
81 cofix mult_Streams_nbz.
82 intros s1 s2 x [Ha0 Hs1] y [Hb0 Hs2].
83 constructor.
84 2: apply (mult_Streams_nbz (CoqStreams.tl s1) (CoqStreams.tl s2)); assumption.
85 destruct x as [x|];[|constructor].
86 destruct y as [y|];[|constructor].
87 simpl.
88 unfold Qball.
89 unfold QAbsSmall.
90 setoid_replace ((CoqStreams.hd s1 * CoqStreams.hd s2)%mc - 0)%Q
91 with ((CoqStreams.hd s1 - 0) * (CoqStreams.hd s2 - 0)).
92 apply Qmult_AbsSmall; assumption.
93 ring_simplify. reflexivity.
94 Qed.
95
96 (* The multiplication of a bounded stream b by a stream a
97 converging to 0 converges to 0. *)
98 Lemma mult_Streams_zl : forall (a b : Stream Q),
99 (Limit a 0) -> forall (x:Qpos), NearBy 0 x b ->
100 Limit (mult_Streams a b) 0.
101 Proof.
102 intros a b Ha x Hb e.
103 assert (H:=Ha (e * (Qpos_inv x))%QposInf).
104 generalize b Hb.
105 clear b Hb.
106 induction H; intros b Hb.
107 left.
108 abstract ( destruct e as [e|];[|apply ForAll_True];
109 assert (Heq:proj1_sig e== proj1_sig ((e*Qpos_inv x)*x)%Qpos);[
110 simpl; field; apply Qpos_nonzero
111 |rewrite -> (NearBy_comp _ _ (ball_refl _ 0 (Qle_refl 0)) _ _ Heq );
112 apply (mult_Streams_nbz H Hb)] ).
113 right.
114 simpl.
115 rename H0 into IHExists.
116 intros.
117 apply (IHExists tt).
118 apply Limit_tl; assumption.
119 destruct Hb; assumption.
120 Defined.
121
122 (**
123 *** [StreamBounds]
124 [StreamBounds] says that one stream pointwise bounds the absolute value
125 of the other. *)
126 Definition StreamBounds (a b : Stream Q)
127 := ForAll (fun (x:Stream (Q*Q)) => let (a,b):=(CoqStreams.hd x) in QAbsSmall a b)
128 (zipWith pair a b).
129
130 (** If the bounding stream goes to 0, so does the bounded stream. *)
131 Lemma Stream_Bound_nbz : forall a b e, (StreamBounds a b) -> NearBy 0 e a -> NearBy 0 e b.
132 Proof.
133 cofix Stream_Bound_nbz.
134 intros a b e Hb Ha.
135 constructor.
136 destruct Hb as [[Hb1 Hb2] _].
137 destruct e as [e|];[|constructor].
138 destruct Ha as [[Ha1 Ha2] _].
139 simpl in *.
140 split.
141 apply Qle_trans with (-(CoqStreams.hd a -0)).
142 apply Qopp_le_compat.
143 assumption.
144 ring_simplify.
145 assumption.
146 apply Qle_trans with (CoqStreams.hd a - 0).
147 ring_simplify.
148 assumption.
149 assumption.
150 eapply Stream_Bound_nbz.
151 destruct Hb as [_ Hb].
152 change (StreamBounds (CoqStreams.tl a) (CoqStreams.tl b)) in Hb.
153 apply Hb.
154 destruct Ha as [_ Ha].
155 assumption.
156 Qed.
157
158 Lemma Stream_Bound_zl : forall a b, (StreamBounds a b) -> Limit a 0 -> Limit b 0.
159 Proof.
160 intros a b H Ha e.
161 assert (Ha':=(Ha e)); clear Ha.
162 generalize b H; clear b H.
163 induction Ha'; intros b Hb.
164 left.
165 apply Stream_Bound_nbz with x; assumption.
166 right.
167 rename H0 into IHHa'.
168 intros _.
169 apply (IHHa' tt).
170 destruct Hb; assumption.
171 Defined.
172
173 Section Qpowers.
174 Variable a : Q.
175
176 Hypothesis Ha : 0 <= a <= 1.
177
178 (** It is decreasing and nonnegative when a is between 0 and 1. *)
179 Lemma powers_help_dnn : forall x, (0 <= x) -> DecreasingNonNegative (powers_help a x).
180 Proof.
181 intros x Hx.
182 destruct Ha as [Ha0 Ha1].
183 generalize x Hx; clear x Hx.
184 cofix powers_help_dnn.
185 intros b Hb.
186 constructor.
187 simpl.
188 split.
189 rewrite <- (Qmult_0_l a). apply Qmult_le_compat_r; assumption.
190 rewrite Qmult_comm.
191 rewrite <- (Qmult_1_l b) at 2.
192 apply Qmult_le_compat_r. exact Ha1. exact Hb.
193 apply powers_help_dnn.
194 rewrite <- (Qmult_0_l a). apply Qmult_le_compat_r; assumption.
195 Qed.
196
197 Lemma powers_dnn : DecreasingNonNegative (powers a).
198 Proof.
199 apply powers_help_dnn.
200 discriminate.
201 Qed.
202
203 Lemma powers_help_nbz : forall x,
204 0 <= x <= 1 -> NearBy 0 (Qpos2QposInf (1#1)) (powers_help a x).
205 Proof.
206 cofix powers_help_nbz.
207 intros b [Hb0 Hb1].
208 destruct Ha as [Ha0 Ha1].
209 constructor.
210 simpl.
211 unfold Qball.
212 unfold QAbsSmall. setoid_replace (b-0)%Q with b.
213 2: unfold Qminus; apply Qplus_0_r.
214 split;simpl.
215 apply Qle_trans with 0;[discriminate|assumption].
216 assumption.
217 simpl.
218 apply powers_help_nbz.
219 split.
220 rewrite <- (Qmult_0_l a). apply Qmult_le_compat_r; assumption.
221 apply (Qle_trans _ (1*a)).
222 apply Qmult_le_compat_r; assumption.
223 rewrite Qmult_1_l. exact Ha1.
224 Qed.
225
226 Lemma powers_nbz : NearBy 0 (Qpos2QposInf (1#1)) (powers a).
227 Proof.
228 apply powers_help_nbz.
229 split; discriminate.
230 Qed.
231 End Qpowers.
232
233
234 (**
235 *** [ppositives]
236 The stream of postive numbers (as positive).
237
238 We do not use [positives] because [positive] does not form a semiring.
239 *)
240 CoFixpoint ppositives_help (n:positive) : Stream positive :=
241 Cons n (ppositives_help (Pos.succ n)).
242
243 Definition ppositives := ppositives_help 1.
244
245 Lemma Str_nth_ppositives : forall n, Str_nth n ppositives ≡ P_of_succ_nat n.
246 Proof.
247 intros n.
248 unfold ppositives.
249 apply nat_of_P_inj.
250 rewrite nat_of_P_o_P_of_succ_nat_eq_succ.
251 change (S n) with ((nat_of_P 1) + n)%nat.
252 generalize 1%positive.
253 induction n.
254 intros c.
255 rewrite Nat.add_comm.
256 reflexivity.
257 intros c.
258 unfold Str_nth in *.
259 simpl.
260 rewrite IHn.
261 rewrite nat_of_P_succ_morphism.
262 apply plus_n_Sm.
263 Qed.
264
265 Lemma Str_nth_ppositives' n
266 : inject_Z (Zpos (Str_nth n ppositives)) = Str_nth n positives.
267 Proof.
268 rewrite Str_nth_ppositives, Str_nth_positives.
269 rewrite Z.P_of_succ_nat_Zplus.
270 rewrite <-(naturals.to_semiring_unique (Basics.compose inject_Z Z_of_nat)).
271 unfold Basics.compose.
272 rewrite <-(rings.preserves_1 (f:=inject_Z)).
273 rewrite <-rings.preserves_plus.
274 now rewrite commutativity.
275 Qed.
276
277 (**
278 *** [Qrecip_positives]
279 The stream of 1/n.
280 *)
281 Definition Qrecip_positives := CoqStreams.map (fun x => 1#x) ppositives.
282
283 Lemma Str_nth_Qrecip_positives : forall n, Str_nth n Qrecip_positives = 1#(P_of_succ_nat n).
284 Proof.
285 intros n.
286 unfold Qrecip_positives.
287 rewrite Str_nth_map.
288 rewrite Str_nth_ppositives.
289 reflexivity.
290 Qed.
291
292 Lemma Str_nth_Qrecip_positives' n : Str_nth n Qrecip_positives = / Str_nth n positives.
293 Proof.
294 unfold Qrecip_positives.
295 rewrite Str_nth_map.
296 rewrite Qmake_Qdiv.
297 rewrite Str_nth_ppositives'.
298 apply (left_identity (/ Str_nth n positives)).
299 Qed.
300
301 (** The limit of [recip_positives] is 0. *)
302 Lemma Qrecip_positives_help_nbz : forall (x: Qpos) (q:positive),
303 (Zpos (Qden (proj1_sig x)) <= Zpos q)%Z
304 -> NearBy 0 (Qpos2QposInf x) (CoqStreams.map (fun x => 1#x) (ppositives_help q)).
305 Proof.
306 assert (∀ (q n d : positive),
307 (Zpos d <= Zpos q)%Z
308 → NearBy 0 (Qpos2QposInf (n # d)) (CoqStreams.map (λ x : positive, 1 # x) (ppositives_help q))).
309 { cofix Qrecip_positives_help_nbz.
310 intros q n d Hpq.
311 constructor.
312 - simpl.
313 unfold Qball, QAbsSmall, Qminus.
314 rewrite Qplus_0_r.
315 split. discriminate.
316 change (1*Zpos d <= Zpos n*Zpos q)%Z.
317 apply Zmult_le_compat.
318 apply Pos.le_1_l. exact Hpq.
319 discriminate. discriminate.
320 - apply Qrecip_positives_help_nbz.
321 clear Qrecip_positives_help_nbz.
322 rewrite Zpos_succ_morphism.
323 apply (Z.le_trans _ _ _ Hpq).
324 apply Z.le_succ_diag_r. }
325 intros. destruct x as [[n d] xpos].
326 destruct n as [|n|n]. inversion xpos. 2: inversion xpos.
327 apply H. exact H0.
328 Qed.
329
330 (* Make a lazy list of LazyFurthers. *)
331 Fixpoint Qrecip_positives_help_Exists P (n:LazyNat) (p:positive)
332 (H : LazyExists P (CoqStreams.map (fun x => (1#x)) (ppositives_help (Pplus_LazyNat p n)))) { struct n }
333 : LazyExists P (CoqStreams.map (fun x => (1#x)) (ppositives_help p)).
334 Proof.
335 destruct n.
336 - exact H.
337 - apply LazyFurther.
338 exact (fun _ => Qrecip_positives_help_Exists P (l tt) (Pos.succ p) H).
339 Defined.
340
341 Lemma Qrecip_positives_nbz : forall (n : Z) (d : positive) (U : 0 < n # d),
342 NearBy 0 (Qpos2QposInf (exist _ (n # d) U))
343 (map (λ x : positive, 1 # x)
344 (ppositives_help (Pplus_LazyNat 1 (LazyPred (LazyNat_of_P d))))).
345 Proof.
346 intros.
347 apply Qrecip_positives_help_nbz.
348 induction d using Pind;[simpl;auto with *|].
349 autorewrite with UnLazyNat in *.
350 rewrite nat_of_P_succ_morphism; assert (H:=lt_O_nat_of_P d);
351 destruct (nat_of_P d);[exfalso;auto with *|]; simpl in *;
352 replace (Pplus_LazyNat 2 (LazifyNat n0)) with (Pos.succ (Pplus_LazyNat 1 (LazifyNat n0)));[
353 repeat rewrite Zpos_succ_morphism; auto with * |]; clear -n0;
354 change 2%positive with (Pos.succ 1); generalize 1%positive;
355 induction n0;intros p;[reflexivity|]; simpl in *; rewrite IHn0; reflexivity.
356 Qed.
357
358 #[global]
359 Instance Qrecip_positives_zl : Limit Qrecip_positives 0.
360 intros [[[n d] U] | ]; [| left; apply ForAll_True].
361 unfold Qrecip_positives.
362 unfold ppositives.
363 apply Qrecip_positives_help_Exists with (LazyPred (LazyNat_of_P d)).
364 left. apply Qrecip_positives_nbz.
365 Defined.
366
367 (** [recip_positives] is [DecreasingNonNegative]. *)
368 #[global]
369 Instance Qrecip_positives_dnn : DecreasingNonNegative Qrecip_positives.
370 Proof.
371 unfold Qrecip_positives.
372 unfold ppositives.
373 generalize (1%positive) at 2.
374 cofix Qrecip_positives_dnn.
375 intros p.
376 constructor.
377 simpl.
378 split.
379 discriminate.
380 change (Zpos p <= Zpos (Pos.succ p))%Z.
381 repeat rewrite Zpos_succ_morphism.
382 auto with *.
383 simpl.
384 apply Qrecip_positives_dnn.
385 Qed.
386
387 (**
388 *** [pfactorials]
389 The stream of factorials as positives.
390
391 Again, we do not use [factorials] because [positive] does not form a semiring.
392 *)
393 CoFixpoint pfactorials_help (n c:positive) : Stream positive :=
394 Cons c (pfactorials_help (Pos.succ n) (n*c)).
395
396 Definition pfactorials := pfactorials_help 1 1.
397
398 Lemma Str_nth_pfactorials : forall n, nat_of_P (Str_nth n pfactorials) ≡ fact n.
399 Proof.
400 unfold pfactorials.
401 intros n.
402 pose (ONE:=1%positive).
403 replace (fact n) with ((nat_of_P 1)*fact (pred (nat_of_P ONE) + n))%nat by (simpl;auto).
404 replace (nat_of_P (Str_nth n (pfactorials_help 1 1)))
405 with ((fact (pred (nat_of_P ONE)))*(nat_of_P (Str_nth n (pfactorials_help ONE 1))))%nat by (simpl; auto with * ).
406 change (pfactorials_help 1 1) with (pfactorials_help ONE 1).
407 generalize ONE.
408 generalize 1%positive.
409 unfold ONE; clear ONE.
410 induction n.
411 intros a b.
412 unfold Str_nth.
413 simpl.
414 rewrite Nat.add_comm.
415 now rewrite Nat.mul_comm.
416 intros a b.
417 unfold Str_nth in *.
418 simpl.
419 assert (X:=IHn (b*a)%positive (Pos.succ b)).
420 clear IHn.
421 rewrite nat_of_P_succ_morphism in X.
422 rewrite <- plus_n_Sm.
423 assert (forall (n m:nat), eq (Z_of_nat n) (Z_of_nat m) -> eq n m).
424 { intros i j H. intuition. }
425 apply H. clear H.
426 apply Zmult_reg_l with (Z.of_nat (nat_of_P b));
427 [rewrite positive_nat_Z; auto with *|].
428 do 2 rewrite <- (inj_mult (nat_of_P b)).
429 apply inj_eq.
430 rewrite (Nat.mul_assoc (nat_of_P b) (nat_of_P a)).
431 rewrite <- Pos2Nat.inj_mul.
432 rewrite <- pred_Sn in X.
433 change (S (pred (nat_of_P b) + n))%nat with (S (pred (nat_of_P b)) + n)%nat.
434 assert (Z:S (pred (nat_of_P b)) = nat_of_P b).
435 { apply (Nat.lt_succ_pred 0). apply Pos2Nat.is_pos. }
436 rewrite Z.
437 rewrite <- X.
438 replace (fact (nat_of_P b)) with (fact (S (pred (nat_of_P b)))) by congruence.
439 change (fact (S (pred (nat_of_P b)))) with ((S (pred (nat_of_P b)))*(fact (pred (nat_of_P b))))%nat.
440 rewrite Z.
441 ring.
442 Qed.
443
444 Lemma Str_nth_pfactorials' n
445 : inject_Z (Zpos (Str_nth n pfactorials)) = Str_nth n factorials.
446 Proof.
447 rewrite Str_nth_factorials.
448 rewrite <-Str_nth_pfactorials.
449 rewrite <-(naturals.to_semiring_unique (Basics.compose inject_Z Z_of_nat)).
450 unfold Basics.compose.
451 rewrite positive_nat_Z. reflexivity.
452 Qed.
453
454 (**
455 *** [Qrecip_factorials]
456 The stream of 1/n!.
457 **)
458 Definition Qrecip_factorials := CoqStreams.map (fun x => 1#x) pfactorials.
459
460 Lemma Str_nth_Qrecip_factorials : forall n, (Str_nth n Qrecip_factorials) = 1#(P_of_succ_nat (pred (fact n))).
461 Proof.
462 intros n.
463 unfold Qrecip_factorials.
464 rewrite Str_nth_map.
465 rewrite <- Str_nth_pfactorials.
466 unfold equiv, stdlib_rationals.Q_eq, Qeq. simpl.
467 apply f_equal.
468 transitivity (Pos.of_nat (Pos.to_nat (Str_nth n pfactorials))).
469 2: apply Pos2Nat.id.
470 destruct (Pos.to_nat (Str_nth n pfactorials)) eqn:des.
471 2: apply Pos.of_nat_succ.
472 exfalso. pose proof (Pos2Nat.is_pos (Str_nth n pfactorials)).
473 rewrite des in H. inversion H.
474 Qed.
475
476 Lemma Str_nth_Qrecip_factorials' n : Str_nth n Qrecip_factorials = / Str_nth n factorials.
477 Proof.
478 unfold Qrecip_factorials.
479 rewrite Str_nth_map.
480 rewrite Qmake_Qdiv.
481 rewrite Str_nth_pfactorials'.
482 now apply (left_identity (/ Str_nth n factorials)).
483 Qed.
484
485 (** [Qrecip_factorials] is [DecreasingNonNegative]. *)
486 #[global]
487 Instance Qrecip_factorials_dnn : DecreasingNonNegative Qrecip_factorials.
488 Proof.
489 unfold Qrecip_factorials.
490 unfold pfactorials.
491 generalize (1%positive) at 3. generalize (1%positive) at 2.
492 cofix Qrecip_factorials_dnn.
493 intros a b.
494 constructor.
495 simpl.
496 split.
497 discriminate.
498 apply (Z.mul_le_mono_nonneg_r 1 (Zpos a) (Zpos b)).
499 discriminate. apply Pos.le_1_l.
500 simpl.
501 apply Qrecip_factorials_dnn.
502 Qed.
503
504 (** The limit of [Qrecip_factorial] is 0. *)
505 Lemma Qrecip_factorial_bounded
506 : StreamBounds Qrecip_positives (CoqStreams.tl Qrecip_factorials).
507 Proof.
508 unfold Qrecip_positives, Qrecip_factorials, ppositives, pfactorials.
509 cut (forall (p q:positive), StreamBounds (CoqStreams.map (fun x : positive => 1 # x) (ppositives_help p))
510 (CoqStreams.tl (CoqStreams.map (fun x : positive => 1 # x) (pfactorials_help p q)))).
511 intros H.
512 apply (H 1%positive 1%positive).
513 auto with *.
514 cofix Qrecip_factorial_bounded.
515 constructor.
516 simpl.
517 split.
518 discriminate.
519 change (Zpos p <= Zpos p * Zpos q)%Z.
520 rewrite Z.mul_comm.
521 apply (Z.mul_le_mono_nonneg_r 1 (Zpos q) (Zpos p)).
522 discriminate. apply Pos.le_1_l.
523 simpl in *.
524 apply Qrecip_factorial_bounded.
525 Qed.
526
527 #[global]
528 Instance Qrecip_factorials_zl : Limit Qrecip_factorials 0.
529 Proof.
530 intros e.
531 right.
532 intros _.
533 apply (Stream_Bound_zl _ _ Qrecip_factorial_bounded).
534 apply Qrecip_positives_zl.
535 Defined.
536
537 Section StreamGenerators.
538 (* Strictly speaking those are generators of streams with a state X,
539 or stream co-algebras, rather than actual streams. Instead of using
540 corecursion to produce actual coinductive streams, we directly call
541 the generator functions.
542
543 The type Stream Y is isomorphic the type nat -> Y. We use the former
544 to compute series such as exp x = sum_k x^k / k!
545 because the (k+1)-th term is quickly computed from the k-th term,
546 rather than recomputing the power and the factorial from 0 for each k. *)
547
548 Variable X : Type.
549 Variable f : X -> X.
550
551 Fixpoint iterate (p : positive) (x : X) : X :=
552 match p with
553 | xI q => iterate q (iterate q (f x))
554 | xO q => iterate q (iterate q x)
555 | xH => f x
556 end.
557
558 Lemma iterate_one : forall x:X,
559 iterate 1 x ≡ f x.
560 Proof.
561 reflexivity.
562 Qed.
563
564 Lemma iterate_shift : forall (p:positive) (x : X),
565 f (iterate p x) ≡ iterate p (f x).
566 Proof.
567 induction p.
568 - intro x. simpl.
569 rewrite IHp, IHp. reflexivity.
570 - intro x. simpl.
571 rewrite IHp, IHp. reflexivity.
572 - reflexivity.
573 Qed.
574
575 Lemma iterate_succ : forall (p:positive) (x : X),
576 iterate (Pos.succ p) x ≡ f (iterate p x).
577 Proof.
578 induction p.
579 - intro x. simpl.
580 rewrite IHp. f_equal.
581 rewrite IHp. f_equal.
582 rewrite iterate_shift. reflexivity.
583 - intro x. simpl.
584 rewrite iterate_shift, iterate_shift.
585 reflexivity.
586 - reflexivity.
587 Qed.
588
589 Lemma iterate_add : forall (p q:positive) (x : X),
590 iterate (p+q)%positive x ≡ iterate p (iterate q x).
591 Proof.
592 apply (Pos.peano_ind
593 (fun p => forall (q : positive) (x : X),
594 iterate (p + q) x ≡ iterate p (iterate q x))).
595 - intros. rewrite Pos.add_1_l, iterate_succ. reflexivity.
596 - intros. rewrite iterate_succ.
597 rewrite <- Pos.add_1_l, <- Pos.add_assoc, Pos.add_1_l.
598 rewrite iterate_succ, H. reflexivity.
599 Qed.
600
601 Variable stop : X -> bool.
602
603 (* iterate_stop p x = iterate q x, where q = p or q < p and
604 q is the lowest index such as stop (iterate q) = true.
605 Testing whether the recursive iterate_stop stops regrettably
606 adds a logarithmic useless number of stop tests.
607 This could be improved by returning a pair X*bool to indicate
608 that the iteration stopped. We could also try using a LazyNat fuel. *)
609 Fixpoint iterate_stop (p : positive) (x : X) : X :=
610 match p with
611 | xI q => (* p = 2q+1 *)
612 let g := f x in
613 if stop g then g else
614 let h := iterate_stop q g in
615 if stop h then h else iterate_stop q h
616 | xO q => let g := iterate_stop q x in
617 if stop g then g else iterate_stop q g
618 | xH => f x
619 end.
620
621 (* The q below is even unique. Because it is either p or
622 the first index where iterate stops. *)
623 Lemma iterate_stop_correct : forall (p:positive) (x:X),
624 exists q:positive,
625 iterate_stop p x ≡ iterate q x
626 /\ (forall r, Pos.lt r q -> stop (iterate r x) ≡ false)
627 /\ (p ≡ q
628 \/ (Pos.lt q p /\ stop (iterate q x) ≡ true)).
629 Proof.
630 induction p.
631 - intro x. simpl.
632 destruct (stop (f x)) eqn:des1.
633 exists xH. split. reflexivity.
634 split. intros. exfalso; exact (Pos.nlt_1_r r H).
635 right. split. rewrite Pos.xI_succ_xO.
636 apply Pos.lt_1_succ.
637 exact des1.
638 destruct (stop (iterate_stop p (f x))) eqn:des.
639 + (* Stopped at p+1 by the stop predicate,
640 prove that value is the same at 2p+1. *)
641 specialize (IHp (f x)) as [q [itereq [H H0]]].
642 exists (Pos.succ q). split.
643 rewrite itereq, iterate_succ, iterate_shift.
644 reflexivity. split.
645 apply (Pos.peano_case
646 (fun r => (r < Pos.succ q)%positive → stop (iterate r x) ≡ false)).
647 intros. exact des1. intros.
648 rewrite iterate_succ, iterate_shift. apply H.
649 apply Pos.succ_lt_mono in H1.
650 exact H1. right.
651 split. rewrite Pos.xI_succ_xO.
652 rewrite <- Pos.succ_lt_mono.
653 destruct H0. rewrite H0.
654 rewrite <- Pos.add_diag. apply Pos.lt_add_r.
655 apply (Pos.lt_trans _ p). apply H0.
656 rewrite <- Pos.add_diag. apply Pos.lt_add_r.
657 rewrite iterate_succ, iterate_shift, <- itereq. exact des.
658 + pose proof (IHp (f x)) as [q [itereq [H H0]]].
659 destruct H0.
660 2: exfalso; destruct H0; rewrite <- itereq, des in H1; discriminate.
661 subst q.
662 specialize (IHp (iterate_stop p (f x))) as [q [qeq [H0 H1]]].
663 exists (Pos.succ q+p)%positive. split.
664 rewrite qeq.
665 rewrite <- Pos.add_1_r, <- Pos.add_assoc, iterate_add.
666 apply f_equal.
667 rewrite Pos.add_1_l, itereq, iterate_succ, iterate_shift.
668 reflexivity. split.
669 apply (Pos.peano_case
670 (fun r => (r < Pos.succ q+p)%positive → stop (iterate r x) ≡ false)).
671 intros. exact des1.
672 intros r H2.
673 rewrite iterate_succ, iterate_shift.
674 destruct (Pos.lt_total r p).
675 apply H, H3.
676 destruct H3. rewrite H3.
677 rewrite <- itereq. exact des.
678 rewrite <- (Pplus_minus r p).
679 2: apply Pos.lt_gt, H3.
680 rewrite Pos.add_comm, iterate_add, <- itereq.
681 apply (H0 (r-p)%positive).
682 rewrite <- (Pos.add_1_l q), <- Pos.add_assoc, Pos.add_1_l in H2.
683 apply Pos.succ_lt_mono in H2.
684 rewrite <- (Pplus_minus r p) in H2.
685 2: apply Pos.lt_gt, H3.
686 rewrite Pos.add_comm in H2.
687 apply Pos.add_lt_mono_r in H2. exact H2.
688 destruct H1. left. rewrite H1.
689 rewrite Pos.xI_succ_xO.
690 rewrite <- (Pos.add_1_l q), <- Pos.add_assoc, Pos.add_1_l.
691 rewrite Pos.add_diag. reflexivity.
692 right. split. rewrite Pos.xI_succ_xO.
693 rewrite <- Pos.add_1_l, <- Pos.add_assoc, Pos.add_1_l.
694 rewrite <- Pos.succ_lt_mono, <- Pos.add_diag.
695 apply Pos.add_lt_mono_r, H1.
696 rewrite <- Pos.add_1_r, <- Pos.add_assoc, iterate_add.
697 rewrite Pos.add_1_l, iterate_succ, iterate_shift.
698 rewrite <- itereq. apply H1.
699 - intro x. simpl.
700 destruct (stop (iterate_stop p x)) eqn:des.
701 + (* Stopped at p by the stop predicate,
702 prove that value is the same at 2p. *)
703 specialize (IHp x) as [q [itereq [H H0]]].
704 exists q. split. exact itereq. split.
705 intros. apply H, H1. right.
706 split. destruct H0.
707 rewrite H0. rewrite <- Pos.add_diag. apply Pos.lt_add_r.
708 apply (Pos.lt_trans _ p). apply H0.
709 rewrite <- Pos.add_diag. apply Pos.lt_add_r.
710 rewrite <- itereq. exact des.
711 + pose proof (IHp x) as [q [itereq [H H0]]].
712 destruct H0.
713 2: exfalso; destruct H0; rewrite <- itereq, des in H1; discriminate.
714 subst q.
715 specialize (IHp (iterate_stop p x)) as [q [qeq [H0 H1]]].
716 exists (q+p)%positive. split.
717 rewrite qeq, iterate_add.
718 apply f_equal. exact itereq.
719 split. intros.
720 destruct (Pos.lt_total r p).
721 apply H, H3. destruct H3. rewrite H3. clear H3 H2 r.
722 rewrite <- itereq. exact des.
723 rewrite <- (Pplus_minus r p).
724 2: apply Pos.lt_gt, H3.
725 rewrite Pos.add_comm, iterate_add, <- itereq.
726 apply (H0 (r-p)%positive).
727 rewrite <- (Pplus_minus r p) in H2.
728 2: apply Pos.lt_gt, H3.
729 rewrite Pos.add_comm in H2.
730 apply Pos.add_lt_mono_r in H2.
731 exact H2.
732 destruct H1. left. rewrite H1.
733 rewrite Pos.add_diag. reflexivity.
734 right. split.
735 rewrite <- Pos.add_diag.
736 apply Pos.add_lt_mono_r, H1.
737 rewrite iterate_add, <- itereq. apply H1.
738 - intro x. exists xH. split. reflexivity.
739 split. intros. exfalso; exact (Pos.nlt_1_r r H).
740 left. reflexivity.
741 Qed.
742
743 Lemma iterate_stop_one : forall (x : X),
744 iterate_stop 1 x ≡ f x.
745 Proof.
746 reflexivity.
747 Qed.
748
749 Lemma iterate_stop_indep : forall (p q : positive) (x : X),
750 stop (iterate p x) ≡ true
751 -> stop (iterate q x) ≡ true
752 -> iterate_stop p x ≡ iterate_stop q x.
753 Proof.
754 intros.
755 pose proof (iterate_stop_correct p x) as [r [rpeq [H1 H2]]].
756 assert (stop (iterate r x) ≡ true) as rstop.
757 { destruct H2. rewrite <- H2. exact H. apply H2. }
758 rewrite rpeq. clear H2 rpeq H p.
759 pose proof (iterate_stop_correct q x) as [s [sqeq [H H2]]].
760 assert (stop (iterate s x) ≡ true) as sstop.
761 { destruct H2. rewrite <- H2. exact H0. apply H2. }
762 rewrite sqeq. clear H2 sqeq H0 q.
763 destruct (Pos.lt_total r s).
764 - exfalso. specialize (H r H0).
765 rewrite H in rstop. discriminate.
766 - destruct H0. rewrite H0. reflexivity.
767 exfalso. specialize (H1 s H0).
768 rewrite H1 in sstop. discriminate.
769 Qed.
770
771 Lemma iterate_stop_unique : forall (p q : positive) (x : X),
772 stop (iterate p x) ≡ true
773 -> stop (iterate q x) ≡ true
774 -> (forall i:positive, Pos.lt i q -> stop (iterate i x) ≡ false)
775 -> iterate_stop p x ≡ iterate q x.
776 Proof.
777 intros.
778 pose proof (iterate_stop_correct p x) as [r [rpeq [H2 H3]]].
779 rewrite rpeq. replace r with q. reflexivity.
780 destruct (Pos.lt_total q r).
781 - exfalso. specialize (H2 q H4). rewrite H0 in H2. discriminate.
782 - destruct H4. exact H4. exfalso.
783 destruct H3.
784 + subst r.
785 specialize (H1 p H4). rewrite H in H1. discriminate.
786 + destruct H3. specialize (H1 r H4).
787 rewrite H1 in H5. discriminate.
788 Qed.
789
790 Definition CRstream_opp (X:Type) (f : X*Q->X*Q) (xq : X*Q) : X*Q
791 := let (x,q) := xq in
792 let (y,r) := f (x,-q) in
793 (y,-r).
794
795 End StreamGenerators.
796
797 Lemma CRstream_opp_pth : forall (X:Type) (f : X*Q->X*Q) (xq : X*Q) (p : positive),
798 let (y,r) := iterate _ f p xq in
799 let (z,s) := iterate _ (CRstream_opp X f) p (let (x,q):=xq in (x,-q)) in
800 y ≡ z /\ s ≡ -r.
801 Proof.
802 intros X f xq.
803 apply Pos.peano_ind.
804 - simpl. destruct xq as [x q].
805 unfold CRstream_opp.
806 replace (--q) with q. destruct (f (x,q)).
807 split; reflexivity.
808 destruct q. unfold Qopp; simpl.
809 rewrite Z.opp_involutive. reflexivity.
810 - intros IHp H.
811 rewrite CRstreams.iterate_succ, CRstreams.iterate_succ.
812 destruct (iterate _ f IHp xq),
813 (iterate _ (CRstream_opp X f) IHp
814 (let (x0, q0) := xq in (x0, - q0))).
815 unfold CRstream_opp. destruct H. subst q0. subst x0.
816 replace (--q) with q. destruct (f (x,q)).
817 split; reflexivity.
818 destruct q. unfold Qopp; simpl.
819 rewrite Z.opp_involutive. reflexivity.
820 Qed.