Debian Codegraph @

reals/fast/CRexp.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.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 *)