Debian Codegraph @

reals/fast/CRpi_fast.v

raw
1 (*
2 Copyright © 2006 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
22 Require Import CoRN.algebra.RSetoid.
23 Require Import CoRN.metric2.Metric.
24 Require Import CoRN.metric2.UniformContinuity.
25 Require Export CoRN.reals.fast.CRArith.
26 Require Import CoRN.reals.fast.CRIR.
27 Require Import CoRN.reals.Q_in_CReals.
28 Require Import CoRN.model.totalorder.QMinMax.
29 Require Import CoRN.reals.fast.CRarctan_small.
30 Require Import CoRN.transc.MoreArcTan.
31 Require Import CoRN.tactics.CornTac.
32 Require Import MathClasses.interfaces.abstract_algebra.
33 Require Import CoRN.stdlib_omissions.Q.
34
35 (* Backwards compatibility for Hint Rewrite locality attributes *)
36 Set Warnings "-unsupported-attributes".
37
38 Set Implicit Arguments.
39
40 Local Open Scope Q_scope.
41 Local Open Scope uc_scope.
42
43 Opaque inj_Q CR.
44 (**
45 ** Pi
46 (Please import CRpi instead)
47
48 This version is faster to compute than CRpi_slow; however it is slower to
49 compile.
50
51 Pi is defined as
52
53 176*arctan(1/57) + 28*arctan(1/239) - 48*arctan(1/682) + 96*arctan(1/12943).
54 *)
55 Section Pi.
56
57 Lemma small_per_57 : (-1 < (1#(57%positive)) < 1)%Q.
58 Proof. split; easy. Qed.
59
60 Lemma small_per_239 : (-1 < (1#(239%positive)) < 1)%Q.
61 Proof. split; easy. Qed.
62
63 Lemma small_per_682 : (-1 < (1#(682%positive)) < 1)%Q.
64 Proof. split; easy. Qed.
65
66 Lemma small_per_12943 : (-1 < (1#(12943%positive)) < 1)%Q.
67 Proof. split; easy. Qed.
68
69 Definition r_pi (r:Q) : CR :=
70 ((scale (176%Z*r) (rational_arctan_small (widen_interval small_per_57)) +
71 scale (28%Z*r) (rational_arctan_small (widen_interval small_per_239))) +
72 (scale (-(48%Z)*r) (rational_arctan_small (widen_interval small_per_682)) +
73 scale (96%Z*r) (rational_arctan_small (widen_interval small_per_12943))))%CR.
74
75 (** To prove that pi is is correct we repeatedly use the arctan sum law.
76 The problem is that the arctan sum law only works for input between -1
77 and 1. We use reflect to show that our use of arctan sum law always
78 satifies this restriction. *)
79
80 Let f (a b:Q) : Q :=
81 let (x,y) := a in
82 let (z,w) := b in
83 Qred ((x*w + y*z)%Z/(y*w-x*z)%Z).
84
85 Lemma f_char : forall a b, f a b == (a+b)/(1-a*b).
86 Proof.
87 intros [x y] [w z].
88 unfold f.
89 rewrite -> Qred_correct.
90 destruct (Z.eq_dec (y*z) (x*w)) as [H|H].
91 unfold Qmult.
92 simpl ((Qnum (x # y) * Qnum (w # z) # Qden (x # y) * Qden (w # z))).
93 repeat rewrite <- H.
94 replace (y * z - y * z)%Z with 0%Z by ring.
95 setoid_replace (1-(y * z # y * z)) with 0.
96 change ((x * z + y * w)%Z * 0 == ((x # y) + (w # z)) * 0).
97 ring.
98 rewrite -> (Qmake_Qdiv (y*z)).
99 change (1 - (y * z)%positive / (y * z)%positive == 0).
100 field; discriminate.
101 unfold Zminus.
102 repeat rewrite -> injz_plus.
103 change (((x * Zpos z) + (Zpos y * w)) / (Zpos y * Zpos z - x * w) == ((x # y) + (w # z)) / (1 - (x #y)*(w # z))).
104 repeat rewrite -> Qmake_Qdiv.
105 field.
106 repeat split; try discriminate.
107 cut (~(y * z)%Z == (x * w)%Z).
108 intros X Y.
109 apply X.
110 replace RHS with ((x * w)%Z + 0) by simpl; ring.
111 rewrite <- Y.
112 change ((y * z) == (x * w) + (y * z - x * w)).
113 ring.
114 intros X; apply H.
115 unfold Qeq in X.
116 simpl in X.
117 rewrite Pmult_1_r in X.
118 change ((y * z)%Z = (x * w * 1)%Z) in X.
119 rewrite X.
120 ring.
121 Qed.
122
123 Lemma ArcTan_plus_ArcTan_Q : forall x y, -(1) <= x <= 1 -> -(1) <= y <= 1 -> ~1-x*y==0 ->
124 (ArcTan (inj_Q _ x)[+]ArcTan (inj_Q _ y)[=]ArcTan (inj_Q _ (f x y))).
125 Proof.
126 intros x y [Hx0 Hx1] [Hy0 Hy1] H.
127 assert (X:forall z, -(1) <= z -> [--][1][<=]inj_Q IR z).
128 intros z Hz.
129 stepl ((inj_Q IR (-(1)))).
130 apply inj_Q_leEq; assumption.
131 eapply eq_transitive.
132 apply (inj_Q_inv IR (1)).
133 apply un_op_wd_unfolded.
134 rstepr (nring 1:IR).
135 apply (inj_Q_nring IR 1).
136 assert (X0:forall z, z <= 1 -> inj_Q IR z[<=][1]).
137 intros z Hz.
138 stepr ((inj_Q IR ((1)))).
139 apply inj_Q_leEq; assumption.
140 rstepr (nring 1:IR).
141 apply (inj_Q_nring IR 1).
142 assert ([1][-](inj_Q IR x)[*](inj_Q IR y)[#][0]).
143 stepl (inj_Q IR (1[-]x[*]y)).
144 (stepr (inj_Q IR [0]); [| now apply (inj_Q_nring IR 0)]).
145 apply inj_Q_ap; assumption.
146 eapply eq_transitive.
147 apply inj_Q_minus.
148 apply bin_op_wd_unfolded.
149 rstepr (nring 1:IR); apply (inj_Q_nring IR 1).
150 apply un_op_wd_unfolded.
151 apply inj_Q_mult.
152 apply eq_transitive with (ArcTan (inj_Q IR x[+]inj_Q IR y[/]([1][-]inj_Q IR x[*]inj_Q IR y)[//]X1)).
153 apply ArcTan_plus_ArcTan; first [apply X; assumption |apply X0; assumption].
154 apply ArcTan_wd.
155 stepl (inj_Q IR ((x[+]y)/([1][-]x*y))).
156 apply inj_Q_wd.
157 simpl.
158 symmetry.
159 apply f_char.
160 assert (H0:(inj_Q IR ([1][-]x * y))[#][0]).
161 (stepr (inj_Q IR 0); [| now apply (inj_Q_nring IR 0)]).
162 apply inj_Q_ap; assumption.
163 apply eq_transitive with (inj_Q IR (x[+]y)[/]inj_Q IR ([1][-]x * y)[//]H0).
164 apply (inj_Q_div).
165 apply div_wd.
166 apply inj_Q_plus.
167 eapply eq_transitive.
168 apply inj_Q_minus.
169 apply bin_op_wd_unfolded.
170 rstepr (nring 1:IR).
171 apply (inj_Q_nring IR 1).
172 apply un_op_wd_unfolded.
173 apply inj_Q_mult.
174 Qed.
175
176 Definition ArcTan_multiple : forall x, -(1) <= x <= 1 -> forall n,
177 sumbool True ((nring n)[*]ArcTan (inj_Q _ x)[=]ArcTan (inj_Q _ (iter_nat n _ (f x) 0))).
178 Proof.
179 intros x Hx.
180 induction n.
181 right.
182 abstract ( rstepl ([0]:IR); (stepl (ArcTan [0]); [| now apply ArcTan_zero]); apply ArcTan_wd;
183 apply eq_symmetric; apply (inj_Q_nring IR 0)).
184 simpl.
185 destruct (IHn) as [H|H].
186 left; constructor.
187 set (y:=(iter_nat n Q (f x) 0)) in *.
188 destruct (Qlt_le_dec_fast 1 y) as [_|Y0].
189 left; constructor.
190 destruct (Qlt_le_dec_fast y (-(1))) as [_|Y1].
191 left; constructor.
192 destruct (Qeq_dec (1-x*y) 0) as [_|Y2].
193 left; constructor.
194 right.
195 abstract ( rstepl (ArcTan (inj_Q IR x)[+](nring n[*]ArcTan (inj_Q IR x))); csetoid_rewrite H;
196 apply ArcTan_plus_ArcTan_Q; try assumption; split; assumption).
197 Defined.
198
199 Lemma reflect_right : forall A B (x:{A}+{B}), (match x with left _ => False | right _ => True end) -> B.
200 Proof.
201 intros A B x.
202 elim x.
203 contradiction.
204 trivial.
205 Qed.
206
207 Lemma Pi_Formula :
208 (((nring 44)[*]ArcTan (inj_Q IR (1 / 57%Z))[-]
209 (nring 12)[*]ArcTan (inj_Q IR (1 / 682%Z))[+]
210 (nring 7)[*]ArcTan (inj_Q IR (1 / 239%Z))[+]
211 (nring 24)[*]ArcTan (inj_Q IR (1 / 12943%Z)))[=]
212 Pi[/]FourNZ).
213 Proof.
214 assert (H0:-(1) <= (1/(57%Z)) <= 1).
215 split; discriminate.
216 assert (H1:-(1) <= (1/(239%Z)) <= 1).
217 split; discriminate.
218 assert (H2:-(1) <= (1/(682%Z)) <= 1).
219 split; discriminate.
220 assert (H3:-(1) <= (1/(12943%Z)) <= 1).
221 split; discriminate.
222 set (y0:=(iter_nat 44 _ (f (1/57%Z)) 0)).
223 set (y1:=(iter_nat 7 _ (f (1/239%Z)) 0)).
224 set (y2:=(iter_nat 12 _ (f (1/682%Z)) 0)).
225 set (y3:=(iter_nat 24 _ (f (1/12943%Z)) 0)).
226 rstepl (nring 44[*]ArcTan (inj_Q IR (1 / 57%Z))[+]
227 [--](nring 12[*]ArcTan (inj_Q IR (1 / 682%Z)))[+]
228 (nring 7[*]ArcTan (inj_Q IR (1 / 239%Z))[+]
229 nring 24[*]ArcTan (inj_Q IR (1 / 12943%Z)))).
230 csetoid_replace ((nring 44)[*]ArcTan (inj_Q IR (1 / 57%Z)))
231 (ArcTan (inj_Q IR y0)); [|apply: (reflect_right (ArcTan_multiple H0 44)); now vm_compute].
232 csetoid_replace ((nring 7)[*]ArcTan (inj_Q IR (1 / 239%Z))) (ArcTan (inj_Q IR y1));
233 [|apply: (reflect_right (ArcTan_multiple H1 7)); now vm_compute].
234 csetoid_replace ((nring 12)[*]ArcTan (inj_Q IR (1 / 682%Z))) (ArcTan (inj_Q IR y2));
235 [|apply: (reflect_right (ArcTan_multiple H2 12)); now vm_compute].
236 csetoid_replace ((nring 24)[*]ArcTan (inj_Q IR (1 / 12943%Z))) (ArcTan (inj_Q IR y3));
237 [|apply: (reflect_right (ArcTan_multiple H3 24)); now vm_compute].
238 vm_compute in y0.
239 vm_compute in y1.
240 vm_compute in y2.
241 vm_compute in y3.
242 csetoid_replace ([--](ArcTan (inj_Q IR y2))) (ArcTan (inj_Q IR (-y2)));
243 [|csetoid_rewrite_rev (ArcTan_inv (inj_Q IR y2));
244 apply ArcTan_wd; apply eq_symmetric; apply (inj_Q_inv IR y2)].
245 csetoid_replace (ArcTan (inj_Q IR y0)[+]ArcTan (inj_Q IR (-y2))) (ArcTan (inj_Q IR (f y0 (-y2))));
246 [|apply ArcTan_plus_ArcTan_Q; try split; now vm_compute].
247 csetoid_replace (ArcTan (inj_Q IR y1)[+]ArcTan (inj_Q IR y3)) (ArcTan (inj_Q IR (f y1 y3)));
248 [|apply ArcTan_plus_ArcTan_Q; try split; now vm_compute].
249 set (z0 := (f y0 (-y2))).
250 set (z1 := (f y1 y3)).
251 vm_compute in z0.
252 vm_compute in z1.
253 csetoid_replace (ArcTan (inj_Q IR z0)[+]ArcTan (inj_Q IR z1)) (ArcTan (inj_Q IR (f z0 z1)));
254 [|apply ArcTan_plus_ArcTan_Q; try split; now vm_compute].
255 set (z3:= (f z0 z1)).
256 vm_compute in z3.
257 eapply eq_transitive;[|apply ArcTan_one].
258 apply ArcTan_wd.
259 rstepr (nring 1:IR).
260 apply (inj_Q_nring IR 1).
261 Qed.
262
263 Lemma r_pi_correct : forall r, (r_pi r == IRasCR ((inj_Q IR r)[*]Pi))%CR.
264 Proof.
265 intros r.
266 unfold r_pi.
267 repeat rewrite <- (CRmult_scale).
268 setoid_replace (176%Z* r) with (4%Z * r * 44%Z) by (simpl; ring).
269 setoid_replace (28%Z * r) with (4%Z * r * 7%Z) by (simpl; ring).
270 setoid_replace (-(48)%Z * r) with (4%Z * r * -(12)%Z) by (simpl; ring).
271 setoid_replace (96%Z * r) with (4%Z * r * 24%Z) by (simpl; ring).
272 repeat rewrite <- CRmult_Qmult.
273 transitivity ('4%Z * 'r *(' 44%Z * rational_arctan_small (widen_interval small_per_57) +
274 ' 7%Z * rational_arctan_small (widen_interval small_per_239) +
275 (' (-12)%Z * rational_arctan_small (widen_interval small_per_682) +
276 ' 24%Z * rational_arctan_small (widen_interval small_per_12943))))%CR.
277 ring.
278 repeat rewrite rational_arctan_small_correct.
279 repeat rewrite <- IR_inj_Q_as_CR.
280 repeat (rewrite <- IR_mult_as_CR || rewrite <- IR_plus_as_CR).
281 apply IRasCR_wd.
282 rstepr (Four[*]inj_Q IR r[*]Pi[/]FourNZ).
283 apply mult_wd.
284 apply mult_wdl.
285 apply (inj_Q_nring IR 4).
286 eapply eq_transitive;[|apply Pi_Formula].
287 rstepr (nring 44[*]ArcTan (inj_Q IR (1 / 57%Z))[+]
288 nring 7[*]ArcTan (inj_Q IR (1 / 239%Z))[+]
289 (([--](nring 12))[*]ArcTan (inj_Q IR (1 / 682%Z))[+]
290 nring 24[*]ArcTan (inj_Q IR (1 / 12943%Z)))).
291 repeat apply bin_op_wd_unfolded; try apply eq_reflexive.
292 apply (inj_Q_nring IR 44).
293 apply (inj_Q_nring IR 7).
294 eapply eq_transitive.
295 apply (inj_Q_inv IR (nring 12)).
296 csetoid_rewrite (inj_Q_nring IR 12).
297 apply eq_reflexive.
298 apply (inj_Q_nring IR 24).
299 Qed.
300
301 Global Instance: Proper (Qeq ==> msp_eq) r_pi.
302 Proof.
303 intros ? ? E. unfold r_pi.
304 apply ucFun2_wd.
305 apply ucFun2_wd.
306 apply Cmap_wd. 2: reflexivity. simpl.
307 split. discriminate. intro q. simpl.
308 unfold Qmetric.Qball, Qmetric.QAbsSmall.
309 rewrite E. unfold Qminus. rewrite Qplus_opp_r.
310 split; discriminate.
311 apply Cmap_wd. 2: reflexivity. simpl.
312 split. discriminate. intro q. simpl.
313 unfold Qmetric.Qball, Qmetric.QAbsSmall.
314 rewrite E. unfold Qminus. rewrite Qplus_opp_r.
315 split; discriminate.
316 apply ucFun2_wd.
317 apply Cmap_wd. 2: reflexivity. simpl.
318 split. discriminate. intro q. simpl.
319 unfold Qmetric.Qball, Qmetric.QAbsSmall.
320 rewrite E. unfold Qminus. rewrite Qplus_opp_r.
321 split; discriminate.
322 apply Cmap_wd. 2: reflexivity. simpl.
323 split. discriminate. intro q. simpl.
324 unfold Qmetric.Qball, Qmetric.QAbsSmall.
325 rewrite E. unfold Qminus. rewrite Qplus_opp_r.
326 split; discriminate.
327 Qed.
328
329 Definition CRpi : CR := (r_pi 1).
330
331 Lemma CRpi_correct : (IRasCR Pi == CRpi)%CR.
332 Proof.
333 unfold CRpi.
334 rewrite -> r_pi_correct.
335 apply IRasCR_wd.
336 rstepl ((nring 1)[*]Pi).
337 apply mult_wdl.
338 apply eq_symmetric.
339 apply (inj_Q_nring IR 1).
340 Qed.
341
342 End Pi.
343 (* begin hide *)
344 #[global]
345 Hint Rewrite CRpi_correct : IRtoCR.
346 (* end hide *)