| 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.metric2.Metric. |
| 23 |
Require Import CoRN.metric2.UniformContinuity. |
| 24 |
Require Import CoRN.model.totalorder.QMinMax. |
| 25 |
Require Import CoRN.reals.fast.CRAlternatingSum. |
| 26 |
Require Import CoRN.reals.fast.CRAlternatingSum_alg. |
| 27 |
Require Import CoRN.reals.fast.CRstreams. |
| 28 |
Require Export CoRN.reals.fast.CRArith. |
| 29 |
Require Import CoRN.reals.fast.CRIR. |
| 30 |
Require Import CoRN.reals.iso_CReals. |
| 31 |
From Coq Require Import Qpower. |
| 32 |
Require Import CoRN.algebra.COrdFields2. |
| 33 |
Require Import CoRN.model.ordfields.Qordfield. |
| 34 |
Require Import CoRN.transc.PowerSeries. |
| 35 |
Require Import CoRN.reals.fast.CRpower. |
| 36 |
Require Import CoRN.transc.Exponential. |
| 37 |
Require Import CoRN.transc.RealPowers. |
| 38 |
Require Import CoRN.reals.fast.Compress. |
| 39 |
Require Import CoRN.reals.fast.ModulusDerivative. |
| 40 |
Require Import CoRN.reals.fast.ContinuousCorrect. |
| 41 |
Require Import CoRN.reals.fast.CRsign. |
| 42 |
Require Import CoRN.reals.Q_in_CReals. |
| 43 |
From Coq Require Import Qabs. |
| 44 |
From Coq Require Import Qround. |
| 45 |
Require Import CoRN.tactics.CornTac. |
| 46 |
Require Import MathClasses.theory.int_pow. |
| 47 |
Require Import MathClasses.interfaces.abstract_algebra. |
| 48 |
|
| 49 |
(* Backwards compatibility for Hint Rewrite locality attributes *) |
| 50 |
Set Warnings "-unsupported-attributes". |
| 51 |
|
| 52 |
Set Implicit Arguments. |
| 53 |
|
| 54 |
Opaque CR. |
| 55 |
Opaque Exp. |
| 56 |
|
| 57 |
Local Open Scope Q_scope. |
| 58 |
Local Open Scope uc_scope. |
| 59 |
|
| 60 |
Lemma Qpower_le_1 : forall (a : Q) (p : positive), |
| 61 |
0 <= a <= 1 -> 0 <= a ^ p <= 1. |
| 62 |
Proof. |
| 63 |
split. |
| 64 |
- apply Qpower_pos, H. |
| 65 |
- revert p. apply Pos.peano_ind. apply H. |
| 66 |
intros p Hp. unfold Qpower. |
| 67 |
rewrite <- Pos.add_1_l, Qpower_plus_positive. |
| 68 |
apply (Qle_trans _ (1*Qpower_positive a p)). |
| 69 |
apply Qmult_le_compat_r. apply H. |
| 70 |
apply (Qpower_pos a p), H. |
| 71 |
rewrite Qmult_1_l. apply Hp. |
| 72 |
Qed. |
| 73 |
|
| 74 |
Lemma Qabs_Qpower : forall (a:Q) (p:positive), |
| 75 |
Qabs (a ^ p) == (Qabs a) ^ p. |
| 76 |
Proof. |
| 77 |
intro a. apply Pos.peano_ind. |
| 78 |
- reflexivity. |
| 79 |
- intros p Hp. |
| 80 |
simpl. rewrite <- Pos.add_1_l. |
| 81 |
rewrite Qpower_plus_positive. |
| 82 |
rewrite Qabs_Qmult, Hp. clear Hp. |
| 83 |
rewrite Qpower_plus_positive. reflexivity. |
| 84 |
Qed. |
| 85 |
|
| 86 |
Lemma Qinv_le_compat : forall (a b : Q), |
| 87 |
0 < a -> a <= b -> /b <= /a. |
| 88 |
Proof. |
| 89 |
intros. apply Qle_shift_inv_l. exact H. |
| 90 |
apply (Qmult_le_l _ _ b). |
| 91 |
exact (Qlt_le_trans _ a _ H H0). |
| 92 |
rewrite Qmult_1_r, Qmult_assoc. |
| 93 |
rewrite Qmult_inv_r. |
| 94 |
rewrite Qmult_1_l. exact H0. |
| 95 |
intro abs. rewrite abs in H0. |
| 96 |
apply (Qlt_irrefl 0). |
| 97 |
exact (Qlt_le_trans _ _ _ H H0). |
| 98 |
Qed. |
| 99 |
|
| 100 |
Lemma fact_power_2 : forall n:nat, (2^pred n <= fact n)%nat. |
| 101 |
Proof. |
| 102 |
induction n. |
| 103 |
- apply Nat.le_refl. |
| 104 |
- apply (Nat.le_trans _ ((S n) * 2^pred n)). |
| 105 |
2: apply Nat.mul_le_mono_nonneg_l; [apply Nat.le_0_l | exact IHn]. |
| 106 |
clear IHn. destruct n. simpl. apply Nat.le_refl. |
| 107 |
simpl. |
| 108 |
apply Nat.add_le_mono_l, Nat.add_le_mono_l, Nat.le_0_l. |
| 109 |
Qed. |
| 110 |
|
| 111 |
Lemma Qceiling_fact_le : forall q:Q, |
| 112 |
0 < q -> |
| 113 |
q <= |
| 114 |
Pos.of_nat (fact (Pos.to_nat (Pos.succ (Z.to_pos (Z.log2_up (Qceiling q)))))) |
| 115 |
# 1. |
| 116 |
Proof. |
| 117 |
intros q H. |
| 118 |
apply (Qle_trans _ _ _ (Qle_ceiling q)). |
| 119 |
assert (0 < Qceiling q)%Z. |
| 120 |
{ rewrite Zlt_Qlt. apply (Qlt_le_trans _ _ _ H). apply Qle_ceiling. } |
| 121 |
revert H0. generalize (Qceiling q). intros p ppos. clear H q. |
| 122 |
unfold Qle; simpl. |
| 123 |
rewrite Z.mul_1_r, Pos.mul_1_r. |
| 124 |
destruct p as [|p|p]. |
| 125 |
exfalso; inversion ppos. |
| 126 |
2: exfalso; inversion ppos. clear ppos. |
| 127 |
apply (Z.le_trans _ (2 ^ Z.log2_up p)). |
| 128 |
apply Z.log2_up_le_pow2. reflexivity. |
| 129 |
apply Z.le_refl. |
| 130 |
revert p. apply Pos.peano_case. discriminate. |
| 131 |
intro p. |
| 132 |
generalize (Z.log2_up (Pos.succ p)) |
| 133 |
(Z.log2_up_pos (Pos.succ p) (Pos.lt_1_succ p)). |
| 134 |
clear p. intros p ppos. |
| 135 |
destruct p. inversion ppos. |
| 136 |
2: inversion ppos. clear ppos. |
| 137 |
unfold Z.to_pos. |
| 138 |
pose proof (fact_power_2 (Pos.to_nat (Pos.succ p))). |
| 139 |
rewrite Pos2Nat.inj_succ in H. |
| 140 |
unfold pred in H. |
| 141 |
rewrite Pos2Nat.inj_succ. |
| 142 |
simpl (2^p)%Z. |
| 143 |
rewrite <- Pos2Z.inj_pow_pos. |
| 144 |
apply Pos2Nat.inj_le. |
| 145 |
rewrite Nat2Pos.id. |
| 146 |
2: apply fact_neq_0. |
| 147 |
refine (Nat.le_trans _ _ _ _ H). |
| 148 |
clear H. generalize p. |
| 149 |
apply Pos.peano_ind. |
| 150 |
+ apply Nat.le_refl. |
| 151 |
+ intros. rewrite Pos2Nat.inj_succ, Pos.pow_succ_r. |
| 152 |
rewrite Pos2Nat.inj_mul. |
| 153 |
apply Nat.mul_le_mono_nonneg_l. apply Nat.le_0_l. |
| 154 |
exact H. |
| 155 |
Qed. |
| 156 |
|
| 157 |
(** |
| 158 |
** Exponential |
| 159 |
[exp] is implement by its alternating Taylor's series. |
| 160 |
*) |
| 161 |
|
| 162 |
Section ExpSeries. |
| 163 |
Variable a:Q. |
| 164 |
|
| 165 |
Definition expStream (px : positive*Q) : positive*Q |
| 166 |
:= (Pos.succ (fst px), snd px * a * (1#fst px)). |
| 167 |
|
| 168 |
Lemma expStream_fst : forall p, fst (iterate _ expStream p (1%positive, 1)) ≡ Pos.succ p. |
| 169 |
Proof. |
| 170 |
apply Pos.peano_ind. |
| 171 |
- reflexivity. |
| 172 |
- intros. rewrite iterate_succ. simpl. |
| 173 |
rewrite H. reflexivity. |
| 174 |
Qed. |
| 175 |
|
| 176 |
Lemma Str_pth_expStream : forall p, |
| 177 |
Str_pth _ expStream p (xH,1) == (1#Pos.of_nat (fact (Pos.to_nat p)))*a^p. |
| 178 |
Proof. |
| 179 |
apply Pos.peano_ind. |
| 180 |
- unfold Str_pth. simpl. apply Qmult_1_r. |
| 181 |
- intros. unfold Str_pth. |
| 182 |
rewrite iterate_succ. simpl. |
| 183 |
unfold Str_pth in H. rewrite H. clear H. |
| 184 |
rewrite expStream_fst. simpl. |
| 185 |
rewrite <- (Qmult_comm (1#Pos.succ p)), Qmult_assoc, Qmult_assoc. |
| 186 |
rewrite <- (Qmult_assoc ((1 # Pos.succ p) * (1 # Pos.of_nat (fact (Pos.to_nat p))))). |
| 187 |
apply Qmult_comp. |
| 188 |
+ unfold Qmult, Qeq, Qnum, Qden. rewrite Z.mul_1_l. |
| 189 |
rewrite Z.mul_1_l. |
| 190 |
rewrite Pos2Nat.inj_succ. |
| 191 |
change (fact (S (Pos.to_nat p)))%nat |
| 192 |
with (S (Pos.to_nat p) * fact (Pos.to_nat p))%nat. |
| 193 |
rewrite Nat2Pos.inj_mul. 2: discriminate. |
| 194 |
2: apply fact_neq_0. |
| 195 |
rewrite Nat2Pos.inj_succ, Pos2Nat.id. |
| 196 |
reflexivity. pose proof (Pos2Nat.is_pos p). |
| 197 |
intro abs. rewrite abs in H. inversion H. |
| 198 |
+ rewrite <- Pos.add_1_r. |
| 199 |
rewrite Qpower_plus_positive. reflexivity. |
| 200 |
Qed. |
| 201 |
|
| 202 |
Lemma expStream_alt : -1 <= a <= 0 -> Str_alt_decr _ expStream (xH,1). |
| 203 |
Proof. |
| 204 |
intros aneg p. |
| 205 |
unfold Str_pth. rewrite iterate_succ. |
| 206 |
generalize (iterate (positive and Q) expStream p (1%positive, 1)). |
| 207 |
intros [n q]. unfold expStream, snd, fst. split. |
| 208 |
- rewrite <- Qmult_assoc. |
| 209 |
rewrite <- (Qmult_1_l (Qabs q)). |
| 210 |
rewrite Qabs_Qmult, Qmult_comm. |
| 211 |
apply Qmult_le_compat_r. 2: apply Qabs_nonneg. |
| 212 |
rewrite Qabs_Qmult. |
| 213 |
apply (Qle_trans _ (1 * Qabs (1#n))). |
| 214 |
apply Qmult_le_compat_r. 2: apply Qabs_nonneg. |
| 215 |
apply Qabs_Qle_condition. split. |
| 216 |
apply aneg. apply (Qle_trans _ 0). apply aneg. discriminate. |
| 217 |
rewrite Qmult_1_l. apply Pos.le_1_l. |
| 218 |
- destruct aneg as [_ aneg]. |
| 219 |
rewrite <- (Qmult_comm a). |
| 220 |
rewrite <- Qmult_assoc, <- Qmult_assoc. |
| 221 |
rewrite <- (Qmult_0_l (q * ((1 # n) * q))). |
| 222 |
apply Qmult_le_compat_r. exact aneg. |
| 223 |
rewrite Qmult_comm. |
| 224 |
destruct q, Qnum; unfold Qle; discriminate. |
| 225 |
Qed. |
| 226 |
|
| 227 |
Lemma expStream_zl |
| 228 |
: -1 <= a <= 0 |
| 229 |
-> Limit_zero _ expStream (xH,1) |
| 230 |
(fun e:Qpos => Pos.succ (Z.to_pos (Z.log2_up (Qceiling (/ (proj1_sig e)))))). |
| 231 |
Proof. |
| 232 |
(* 1/e <= Qceiling (1/e) <= 2 ^ (Z.log2_up (Qceiling (1/e))) |
| 233 |
and we add 1 more to get <= fact. *) |
| 234 |
intros aneg [e epos]; unfold proj1_sig. |
| 235 |
(* Replace a^k by 1 *) |
| 236 |
rewrite Str_pth_expStream. |
| 237 |
rewrite Qabs_Qmult, Qmult_comm. |
| 238 |
apply (Qle_trans |
| 239 |
_ (1 * Qabs (1 # Pos.of_nat (fact (Pos.to_nat (Pos.succ (Z.to_pos (Z.log2_up (Qceiling (/ e)))))))))). |
| 240 |
apply Qmult_le_compat_r. 2: apply Qabs_nonneg. |
| 241 |
- generalize (Pos.succ (Z.to_pos (Z.log2_up (Qceiling (/ e))))). |
| 242 |
intro p. rewrite Qabs_Qpower. |
| 243 |
apply Qpower_le_1. split. apply Qabs_nonneg. |
| 244 |
apply Qabs_Qle_condition. split. apply aneg. |
| 245 |
apply (Qle_trans _ 0). apply aneg. discriminate. |
| 246 |
- rewrite Qmult_1_l. clear aneg a. |
| 247 |
(* Replace fact k by 2^k. *) |
| 248 |
simpl. |
| 249 |
rewrite <- (Qinv_involutive e) at 2. |
| 250 |
assert (0 < /e) as H. |
| 251 |
{ apply Qinv_lt_0_compat, epos. } |
| 252 |
apply (@Qinv_le_compat |
| 253 |
(/e) ((Pos.of_nat (fact (Pos.to_nat (Pos.succ (Z.to_pos (Z.log2_up (Qceiling (/ e)))))))) # 1)). |
| 254 |
exact H. |
| 255 |
apply Qceiling_fact_le, H. |
| 256 |
Qed. |
| 257 |
|
| 258 |
End ExpSeries. |
| 259 |
|
| 260 |
Lemma exp_ps_correct : forall (a:Q) (p:positive) H, |
| 261 |
inj_Q IR (Str_pth _ (expStream a) p (xH,1))%Q |
| 262 |
= Exp_ps (Pos.to_nat p) (inj_Q IR a) H. |
| 263 |
Proof. |
| 264 |
intros a p H. |
| 265 |
rewrite (inj_Q_wd _ _ _ (Str_pth_expStream a p)). |
| 266 |
revert p H. |
| 267 |
apply (Pos.peano_ind (fun p => ∀ (H : Dom (Exp_ps (Pos.to_nat p)) (inj_Q IR a)), |
| 268 |
inj_Q IR ((1 # Pos.of_nat (fact (Pos.to_nat p))) * a ^ p) = |
| 269 |
Exp_ps (Pos.to_nat p) (inj_Q IR a) H)). |
| 270 |
- intros H. |
| 271 |
simpl ((1 # Pos.of_nat (fact (Pos.to_nat 1))) * a ^ 1). |
| 272 |
rewrite (inj_Q_wd _ _ _ (one_mult _ a)). |
| 273 |
unfold Pos.to_nat. simpl. |
| 274 |
rewrite one_mult. |
| 275 |
setoid_replace ([1] [/] [0] [+] [1] [//] nring_fac_ap_zero IR 1) with (cr_one IR). |
| 276 |
rewrite one_mult. |
| 277 |
rewrite cg_inv_zero. |
| 278 |
reflexivity. |
| 279 |
unfold cf_div. |
| 280 |
rewrite one_mult. |
| 281 |
rewrite <- inv_one at 2. |
| 282 |
apply f_rcpcl_wd. |
| 283 |
rewrite cm_lft_unit. |
| 284 |
reflexivity. |
| 285 |
- intros p IHp H. |
| 286 |
rewrite Pos2Nat.inj_succ. |
| 287 |
stepl (([1][/](nring (S (Pos.to_nat p)))[//]nringS_ap_zero IR (Pos.to_nat p)) |
| 288 |
[*](inj_Q IR a)[*]Exp_ps (Pos.to_nat p) (inj_Q IR a) H). |
| 289 |
+ simpl. |
| 290 |
rewrite (mult_commutes IR (nexp IR (Pos.to_nat p) (inj_Q IR a [-] [0]))). |
| 291 |
rewrite (ax_mult_assoc IR _ _ (cr_proof IR)). |
| 292 |
rewrite (ax_mult_assoc IR _ _ (cr_proof IR)). |
| 293 |
apply mult_wd. 2: reflexivity. |
| 294 |
rewrite cg_inv_zero. |
| 295 |
rewrite <- (mult_commutes IR (inj_Q IR a)). |
| 296 |
rewrite <- (mult_commutes IR (inj_Q IR a)). |
| 297 |
rewrite <- (ax_mult_assoc IR _ _ (cr_proof IR)). |
| 298 |
apply mult_wd. reflexivity. |
| 299 |
pose proof (mult_resp_ap_zero _ _ _ (nringS_ap_zero IR (Pos.to_nat p)) (nring_fac_ap_zero IR (Pos.to_nat p))) |
| 300 |
as X. |
| 301 |
rewrite <- (mult_of_divs _ _ _ _ _ _ _ X). |
| 302 |
apply div_wd. apply mult_one. |
| 303 |
apply eq_symmetric. |
| 304 |
change (fact (Pos.to_nat p) + (Pos.to_nat p) * fact (Pos.to_nat p))%nat |
| 305 |
with (S (Pos.to_nat p)*(fact (Pos.to_nat p)))%nat. |
| 306 |
apply nring_comm_mult. |
| 307 |
+ stepl (inj_Q IR ((1#(Pos.succ p)) |
| 308 |
*a*((1 # Pos.of_nat (fact (Pos.to_nat p))) * a ^ Pos.to_nat p))%Q). |
| 309 |
* apply inj_Q_wd. |
| 310 |
rewrite <- Pos.add_1_l at 2. |
| 311 |
rewrite (Qpower_plus' a 1 p). |
| 312 |
2: discriminate. |
| 313 |
simpl (a ^ 1). |
| 314 |
rewrite Qmult_assoc, Qmult_assoc. |
| 315 |
apply Qmult_comp. |
| 316 |
rewrite <- (Qmult_comm a), <- Qmult_assoc, Qmult_comm. |
| 317 |
apply Qmult_comp. 2: reflexivity. |
| 318 |
change (fact (S (Pos.to_nat p)))%nat |
| 319 |
with ((S (Pos.to_nat p)) * fact (Pos.to_nat p))%nat. |
| 320 |
rewrite Nat2Pos.inj_mul. |
| 321 |
2: discriminate. 2: apply fact_neq_0. |
| 322 |
replace (Pos.of_nat (S (Pos.to_nat p))) with (Pos.succ p). |
| 323 |
reflexivity. |
| 324 |
rewrite Nat2Pos.inj_succ. |
| 325 |
rewrite Pos2Nat.id. reflexivity. |
| 326 |
pose proof (Pos2Nat.is_pos p). |
| 327 |
intro abs. rewrite abs in H0. inversion H0. |
| 328 |
rewrite positive_nat_Z. reflexivity. |
| 329 |
* stepl (([1][/]nring (R:=IR) (S (Pos.to_nat p))[//]nringS_ap_zero IR (Pos.to_nat p))[*]inj_Q IR a[*] |
| 330 |
inj_Q IR ((1 # Pos.of_nat (fact (Pos.to_nat p))) * a ^ p)%Q) |
| 331 |
; [apply mult_wdr; apply IHp|]. |
| 332 |
clear IHp H. |
| 333 |
apply eq_symmetric. |
| 334 |
eapply eq_transitive;[apply inj_Q_mult|]. |
| 335 |
eapply eq_transitive;[apply mult_wdl;apply inj_Q_mult|]. |
| 336 |
rewrite positive_nat_Z. |
| 337 |
apply mult_wdl. |
| 338 |
apply mult_wdl. |
| 339 |
change (1 # Pos.succ p)%Q with (1/Pos.succ p)%Q. |
| 340 |
assert (A:inj_Q IR ((Pos.succ p):Q)[=]nring (S (Pos.to_nat p))). |
| 341 |
{ stepl (inj_Q IR (nring (S (Pos.to_nat p)))). |
| 342 |
apply inj_Q_nring. |
| 343 |
apply inj_Q_wd. |
| 344 |
simpl. |
| 345 |
rewrite <- Pos.add_1_r. |
| 346 |
rewrite Pos2Z.inj_add, inject_Z_plus. |
| 347 |
apply Qplus_comp. 2: reflexivity. |
| 348 |
revert p. apply Pos.peano_ind. |
| 349 |
reflexivity. intros p IHp. |
| 350 |
rewrite Pos2Nat.inj_succ. simpl. |
| 351 |
rewrite -> IHp. |
| 352 |
rewrite <- Pos.add_1_r. |
| 353 |
rewrite Pos2Z.inj_add, inject_Z_plus. |
| 354 |
reflexivity. } |
| 355 |
assert (B:inj_Q IR (Pos.succ p:Q)[#][0]). |
| 356 |
{ stepl (nring (R:=IR) (S (Pos.to_nat p))). |
| 357 |
apply nringS_ap_zero. |
| 358 |
apply eq_symmetric;assumption. } |
| 359 |
eapply eq_transitive;[apply inj_Q_div|]. |
| 360 |
instantiate (1:=B). |
| 361 |
apply div_wd. |
| 362 |
apply inj_Q_One. |
| 363 |
exact A. |
| 364 |
Qed. |
| 365 |
|
| 366 |
Definition rational_exp_small_neg (a:Q) (p:-(1) <= a <= 0) : CR |
| 367 |
:= translate 1 (AltSeries _ (expStream a) (xH,1%Q) _ |
| 368 |
(expStream_alt p) (expStream_zl p)). |
| 369 |
|
| 370 |
Lemma rational_exp_small_neg_wd (a1 a2 : Q) (p1 : -(1) <= a1 <= 0) (p2 : -(1) <= a2 <= 0) : |
| 371 |
a1 == a2 → rational_exp_small_neg p1 = rational_exp_small_neg p2. |
| 372 |
Proof. |
| 373 |
intros E. unfold rational_exp_small_neg. |
| 374 |
rewrite <- CRplus_translate. |
| 375 |
rewrite <- CRplus_translate. |
| 376 |
apply CRplus_eq_r. |
| 377 |
apply AltSeries_wd. |
| 378 |
apply Pos.peano_ind. |
| 379 |
- unfold Str_pth; simpl. |
| 380 |
rewrite E. reflexivity. |
| 381 |
- intros. unfold Str_pth. |
| 382 |
rewrite iterate_succ, iterate_succ. |
| 383 |
simpl. |
| 384 |
unfold Str_pth in H. rewrite H. clear H. |
| 385 |
apply Qmult_comp. |
| 386 |
apply Qmult_comp. reflexivity. |
| 387 |
exact E. |
| 388 |
rewrite expStream_fst, expStream_fst. |
| 389 |
reflexivity. |
| 390 |
- reflexivity. |
| 391 |
Qed. |
| 392 |
|
| 393 |
Lemma rational_exp_small_neg_correct : forall (a:Q) Ha, |
| 394 |
(@rational_exp_small_neg a Ha == IRasCR (Exp (inj_Q IR a)))%CR. |
| 395 |
Proof. |
| 396 |
intros a Ha. |
| 397 |
unfold rational_exp_small_neg. |
| 398 |
rewrite <- CRplus_translate. |
| 399 |
setoid_replace 1%CR with |
| 400 |
(IRasCR |
| 401 |
((λ n : nat, |
| 402 |
Exp_ps n (inj_Q IR a) |
| 403 |
(fun_series_inc_IR realline Exp_ps Exp_conv (inj_Q IR a) I n)) 0%nat)). |
| 404 |
apply: AltSeries_correct. |
| 405 |
intro p. |
| 406 |
apply exp_ps_correct. |
| 407 |
simpl. |
| 408 |
rewrite <- IR_One_as_CR. |
| 409 |
apply IRasCR_wd. |
| 410 |
rewrite mult_one. |
| 411 |
unfold cf_div. |
| 412 |
rewrite one_mult. |
| 413 |
rewrite <- inv_one at 1. |
| 414 |
apply f_rcpcl_wd. |
| 415 |
rewrite cm_lft_unit. |
| 416 |
reflexivity. |
| 417 |
Qed. |
| 418 |
|
| 419 |
Program Definition CRe_inv := @rational_exp_small_neg (-1) _. |
| 420 |
Next Obligation. constructor; discriminate. Qed. |
| 421 |
|
| 422 |
(** exp is extended to work on [[-2^n, 0]] for all n. *) |
| 423 |
|
| 424 |
(* Faster to compress between the powers of 2, than take a big power 2^n. *) |
| 425 |
Fixpoint CRpower_2_iter (n : nat) (x : CR) : CR := |
| 426 |
match n with |
| 427 |
| O => x |
| 428 |
| S p => CRpower_N_bounded 2 (1#1) (compress (CRpower_2_iter p x)) |
| 429 |
end. |
| 430 |
|
| 431 |
Lemma CRpower_2_iter_wd : forall (n : nat) (x y : CR), |
| 432 |
(x == y)%CR -> (CRpower_2_iter n x == CRpower_2_iter n y)%CR. |
| 433 |
Proof. |
| 434 |
induction n. |
| 435 |
- intros. exact H. |
| 436 |
- intros. simpl. apply Cmap_wd. reflexivity. |
| 437 |
rewrite compress_fun_correct, compress_fun_correct. |
| 438 |
apply IHn, H. |
| 439 |
Qed. |
| 440 |
|
| 441 |
Local Opaque compress CRpower_N_bounded. |
| 442 |
Lemma rational_exp_neg_bounded_correct_aux (a : Q) : |
| 443 |
a ≤ 0 → (CRpower_N_bounded 2 (1 # 1)) (IRasCR (Exp (inj_Q IR (a / 2)))) |
| 444 |
= IRasCR (Exp (inj_Q IR a)). |
| 445 |
Proof. |
| 446 |
intros Ea. |
| 447 |
rewrite <- CRpower_N_bounded_correct. |
| 448 |
- change (CRpower_slow (IRasCR (Exp (inj_Q IR (a / 2)))) (N.to_nat 2))%CR |
| 449 |
with (IRasCR (Exp (inj_Q IR (a / 2))) |
| 450 |
* (IRasCR (Exp (inj_Q IR (a / 2))) * 1))%CR. |
| 451 |
rewrite CRmult_1_r. |
| 452 |
rewrite <- IR_mult_as_CR. |
| 453 |
apply IRasCR_wd. |
| 454 |
set (a':=inj_Q IR (a/2)). |
| 455 |
simpl. |
| 456 |
stepl (Exp (a'[+]a')); [| now apply Exp_plus]. |
| 457 |
apply Exp_wd. |
| 458 |
unfold a'. |
| 459 |
eapply eq_transitive. |
| 460 |
apply eq_symmetric; apply (inj_Q_plus IR). |
| 461 |
apply inj_Q_wd. |
| 462 |
change (a / (2#1) + a / (2#1) == a). field. |
| 463 |
- apply leEq_imp_AbsSmall. |
| 464 |
+ rewrite <- IR_Zero_as_CR. |
| 465 |
apply IR_leEq_as_CR. |
| 466 |
apply less_leEq; apply Exp_pos. |
| 467 |
+ apply (@CRle_trans _ (IRasCR [1])). |
| 468 |
apply IR_leEq_as_CR. apply Exp_leEq_One. |
| 469 |
stepr (inj_Q IR 0); [| now apply (inj_Q_nring IR 0)]. |
| 470 |
apply inj_Q_leEq. |
| 471 |
apply mult_cancel_leEq with (2:Q). |
| 472 |
constructor. |
| 473 |
change (a/2*2<=0). |
| 474 |
now replace LHS with a by (simpl; field; discriminate). |
| 475 |
simpl. rewrite IR_One_as_CR. apply CRle_refl. |
| 476 |
Qed. |
| 477 |
|
| 478 |
(** [exp] works on all nonpositive numbers. *) |
| 479 |
|
| 480 |
(* Do not do 2^n in nat, it could make a very large unary nat. *) |
| 481 |
Lemma rational_exp_neg_bounded_correct : forall (n:nat) (a:Q) (Ha : -1 <= a*(1#2)^n <= 0), |
| 482 |
(CRpower_2_iter n (rational_exp_small_neg Ha) == IRasCR (Exp (inj_Q IR a)))%CR. |
| 483 |
Proof. |
| 484 |
induction n. |
| 485 |
- intros. simpl. |
| 486 |
assert (-1 <= a <= 0) as Ha_simpl. |
| 487 |
{ simpl in Ha. rewrite Qmult_1_r in Ha. exact Ha. } |
| 488 |
rewrite <- (rational_exp_small_neg_correct Ha_simpl). |
| 489 |
apply rational_exp_small_neg_wd. |
| 490 |
apply Qmult_1_r. |
| 491 |
- intros a Ha. |
| 492 |
simpl. |
| 493 |
rewrite -> compress_correct. |
| 494 |
rewrite <- rational_exp_neg_bounded_correct_aux. |
| 495 |
apply Cmap_wd. reflexivity. |
| 496 |
assert (-1 <= (a/2)*(1#2)^n <= 0) as Ha_div. |
| 497 |
{ change (S n) with (1+n)%nat in Ha. |
| 498 |
rewrite Nat2Z.inj_add, Qpower_plus in Ha. |
| 499 |
simpl in Ha. rewrite Qmult_assoc in Ha. |
| 500 |
exact Ha. discriminate. } |
| 501 |
rewrite <- (IHn _ Ha_div). |
| 502 |
apply CRpower_2_iter_wd, rational_exp_small_neg_wd. |
| 503 |
unfold Qdiv. rewrite <- Qmult_assoc. |
| 504 |
apply Qmult_comp. reflexivity. |
| 505 |
change (/2) with ((1#2)^1). |
| 506 |
rewrite <- Qpower_plus. |
| 507 |
clear IHn. |
| 508 |
change 1%Z with (Z.of_nat 1). |
| 509 |
rewrite <- (Nat2Z.inj_add 1 n). |
| 510 |
reflexivity. discriminate. |
| 511 |
destruct Ha as [_ Ha]. |
| 512 |
apply (Qmult_le_r _ _ ((1#2)^S n)). |
| 513 |
apply Q.Qpower_0_lt. reflexivity. |
| 514 |
rewrite Qmult_0_l. exact Ha. |
| 515 |
Qed. |
| 516 |
|
| 517 |
(* Improve n such as -2^n <= a. |
| 518 |
-a <= 2^n is equivalent to Qceiling(-a) <= 2^n and then |
| 519 |
we can use the integer log2. *) |
| 520 |
Lemma rational_exp_bound_power_2 : forall (a:Q), |
| 521 |
a <= 0 -> - inject_Z (2^Z.to_nat (Z.log2_up (Qceiling(-a)))) <= a. |
| 522 |
Proof. |
| 523 |
intros [[|n|n] d] Ha; simpl. |
| 524 |
discriminate. |
| 525 |
elim Ha. |
| 526 |
reflexivity. |
| 527 |
rewrite Z2Nat.id. |
| 528 |
clear Ha. |
| 529 |
rewrite <- (Qopp_involutive (Z.neg n # d)) at 2. |
| 530 |
apply Qopp_le_compat. |
| 531 |
change (-(Z.neg n#d)) with (Zpos n # d). |
| 532 |
apply Q.Zle_Qle_Qceiling. |
| 533 |
apply Z.log2_up_le_pow2. |
| 534 |
2: apply Z.le_refl. |
| 535 |
apply Z2Nat.inj_lt. apply Z.le_refl. |
| 536 |
apply (Qceiling_resp_le 0). discriminate. |
| 537 |
apply Q.Qlt_lt_of_nat_inject_Z. |
| 538 |
reflexivity. |
| 539 |
apply Z.log2_up_nonneg. |
| 540 |
Qed. |
| 541 |
|
| 542 |
Lemma power_2_improve_bound_correct : forall (n:nat) (a:Q), |
| 543 |
a <= 0 -> |
| 544 |
-inject_Z (2^n) <= a -> |
| 545 |
-1 <= a*(1#2)^n <= 0. |
| 546 |
Proof. |
| 547 |
split. |
| 548 |
- apply (Qmult_le_r _ _ ((2#1)^n)). |
| 549 |
apply Q.Qpower_0_lt. reflexivity. |
| 550 |
apply (Qle_trans _ a). |
| 551 |
rewrite Zpower_Qpower in H0. |
| 552 |
exact H0. apply Nat2Z.is_nonneg. |
| 553 |
rewrite <- Qmult_assoc, <- Qmult_power. |
| 554 |
setoid_replace ((1 # 2) * 2)%Q with 1%Q by reflexivity. |
| 555 |
rewrite Qpower_1, Qmult_1_r. apply Qle_refl. |
| 556 |
- rewrite <- (Qmult_0_l ((1#2)^n)). |
| 557 |
apply Qmult_le_compat_r. exact H. |
| 558 |
apply Qpower_pos. discriminate. |
| 559 |
Qed. |
| 560 |
|
| 561 |
Definition rational_exp_neg (a:Q) (Ha : a <= 0) : CR |
| 562 |
:= CRpower_2_iter |
| 563 |
(Z.to_nat (Z.log2_up (Qceiling(-a)))) |
| 564 |
(rational_exp_small_neg |
| 565 |
(power_2_improve_bound_correct _ Ha (rational_exp_bound_power_2 Ha))). |
| 566 |
|
| 567 |
(* Some time measures on a 5000 bogomips CPU |
| 568 |
Lemma Zneg_neg : forall p:positive, Z.neg p # 1 <= 0. |
| 569 |
Proof. intros. discriminate. Qed. |
| 570 |
Time Eval vm_compute in (approximate (rational_exp_neg (@Zneg_neg 100%positive)) |
| 571 |
(Qpos2QposInf (1#(10 ^ 100)%positive))). |
| 572 |
(* 1.3 secs *) |
| 573 |
Time Eval vm_compute in (approximate (rational_exp_neg (@Zneg_neg 200%positive)) |
| 574 |
(Qpos2QposInf (1#(10 ^ 200)%positive))). |
| 575 |
(* 8 secs *) |
| 576 |
Time Eval vm_compute in (approximate (rational_exp_neg (@Zneg_neg 300%positive)) |
| 577 |
(Qpos2QposInf (1#(10 ^ 300)%positive))). |
| 578 |
(* 23.6 secs *) |
| 579 |
*) |
| 580 |
|
| 581 |
Lemma rational_exp_neg_correct : forall (a:Q) Ha, |
| 582 |
(@rational_exp_neg a Ha == IRasCR (Exp (inj_Q IR a)))%CR. |
| 583 |
Proof. |
| 584 |
intros a Ha. |
| 585 |
apply rational_exp_neg_bounded_correct. |
| 586 |
Qed. |
| 587 |
|
| 588 |
(** exp(x) is bounded below by (3^x) for x nonpositive, and hence |
| 589 |
exp(x) is positive. *) |
| 590 |
Lemma CRe_inv_posH : ('(1#3) <= CRe_inv)%CR. |
| 591 |
Proof. |
| 592 |
unfold CRle. |
| 593 |
apply CRpos_nonNeg. |
| 594 |
CR_solve_pos (1#1)%Qpos. |
| 595 |
Qed. |
| 596 |
|
| 597 |
(* We parametrize the following lemmas by a lowerbound of [CRe_inv] so that |
| 598 |
we can easily swap lowerbounds. *) |
| 599 |
Lemma rational_exp_neg_posH (q : Qpos) (n:nat) (a:Q) : |
| 600 |
-n ≤ a → a ≤ 0 → '(proj1_sig q) ≤ CRe_inv |
| 601 |
→ '(proj1_sig q^n) ≤ IRasCR (Exp (inj_Q IR a)). |
| 602 |
Proof. |
| 603 |
intros Hn Ha small. |
| 604 |
rewrite <- IR_inj_Q_as_CR. |
| 605 |
rewrite <- IR_leEq_as_CR. |
| 606 |
stepl (inj_Q IR (proj1_sig q) [^]n) |
| 607 |
by (now (apply eq_symmetric; apply inj_Q_power)). |
| 608 |
assert (X:[0][<]inj_Q IR (`q)). |
| 609 |
stepl (inj_Q IR 0); [| now apply (inj_Q_nring IR 0)]. |
| 610 |
apply inj_Q_less. |
| 611 |
now destruct q. |
| 612 |
astepl (inj_Q IR (`q)[!](nring n)[//]X). |
| 613 |
unfold power. |
| 614 |
apply Exp_resp_leEq. |
| 615 |
destruct n. |
| 616 |
simpl (nring 0). |
| 617 |
rewrite cring_mult_zero_op. |
| 618 |
stepl (inj_Q IR 0); [| now apply (inj_Q_nring IR 0)]. |
| 619 |
apply inj_Q_leEq. |
| 620 |
assumption. |
| 621 |
apply (fun a b => (shift_mult_leEq' _ a b _ (nringS_ap_zero IR n))). |
| 622 |
apply nring_pos; auto with *. |
| 623 |
stepr (inj_Q IR (a/(S n))). |
| 624 |
apply Exp_cancel_leEq. |
| 625 |
astepl (inj_Q IR (`q)). |
| 626 |
rewrite -> IR_leEq_as_CR. |
| 627 |
rewrite -> IR_inj_Q_as_CR. |
| 628 |
assert (Ha0 : -(1)<=(a/S n)<=0). |
| 629 |
split. |
| 630 |
rewrite -> Qle_minus_iff. |
| 631 |
replace RHS with ((a + S n)*(1/(S n))) by (simpl; field;discriminate). |
| 632 |
replace LHS with (0*(1/(S n))) by simpl; ring. |
| 633 |
apply: mult_resp_leEq_rht;simpl. |
| 634 |
replace RHS with (a + - (- (P_of_succ_nat n))) by simpl; ring. |
| 635 |
rewrite <- Qle_minus_iff. |
| 636 |
assumption. |
| 637 |
rewrite <- (Qmake_Qdiv 1 (P_of_succ_nat n)). |
| 638 |
discriminate. |
| 639 |
replace RHS with (0*(1/(S n))) by simpl; ring. |
| 640 |
apply: mult_resp_leEq_rht;simpl. |
| 641 |
assumption. |
| 642 |
rewrite <- (Qmake_Qdiv 1 (P_of_succ_nat n)). |
| 643 |
discriminate. |
| 644 |
rewrite <- (rational_exp_small_neg_correct Ha0). |
| 645 |
apply CRle_trans with CRe_inv. |
| 646 |
apply small. |
| 647 |
unfold CRe_inv. |
| 648 |
do 2 rewrite -> (rational_exp_small_neg_correct). |
| 649 |
rewrite <- IR_leEq_as_CR. |
| 650 |
apply Exp_resp_leEq. |
| 651 |
apply inj_Q_leEq. |
| 652 |
tauto. |
| 653 |
assert (X0:inj_Q IR (inject_Z (S n))[#][0]). |
| 654 |
stepl (inj_Q IR (nring (S n))). |
| 655 |
stepl (@nring IR (S n)); [| now (apply eq_symmetric; apply (inj_Q_nring IR (S n)))]. |
| 656 |
apply (nringS_ap_zero). |
| 657 |
apply inj_Q_wd. |
| 658 |
apply nring_Q. |
| 659 |
stepl (inj_Q IR a[/]_[//]X0). |
| 660 |
apply div_wd. |
| 661 |
apply eq_reflexive. |
| 662 |
stepl (inj_Q IR (nring (S n))). |
| 663 |
apply inj_Q_nring. |
| 664 |
apply inj_Q_wd. |
| 665 |
apply nring_Q. |
| 666 |
apply eq_symmetric. |
| 667 |
apply inj_Q_div. |
| 668 |
Qed. |
| 669 |
|
| 670 |
Lemma rational_exp_neg_posH' (c : Qpos) (a : Q) : |
| 671 |
a ≤ 0 → '(proj1_sig c) ≤ CRe_inv |
| 672 |
→ '(proj1_sig (Qpos_power c (-Qfloor a))) ≤ IRasCR (Exp (inj_Q IR a)). |
| 673 |
Proof. |
| 674 |
intros Ha small. |
| 675 |
assert (X0:(0 <= -Qfloor a)%Z). |
| 676 |
apply Z.opp_nonneg_nonpos. |
| 677 |
rewrite Q.Zle_Qle. |
| 678 |
apply Qle_trans with a; [| assumption]. |
| 679 |
now apply Qfloor_le. |
| 680 |
setoid_replace (proj1_sig (Qpos_power c (-Qfloor a))) |
| 681 |
with (proj1_sig c ^ Z_to_nat X0). |
| 682 |
apply rational_exp_neg_posH; trivial. |
| 683 |
rewrite <- (Z_to_nat_correct X0). |
| 684 |
rewrite inject_Z_opp, Qopp_involutive. |
| 685 |
now apply Qfloor_le. |
| 686 |
now rewrite <- Z_to_nat_correct. |
| 687 |
Qed. |
| 688 |
|
| 689 |
(* Need transparent and fast positivity to define |
| 690 |
exponential on positive rationals by division. *) |
| 691 |
Lemma rational_exp_neg_pos : forall (a:Q) Ha, |
| 692 |
CRpos (@rational_exp_neg a Ha). |
| 693 |
Proof. |
| 694 |
intros a Ha. |
| 695 |
exists (Qpos_power (1#3) (-Qfloor a))%Qpos. simpl. |
| 696 |
rewrite rational_exp_neg_correct. |
| 697 |
apply (rational_exp_neg_posH' (1#3)); trivial. |
| 698 |
apply CRe_inv_posH. |
| 699 |
Defined. |
| 700 |
|
| 701 |
(** exp is extended to all numbers by saying exp(x) = 1/exp(-x) when x |
| 702 |
is positive. *) |
| 703 |
Definition rational_exp (a:Q) : CR. |
| 704 |
Proof. |
| 705 |
destruct a as [[|n|n] d]. |
| 706 |
- exact 1%CR. |
| 707 |
- refine (CRinv_pos (Qpos_power (1#3) (Qceiling (n#d)))%Qpos |
| 708 |
(@rational_exp_neg (Zneg n#d) _)). |
| 709 |
discriminate. |
| 710 |
- apply (@rational_exp_neg (Zneg n#d)). |
| 711 |
discriminate. |
| 712 |
Defined. |
| 713 |
|
| 714 |
(* Some time measures on a 5000 bogomips CPU |
| 715 |
Time Eval vm_compute in (approximate (rational_exp (100#1)) (Qpos2QposInf (1#1))). |
| 716 |
(* 1.2 secs *) |
| 717 |
|
| 718 |
Time Eval vm_compute in (approximate (rational_exp (200#1)) (Qpos2QposInf (1#1))). |
| 719 |
(* 7.1 secs *) |
| 720 |
|
| 721 |
Time Eval vm_compute in (approximate (rational_exp (300#1)) (Qpos2QposInf (1#1))). |
| 722 |
(* 21 secs *) |
| 723 |
*) |
| 724 |
|
| 725 |
Lemma rational_exp_pos_correct (a : Q) (Pa : 0 ≤ a) (c : Qpos) : |
| 726 |
('proj1_sig c <= IRasCR (Exp (inj_Q IR (-a)%Q)))%CR → |
| 727 |
CRinv_pos c (IRasCR (Exp (inj_Q IR (-a)))) = IRasCR (Exp (inj_Q IR a)). |
| 728 |
Proof. |
| 729 |
intros Ec. |
| 730 |
assert (X: (IRasCR (Exp (inj_Q IR (-a)%Q)) >< 0)%CR). |
| 731 |
right. exists c. |
| 732 |
now ring_simplify. |
| 733 |
rewrite (CRinvT_pos_inv c X); trivial. |
| 734 |
rewrite <- IR_recip_as_CR_2. |
| 735 |
apply IRasCR_wd. |
| 736 |
apply eq_symmetric. |
| 737 |
eapply eq_transitive;[|apply div_wd; apply eq_reflexive]. |
| 738 |
apply Exp_inv'. |
| 739 |
rewrite (inj_Q_inv IR a), cg_inv_inv. |
| 740 |
reflexivity. |
| 741 |
Qed. |
| 742 |
|
| 743 |
Lemma rational_exp_correct (a : Q) : |
| 744 |
(rational_exp a = IRasCR (Exp (inj_Q IR a)))%CR. |
| 745 |
Proof. |
| 746 |
unfold rational_exp. |
| 747 |
destruct a as [[|n|n] d]. |
| 748 |
- rewrite <- IR_One_as_CR. |
| 749 |
apply IRasCR_wd. |
| 750 |
setoid_replace (inj_Q IR (0 # d)) with (cm_unit IR). |
| 751 |
symmetry. apply Exp_zero. |
| 752 |
rewrite <- inj_Q_Zero. |
| 753 |
apply inj_Q_wd. reflexivity. |
| 754 |
- rewrite rational_exp_neg_correct. |
| 755 |
apply (@rational_exp_pos_correct (Zpos n#d)). |
| 756 |
discriminate. |
| 757 |
apply (rational_exp_neg_posH' (1#3)). |
| 758 |
discriminate. |
| 759 |
now apply CRe_inv_posH. |
| 760 |
- apply rational_exp_neg_correct. |
| 761 |
Qed. |
| 762 |
|
| 763 |
Lemma rational_exp_square (a : Q) : |
| 764 |
a ≤ 0 → CRpower_N_bounded 2 (1 # 1) (rational_exp (a / 2)) = rational_exp a. |
| 765 |
Proof. |
| 766 |
intros. |
| 767 |
rewrite 2!rational_exp_correct. |
| 768 |
now apply rational_exp_neg_bounded_correct_aux. |
| 769 |
Qed. |
| 770 |
|
| 771 |
Lemma rational_exp_opp (c : Qpos) (a : Q) : |
| 772 |
0 ≤ a → '(proj1_sig c) ≤ rational_exp (-a) → CRinv_pos c (rational_exp (-a)) = rational_exp a. |
| 773 |
Proof. |
| 774 |
rewrite ?rational_exp_correct. |
| 775 |
intros. now apply rational_exp_pos_correct. |
| 776 |
Qed. |
| 777 |
|
| 778 |
Lemma rational_exp_lower_bound (c : Qpos) (a : Q) : |
| 779 |
a ≤ 0 → '(proj1_sig c) ≤ CRe_inv |
| 780 |
→ '(proj1_sig (Qpos_power c (-Qfloor a))) ≤ rational_exp a. |
| 781 |
Proof. |
| 782 |
rewrite rational_exp_correct. |
| 783 |
now apply rational_exp_neg_posH'. |
| 784 |
Qed. |
| 785 |
|
| 786 |
(** |
| 787 |
*** e |
| 788 |
*) |
| 789 |
Definition CRe : CR := rational_exp 1. |
| 790 |
|
| 791 |
Lemma CRe_correct : (CRe = IRasCR E)%CR. |
| 792 |
Proof. |
| 793 |
unfold CRe. |
| 794 |
rewrite -> rational_exp_correct. |
| 795 |
apply IRasCR_wd. |
| 796 |
rewrite inj_Q_One. |
| 797 |
algebra. |
| 798 |
Qed. |
| 799 |
|
| 800 |
#[global] |
| 801 |
Hint Rewrite <- CRe_correct : IRtoCR. |
| 802 |
|
| 803 |
Opaque inj_Q. |
| 804 |
|
| 805 |
(** [exp] is uniformly continuous below any given integer. *) |
| 806 |
Definition exp_bound (z:Z) : Qpos := |
| 807 |
(match z with |
| 808 |
|Z0 => 1#1 |
| 809 |
|Zpos p => Qpos_power (3#1) p |
| 810 |
|Zneg p => Qpos_power (1#2) p |
| 811 |
end)%Qpos. |
| 812 |
|
| 813 |
Lemma exp_bound_bound : forall (z:Z) x, closer (inj_Q IR (z:Q)) x -> AbsIR (Exp x)[<=]inj_Q IR (proj1_sig (exp_bound z)). |
| 814 |
Proof. |
| 815 |
intros [|z|z]; simpl; intros x Hx; apply AbsSmall_imp_AbsIR; |
| 816 |
(apply leEq_imp_AbsSmall;[apply less_leEq; apply Exp_pos|]). |
| 817 |
rewrite inj_Q_One. |
| 818 |
apply Exp_leEq_One. |
| 819 |
rewrite inj_Q_Zero in Hx. |
| 820 |
exact Hx. |
| 821 |
apply leEq_transitive with (Exp (Max x [0])). |
| 822 |
apply Exp_resp_leEq. |
| 823 |
apply lft_leEq_Max. |
| 824 |
stepr (Three[!](inj_Q IR (inject_Z z))[//](pos_three IR)). |
| 825 |
astepl (E[!](Max x [0])[//]pos_E). |
| 826 |
apply real_power_resp_leEq_both; try solve [IR_solve_ineq (1#1)%Qpos]. |
| 827 |
apply rht_leEq_Max. |
| 828 |
apply Max_leEq; auto. |
| 829 |
stepl (inj_Q IR 0). |
| 830 |
apply inj_Q_leEq. |
| 831 |
simpl; auto with *. |
| 832 |
apply (inj_Q_nring IR 0). |
| 833 |
stepl (Three[!]nring (nat_of_P z)[//]pos_three IR). |
| 834 |
astepl (@nring IR 3 [^](nat_of_P z)). |
| 835 |
stepl ((inj_Q IR (3%mc:Q))[^](nat_of_P z)). |
| 836 |
stepl (inj_Q IR (3%mc^z)). |
| 837 |
apply inj_Q_wd. |
| 838 |
apply eq_symmetric. |
| 839 |
reflexivity. |
| 840 |
rewrite <- convert_is_POS. |
| 841 |
apply inj_Q_power. |
| 842 |
apply nexp_wd. |
| 843 |
apply (inj_Q_nring IR 3). |
| 844 |
apply power_wd. |
| 845 |
apply eq_reflexive. |
| 846 |
apply eq_symmetric. |
| 847 |
rewrite <- convert_is_POS. |
| 848 |
stepl (inj_Q IR (nring (nat_of_P z))). |
| 849 |
apply (inj_Q_nring). |
| 850 |
apply inj_Q_wd; apply nring_Q. |
| 851 |
stepr (Half[!](inj_Q IR (inject_Z z))[//](pos_half IR)). |
| 852 |
astepl (Exp [--][--]x). |
| 853 |
astepl ([1][/]_[//](Exp_ap_zero [--]x)). |
| 854 |
unfold Half. |
| 855 |
astepr (([1][!]inj_Q IR (z:Q)[//]pos_one _)[/]((Two[!]inj_Q IR (z:Q)[//]pos_two _))[//]power_ap_zero _ _ _). |
| 856 |
astepr ([1][/]((Two[!]inj_Q IR (z:Q)[//]pos_two _))[//]power_ap_zero _ _ _). |
| 857 |
apply recip_resp_leEq. |
| 858 |
apply power_pos. |
| 859 |
astepr (E[!][--]x[//]pos_E). |
| 860 |
apply real_power_resp_leEq_both; try solve [IR_solve_ineq (1#1)%Qpos]. |
| 861 |
stepl (inj_Q IR 0). |
| 862 |
apply inj_Q_leEq. |
| 863 |
simpl; auto with *. |
| 864 |
apply (inj_Q_nring IR 0). |
| 865 |
rewrite <- cg_inv_inv. |
| 866 |
apply inv_resp_leEq. |
| 867 |
stepr (inj_Q IR ((Zneg z):Q)). |
| 868 |
assumption. |
| 869 |
astepr (inj_Q IR (-(z:Q))). |
| 870 |
apply inj_Q_wd. |
| 871 |
simpl; reflexivity. |
| 872 |
stepl (Half[!]nring (nat_of_P z)[//]pos_half IR). |
| 873 |
astepl (@Half IR [^](nat_of_P z)). |
| 874 |
stepl ((inj_Q IR ((1#2):Q))[^](nat_of_P z)). |
| 875 |
stepl (inj_Q IR ((1#2)^z)). |
| 876 |
apply inj_Q_wd. |
| 877 |
apply eq_symmetric. |
| 878 |
reflexivity. |
| 879 |
rewrite <- (convert_is_POS z). |
| 880 |
apply inj_Q_power. |
| 881 |
apply nexp_wd. |
| 882 |
assert (X:(inj_Q IR (2:Q))[#][0]). |
| 883 |
stepr (inj_Q IR 0). |
| 884 |
apply inj_Q_ap; discriminate. |
| 885 |
apply (inj_Q_nring IR 0). |
| 886 |
stepr ((inj_Q IR 1)[/]_[//]X). |
| 887 |
stepl (inj_Q IR (1/2)). |
| 888 |
apply inj_Q_div. |
| 889 |
apply inj_Q_wd. |
| 890 |
apply eq_symmetric; apply Qmake_Qdiv. |
| 891 |
apply div_wd. |
| 892 |
apply inj_Q_One. |
| 893 |
apply (inj_Q_nring IR 2). |
| 894 |
apply power_wd. |
| 895 |
apply eq_reflexive. |
| 896 |
apply eq_symmetric. |
| 897 |
rewrite <- convert_is_POS. |
| 898 |
stepl (inj_Q IR (nring (nat_of_P z))). |
| 899 |
apply (inj_Q_nring). |
| 900 |
apply inj_Q_wd; apply nring_Q. |
| 901 |
Qed. |
| 902 |
|
| 903 |
Lemma exp_bound_uc_prf : forall z:Z, is_UniformlyContinuousFunction (fun a => rational_exp (Qmin z a)) (Qscale_modulus (proj1_sig (exp_bound z))). |
| 904 |
Proof. |
| 905 |
intros z. |
| 906 |
assert (Z:Derivative (closer (inj_Q IR (z:Q))) I Expon Expon). |
| 907 |
apply (Included_imp_Derivative realline I). |
| 908 |
Deriv. |
| 909 |
Included. |
| 910 |
apply (is_UniformlyContinuousD None (Some (z:Q)) I _ _ Z). |
| 911 |
intros q [] H. |
| 912 |
apply rational_exp_correct. |
| 913 |
intros x [] H. |
| 914 |
apply: exp_bound_bound. |
| 915 |
assumption. |
| 916 |
Qed. |
| 917 |
|
| 918 |
Definition exp_bound_uc (z:Z) : Q_as_MetricSpace --> CR := |
| 919 |
Build_UniformlyContinuousFunction (@exp_bound_uc_prf z). |
| 920 |
|
| 921 |
(** [exp] for any real number upto a given integer. *) |
| 922 |
Definition exp_bounded (z:Z) : CR --> CR := (Cbind QPrelengthSpace (exp_bound_uc z)). |
| 923 |
|
| 924 |
Lemma exp_bounded_correct : forall (z:Z) x, closer (inj_Q _ (z:Q)) x -> (IRasCR (Exp x)==exp_bounded z (IRasCR x))%CR. |
| 925 |
Proof. |
| 926 |
intros z x Hx. |
| 927 |
assert (Z:Continuous (closer (inj_Q IR (z:Q))) Expon). |
| 928 |
apply (Included_imp_Continuous realline). |
| 929 |
Contin. |
| 930 |
Included. |
| 931 |
apply (fun a b c => @ContinuousCorrect _ a Expon Z b c x I); auto with *. |
| 932 |
constructor. |
| 933 |
intros q [] H. |
| 934 |
transitivity (exp_bound_uc z q);[|]. |
| 935 |
change (' q)%CR with (Cunit_fun _ q). |
| 936 |
unfold exp_bounded. |
| 937 |
pose proof (Cbind_correct QPrelengthSpace (exp_bound_uc z)). |
| 938 |
apply ucEq_equiv in H0. |
| 939 |
rewrite (H0 (Cunit_fun Q_as_MetricSpace q)). clear H0. |
| 940 |
apply BindLaw1. |
| 941 |
change (rational_exp (Qmin z q) == IRasCR (Exp (inj_Q IR q)))%CR. |
| 942 |
rewrite -> rational_exp_correct. |
| 943 |
apply IRasCR_wd. |
| 944 |
apply Exp_wd. |
| 945 |
apply inj_Q_wd. |
| 946 |
simpl. |
| 947 |
rewrite <- Qle_min_r. |
| 948 |
apply leEq_inj_Q with IR. |
| 949 |
assumption. |
| 950 |
Qed. |
| 951 |
|
| 952 |
(** exp on all real numbers. [exp_bounded] should be used instead when [x] |
| 953 |
is known to be bounded by some intenger. *) |
| 954 |
Definition exp (x:CR) : CR |
| 955 |
:= exp_bounded (Qceiling (approximate x (Qpos2QposInf (1#1)) + (1#1))) x. |
| 956 |
(* begin hide *) |
| 957 |
Arguments exp : clear implicits. |
| 958 |
(* end hide *) |
| 959 |
Lemma exp_bound_lemma : forall x : CR, (x <= ' (approximate x (Qpos2QposInf (1 # 1)) + 1)%Q)%CR. |
| 960 |
Proof. |
| 961 |
intros x. |
| 962 |
assert (X:=ball_approx_l x (1#1)). |
| 963 |
rewrite <- CRAbsSmall_ball in X. |
| 964 |
destruct X as [X _]. |
| 965 |
simpl in X. |
| 966 |
rewrite <- CRplus_Qplus. |
| 967 |
apply CRle_trans with (doubleSpeed x). |
| 968 |
rewrite -> (doubleSpeed_Eq x); apply CRle_refl. |
| 969 |
intros e. |
| 970 |
assert (Y:=X e). |
| 971 |
simpl in *. |
| 972 |
do 2 (unfold Cap_raw in *; simpl in * ). |
| 973 |
apply (Qle_trans _ _ _ Y). |
| 974 |
ring_simplify. apply Qle_refl. |
| 975 |
Qed. |
| 976 |
|
| 977 |
Lemma exp_correct : forall x, (IRasCR (Exp x) = exp (IRasCR x))%CR. |
| 978 |
Proof. |
| 979 |
intros x. |
| 980 |
unfold exp. |
| 981 |
apply exp_bounded_correct. |
| 982 |
simpl. |
| 983 |
apply leEq_transitive with (inj_Q IR ((approximate (IRasCR x) (Qpos2QposInf (1 # 1)) + 1))); |
| 984 |
[|apply inj_Q_leEq; simpl;auto with *]. |
| 985 |
rewrite -> IR_leEq_as_CR. |
| 986 |
rewrite -> IR_inj_Q_as_CR. |
| 987 |
apply exp_bound_lemma. |
| 988 |
Qed. |
| 989 |
(* begin hide *) |
| 990 |
#[global] |
| 991 |
Hint Rewrite exp_correct : IRtoCR. |
| 992 |
(* end hide *) |
| 993 |
Lemma exp_bound_exp : forall (z:Z) (x:CR), |
| 994 |
(x <= 'z -> |
| 995 |
exp_bounded z x == exp x)%CR. |
| 996 |
Proof. |
| 997 |
intros z x H. |
| 998 |
unfold exp. |
| 999 |
set (a:=(approximate x (Qpos2QposInf (1 # 1)) + 1)). |
| 1000 |
rewrite <- (CRasIRasCR_id x). |
| 1001 |
rewrite <- exp_bounded_correct. |
| 1002 |
rewrite <- exp_bounded_correct. |
| 1003 |
reflexivity. |
| 1004 |
change (CRasIR x [<=] inj_Q IR (Qceiling a:Q)). |
| 1005 |
rewrite -> IR_leEq_as_CR. |
| 1006 |
autorewrite with IRtoCR. |
| 1007 |
rewrite -> CRasIRasCR_id. |
| 1008 |
apply CRle_trans with ('a)%CR. |
| 1009 |
apply exp_bound_lemma. |
| 1010 |
rewrite -> CRle_Qle. |
| 1011 |
auto with *. |
| 1012 |
change (CRasIR x [<=] inj_Q IR (z:Q)). |
| 1013 |
rewrite -> IR_leEq_as_CR. |
| 1014 |
autorewrite with IRtoCR. |
| 1015 |
rewrite -> CRasIRasCR_id. |
| 1016 |
assumption. |
| 1017 |
Qed. |
| 1018 |
(* begin hide *) |
| 1019 |
Add Morphism exp with signature (@msp_eq _) ==> (@msp_eq _) as exp_wd. |
| 1020 |
Proof. |
| 1021 |
intros x y Hxy. |
| 1022 |
unfold exp at 1. |
| 1023 |
set (a := (approximate x (Qpos2QposInf (1 # 1)) + 1)). |
| 1024 |
rewrite -> Hxy. |
| 1025 |
apply exp_bound_exp. |
| 1026 |
rewrite <- Hxy. |
| 1027 |
apply CRle_trans with ('a)%CR. |
| 1028 |
apply exp_bound_lemma. |
| 1029 |
rewrite -> CRle_Qle. |
| 1030 |
auto with *. |
| 1031 |
Qed. |
| 1032 |
(* end hide *) |
| 1033 |
Lemma exp_Qexp : forall x : Q, (exp (' x) = rational_exp x)%CR. |
| 1034 |
Proof. |
| 1035 |
intros x. |
| 1036 |
rewrite <- IR_inj_Q_as_CR. |
| 1037 |
rewrite <- exp_correct. |
| 1038 |
rewrite <- rational_exp_correct. |
| 1039 |
reflexivity. |
| 1040 |
Qed. |
| 1041 |
|
| 1042 |
#[global] |
| 1043 |
Instance: Proper ((=) ==> (=)) rational_exp. |
| 1044 |
Proof. |
| 1045 |
intros x1 x2 E. |
| 1046 |
rewrite <-2!exp_Qexp. |
| 1047 |
now rewrite E. |
| 1048 |
Qed. |
| 1049 |
|
| 1050 |
(* begin hide *) |
| 1051 |
#[global] |
| 1052 |
Hint Rewrite exp_Qexp : CRfast_compute. |
| 1053 |
(* end hide *) |