Debian Codegraph @

reals/fast/CRln.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 Import CoRN.reals.fast.CRartanh_slow.
26 Require Export CoRN.reals.fast.CRArith.
27 Require Import CoRN.reals.fast.CRIR.
28 From Coq Require Import Qpower.
29 Require Import CoRN.model.ordfields.Qordfield.
30 Require Import CoRN.reals.fast.ModulusDerivative.
31 Require Import CoRN.reals.fast.ContinuousCorrect.
32 Require Import CoRN.model.metric2.Qmetric.
33 Require Import CoRN.tactics.Qauto.
34 Require Import CoRN.transc.Exponential.
35 Require Import CoRN.transc.ArTanH.
36 Require Import CoRN.tactics.CornTac.
37
38 Set Implicit Arguments.
39
40 Local Open Scope Q_scope.
41 Local Open Scope uc_scope.
42
43 Opaque inj_Q CR Logarithm.
44
45 (**
46 ** Logarithm
47 Logarithm is defined in terms of artanh. [ln (n/d) = 2*artan((n-d)/(n+d))]
48 *)
49
50 Lemma lnDomainAdaptor : forall a, (0 < a) ->
51 (let (n,d) := a in (n - Zpos d)/(n + Zpos d))^2 < 1.
52 Proof.
53 intros [[|n|n] d] Ha; try solve [elim (Qlt_not_le _ _ Ha); auto with *].
54 simpl.
55 replace LHS with ((n-d)*(n-d)/((n+d)*(n+d))) by simpl; field; auto with *.
56 apply Qlt_shift_div_r.
57 auto with *.
58 rewrite -> Qlt_minus_iff.
59 ring_simplify.
60 Qauto_pos.
61 Qed.
62
63 (** Although [rational_ln_slow] works on the entire to domain, it is
64 only efficent for values close 1. *)
65 Definition rational_ln_slow (a:Q) (p: 0 < a) : CR :=
66 scale 2 (rational_artanh_slow (lnDomainAdaptor p)).
67
68 Lemma Qpos_adaptor : forall q, 0 < q -> [0][<]inj_Q IR q.
69 Proof.
70 intros q H.
71 stepl (inj_Q IR 0).
72 apply inj_Q_less.
73 assumption.
74 apply (inj_Q_nring IR 0).
75 Qed.
76
77 Lemma rational_ln_slow_correct : forall (a:Q) Ha Ha0,
78 (@rational_ln_slow a Ha == IRasCR (Log (inj_Q IR a) Ha0))%CR.
79 Proof.
80 intros a Ha Ha0.
81 unfold rational_ln_slow.
82 assert (X:=artanh_DomArTanH (lnDomainAdaptor Ha)).
83 rewrite -> (fun x => rational_artanh_slow_correct x X).
84 rewrite <- CRmult_scale.
85 rewrite <- IR_inj_Q_as_CR.
86 rewrite <- IR_mult_as_CR.
87 apply IRasCR_wd.
88 csetoid_replace (inj_Q IR (2:Q)) (Two:IR); [|apply (inj_Q_nring IR 2)].
89 stepr (Two[*](Half[*]Log _ Ha0)); [|unfold Half; rational].
90 do 2 apply: mult_wdr.
91 unfold Log.
92 simpl.
93 apply cspf_wd.
94 set (b:=let (n, d) := a in (n - Zpos d) / (n + Zpos d)).
95 assert (Y:inj_Q IR a[+][1][#][0]).
96 apply Greater_imp_ap.
97 apply plus_resp_pos; try assumption.
98 apply pos_one.
99 assert (Z:[1][-](inj_Q IR a[-][1][/]_[//]Y)[#][0]).
100 apply Greater_imp_ap.
101 rstepr (Two[/]_[//]Y).
102 apply div_resp_pos.
103 apply plus_resp_pos; try assumption.
104 apply pos_one.
105 apply pos_two.
106 rstepr ([1][+](inj_Q IR a[-][1][/]_[//]Y)[/]_[//]Z).
107 cut (inj_Q IR b[=](inj_Q IR a[-][1][/]inj_Q IR a[+][1][//]Y)).
108 intros.
109 apply div_wd;
110 apply bin_op_wd_unfolded; try apply eq_reflexive; try apply un_op_wd_unfolded; assumption.
111 stepr (inj_Q IR ((a-1)/(a+1))).
112 apply inj_Q_wd.
113 clear - Ha.
114 destruct a as [n d].
115 simpl.
116 unfold b.
117 rewrite -> Qmake_Qdiv.
118 field.
119 split.
120 unfold Qeq.
121 auto with *.
122 unfold Qeq, Qlt in *.
123 simpl in *.
124 intros H.
125 apply (Zlt_not_le _ _ Ha).
126 ring_simplify in H.
127 ring_simplify.
128 apply Z.le_trans with (-(d*1))%Z. 2: auto with *.
129 apply Zle_left_rev.
130 replace RHS with (-(n + (d*1)))%Z by ring.
131 simpl.
132 rewrite H.
133 apply Z.le_refl.
134 clear - Y.
135 assert (X:inj_Q IR (a + 1)[#][0]).
136 stepl (inj_Q IR a [+]inj_Q IR (nring 1)); [| now apply eq_symmetric; apply inj_Q_plus].
137 csetoid_rewrite (inj_Q_nring IR 1).
138 rstepl (inj_Q IR a[+][1]).
139 assumption.
140 stepl (inj_Q IR (a - 1)[/]_[//]X); [| now apply eq_symmetric; apply inj_Q_div].
141 apply div_wd.
142 stepl (inj_Q IR a[-]inj_Q IR 1); [| now apply eq_symmetric; apply inj_Q_minus].
143 apply bin_op_wd_unfolded.
144 apply eq_reflexive.
145 apply un_op_wd_unfolded.
146 rstepr (nring 1:IR).
147 apply (inj_Q_nring IR 1).
148 stepl (inj_Q IR a[+]inj_Q IR 1); [| now apply eq_symmetric; apply inj_Q_plus].
149 apply bin_op_wd_unfolded.
150 apply eq_reflexive.
151 rstepr (nring 1:IR).
152 apply (inj_Q_nring IR 1).
153 Qed.
154
155 Lemma rational_ln_slow_correct' : forall (a:Q) Ha,
156 (@rational_ln_slow a Ha == IRasCR (Log (inj_Q IR a) (Qpos_adaptor Ha)))%CR.
157 Proof.
158 intros.
159 apply rational_ln_slow_correct.
160 Qed.
161
162 (** Efficeny of ln is imporved by scaling the input by a power of two
163 and adding or subtracting a multiple of [ln 2]. *)
164 Definition ln2 : CR := rational_ln_slow (pos_two Q_as_COrdField).
165
166 Lemma ln2_correct : (ln2 == IRasCR (Log Two (pos_two IR)))%CR.
167 Proof.
168 unfold ln2.
169 rewrite -> rational_ln_slow_correct'.
170 apply IRasCR_wd.
171 apply Log_wd.
172 apply (inj_Q_nring IR 2).
173 Qed.
174
175 Lemma ln_scale_by_two_power_adapt : forall (n:Z) q, 0 < q -> 0 < (2^n*q).
176 Proof.
177 intros n q H.
178 apply (Qlt_le_trans _ (proj1_sig (Qpos_power (2#1) n * exist _ _ H)%Qpos)).
179 apply Qpos_ispos.
180 apply Qle_refl.
181 Qed.
182
183 Lemma ln_scale_by_two_power : forall (n:Z) q (Hq:0 < q), (rational_ln_slow Hq + scale n ln2 == rational_ln_slow (ln_scale_by_two_power_adapt n Hq))%CR.
184 Proof.
185 intros n q Hq.
186 rewrite -> ln2_correct.
187 do 2 rewrite -> rational_ln_slow_correct'.
188 rewrite <- CRmult_scale.
189 rewrite <- IR_inj_Q_as_CR.
190 rewrite <- IR_mult_as_CR.
191 rewrite <- IR_plus_as_CR.
192 apply IRasCR_wd.
193 assert (X:[0][<](Two[//](two_ap_zero IR))[^^]n).
194 apply zexp_pos.
195 apply pos_two.
196 stepl (Log _ (Qpos_adaptor Hq)[+]Log _ X).
197 assert (Y:[0][<](inj_Q IR q)[*](Two[//](two_ap_zero IR))[^^]n).
198 apply mult_resp_pos.
199 apply (Qpos_adaptor Hq).
200 assumption.
201 stepl (Log _ Y).
202 apply Log_wd.
203 assert (Z:(inj_Q IR (2:Q))[#][0]).
204 stepr (inj_Q IR (0:Q)).
205 apply inj_Q_ap.
206 discriminate.
207 apply (inj_Q_nring IR 0).
208 csetoid_replace ((Two[//]two_ap_zero IR)[^^](n)) (((inj_Q IR (2:Q))[//]Z)[^^]n).
209 stepr (inj_Q IR q[*]inj_Q IR (2^n)).
210 apply mult_wdr.
211 apply eq_symmetric.
212 apply inj_Q_power_Z.
213 rstepl (inj_Q IR (2 ^ n)[*]inj_Q IR q).
214 apply eq_symmetric.
215 apply (inj_Q_mult IR (2^n) q).
216 apply zexp_wd.
217 apply eq_symmetric.
218 apply (inj_Q_nring IR 2).
219 apply Log_mult.
220 apply bin_op_wd_unfolded.
221 apply eq_reflexive.
222 astepl ((zring n)[*]Log Two (pos_two IR)).
223 apply mult_wdl.
224 Transparent inj_Q.
225 unfold inj_Q.
226 simpl.
227 rational.
228 Qed.
229
230 Definition ln_scale_power_factor q (Hq:0 < q) : Z.
231 Proof.
232 revert q Hq.
233 intros [[|n|n] d] Hq; try abstract discriminate Hq.
234 exact (Z.pred (Z.log2 d - Z.log2_up n))%Z.
235 Defined.
236
237 Definition rational_ln (a:Q) (p: 0 < a) : CR :=
238 let n := ln_scale_power_factor p in
239 (rational_ln_slow (ln_scale_by_two_power_adapt n p) + scale (-n)%Z ln2)%CR.
240
241 Lemma rational_ln_correct : forall (a:Q) Ha Ha0,
242 (@rational_ln a Ha == IRasCR (Log (inj_Q IR a) Ha0))%CR.
243 Proof.
244 intros a Ha Ha0.
245 unfold rational_ln.
246 rewrite <- ln_scale_by_two_power.
247 do 2 rewrite <- CRmult_scale.
248 change (((- ln_scale_power_factor Ha)%Z):Q) with ((- ln_scale_power_factor Ha)%Q).
249 rewrite <- CRopp_Qopp.
250 ring_simplify.
251 apply rational_ln_slow_correct.
252 Qed.
253
254 Lemma rational_ln_correct' : forall (a:Q) Ha,
255 (@rational_ln a Ha == IRasCR (Log (inj_Q IR a) (Qpos_adaptor Ha)))%CR.
256 Proof.
257 intros.
258 apply rational_ln_correct.
259 Qed.
260
261 (** [ln] is uniformly continuous on any close strictly positive interval. *)
262 Lemma ln_uc_prf_pos : forall (c:Qpos) (x:Q), (0 < Qmax (proj1_sig c) x).
263 Proof.
264 intros c x.
265 simpl.
266 apply Qlt_le_trans with (proj1_sig c); auto with *.
267 Qed.
268
269 Definition rational_ln_modulus (c:Qpos) (e:Qpos) : QposInf :=
270 Qpos2QposInf (c*e).
271
272 Lemma ln_pos_uc_prf (c:Qpos)
273 : @is_UniformlyContinuousFunction
274 Q_as_MetricSpace CR
275 (fun x => rational_ln (ln_uc_prf_pos c x)) (rational_ln_modulus c).
276 Proof.
277 set (lnf := fun x => match (Qlt_le_dec 0 x) with | left p => rational_ln p | right _ => 0%CR end).
278 apply (is_UniformlyContinuousFunction_wd)
279 with (fun x : Q_as_MetricSpace => lnf (QboundBelow_uc (proj1_sig c) x)) (Qscale_modulus (proj1_sig (Qpos_inv c))).
280 intros x.
281 unfold lnf.
282 destruct (Qlt_le_dec 0 (QboundBelow_uc (proj1_sig c) x)).
283 do 2 rewrite -> rational_ln_correct'.
284 apply IRasCR_wd.
285 algebra.
286 elim (Qle_not_lt _ _ q).
287 apply: ln_uc_prf_pos.
288 intros [[xn xd] xpos].
289 destruct xn as [|xn|xn]. inversion xpos. 2: inversion xpos.
290 destruct c as [[a b] cpos].
291 destruct a as [|a|a]. inversion cpos. 2: inversion cpos.
292 apply: Qle_refl.
293 assert (Z:Derivative (closel (inj_Q IR (proj1_sig c))) I Logarithm {1/}FId).
294 apply (Included_imp_Derivative (openl [0]) I).
295 Deriv.
296 intros x Hx.
297 simpl.
298 apply less_leEq_trans with (inj_Q IR (proj1_sig c)); try assumption.
299 stepl (inj_Q IR 0).
300 apply inj_Q_less.
301 simpl; auto with *.
302 apply (inj_Q_nring IR 0).
303 apply (is_UniformlyContinuousD (Some (proj1_sig c)) None I _ _ Z lnf).
304 intros q Hq Hc.
305 unfold lnf.
306 destruct (Qlt_le_dec 0 q).
307 apply rational_ln_correct.
308 elim (Qle_not_lt _ _ q0).
309 apply Qlt_le_trans with (proj1_sig c); auto with *.
310 apply leEq_inj_Q with IR.
311 assumption.
312 intros x Hx Hc.
313 apply AbsSmall_imp_AbsIR.
314 apply leEq_imp_AbsSmall.
315 apply: shift_leEq_div.
316 apply less_leEq_trans with (inj_Q IR (proj1_sig c)); try assumption.
317 stepl (inj_Q IR 0).
318 apply inj_Q_less.
319 simpl; auto with *.
320 apply (inj_Q_nring IR 0).
321 rstepl ([0]:IR).
322 apply less_leEq.
323 apply pos_one.
324 stepr ([1][/]_[//](Greater_imp_ap _ _ _ (Qpos_adaptor (Qpos_ispos c)))).
325 apply: recip_resp_leEq; try assumption.
326 stepl (inj_Q IR 0).
327 apply inj_Q_less.
328 simpl; auto with *.
329 apply (inj_Q_nring IR 0).
330 stepl (((inj_Q IR 1)[/]_[//] Greater_imp_ap IR (inj_Q IR (proj1_sig c)) [0] (Qpos_adaptor (Qpos_ispos c)))).
331 clear.
332 destruct c as [[a b] cpos].
333 destruct a as [|a|a]. inversion cpos. 2: inversion cpos.
334 unfold Qpos_inv, proj1_sig.
335 change (inj_Q IR (/ (a#b))) with (inj_Q IR (1/(a#b))).
336 apply eq_symmetric.
337 apply inj_Q_div.
338 apply div_wd.
339 rstepr (nring 1:IR).
340 apply (inj_Q_nring IR 1).
341 apply eq_reflexive.
342 Qed.
343
344 Definition ln_pos_uc (c:Qpos) : Q_as_MetricSpace --> CR :=
345 Build_UniformlyContinuousFunction (@ln_pos_uc_prf c).
346
347 Definition CRln_pos (c:Qpos) : CR --> CR := (Cbind QPrelengthSpace (ln_pos_uc c)).
348
349 Lemma CRln_pos_correct : forall (c:Qpos) x Hx, closel (inj_Q _ (proj1_sig c)) x -> (IRasCR (Log x Hx)==CRln_pos c (IRasCR x))%CR.
350 Proof.
351 intros c x Hx Hx0.
352 assert (Z:Continuous (closel (inj_Q IR (proj1_sig c))) Logarithm).
353 apply (Included_imp_Continuous (openl [0])).
354 Contin.
355 clear - c.
356 intros x Hx.
357 simpl.
358 apply less_leEq_trans with (inj_Q IR (proj1_sig c)); try assumption.
359 stepl (inj_Q IR 0).
360 apply inj_Q_less.
361 simpl; auto with *.
362 apply (inj_Q_nring IR 0).
363 apply (fun x => @ContinuousCorrect _ x Logarithm Z); auto with *.
364 constructor.
365 intros q Hq H.
366 change (CRln_pos c (' q) == IRasCR (Log (inj_Q IR q) Hq))%CR.
367 transitivity (ln_pos_uc c q);[|].
368 unfold CRln_pos.
369 change (' q)%CR with (Cunit_fun Q_as_MetricSpace q).
370 pose proof (Cbind_correct QPrelengthSpace (ln_pos_uc c)).
371 apply ucEq_equiv in H0.
372 rewrite -> (H0 (Cunit_fun Q_as_MetricSpace q)).
373 apply BindLaw1.
374 simpl.
375 rewrite -> rational_ln_correct'.
376 apply IRasCR_wd.
377 apply Log_wd.
378 apply inj_Q_wd.
379 simpl.
380 rewrite <- Qle_max_r.
381 apply leEq_inj_Q with IR.
382 assumption.
383 Qed.
384
385 Definition CRln (x:CR) (Hx:(0 < x)%CR) : CR :=
386 let (c,_) := Hx in CRln_pos c x.
387 (* begin hide *)
388 Arguments CRln : clear implicits.
389 (* end hide *)
390 Lemma CRln_correct : forall x Hx Hx0, (IRasCR (Log x Hx)==CRln (IRasCR x) Hx0)%CR.
391 Proof.
392 intros x Hx [c Hc].
393 apply CRln_pos_correct.
394 change ((inj_Q IR (proj1_sig c))[<=]x).
395 rewrite -> IR_leEq_as_CR.
396 rewrite -> IR_inj_Q_as_CR.
397 setoid_replace (IRasCR x) with (IRasCR x - 0)%CR by (simpl; ring).
398 assumption.
399 Qed.
400
401 Lemma CRln_pos_ln : forall (c:Qpos) (x:CR) Hx,
402 ('proj1_sig c <= x ->
403 CRln_pos c x == CRln x Hx)%CR.
404 Proof.
405 intros c x Hx Hc.
406 assert (X:[0][<](CRasIR x)).
407 apply CR_less_as_IR.
408 apply CRltT_wd with 0%CR x; try assumption.
409 rewrite -> IR_Zero_as_CR.
410 reflexivity.
411 rewrite -> CRasIRasCR_id.
412 reflexivity.
413 destruct Hx as [d Hd].
414 unfold CRln.
415 rewrite <- (CRasIRasCR_id x).
416 rewrite <- (CRln_pos_correct c _ X).
417 rewrite <- (CRln_pos_correct d _ X).
418 reflexivity.
419 change (inj_Q IR (proj1_sig d)[<=](CRasIR x)).
420 rewrite -> IR_leEq_as_CR.
421 autorewrite with IRtoCR.
422 rewrite -> CRasIRasCR_id.
423 ring_simplify in Hd.
424 assumption.
425 change (inj_Q IR (proj1_sig c)[<=](CRasIR x)).
426 rewrite -> IR_leEq_as_CR.
427 autorewrite with IRtoCR.
428 rewrite -> CRasIRasCR_id.
429 assumption.
430 Qed.
431
432 Lemma CRln_wd : forall (x y:CR) Hx Hy, (x == y -> CRln x Hx == CRln y Hy)%CR.
433 Proof.
434 intros x y [c Hc] Hy Hxy.
435 unfold CRln at 1.
436 rewrite -> Hxy.
437 apply CRln_pos_ln.
438 rewrite <- Hxy.
439 ring_simplify in Hc.
440 assumption.
441 Qed.
442
443 Lemma CRln_irrelvent : forall x Hx Hx0, (CRln x Hx == CRln x Hx0)%CR.
444 Proof.
445 intros.
446 apply CRln_wd.
447 reflexivity.
448 Qed.