Debian Codegraph @

reals/faster/ARarctan_small.v

raw
1 Require Import
2 MathClasses.interfaces.abstract_algebra
3 MathClasses.theory.nat_pow
4 MathClasses.theory.int_pow
5 CoRN.algebra.RSetoid
6 CoRN.stdlib_omissions.Q
7 CoRN.metric2.Metric
8 CoRN.metric2.UniformContinuity
9 CoRN.reals.fast.CRarctan_small
10 CoRN.reals.fast.CRarctan
11 CoRN.reals.fast.CRstreams
12 CoRN.reals.fast.CRAlternatingSum
13 CoRN.reals.faster.ARAlternatingSum
14 CoRN.reals.faster.ARsin.
15 Require Export
16 CoRN.reals.faster.ARArith.
17
18 Section ARarctan_small.
19 Context `{AppRationals AQ}
20 {num den : AQ} (Pnd : -den < num < den) (dpos : 0 < den).
21
22 (*
23 Split the stream
24 (-1)^i a^(2i+1) / (2i+1)
25 up into the streams
26 (-1)^i a^(2i+1) and (2i+1)
27 because we do not have exact division
28 *)
29 Definition ARarctanStream (px : positive*(AQ*AQ)) : AQ*AQ
30 := (- fst (snd px) * num * num * ZtoAQ (Zpos (Pos.pred (fst px)~0)),
31 snd (snd px) * den * den * ZtoAQ (Zpos (fst px)~1)).
32
33 Lemma arctanStream_pos : ∀ x : positive * (AQ * AQ),
34 0 < snd (snd x) → 0 < snd (ARarctanStream x).
35 Proof.
36 assert (0 = ZtoAQ 0) as zero_int.
37 { destruct H4. destruct aq_ints_mor, semiringmor_plus_mor.
38 rewrite preserves_mon_unit. reflexivity. }
39 intros. destruct x; simpl.
40 simpl in H5.
41 apply AQmult_lt_0_compat.
42 apply AQmult_lt_0_compat.
43 apply AQmult_lt_0_compat.
44 exact H5. exact dpos. exact dpos.
45 rewrite zero_int.
46 apply (strictly_order_preserving (cast Z AQ)).
47 reflexivity.
48 Qed.
49
50 Lemma arctanStream_correct : ∀ p : positive,
51 Str_pth _ (arctanStream (AQtoQ num / AQtoQ den))
52 p (1%positive, AQtoQ num / AQtoQ den)
53 == let (_, r) := iterate _ (fS ARarctanStream) p (1%positive, (num, den)) in
54 AQtoQ (fst r) / AQtoQ (snd r).
55 Proof.
56 assert (forall n:Z, AQtoQ (ZtoAQ n) == (n#1)).
57 { intro n. destruct n as [|n|n].
58 pose proof (rings.preserves_0 (f:=cast Z AQ)). rewrite H5. clear H5.
59 rewrite rings.preserves_0. reflexivity.
60 apply ZtoQ. change (Z.neg n) with (-Z.pos n)%Z.
61 pose proof (rings.preserves_negate (f:=cast Z AQ)).
62 rewrite H5. clear H5. rewrite rings.preserves_negate.
63 rewrite ZtoQ. reflexivity. }
64 apply Pos.peano_ind.
65 - unfold Str_pth, iterate, arctanStream, snd.
66 rewrite Qred_correct. simpl.
67 do 6 rewrite rings.preserves_mult.
68 rewrite rings.preserves_negate.
69 rewrite H5, H5.
70 unfold dec_recip, stdlib_rationals.Q_recip.
71 unfold mult, stdlib_rationals.Q_mult.
72 unfold negate, stdlib_rationals.Q_opp.
73 rewrite Qmult_1_r.
74 change (1#3) with (/3)%Q.
75 unfold Qdiv.
76 do 3 rewrite Qinv_mult_distr.
77 do 3 rewrite Qmult_assoc.
78 apply Qmult_comp. 2: reflexivity.
79 do 2 rewrite Qmult_assoc.
80 apply Qmult_comp. 2: reflexivity.
81 ring.
82 - intros p IHp. unfold Str_pth. unfold Str_pth in IHp.
83 rewrite iterate_succ, iterate_succ.
84 pose proof (arctanStream_fst (AQtoQ num / AQtoQ den) p) as H7.
85 unfold dec_recip, stdlib_rationals.Q_recip.
86 unfold dec_recip, stdlib_rationals.Q_recip in IHp.
87 unfold mult, stdlib_rationals.Q_mult.
88 unfold mult, stdlib_rationals.Q_mult in IHp.
89 unfold Qdiv in H7. unfold Qdiv.
90 unfold Qdiv in IHp.
91 unfold Q_as_MetricSpace, msp_car.
92 unfold Q_as_MetricSpace, msp_car in IHp.
93 destruct (iterate _ (arctanStream (AQtoQ num * / AQtoQ den)%Q) p
94 (1%positive, (AQtoQ num * / AQtoQ den)%Q)).
95 simpl in H7. simpl in IHp. subst p0.
96 unfold arctanStream, snd, fst. rewrite Qred_correct.
97 rewrite IHp. clear IHp.
98 pose proof (fS_fst ARarctanStream p (num, den)) as H6.
99 destruct (iterate _ (fS ARarctanStream) p (1%positive, (num, den))) as [p0 p1].
100 simpl in H6. subst p0. unfold ARarctanStream, fS.
101 simpl (fst (Pos.succ p, p1)).
102 simpl (snd (Pos.succ p, p1)).
103 replace (Pos.pred (Pos.succ p)~0) with (p~1)%positive.
104 do 6 rewrite rings.preserves_mult.
105 rewrite rings.preserves_negate.
106 unfold mult, stdlib_rationals.Q_mult.
107 unfold negate, stdlib_rationals.Q_opp.
108 rewrite ZtoQ, ZtoQ.
109 do 3 rewrite Qinv_mult_distr.
110 setoid_replace (Z.pos p~1 # 2 + p~1)%Q
111 with ((Z.pos p~1 # 1) * / (Z.pos (Pos.succ p)~1 # 1))%Q.
112 ring.
113 unfold Qinv, Qeq, Qmult, Qnum, Qden.
114 rewrite Pos.mul_1_l, Z.mul_1_r.
115 replace (2 + p~1)%positive with ((Pos.succ p)~1)%positive.
116 reflexivity.
117 change (p~1)%positive with (2*p+1)%positive.
118 change ((Pos.succ p)~1)%positive with (2*Pos.succ p+1)%positive.
119 rewrite Pplus_one_succ_l.
120 rewrite Pos.mul_add_distr_l. reflexivity.
121 rewrite Pplus_one_succ_l.
122 change (p~1)%positive with (2*p+1)%positive.
123 change ((1+p)~0)%positive with (2*(1+p))%positive.
124 rewrite Pos.mul_add_distr_l.
125 rewrite Pos.pred_sub.
126 rewrite (Pos.add_comm (2*1)).
127 rewrite <- Pos.add_sub_assoc. reflexivity. reflexivity.
128 Qed.
129
130 Lemma AQarctan_small_Qprf : -1 < AQtoQ num / AQtoQ den < 1.
131 Proof.
132 split.
133 - apply Qlt_shift_div_l.
134 pose proof (rings.preserves_0 (f:=cast AQ Q)).
135 rewrite <- H5.
136 apply (strictly_order_preserving (cast AQ Q)), dpos.
137 setoid_replace (-1 * AQtoQ den) with (-AQtoQ den) by reflexivity.
138 rewrite <- rings.preserves_negate.
139 apply (strictly_order_preserving (cast AQ Q)), Pnd.
140 - apply Qlt_shift_div_r.
141 pose proof (rings.preserves_0 (f:=cast AQ Q)).
142 rewrite <- H5.
143 apply (strictly_order_preserving (cast AQ Q)), dpos.
144 rewrite Qmult_1_l.
145 apply (strictly_order_preserving (cast AQ Q)), Pnd.
146 Qed.
147
148 Definition AQarctan_small : msp_car AR
149 := CRtoAR (inject_Q_CR (AQtoQ num / AQtoQ den))
150 + AltSeries ARarctanStream arctanStream_pos
151 positive (arctanStream (AQtoQ num / AQtoQ den))
152 (num,den) (xH,AQtoQ num / AQtoQ den) arctanStream_correct _
153 (arctanStream_alt (widen_interval AQarctan_small_Qprf))
154 dpos (arctanStream_zl (widen_interval AQarctan_small_Qprf)).
155
156 Lemma AQarctan_small_correct :
157 'AQarctan_small = rational_arctan_small (widen_interval AQarctan_small_Qprf).
158 Proof.
159 unfold AQarctan_small, rational_arctan_small.
160 rewrite ARtoCR_preserves_plus.
161 apply ucFun2_wd.
162 pose proof CRAR_id.
163 unfold cast. unfold cast in H5.
164 rewrite H5. reflexivity.
165 apply AltSeries_correct.
166 Qed.
167
168 End ARarctan_small.