Debian Codegraph @

reals/faster/ARexp.v

raw
1 From Coq Require Import ZArith.
2 Require Import CoRN.algebra.RSetoid.
3 Require Import CoRN.metric2.Metric.
4 Require Import CoRN.metric2.UniformContinuity.
5 From Coq Require Import Program.
6 Require Import MathClasses.misc.workaround_tactics
7 CoRN.model.totalorder.QposMinMax
8 CoRN.model.totalorder.QMinMax.
9 From Coq Require Import Qround Qabs.
10 Require Import CoRN.util.Qdlog CoRN.stdlib_omissions.Q
11 CoRN.reals.fast.CRexp CoRN.reals.fast.CRstreams CoRN.reals.fast.CRAlternatingSum
12 CoRN.reals.fast.Compress CoRN.reals.fast.CRpower
13 CoRN.metric2.MetricMorphisms CoRN.reals.faster.ARAlternatingSum MathClasses.interfaces.abstract_algebra
14 MathClasses.orders.minmax MathClasses.theory.nat_pow MathClasses.theory.int_pow.
15 Require Export
16 CoRN.reals.faster.ARArith.
17
18 Section ARexp.
19 Context `{AppRationals AQ}.
20
21 Section exp_small_neg.
22 Context {a : AQ} (Pa : -1 ≤ a ≤ 0).
23
24 (*
25 Split the stream
26 (-a)^i / i!
27 up into the streams
28 (-a)^i and i!
29 because we do not have exact division
30 *)
31 Definition ARexpStream (px : positive*(AQ*AQ)) : AQ*AQ
32 := (fst (snd px) * a, snd (snd px) * ZtoAQ (Zpos (fst px))).
33
34 Lemma AQexp_small_neg_prf : -1 ≤ ('a : Q) ≤ 0.
35 Proof.
36 split.
37 now apply rings.preserves_ge_negate1.
38 now apply semirings.preserves_nonpos.
39 Qed.
40
41 (*
42 The ARInfAltSum function computes the infinite alternating sum
43 and takes care of:
44 - Computing the length of the partial sum
45 - Computing the precision of the approximate division
46 *)
47 Lemma expStream_pos : ∀ x : positive * (AQ * AQ),
48 0 < snd (snd x) → 0 < snd (ARexpStream x).
49 Proof.
50 intros. unfold ARexpStream. simpl.
51 assert (AQtoQ 0 == 0).
52 apply rings.preserves_0.
53 destruct aq_strict_order_embed.
54 apply strict_order_embedding_reflecting.
55 rewrite rings.preserves_mult, rings.preserves_0.
56 apply (Qle_lt_trans _ (AQtoQ (snd (snd x)) * 0)).
57 rewrite Qmult_0_r. apply Qle_refl.
58 apply Qmult_lt_l.
59 rewrite <- H6. apply strict_order_embedding_preserving, H5.
60 pose proof AQtoQ_ZtoAQ.
61 unfold cast in H7. rewrite H7.
62 reflexivity.
63 Qed.
64
65 Lemma AQ0_lt_1 : 0 < 1.
66 Proof.
67 destruct aq_strict_order_embed.
68 apply strict_order_embedding_reflecting.
69 rewrite rings.preserves_0, rings.preserves_1.
70 reflexivity.
71 Qed.
72
73 Lemma expStream_correct : ∀ p : positive,
74 Str_pth _ (CRexp.expStream (AQtoQ a)) p (1%positive, 1%Q)
75 == let (_, r) := iterate _ (fS ARexpStream) p (1%positive, (1, 1)) in
76 AQtoQ (fst r) / AQtoQ (snd r).
77 Proof.
78 apply Pos.peano_ind.
79 - unfold Str_pth. simpl.
80 rewrite Qmult_1_l, Qmult_1_r.
81 rewrite rings.mult_1_l, rings.mult_1_l.
82 pose proof (AQtoQ_ZtoAQ 1).
83 unfold cast in H5. rewrite H5.
84 unfold stdlib_rationals.inject_Z_Q, inject_Z.
85 unfold Qdiv. rewrite Qmult_1_r. reflexivity.
86 - intros. unfold Str_pth.
87 rewrite iterate_succ, iterate_succ.
88 unfold Str_pth in H5.
89 pose proof (fS_fst ARexpStream p (1,1)).
90 pose proof (expStream_fst (AQtoQ a) p).
91 destruct (iterate _ (CRexp.expStream (AQtoQ a)) p (1%positive, 1%Q)) as [u v].
92 destruct (iterate (positive * (AQ * AQ)) (fS ARexpStream) p (1%positive, (1, 1))).
93 unfold snd in H5 at 1. simpl.
94 unfold fst in H6. subst p0.
95 rewrite H5. unfold fst in H7. clear H5 v.
96 subst u.
97 assert (forall i j : AQ, AQtoQ (i*j) == AQtoQ i * AQtoQ j).
98 { intros. rewrite rings.preserves_mult. reflexivity. }
99 rewrite H5, H5. unfold Qdiv.
100 rewrite Qinv_mult_distr.
101 pose proof (AQtoQ_ZtoAQ).
102 unfold cast in H6. rewrite H6.
103 unfold stdlib_rationals.inject_Z_Q, inject_Z.
104 setoid_replace (/ (Z.pos (Pos.succ p) # 1))%Q with (1#Pos.succ p).
105 ring. reflexivity.
106 Qed.
107
108 Definition AQexp_small_neg : AR
109 := 1+ AltSeries ARexpStream expStream_pos
110 positive (CRexp.expStream (AQtoQ a))
111 (1,1) (xH,1) expStream_correct _
112 (expStream_alt AQexp_small_neg_prf)
113 AQ0_lt_1 (expStream_zl AQexp_small_neg_prf).
114
115 Lemma AQexp_small_neg_correct
116 : 'AQexp_small_neg = rational_exp_small_neg AQexp_small_neg_prf.
117 Proof.
118 unfold AQexp_small_neg, rational_exp_small_neg.
119 rewrite ARtoCR_preserves_plus.
120 rewrite ARtoCR_preserves_1.
121 rewrite <- CRplus_translate.
122 apply ucFun2_wd. reflexivity.
123 apply AltSeries_correct.
124 Qed.
125
126 End exp_small_neg.
127
128 (*
129 Implement the range reduction
130 exp(x) = exp(x/2) ^ 2
131 *)
132 Fixpoint ARpower_2_iter (n : nat) (x : AR) : AR :=
133 match n with
134 | O => x
135 | S p => ARpower_N_bounded 2 1 (ARcompress (ARpower_2_iter p x))
136 end.
137
138 Lemma ARpower_2_iter_wd : forall (n : nat) (x y : AR),
139 x = y -> ARpower_2_iter n x = ARpower_2_iter n y.
140 Proof.
141 induction n.
142 - intros. exact H5.
143 - intros. simpl. apply Cmap_wd. reflexivity.
144 pose proof ARcompress_correct.
145 simpl in H6.
146 rewrite H6, H6.
147 apply IHn, H5.
148 Qed.
149
150 Lemma AQexp_neg_bounded_correct : ∀ (n : nat) a (abound : -1 ≤ a * (1 ≪ (-1)) ^ n ≤ 0),
151 a ≤ 0 ->
152 ' ARpower_2_iter n (AQexp_small_neg abound) = rational_exp (' a).
153 Proof.
154 induction n.
155 - intros. simpl.
156 rewrite AQexp_small_neg_correct.
157 rewrite rational_exp_small_neg_correct.
158 rewrite rational_exp_correct.
159 apply CRIR.IRasCR_wd, Exponential.Exp_wd.
160 apply Q_in_CReals.inj_Q_wd.
161 rewrite rings.preserves_mult.
162 unfold pow. simpl.
163 rewrite rings.preserves_1, Qmult_1_r.
164 reflexivity.
165 - intros a abound aneg.
166 change (ARpower_2_iter (S n) (AQexp_small_neg abound))
167 with (ARpower_N_bounded 2 1 (ARcompress (ARpower_2_iter n (AQexp_small_neg abound)))).
168 rewrite ARcompress_correct.
169 rewrite ARtoCR_preserves_power_N_bounded.
170 assert (-1 ≤ a * (1 ≪ (-1)) * (1 ≪ (-1)) ^ n ≤ 0) as abound_shift.
171 { setoid_replace (a * 1 ≪ (-1) * (1 ≪ (-1)) ^ n )
172 with (a * (1 ≪ (-1)) ^ S n). exact abound.
173 unfold pow at 2. simpl.
174 rewrite (rings.mult_assoc a). reflexivity. }
175 specialize (IHn _ abound_shift).
176 setoid_replace (' ARpower_2_iter n (AQexp_small_neg abound))
177 with (' ARpower_2_iter n (AQexp_small_neg abound_shift)).
178 rewrite IHn. clear IHn.
179 transitivity (CRpower_N_bounded 2 (1#1)%Qpos (rational_exp (' (a ≪ (-1))))).
180 + apply Cmap_wd.
181 setoid_replace ('1 : Qpos) with (1#1)%Qpos.
182 reflexivity.
183 rewrite AQposAsQpos_preserves_1. reflexivity.
184 setoid_replace (' (a * 1 ≪ (-1))) with (' (a ≪ (-1))).
185 reflexivity. rewrite aq_shift_opp_1.
186 rewrite rings.preserves_mult.
187 rewrite aq_shift_opp_1.
188 apply Qmult_comp. reflexivity.
189 rewrite rings.preserves_1. reflexivity.
190 + rewrite aq_shift_opp_1.
191 apply rational_exp_square.
192 now apply semirings.preserves_nonpos.
193 + apply (order_reflecting (cast AQ Q)).
194 rewrite rings.preserves_mult.
195 rewrite rings.preserves_0.
196 rewrite <- (Qmult_0_l (' (1 ≪ (-1)))).
197 apply Qmult_le_compat_r.
198 apply (order_preserving (cast AQ Q)) in aneg.
199 rewrite rings.preserves_0 in aneg.
200 exact aneg.
201 rewrite aq_shift_opp_1.
202 rewrite rings.preserves_1. discriminate.
203 + apply ARpower_2_iter_wd.
204 apply (injective (cast AR CR)).
205 rewrite AQexp_small_neg_correct, AQexp_small_neg_correct.
206 apply rational_exp_small_neg_wd.
207 setoid_replace (' (a * (1 ≪ (-1)) ^ S n))
208 with (' (a * 1 ≪ (-1) * (1 ≪ (-1)) ^ n)).
209 reflexivity.
210 unfold pow at 1. simpl.
211 rewrite (rings.mult_assoc a). reflexivity.
212 Qed.
213
214 Section exp_neg.
215 Context {a : AQ} (Pa : a ≤ 0).
216
217 Lemma AQexp_neg_bound_correct : -2 ^ Z.to_nat (Z.log2_up (Qceiling(-'a))) ≤ a.
218 Proof.
219 apply (order_reflecting (cast AQ Q)).
220 rewrite rings.preserves_negate.
221 rewrite preserves_nat_pow.
222 rewrite rings.preserves_2.
223 rewrite <-(int_pow_nat_pow (f:=Z_of_nat)).
224 assert ('a <= 0)%Q as H5.
225 { apply (order_preserving (cast AQ Q)) in Pa.
226 rewrite rings.preserves_0 in Pa. exact Pa. }
227 pose proof (rational_exp_bound_power_2 H5).
228 rewrite Qpower.Zpower_Qpower in H6.
229 apply H6.
230 apply Nat2Z.is_nonneg.
231 Qed.
232
233 Lemma power_2_improve_bound_correct : forall (n:nat),
234 -2 ^ n ≤ a ->
235 -1 ≤ a*(1 ≪ (-1))^n ≤ 0.
236 Proof.
237 intros.
238 assert ('a <= 0)%Q as aneg.
239 { apply (order_preserving (cast AQ Q)) in Pa.
240 rewrite rings.preserves_0 in Pa. exact Pa. }
241 pose proof (CRexp.power_2_improve_bound_correct n aneg) as H6.
242 assert ('(-1) <= '(a * (1 ≪ (-1)) ^ n) <= '0
243 -> -1 ≤ a * (1 ≪ (-1)) ^ n ≤ 0).
244 { intros. split; apply (order_reflecting (cast AQ Q)); apply H7. }
245 apply H7. clear H7.
246 rewrite rings.preserves_mult.
247 rewrite rings.preserves_negate.
248 rewrite rings.preserves_1.
249 rewrite rings.preserves_0.
250 rewrite preserves_nat_pow.
251 rewrite <-(int_pow_nat_pow (f:=Z_of_nat)).
252 rewrite (aq_shift_correct 1 (-1)).
253 rewrite rings.preserves_1.
254 rewrite Qmult_1_l. apply H6. clear H6.
255 apply (order_preserving (cast AQ Q)) in H5.
256 refine (Qle_trans _ _ _ _ H5).
257 rewrite rings.preserves_negate.
258 rewrite preserves_nat_pow.
259 rewrite <-(int_pow_nat_pow (f:=Z_of_nat)).
260 rewrite Qpower.Zpower_Qpower.
261 rewrite rings.preserves_2.
262 apply Qle_refl. apply Nat2Z.is_nonneg.
263 Qed.
264
265 Definition AQexp_neg : AR
266 := ARpower_2_iter
267 (Z.to_nat (Z.log2_up (Qceiling(-'a))))
268 (AQexp_small_neg
269 (power_2_improve_bound_correct _ (AQexp_neg_bound_correct))).
270
271 Lemma AQexp_neg_correct: 'AQexp_neg = rational_exp ('a).
272 Proof.
273 apply AQexp_neg_bounded_correct, Pa.
274 Qed.
275
276 (* We could use a number closer to 1/exp 1, for example 11 $ -5, but in practice this seems
277 to make it slower. *)
278 Program Definition AQexp_inv_pos_bound : AQ₊ := ((1 ≪ (-2)) ^ Z.abs_N (Qfloor ('a)))↾_.
279 Next Obligation. solve_propholds. Qed.
280
281 Lemma AQexp_inv_pos_bound_correct :
282 '(cast (AQ₊) Q AQexp_inv_pos_bound) ≤ rational_exp ('a).
283 Proof.
284 change (cast Q CR (cast AQ Q ((1 ≪ (-2)) ^ Z.abs_N (Qfloor ('a)))) ≤ rational_exp ('a)).
285 rewrite preserves_nat_pow.
286 rewrite aq_shift_opp_2.
287 rewrite rings.preserves_1, rings.mult_1_l.
288 rewrite <-(int_pow_nat_pow (f:=cast N Z)).
289 rewrite Z_of_N_abs, Z.abs_neq.
290 apply (rational_exp_lower_bound (1#4)).
291 now apply semirings.preserves_nonpos.
292 apply CRpos_nonNeg.
293 now CRsign.CR_solve_pos (1#1)%Qpos.
294 change (Qfloor ('a) ≤ 0).
295 apply (order_reflecting (cast Z Q)).
296 transitivity ('a : Q).
297 now apply Qfloor_le.
298 now apply semirings.preserves_nonpos.
299 Qed.
300 End exp_neg.
301
302 Lemma AQexp_prf1 {a : AQ} (pA : 0 ≤ a) : -a ≤ 0.
303 Proof. now apply rings.flip_nonneg_negate. Qed.
304
305 Lemma AQexp_prf2 {a : AQ} (pA : ¬0 ≤ a) : a ≤ 0.
306 Proof. now apply orders.le_flip. Qed.
307
308 (*
309 Extend it to the full domain.
310 *)
311 Definition AQexp (a : AQ) : AR :=
312 match decide_rel (≤) 0 a with
313 | left Pa => ARinv_pos (AQexp_inv_pos_bound (a:=-a)) (AQexp_neg (AQexp_prf1 Pa))
314 | right Pa => AQexp_neg (AQexp_prf2 Pa)
315 end.
316
317 Lemma AQexp_correct a : 'AQexp a = rational_exp ('a).
318 Proof.
319 unfold AQexp.
320 case (decide_rel _); intros.
321 rewrite ARtoCR_preserves_inv_pos.
322 rewrite AQexp_neg_correct.
323 rewrite rings.preserves_negate.
324 apply rational_exp_opp.
325 now apply semirings.preserves_nonneg.
326 posed_rewrite <-(rings.preserves_negate (f:=cast AQ Q)).
327 apply (AQexp_inv_pos_bound_correct (a:=-a)).
328 now apply rings.flip_nonneg_negate.
329 apply AQexp_neg_correct.
330 Qed.
331
332 Local Obligation Tactic := idtac.
333 Program Definition ARexp_bounded_uc (z : Z) := unary_complete_uc
334 QPrelengthSpace (cast AQ Q_as_MetricSpace) (λ x, AQexp (('z) ⊓ x)) (exp_bound_uc z) _.
335 Next Obligation.
336 intros.
337 change ('AQexp ((' z) ⊓ x) = exp_bound_uc z (' x)).
338 rewrite AQexp_correct, aq_preserves_min, AQtoQ_ZtoAQ.
339 reflexivity.
340 Qed.
341
342 Definition ARexp_bounded (z : Z) := Cbind AQPrelengthSpace (ARexp_bounded_uc z).
343
344 Lemma ARtoCR_preserves_exp_bounded z x : 'ARexp_bounded z x = exp_bounded z ('x).
345 Proof. apply (preserves_unary_complete_fun QPrelengthSpace _ (λ x, AQexp (('z) ⊓ x))). Qed.
346
347 Definition ARexp (x : AR) : AR
348 := ARexp_bounded (Qceiling ('approximate x (Qpos2QposInf (1#1)) + (1#1))) x.
349
350 Lemma ARtoCR_preserves_exp x : 'ARexp x = exp ('x).
351 Proof. unfold ARexp. apply ARtoCR_preserves_exp_bounded. Qed.
352 End ARexp.