| 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 *) |