Debian Codegraph @

reals/faster/ARsin.v

raw
1 From Coq Require Import ZArith Qround Qpower.
2 Require Import MathClasses.interfaces.abstract_algebra
3 MathClasses.theory.nat_pow
4 MathClasses.theory.int_pow
5 CoRN.algebra.RSetoid
6 CoRN.metric2.Metric
7 CoRN.metric2.MetricMorphisms
8 CoRN.metric2.UniformContinuity
9 CoRN.model.totalorder.QMinMax
10 CoRN.util.Qdlog
11 CoRN.stdlib_omissions.Q
12 CoRN.reals.fast.CRsin
13 CoRN.reals.fast.CRstreams
14 CoRN.reals.fast.CRAlternatingSum
15 CoRN.reals.fast.Compress
16 CoRN.reals.faster.ARAlternatingSum.
17 Require Export
18 CoRN.reals.faster.ARArith.
19
20 Local Open Scope mc_scope.
21
22 Section ARsin.
23 Context `{AppRationals AQ}.
24
25 Lemma AQmult_lt_0_compat : forall a b : AQ, 0 < a -> 0 < b -> 0 < a*b.
26 Proof.
27 intros.
28 apply (strictly_order_reflecting (cast AQ Q)).
29 pose proof (rings.preserves_0 (f:=cast AQ Q)).
30 rewrite H7.
31 rewrite rings.preserves_mult.
32 rewrite <- (Qmult_0_l ('b)).
33 apply Qmult_lt_compat_r.
34 rewrite <- H7.
35 apply (strictly_order_preserving (cast AQ Q)), H6.
36 rewrite <- H7.
37 apply (strictly_order_preserving (cast AQ Q)), H5.
38 Qed.
39
40 Lemma ZtoQ : forall n:positive, AQtoQ (ZtoAQ (Zpos n)) == (Zpos n#1).
41 Proof.
42 induction n.
43 - change (Z.pos n~1) with (1+2*Z.pos n)%Z.
44 pose proof (rings.preserves_plus (f:=cast Z AQ) 1 (2*Z.pos n)).
45 rewrite H5. clear H5.
46 rewrite rings.preserves_plus, rings.preserves_1.
47 rewrite rings.preserves_1.
48 pose proof (rings.preserves_mult (f:=cast Z AQ) 2 (Z.pos n)).
49 rewrite H5. clear H5.
50 rewrite rings.preserves_mult, IHn.
51 rewrite rings.preserves_2, rings.preserves_2.
52 unfold Qeq; simpl. rewrite Pos.mul_1_r. reflexivity.
53 - change (Z.pos n~0) with (2*Z.pos n)%Z.
54 pose proof (rings.preserves_mult (f:=cast Z AQ) 2 (Z.pos n)).
55 rewrite H5.
56 rewrite rings.preserves_mult, IHn.
57 rewrite rings.preserves_2.
58 pose proof (rings.preserves_2 (f:=cast AQ Q)).
59 rewrite H6. reflexivity.
60 - pose proof (rings.preserves_1 (f:=cast Z AQ)).
61 rewrite H5. rewrite rings.preserves_1. reflexivity.
62 Qed.
63
64 Local Open Scope uc_scope.
65
66
67 Section sin_small.
68 (* First define (sin a) as a decreasing alternating series on the segment [-1,1].
69 a = num/den and -1 <= a <= 1. *)
70
71 Context {num den : AQ} (Pnd : -den ≤ num ≤ den) (dpos : 0 < den).
72
73 (*
74 Split the stream
75 (-1)^i a^(2i+1) / (2i+1)!
76 up into the streams
77 (-1)^i a^(2i+1) and (2i+1)!
78 because we do not have exact division
79 *)
80 Definition ARsinStream (px : positive*(AQ*AQ)) : AQ*AQ
81 := (- fst (snd px) * num * num,
82 snd (snd px) * den * den * ZtoAQ (Zpos (fst px)~0) * ZtoAQ (Zpos (fst px)~1)).
83
84 Lemma sinStream_pos : ∀ x : positive * (AQ * AQ),
85 0 < snd (snd x) → 0 < snd (ARsinStream x).
86 Proof.
87 assert (0 = ZtoAQ 0) as zero_int.
88 { destruct H4. destruct aq_ints_mor, semiringmor_plus_mor.
89 rewrite preserves_mon_unit. reflexivity. }
90 intros. destruct x; simpl.
91 simpl in H5.
92 apply AQmult_lt_0_compat.
93 apply AQmult_lt_0_compat.
94 apply AQmult_lt_0_compat.
95 apply AQmult_lt_0_compat.
96 exact H5. exact dpos. exact dpos.
97 rewrite zero_int.
98 apply (strictly_order_preserving (cast Z AQ)).
99 reflexivity.
100 rewrite zero_int.
101 apply (strictly_order_preserving (cast Z AQ)).
102 reflexivity.
103 Qed.
104
105 Lemma sinStream_correct : ∀ p : positive,
106 Str_pth _ (sinStream (AQtoQ num / AQtoQ den))
107 p (1%positive, AQtoQ num / AQtoQ den)
108 == let (_, r) := iterate _ (fS ARsinStream) p (1%positive, (num, den)) in
109 AQtoQ (fst r) / AQtoQ (snd r).
110 Proof.
111 assert (forall n:Z, AQtoQ (ZtoAQ n) == (n#1)).
112 { intro n. destruct n as [|n|n].
113 pose proof (rings.preserves_0 (f:=cast Z AQ)). rewrite H5. clear H5.
114 rewrite rings.preserves_0. reflexivity.
115 apply ZtoQ. change (Z.neg n) with (-Z.pos n)%Z.
116 pose proof (rings.preserves_negate (f:=cast Z AQ)).
117 rewrite H5. clear H5. rewrite rings.preserves_negate.
118 rewrite ZtoQ. reflexivity. }
119 apply Pos.peano_ind.
120 - unfold Str_pth. simpl.
121 do 6 rewrite rings.preserves_mult.
122 rewrite rings.preserves_negate.
123 rewrite H5, H5.
124 unfold dec_recip, stdlib_rationals.Q_recip.
125 unfold mult, stdlib_rationals.Q_mult.
126 unfold negate, stdlib_rationals.Q_opp.
127 field. intro abs.
128 apply (strictly_order_preserving (cast AQ Q)) in dpos.
129 rewrite rings.preserves_0, abs in dpos.
130 exact (Qlt_irrefl 0 dpos).
131 - intros p IHp. unfold Str_pth. unfold Str_pth in IHp.
132 rewrite iterate_succ, iterate_succ.
133 pose proof (sinStream_fst (AQtoQ num / AQtoQ den) p) as H7.
134 unfold dec_recip, stdlib_rationals.Q_recip.
135 unfold dec_recip, stdlib_rationals.Q_recip in IHp.
136 unfold mult, stdlib_rationals.Q_mult.
137 unfold mult, stdlib_rationals.Q_mult in IHp.
138 unfold Qdiv in H7. unfold Qdiv.
139 unfold Qdiv in IHp.
140 unfold Q_as_MetricSpace, msp_car.
141 unfold Q_as_MetricSpace, msp_car in IHp.
142 destruct (iterate _ (sinStream (AQtoQ num * / AQtoQ den)%Q) p
143 (1%positive, (AQtoQ num * / AQtoQ den)%Q)).
144 simpl in H7. simpl in IHp. subst p0.
145 unfold sinStream, snd, fst. rewrite IHp. clear IHp.
146 pose proof (fS_fst ARsinStream p (num, den)).
147 destruct (iterate _ (fS ARsinStream) p (1%positive, (num, den))) as [p0 p1].
148 simpl in H6. simpl. subst p0.
149 do 6 rewrite rings.preserves_mult.
150 rewrite rings.preserves_negate.
151 unfold mult, stdlib_rationals.Q_mult.
152 unfold negate, stdlib_rationals.Q_opp.
153 rewrite ZtoQ, ZtoQ.
154 rewrite <- (Qmult_assoc (AQtoQ (snd p1) * AQtoQ den * AQtoQ den)).
155 rewrite Qinv_mult_distr.
156 setoid_replace (/ ((Z.pos (Pos.succ p)~0 # 1) * (Z.pos (Pos.succ p)~1 # 1)))
157 with (1 # (Pos.succ p * (Pos.succ p)~1)~0) by reflexivity.
158 do 2 rewrite Qinv_mult_distr. ring.
159 Qed.
160
161 Lemma AQsin_small_Qprf : -1 ≤ AQtoQ num / AQtoQ den ≤ 1.
162 Proof.
163 split.
164 - apply Qle_shift_div_l.
165 pose proof (rings.preserves_0 (f:=cast AQ Q)).
166 rewrite <- H5.
167 apply (strictly_order_preserving (cast AQ Q)), dpos.
168 setoid_replace (-1 * AQtoQ den) with (-AQtoQ den) by reflexivity.
169 rewrite <- rings.preserves_negate.
170 apply (order_preserving (cast AQ Q)), Pnd.
171 - apply Qle_shift_div_r.
172 pose proof (rings.preserves_0 (f:=cast AQ Q)).
173 rewrite <- H5.
174 apply (strictly_order_preserving (cast AQ Q)), dpos.
175 rewrite Qmult_1_l.
176 apply (order_preserving (cast AQ Q)), Pnd.
177 Qed.
178
179 Definition AQsin_small : msp_car AR
180 := CRtoAR (inject_Q_CR (AQtoQ num / AQtoQ den))
181 + AltSeries ARsinStream sinStream_pos
182 positive (CRsin.sinStream (AQtoQ num / AQtoQ den))
183 (num,den) (xH,AQtoQ num / AQtoQ den) sinStream_correct _
184 (sinStream_alt AQsin_small_Qprf)
185 dpos (sinStream_zl AQsin_small_Qprf).
186
187 Lemma AQsin_small_correct : 'AQsin_small = rational_sin (AQtoQ num / AQtoQ den).
188 Proof.
189 rewrite rational_sin_correct,
190 <- (rational_sin_small_correct AQsin_small_Qprf).
191 unfold AQsin_small, rational_sin_small.
192 rewrite ARtoCR_preserves_plus.
193 apply ucFun2_wd.
194 pose proof CRAR_id. unfold cast in H5.
195 unfold cast. rewrite H5.
196 reflexivity.
197 apply AltSeries_correct.
198 Qed.
199
200 End sin_small.
201
202 Lemma AQsin_small_pos_wd :
203 forall (n1 n2 d1 d2 : AQ) (p1 : -d1 ≤ n1 ≤ d1) (p2 : -d2 ≤ n2 ≤ d2)
204 (d1pos : 0 < d1) (d2pos : 0 < d2),
205 n1 = n2
206 -> d1 = d2
207 -> AQsin_small p1 d1pos = AQsin_small p2 d2pos.
208 Proof.
209 assert (forall x y, ARtoCR x = ARtoCR y -> x = y) as H5.
210 { intros x y H5. exact H5. }
211 intros. apply H5.
212 rewrite (AQsin_small_correct p1 d1pos).
213 rewrite (AQsin_small_correct p2 d2pos).
214 rewrite H6, H7. reflexivity.
215 Qed.
216
217 (** Sine's range can then be extended to [[0,3^n]] by [n] applications
218 of the identity [sin(x) = 3*sin(x/3) - 4*(sin(x/3))^3]. *)
219 Definition AQsin_poly_fun (x : AQ) : AQ := x * (3 - 4 * x ^ (2%mc:N)).
220
221 Lemma AQsin_poly_fun_correct (q : AQ) :
222 'AQsin_poly_fun q = sin_poly_fun ('q).
223 Proof.
224 unfold AQsin_poly_fun, sin_poly_fun.
225 rewrite nat_pow_2.
226 rewrite rings.preserves_mult, rings.preserves_minus, ?rings.preserves_mult.
227 rewrite rings.preserves_3, rings.preserves_4.
228 now rewrite <-(associativity _ ('q) ('q : Q)).
229 Qed.
230
231 (* AQsin_poly_fun is not uniformly continuous because of x^3, but it will
232 only be applied to sine values in [-1,1], a range on which it is
233 uniformly continuous. *)
234 Lemma AQsin_poly_fun_bound_correct
235 : forall q : AQ, msp_eq (' AQsin_poly_fun (ucFun (AQboundAbs_uc 1) q))
236 (sin_poly_fun (Qmax (- (1)) (Qmin 1 (' q)))).
237 Proof.
238 intro q. apply Qball_0.
239 rewrite AQsin_poly_fun_correct.
240 f_equiv.
241 unfold AQboundAbs_uc. simpl.
242 change ('1) with (1:AQ).
243 rewrite ?aq_preserves_max, ?aq_preserves_min.
244 now rewrite ?rings.preserves_negate, ?rings.preserves_1.
245 Qed.
246
247 Definition AQsin_poly_uc : msp_car (AQ_as_MetricSpace --> AQ_as_MetricSpace)
248 := unary_uc (cast AQ (msp_car Q_as_MetricSpace))
249 (λ q : AQ, AQsin_poly_fun (ucFun (AQboundAbs_uc 1) q))
250 sin_poly_uc AQsin_poly_fun_bound_correct.
251
252 Definition ARsin_poly : msp_car (AR --> AR)
253 := uc_compose ARcompress (Cmap AQPrelengthSpace AQsin_poly_uc).
254
255 Lemma ARtoCR_preserves_sin_poly (x : msp_car AR)
256 : 'ucFun ARsin_poly x = ucFun sin_poly ('x).
257 Proof.
258 change ('ucFun ARcompress (ucFun (Cmap AQPrelengthSpace AQsin_poly_uc) x)
259 = ucFun compress (ucFun (Cmap QPrelengthSpace sin_poly_uc) ('x))).
260 rewrite ARcompress_correct, compress_correct.
261 now apply preserves_unary_fun.
262 Qed.
263
264 (* When x = sin y, this function computes sin (y*3^n). *)
265 Fixpoint ARsin_poly_iter (n : nat) (x : msp_car AR) : msp_car AR :=
266 match n with
267 | O => x
268 | S n' => ucFun ARsin_poly (ARsin_poly_iter n' x)
269 end.
270
271 Definition AQsin_bounded {n : nat} {num den : AQ}
272 (Pnd : - (den * 3^n) ≤ num ≤ den * 3^n)
273 (dpos : 0 < den * 3^n) : msp_car AR
274 := ARsin_poly_iter n (AQsin_small Pnd dpos).
275
276 Lemma ARsin_poly_iter_wd : forall n x y,
277 x = y -> ARsin_poly_iter n x = ARsin_poly_iter n y.
278 Proof.
279 induction n.
280 - intros. exact H5.
281 - intros.
282 change (ucFun ARsin_poly (ARsin_poly_iter n x)
283 = ucFun ARsin_poly (ARsin_poly_iter n y)).
284 rewrite (IHn x y H5).
285 reflexivity.
286 Qed.
287
288 Lemma AQsin_bounded_correct {n : nat} {num den : AQ}
289 (Pnd : -(den * 3^n) ≤ num ≤ den * 3^n) (dpos : 0 < den * 3^n) :
290 'AQsin_bounded Pnd dpos = rational_sin ('num / 'den).
291 Proof.
292 revert num den dpos Pnd.
293 induction n; intros.
294 - unfold AQsin_bounded. simpl.
295 rewrite AQsin_small_correct.
296 change (3^0%nat) with 1.
297 rewrite rings.mult_1_r. reflexivity.
298 - unfold AQsin_bounded.
299 change (' ucFun ARsin_poly (ARsin_poly_iter n (AQsin_small Pnd dpos))
300 = rational_sin (' num / ' den)).
301 rewrite ARtoCR_preserves_sin_poly.
302 unfold AQsin_bounded in IHn.
303 assert (le (-(den * 3 * 3 ^ n)) num /\ num ≤ den * 3 * 3 ^ n) as H5.
304 { rewrite <- (associativity den 3). exact Pnd. }
305 assert (0 < den * 3 * 3 ^ n) as H6.
306 { rewrite <- (associativity den 3). exact dpos. }
307 setoid_replace (ARsin_poly_iter n (AQsin_small Pnd dpos))
308 with (ARsin_poly_iter n (AQsin_small H5 H6)).
309 rewrite IHn.
310 change (Qdiv ('num) ('(den * 3))) with (('num : Q) / '(den * 3)).
311 rewrite rings.preserves_mult, rings.preserves_3.
312 rewrite dec_fields.dec_recip_distr, associativity.
313 apply rational_sin_poly.
314 apply ARsin_poly_iter_wd.
315 apply AQsin_small_pos_wd. reflexivity.
316 rewrite <- (associativity den 3). reflexivity.
317 Qed.
318
319 Definition AQsin_bound (a : AQ) : nat := CRsin.sin_bound ('a).
320
321 Lemma AQsin_bound_correct : forall (a:AQ),
322 -(1 * 3 ^ AQsin_bound a) ≤ a ≤ 1 * 3 ^ AQsin_bound a.
323 Proof.
324 intro a. unfold AQsin_bound.
325 pose proof (CRsin.sin_bound_correct ('a)).
326 split; apply (order_reflecting (cast AQ Q)).
327 - rewrite rings.preserves_negate.
328 destruct H4, aq_ring, ring_monoid.
329 destruct commonoid_mon. rewrite monoid_left_id.
330 rewrite preserves_nat_pow.
331 rewrite rings.preserves_3.
332 rewrite <-(int_pow_nat_pow (f:=cast nat Z)).
333 rewrite <- (Zpower_Qpower 3).
334 apply H5. apply (Nat2Z.inj_le 0), Nat.le_0_l.
335 - destruct H4, aq_ring, ring_monoid.
336 destruct commonoid_mon. rewrite monoid_left_id.
337 rewrite preserves_nat_pow.
338 rewrite rings.preserves_3.
339 rewrite <-(int_pow_nat_pow (f:=cast nat Z)).
340 rewrite <- (Zpower_Qpower 3).
341 apply H5. apply (Nat2Z.inj_le 0), Nat.le_0_l.
342 Qed.
343
344 Lemma AQsin_bound_pos : forall a, 0 < 1 * 3 ^ AQsin_bound a.
345 Proof.
346 intro a.
347 destruct H4, aq_ring, ring_monoid.
348 destruct commonoid_mon. rewrite monoid_left_id.
349 apply (strictly_order_reflecting (cast AQ Q)).
350 rewrite preserves_nat_pow.
351 rewrite rings.preserves_3.
352 rewrite <- (int_pow_nat_pow (f:=cast nat Z)).
353 rewrite rings.preserves_0.
354 apply (Qpower_0_lt 3 (Z.of_nat (AQsin_bound a))).
355 reflexivity.
356 Qed.
357
358 Definition AQsin (a:AQ) : msp_car AR
359 := AQsin_bounded (AQsin_bound_correct a) (AQsin_bound_pos a).
360
361 Lemma AQsin_correct : forall a, 'AQsin a = rational_sin ('a).
362 Proof.
363 intro a.
364 mc_setoid_replace ('a : Q) with (('a / '1)%mc : Q).
365 now apply AQsin_bounded_correct.
366 rewrite rings.preserves_1, dec_fields.dec_recip_1.
367 rewrite Qmult_1_r. reflexivity.
368 Qed.
369
370 Lemma AQsin_prf {a : AQ} (pA : ¬0 ≤ a) : 0 ≤ -a.
371 Proof. apply rings.flip_nonpos_negate. now apply orders.le_flip. Qed.
372
373 Definition ARsin_uc : msp_car (AQ_as_MetricSpace --> AR)
374 := unary_complete_uc
375 QPrelengthSpace (cast AQ (msp_car Q_as_MetricSpace)) AQsin sin_uc AQsin_correct.
376
377 Definition ARsin : msp_car (AR --> AR)
378 := Cbind AQPrelengthSpace ARsin_uc.
379
380 Lemma ARtoCR_preserves_sin x : ' ucFun ARsin x = ucFun sin_slow ('x).
381 Proof. apply preserves_unary_complete_fun. Qed.
382
383 End ARsin.