Debian Codegraph @

reals/fast/CRpi_slow.v

raw
1 (*
2 Copyright © 2006-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
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 CoRN.stdlib_omissions.Q.
33
34 (* Backwards compatibility for Hint Rewrite locality attributes *)
35 Set Warnings "-unsupported-attributes".
36
37 Set Implicit Arguments.
38
39 Local Open Scope Q_scope.
40 Local Open Scope uc_scope.
41
42 Opaque inj_Q CR.
43
44 Section Pi.
45
46 (**
47 ** Pi (alternate)
48 (Please import CRpi instead)
49
50 This version is slower to compute than CRpi_fast; however it is faster to
51 compile.
52
53 Pi is defined as
54
55 68*arctan(1/23) + 32*arctan(1/182) + 40*arctan(1/5118) + 20*arctan(1/6072).
56 *)
57
58 Lemma small_per_23 : (-(1#1) < 1#23 < 1)%Q.
59 Proof. split; reflexivity. Qed.
60
61 Lemma small_per_182 : (-(1#1) < 1#182 < 1)%Q.
62 Proof. split; reflexivity. Qed.
63
64 Lemma small_per_5118 : (-(1#1) < 1#5118 < 1)%Q.
65 Proof. split; reflexivity. Qed.
66
67 Lemma small_per_6072 : (-(1#1) < 1#6072 < 1)%Q.
68 Proof. split; reflexivity. Qed.
69
70 Definition r_pi (r:Q) : CR :=
71 ((scale (68%Z*r) (rational_arctan_small (widen_interval small_per_23)) +
72 scale (32%Z*r) (rational_arctan_small (widen_interval small_per_182))) +
73 (scale (40%Z*r) (rational_arctan_small (widen_interval small_per_5118)) +
74 scale (20%Z*r) (rational_arctan_small (widen_interval small_per_6072))))%CR.
75
76 (** To prove that pi is is correct we repeatedly use the arctan sum law.
77 The problem is that the arctan sum law only works for input between -1
78 and 1. We use reflect to show that our use of arctan sum law always
79 satifies this restriction. *)
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, {True} + {(nring n)[*]ArcTan (inj_Q _ x)[=]ArcTan (inj_Q _ (iter_nat n _ (f x) 0))}.
177 Proof.
178 intros x Hx.
179 induction n.
180 right.
181 abstract ( rstepl ([0]:IR); (stepl (ArcTan [0]); [| now apply ArcTan_zero]); apply ArcTan_wd;
182 apply eq_symmetric; apply (inj_Q_nring IR 0)).
183 simpl.
184 destruct (IHn) as [H|H].
185 left; constructor.
186 set (y:=(iter_nat n Q (f x) 0)) in *.
187 destruct (Qlt_le_dec_fast 1 y) as [_|Y0].
188 left; constructor.
189 destruct (Qlt_le_dec_fast y (-(1))) as [_|Y1].
190 left; constructor.
191 destruct (Qeq_dec (1-x*y) 0) as [_|Y2].
192 left; constructor.
193 right.
194 abstract ( rstepl (ArcTan (inj_Q IR x)[+](nring n[*]ArcTan (inj_Q IR x))); csetoid_rewrite H;
195 apply ArcTan_plus_ArcTan_Q; try assumption; split; assumption).
196 Defined.
197
198 Lemma reflect_right : forall A B (x:{A}+{B}), (match x with left _ => False | right _ => True end) -> B.
199 Proof.
200 intros A B x.
201 elim x.
202 contradiction.
203 trivial.
204 Qed.
205
206 Lemma Pi_Formula :
207 (((nring 17)[*]ArcTan (inj_Q IR (1 / 23%Z))[+]
208 (nring 8)[*]ArcTan (inj_Q IR (1 / 182%Z))[+]
209 (nring 10)[*]ArcTan (inj_Q IR (1 / 5118%Z))[+]
210 (nring 5)[*]ArcTan (inj_Q IR (1 / 6072%Z)))[=]
211 Pi[/]FourNZ).
212 Proof.
213 assert (H0:-(1) <= (1/(23%Z)) <= 1).
214 split; discriminate.
215 assert (H1:-(1) <= (1/(182%Z)) <= 1).
216 split; discriminate.
217 assert (H2:-(1) <= (1/(5118%Z)) <= 1).
218 split; discriminate.
219 assert (H3:-(1) <= (1/(6072%Z)) <= 1).
220 split; discriminate.
221 set (y0:=(iter_nat 17 _ (f (1/23%Z)) 0)).
222 set (y1:=(iter_nat 8 _ (f (1/182%Z)) 0)).
223 set (y2:=(iter_nat 10 _ (f (1/5118%Z)) 0)).
224 set (y3:=(iter_nat 5 _ (f (1/6072%Z)) 0)).
225 rstepl (nring 17[*]ArcTan (inj_Q IR (1 / 23%Z))[+]
226 nring 8[*]ArcTan (inj_Q IR (1 / 182%Z))[+]
227 (nring 10[*]ArcTan (inj_Q IR (1 / 5118%Z))[+]
228 nring 5[*]ArcTan (inj_Q IR (1 / 6072%Z)))).
229 csetoid_replace ((nring 17)[*]ArcTan (inj_Q IR (1 / 23%Z))) (ArcTan (inj_Q IR y0));
230 [|apply (reflect_right (ArcTan_multiple H0 17)); vm_compute; constructor].
231 csetoid_replace ((nring 8)[*]ArcTan (inj_Q IR (1 / 182%Z))) (ArcTan (inj_Q IR y1));
232 [|apply (reflect_right (ArcTan_multiple H1 8)); vm_compute; constructor].
233 csetoid_replace ((nring 10)[*]ArcTan (inj_Q IR (1 / 5118%Z))) (ArcTan (inj_Q IR y2));
234 [|apply (reflect_right (ArcTan_multiple H2 10)); vm_compute; constructor].
235 csetoid_replace ((nring 5)[*]ArcTan (inj_Q IR (1 / 6072%Z))) (ArcTan (inj_Q IR y3));
236 [|apply (reflect_right (ArcTan_multiple H3 5)); vm_compute; constructor].
237 vm_compute in y0.
238 vm_compute in y1.
239 vm_compute in y2.
240 vm_compute in y3.
241 csetoid_replace (ArcTan (inj_Q IR y0)[+]ArcTan (inj_Q IR y1)) (ArcTan (inj_Q IR (f y0 y1)));
242 [|apply ArcTan_plus_ArcTan_Q; try split; vm_compute; discriminate].
243 csetoid_replace (ArcTan (inj_Q IR y2)[+]ArcTan (inj_Q IR y3)) (ArcTan (inj_Q IR (f y2 y3)));
244 [|apply ArcTan_plus_ArcTan_Q; try split; vm_compute; discriminate].
245 set (z0 := (f y0 y1)).
246 set (z1 := (f y2 y3)).
247 vm_compute in z0.
248 vm_compute in z1.
249 csetoid_replace (ArcTan (inj_Q IR z0)[+]ArcTan (inj_Q IR z1)) (ArcTan (inj_Q IR (f z0 z1)));
250 [|apply ArcTan_plus_ArcTan_Q; try split; vm_compute; discriminate].
251 set (z3:= (f z0 z1)).
252 vm_compute in z3.
253 eapply eq_transitive;[|apply ArcTan_one].
254 apply ArcTan_wd.
255 rstepr (nring 1:IR).
256 apply (inj_Q_nring IR 1).
257 Qed.
258
259 Lemma r_pi_correct : forall r,
260 (r_pi r == IRasCR ((inj_Q IR r)[*]Pi))%CR.
261 Proof.
262 intros r.
263 unfold r_pi.
264 repeat rewrite <- (CRmult_scale).
265 setoid_replace ((68*r)) with ((4*r*17)) by (simpl; ring).
266 setoid_replace (32*r) with (4*r*8) by (simpl; ring).
267 setoid_replace (40*r) with (4*r*10) by (simpl; ring).
268 setoid_replace (20*r) with (4*r*5) by (simpl; ring).
269 repeat rewrite <- CRmult_Qmult.
270 transitivity ('4 * 'r *(' 17 * rational_arctan_small (widen_interval small_per_23) +
271 ' 8 * rational_arctan_small (widen_interval small_per_182) + (' 10 * rational_arctan_small (widen_interval small_per_5118) +
272 ' 5 * rational_arctan_small (widen_interval small_per_6072))))%CR.
273 ring.
274 repeat rewrite rational_arctan_small_correct.
275 repeat rewrite <- IR_inj_Q_as_CR.
276 repeat (rewrite <- IR_mult_as_CR || rewrite <- IR_plus_as_CR).
277 apply IRasCR_wd.
278 rstepr (Four[*]inj_Q IR r[*]Pi[/]FourNZ).
279 apply mult_wd.
280 apply mult_wdl.
281 apply (inj_Q_nring IR 4).
282 eapply eq_transitive;[|apply Pi_Formula].
283 rstepr (nring 17[*]ArcTan (inj_Q IR (1 / 23%Z))[+]
284 nring 8[*]ArcTan (inj_Q IR (1 / 182%Z))[+]
285 (nring 10[*]ArcTan (inj_Q IR (1 / 5118%Z))[+]
286 nring 5[*]ArcTan (inj_Q IR (1 / 6072%Z)))).
287 repeat apply bin_op_wd_unfolded; try apply eq_reflexive.
288 apply (inj_Q_nring IR 17).
289 apply (inj_Q_nring IR 8).
290 apply (inj_Q_nring IR 10).
291 apply (inj_Q_nring IR 5).
292 Qed.
293
294 Definition CRpi : CR := (r_pi 1).
295
296 Lemma CRpi_correct : (IRasCR Pi == CRpi)%CR.
297 Proof.
298 unfold CRpi.
299 rewrite -> r_pi_correct.
300 apply IRasCR_wd.
301 rstepl ((nring 1)[*]Pi).
302 apply mult_wdl.
303 apply eq_symmetric.
304 apply (inj_Q_nring IR 1).
305 Qed.
306
307 End Pi.
308 (* begin hide *)
309 #[global]
310 Hint Rewrite CRpi_correct : IRtoCR.
311 (* end hide *)