Debian Codegraph @

reals/fast/CRsin.v

raw
1 (*
2 Copyright © 2006 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.model.totalorder.QMinMax.
26 Require Import CoRN.reals.fast.CRAlternatingSum.
27 Require Import CoRN.reals.fast.CRAlternatingSum_alg.
28 Require Import CoRN.reals.fast.CRstreams.
29 Require Import CoRN.reals.fast.CRexp.
30 Require Import CoRN.reals.fast.CRpi.
31 Require Export CoRN.reals.fast.CRArith.
32 Require Import CoRN.reals.fast.CRIR.
33 From Coq Require Import Qpower Qabs.
34 Require Import CoRN.model.ordfields.Qordfield.
35 From Coq Require Import Qround.
36 Require Import CoRN.transc.Pi.
37 Require Import CoRN.reals.fast.ModulusDerivative.
38 Require Import CoRN.reals.fast.ContinuousCorrect.
39 Require Import CoRN.model.metric2.Qmetric.
40 Require Import CoRN.transc.PowerSeries.
41 Require Import CoRN.transc.SinCos.
42 Require Import CoRN.reals.fast.Compress.
43 Require Import CoRN.reals.fast.PowerBound.
44 Require Import CoRN.tactics.CornTac.
45 Require Import MathClasses.interfaces.abstract_algebra.
46 Require Import CoRN.util.Qdlog.
47 From Coq Require Import Lia.
48
49 (* Backwards compatibility for Hint Rewrite locality attributes *)
50 Set Warnings "-unsupported-attributes".
51
52 Set Implicit Arguments.
53
54 Local Open Scope Q_scope.
55 Local Open Scope uc_scope.
56
57 Opaque inj_Q CR Qmin Qmax.
58
59 Lemma Qmult_pos_neg : forall (a b : Q),
60 0 <= a -> b <= 0 -> a*b <= 0.
61 Proof.
62 intros. rewrite Qmult_comm.
63 rewrite <- (Qmult_0_l a).
64 apply Qmult_le_compat_r; assumption.
65 Qed.
66
67 Lemma Qmult_opp_1 : forall q : Q,
68 eq (-q) (-1 * q).
69 Proof.
70 reflexivity.
71 Qed.
72
73 Lemma fact_inc : forall n:nat, (fact n <= fact (S n))%nat.
74 Proof.
75 intro n.
76 rewrite <- (Nat.mul_1_l (fact n)).
77 change (fact (S n)) with ((1+n)*fact n)%nat.
78 apply Nat.mul_le_mono_nonneg_r.
79 apply (Nat.le_trans _ 1).
80 auto. exact (lt_O_fact n).
81 apply le_n_S, Nat.le_0_l.
82 Qed.
83
84 Lemma fact_inc_recurse : forall p n:nat, (n <= p)%nat -> (fact n <= fact p)%nat.
85 Proof.
86 induction p.
87 - intros. inversion H. apply Nat.le_refl.
88 - intros. apply Nat.le_succ_r in H. destruct H.
89 apply (Nat.le_trans (fact n) (fact p)).
90 apply IHp, H. apply fact_inc.
91 subst n. apply Nat.le_refl.
92 Qed.
93
94 (**
95 ** Sine
96 Sine is defined in terms of its alternating Taylor's series.
97 *)
98 Section SinSeries.
99 Variable a:Q.
100
101 (* (1,a) -> (3, -a^3/3!) -> ... *)
102 Definition sinStream (px : positive*Q) : positive*Q
103 := let d := Pos.succ (fst px) in
104 (Pos.add 2 (fst px), - snd px * a * a * (1#(d*Pos.succ d))).
105
106 Lemma sinStream_fst : forall p,
107 fst (iterate _ sinStream p (1%positive, a)) ≡ Pos.succ (2*p).
108 Proof.
109 apply Pos.peano_ind.
110 - reflexivity.
111 - intros p H. rewrite iterate_succ.
112 destruct (iterate (positive and Q) sinStream p (1%positive, a)).
113 simpl in H. subst p0.
114 transitivity (Pos.add 2 (p~1)). reflexivity.
115 clear q a. rewrite Pos.mul_succ_r.
116 rewrite <- Pos.add_1_l, (Pos.add_comm 1).
117 rewrite <- Pos.add_assoc. apply f_equal. reflexivity.
118 Qed.
119
120 (* The closed formula for the sine stream. *)
121 Lemma Str_pth_sinStream : forall (p:positive),
122 Str_pth _ sinStream p (xH,a)
123 == (1#Pos.of_nat (fact (1+2*Pos.to_nat p))) * ((-1)^p*a^(1+2*p))%Q.
124 Proof.
125 apply Pos.peano_ind.
126 - unfold sinStream, Str_pth; simpl.
127 rewrite Qmult_comm. apply Qmult_comp. reflexivity.
128 rewrite Qmult_assoc, Qmult_assoc.
129 reflexivity.
130 - intros p pInd. unfold Str_pth.
131 rewrite iterate_succ. unfold Str_pth in pInd.
132 pose proof (sinStream_fst p) as H0.
133 destruct (iterate (positive and Q) sinStream p (1%positive, a)) as [p0 q].
134 simpl in H0. subst p0. unfold snd in pInd.
135 unfold sinStream, snd, fst.
136 rewrite pInd. clear pInd q.
137 (* Get rid of (-1)^p *)
138 rewrite <- (Qmult_comm ((-1) ^ Pos.succ p * a ^ (1 + 2 * Pos.succ p))).
139 rewrite <- (Pos.add_1_l p).
140 rewrite Pos2Z.inj_add, (Qpower_plus (-1)%Q).
141 simpl ((-1)^1).
142 rewrite Qmult_opp_1.
143 do 5 rewrite <- (Qmult_assoc (-1)).
144 apply (Qmult_comp (-1)). reflexivity.
145 rewrite (Qmult_comm (1 # Pos.of_nat (fact (1 + 2 * Pos.to_nat p)))).
146 do 5 rewrite <- (Qmult_assoc ((-1)^p)).
147 apply Qmult_comp. reflexivity.
148 (* Get rid of a *)
149 setoid_replace (a ^ (1 + 2 * (1 + p))) with (a ^ (1 + 2 * p) * (a * a)).
150 do 4 rewrite <- (Qmult_assoc (a ^ (1 + 2 * p))).
151 apply Qmult_comp. reflexivity.
152 rewrite <- (Qmult_assoc _ a a).
153 rewrite (Qmult_comm (1 # Pos.of_nat (fact (1 + 2 * Pos.to_nat p)))).
154 rewrite <- (Qmult_assoc (a*a)).
155 apply Qmult_comp. reflexivity.
156 (* Get rid of fact *)
157 unfold Qeq, Qmult, Qnum, Qden.
158 rewrite Z.mul_1_l, Z.mul_1_l.
159 rewrite <- (Pos2Nat.id (Pos.succ p~1 * Pos.succ (Pos.succ p~1))).
160 rewrite <- Nat2Pos.inj_mul.
161 2: apply fact_neq_0.
162 replace (fact (1 + 2 * Pos.to_nat (1 + p)))%nat
163 with (fact (1 + 2 * Pos.to_nat p) *
164 Pos.to_nat (Pos.succ p~1 * Pos.succ (Pos.succ p~1)))%nat.
165 reflexivity.
166 rewrite Nat.mul_comm.
167 replace (1 + 2 * Pos.to_nat (1 + p))%nat with (3 + 2 * Pos.to_nat p)%nat.
168 change (fact (3 + 2 * Pos.to_nat p))%nat
169 with ((3 + 2 * Pos.to_nat p)
170 * ((2 + 2 * Pos.to_nat p) * fact (1 + 2 * Pos.to_nat p)))%nat.
171 replace (Pos.to_nat (Pos.succ p~1 * Pos.succ (Pos.succ p~1)))%nat
172 with ((3 + 2 * Pos.to_nat p) * ((2 + 2 * Pos.to_nat p)))%nat.
173 rewrite Nat.mul_assoc.
174 reflexivity.
175 (* Finish equalities *)
176 rewrite Pos2Nat.inj_mul.
177 rewrite Nat.mul_comm. apply f_equal2.
178 rewrite Pos2Nat.inj_succ.
179 apply (f_equal S).
180 rewrite Pos2Nat.inj_xI. reflexivity.
181 rewrite Pos2Nat.inj_succ. apply (f_equal S).
182 rewrite Pos2Nat.inj_succ. apply (f_equal S).
183 rewrite Pos2Nat.inj_xI. reflexivity.
184 rewrite Pos2Nat.inj_add. simpl.
185 rewrite Nat.add_0_r, Nat.add_succ_r. reflexivity.
186 intro abs.
187 pose proof (Pos2Nat.is_pos (Pos.succ p~1 * Pos.succ (Pos.succ p~1))).
188 rewrite abs in H. inversion H.
189 rewrite <- (Qpower_plus_positive a 1 1).
190 rewrite <- (Qpower_plus_positive a (1+2*p)).
191 apply Qpower_positive_comp. reflexivity.
192 rewrite <- Pos.add_assoc.
193 apply f_equal. rewrite (Pos.add_comm 1 p).
194 reflexivity.
195 intro abs. discriminate.
196 Qed.
197
198 (** Sine is first defined on [[-1,1]] by an alternating series. *)
199 Lemma sinStream_alt : -1 <= a <= 1 -> Str_alt_decr _ sinStream (1%positive,a).
200 Proof.
201 intro Ha. split.
202 - (* Replace a by Qabs a *)
203 rewrite Str_pth_sinStream, Str_pth_sinStream.
204 rewrite Qabs_Qmult, Qabs_Qmult, Qabs_Qmult, Qabs_Qmult.
205 rewrite Qabs_Qpower, Qabs_Qpower.
206 change (Qabs (-1)) with 1.
207 rewrite Qpower_1, Qpower_1, Qmult_1_l, Qmult_1_l.
208 rewrite (Qabs_Qpower a (1+2*Pos.succ p)), (Qabs_Qpower a (1+2*p)).
209 (* Finish inequality *)
210 setoid_replace (Qabs a ^ (1 + 2 * Pos.succ p)%positive)
211 with (Qabs a * Qabs a * Qabs a ^ (1 + 2 * p)%positive).
212 rewrite Qmult_assoc.
213 apply Qmult_le_compat_r.
214 2: rewrite <- Qabs_Qpower; apply Qabs_nonneg.
215 + rewrite Qmult_comm.
216 apply (Qabs_Qle_condition a 1) in Ha.
217 apply (Qle_trans _ (1* (1 # Pos.of_nat (fact (1 + 2 * Pos.to_nat (Pos.succ p)))))).
218 apply Qmult_le_compat_r. 2: discriminate.
219 apply (Qle_trans _ (1*Qabs a)).
220 apply Qmult_le_compat_r. exact Ha.
221 apply Qabs_nonneg. rewrite Qmult_1_l. exact Ha.
222 rewrite Qmult_1_l. unfold Qabs, Z.abs.
223 unfold Qle, Qnum, Qden.
224 rewrite Z.mul_1_l, Z.mul_1_l.
225 apply Pos2Nat.inj_le.
226 rewrite Nat2Pos.id, Nat2Pos.id.
227 2: apply fact_neq_0. 2: apply fact_neq_0.
228 replace (1 + 2 * Pos.to_nat (Pos.succ p))%nat
229 with (2 + (1 + 2 * Pos.to_nat p))%nat
230 by (rewrite Pos2Nat.inj_succ; ring).
231 apply (Nat.le_trans _ _ _ (fact_inc _)).
232 apply fact_inc.
233 + replace (1 + 2 * Pos.succ p)%positive with (2 + (1 + 2 * p))%positive.
234 generalize (1 + 2 * p)%positive. clear p. intro p.
235 unfold Qpower.
236 rewrite Qpower_plus_positive. reflexivity.
237 rewrite Pos.add_comm, <- Pos.add_assoc. apply f_equal.
238 rewrite <- Pos.add_1_l.
239 rewrite Pos.mul_add_distr_l, Pos.mul_1_r.
240 apply Pos.add_comm.
241 - rewrite Str_pth_sinStream, Str_pth_sinStream.
242 rewrite Qmult_comm, <- Qmult_assoc. apply Qmult_pos_neg.
243 discriminate. rewrite Qmult_comm, <- Qmult_assoc.
244 apply Qmult_pos_neg. discriminate.
245 rewrite <- Pos.add_1_l.
246 change ((-1) ^ (1 + p)%positive) with (Qpower_positive (-1) (1 + p)).
247 rewrite Qpower_plus_positive. simpl (Qpower_positive (-1) 1).
248 rewrite <- Qmult_assoc, <- Qmult_assoc.
249 apply (Qopp_le_compat 0).
250 rewrite (Qmult_comm (a ^ (1 + 2 * (1 + p)%positive))).
251 rewrite Qmult_assoc, Qmult_assoc.
252 rewrite <- Qmult_assoc.
253 apply Qmult_le_0_compat.
254 simpl.
255 destruct (Qpower_positive (-1) p), Qnum; discriminate.
256 setoid_replace (a ^ (1 + 2 * (1 + p))) with (a ^ (1 + 2 * p) * (a * a)).
257 rewrite Qmult_assoc.
258 apply Qmult_le_0_compat.
259 destruct (a ^ (1 + 2 * p)), Qnum; discriminate.
260 destruct a, Qnum; discriminate.
261 change (a*a) with (Qpower_positive a 2).
262 rewrite <- (Qpower_plus_positive a (1+2*p)).
263 change (a ^ (1 + 2 * (1 + p))) with (Qpower_positive a (1 + 2 * (1 + p))).
264 replace (1 + 2 * (1 + p))%positive with (1 + 2 * p + 2)%positive.
265 reflexivity.
266 rewrite <- Pos.add_assoc. apply f_equal.
267 rewrite Pos.mul_add_distr_l, Pos.mul_1_r.
268 apply Pos.add_comm.
269 Qed.
270
271 Lemma sinStream_zl
272 : -1 <= a <= 1
273 -> Limit_zero _ sinStream (xH,a)
274 (fun e:Qpos => Pos.succ (Z.to_pos (Z.log2_up (Qceiling (/ (proj1_sig e)))))).
275 Proof.
276 intro Ha.
277 intros [e epos]. rewrite Str_pth_sinStream, Qabs_Qmult, Qabs_Qmult.
278 rewrite Qabs_Qpower. change (Qabs (-1)) with 1.
279 rewrite Qpower_1, Qmult_1_l.
280 rewrite Qmult_comm.
281 apply (Qle_trans
282 _ (1 * Qabs (1 # Pos.of_nat (fact (1+2*(Pos.to_nat (Pos.succ (Z.to_pos (Z.log2_up (Qceiling (/ e))))))))))).
283 apply Qmult_le_compat_r. 2: apply Qabs_nonneg.
284 - rewrite (Qabs_Qpower
285 a (1 + 2 * Pos.succ (Z.to_pos (Z.log2_up (Qceiling (/ ` (e ↾ epos))))))).
286 apply Qpower_le_1. split.
287 apply Qabs_nonneg.
288 apply Qabs_Qle_condition, Ha.
289 - clear Ha a.
290 rewrite Qmult_1_l. unfold Qabs, Z.abs, proj1_sig.
291 rewrite <- (Qinv_involutive e) at 2.
292 assert (0 < /e) as H.
293 { apply Qinv_lt_0_compat, epos. }
294 apply (@Qinv_le_compat
295 (/e) ((Pos.of_nat (fact (1+2*(Pos.to_nat (Pos.succ (Z.to_pos (Z.log2_up (Qceiling (/ e))))))))) # 1)).
296 exact H.
297 apply (Qle_trans _ _ _ (Qceiling_fact_le H)).
298 generalize (Pos.succ (Z.to_pos (Z.log2_up (Qceiling (/ e))))).
299 clear H epos e. intro p.
300 unfold Qle, Qnum, Qden.
301 rewrite Z.mul_1_r, Z.mul_1_r.
302 apply Pos2Nat.inj_le.
303 rewrite Nat2Pos.id, Nat2Pos.id.
304 2: apply fact_neq_0. 2: apply fact_neq_0.
305 apply fact_inc_recurse.
306 apply (Nat.le_trans (Pos.to_nat p) (1 + Pos.to_nat p)).
307 apply le_S, Nat.le_refl.
308 apply le_n_S.
309 rewrite <- (Nat.mul_1_l (Pos.to_nat p)) at 1.
310 apply Nat.mul_le_mono_nonneg_r.
311 apply Nat.le_0_l. apply le_S, Nat.le_refl.
312 Qed.
313
314 End SinSeries.
315
316 Definition rational_sin_small (a:Q) (p: -1 <= a <= 1) : CR :=
317 (inject_Q_CR a + AltSeries _ (sinStream a) (xH,a) _
318 (sinStream_alt p) (sinStream_zl p))%CR.
319
320 Lemma rational_sin_small_correct : forall (a:Q) (Ha : -1 <= a <= 1),
321 (@rational_sin_small a Ha == IRasCR (Sin (inj_Q IR a)))%CR.
322 Proof.
323 intros a Ha.
324 unfold rational_sin_small.
325 simpl.
326 generalize (fun_series_conv_imp_conv (inj_Q IR a) (inj_Q IR a)
327 (leEq_reflexive IR (inj_Q IR a)) sin_ps
328 (sin_conv (inj_Q IR a) (inj_Q IR a) (leEq_reflexive IR (inj_Q IR a))
329 (compact_single_iprop realline (inj_Q IR a) I)) (inj_Q IR a)
330 (compact_single_prop (inj_Q IR a))
331 (fun_series_inc_IR realline sin_ps sin_conv (inj_Q IR a) I)).
332 intros H.
333 (* Replace AltSeries by IRasCR (series_sum ...) *)
334 rewrite <- (IR_inj_Q_as_CR a).
335 rewrite
336 (AltSeries_correct
337 _ _ _ _ (sinStream_alt Ha) (sinStream_zl Ha)
338 _ (AltSeries_convergent_0 _ _ _ _ (inj_Q IR a)
339 (sinStream_alt Ha) (sinStream_zl Ha))).
340 apply IRasCR_wd.
341 - (* Prove the 2 series are equal in IR.
342 We need to sum twice as many terms in sin_seq, to get rid of
343 the zeros at even indexes. *)
344 unfold series_sum.
345 apply Lim_seq_eq_Lim_subseq with (fun n => 2*n)%nat.
346 intros; lia.
347 intros n; exists (S n); lia.
348 (* Prove that the partial sums until n are equal. *)
349 intros n.
350 induction n.
351 apply eq_reflexive.
352 replace (2*(S n))%nat with (S (S (2*n)))%nat by lia.
353 set (n':=(2*n)%nat) in *.
354 simpl in *.
355 rstepr (seq_part_sum (fun n0 : nat =>
356 (sin_seq n0[/]nring (R:=IR) (fact n0)[//]nring_fac_ap_zero IR n0)[*]
357 nexp IR n0 (inj_Q IR a[-][0])) n'[+](
358 (sin_seq n'[/]nring (R:=IR) (fact n')[//]nring_fac_ap_zero IR n')[*]
359 nexp IR n' (inj_Q IR a[-][0])[+] (sin_seq (S n')[/]nring (R:=IR) (fact n' + n' * fact n')[//]
360 nring_fac_ap_zero IR (S n'))[*] (nexp IR n' (inj_Q IR a[-][0])[*](inj_Q IR a[-][0])))).
361 apply bin_op_wd_unfolded.
362 assumption.
363 rewrite <- cm_lft_unit.
364 unfold sin_seq.
365 apply bin_op_wd_unfolded.
366 + destruct (even_or_odd_plus n') as [m [Hm|Hm]]; simpl.
367 rational.
368 elim (Nat.Even_Odd_False n');
369 [ exists n; subst n'; ring |
370 now exists m; rewrite Hm, Nat.add_1_r; simpl; rewrite Nat.add_0_r].
371 + destruct (even_or_odd_plus (S n')) as [m [Hm|Hm]]; simpl.
372 elim (Nat.Even_Odd_False (S n')).
373 rewrite Hm.
374 replace (m + m)%nat with (2*m)%nat by lia; now exists m.
375 subst n'; exists n; ring.
376 inversion Hm.
377 unfold n' in H1.
378 replace m with n by lia.
379 clear Hm H1.
380 (* Unfold sinStream *)
381 transitivity (inj_Q IR ((1#Pos.of_nat (fact (1+2*n))) * ((-1)^n*a^(1+2*n))%Q)).
382 clear IHn H. destruct n. simpl.
383 apply inj_Q_wd. rewrite Qmult_1_l, Qmult_1_l. reflexivity.
384 apply inj_Q_wd. rewrite Str_pth_sinStream.
385 rewrite Nat2Pos.id. 2: discriminate.
386 replace (Z.pos (Pos.of_nat (S n))) with (Z.of_nat (S n)).
387 reflexivity.
388 simpl. destruct n. reflexivity.
389 rewrite <- Pos.succ_of_nat. reflexivity. discriminate.
390 (* Get rid of (-1)^n *)
391 transitivity (inj_Q IR ((-(1))^n) [*] (inj_Q IR (a ^ (1 + 2 * n)) [*] inj_Q IR (1 # Pos.of_nat (fact (1 + 2 * n))))).
392 rewrite <- inj_Q_mult, <- inj_Q_mult.
393 apply inj_Q_wd. rewrite Qmult_comm. rewrite Qmult_assoc. reflexivity.
394 change (inj_Q IR ((- (1)) ^ n) [*] (inj_Q IR (a ^ (1 + 2 * n))
395 [*] inj_Q IR (1 # Pos.of_nat (fact (1 + 2 * n))))
396 [=]
397 (nexp IR n [--][1][/]nring (R:=IR) (fact (S n'))[//]nring_fac_ap_zero IR (S n'))[*]
398 (nexp IR (S n') (inj_Q IR a[-][0]))).
399 rstepr ((nexp IR n [--][1][*](nexp IR (S n') (inj_Q IR a[-][0])[/]nring (R:=IR) (fact (S n'))[//]
400 nring_fac_ap_zero IR (S n')))).
401 apply mult_wd.
402 stepr ((inj_Q IR (-(1)))[^]n).
403 apply inj_Q_power.
404 apply nexp_wd.
405 stepr ([--](inj_Q IR 1)).
406 apply inj_Q_inv.
407 apply un_op_wd_unfolded.
408 rstepr (nring 1:IR).
409 apply (inj_Q_nring IR 1).
410 stepr (inj_Q IR ((1/P_of_succ_nat (pred (fact (1+2*n))))*a^(1+2*n)%nat)).
411 rewrite <- inj_Q_mult.
412 apply inj_Q_wd.
413 rewrite Qmult_comm.
414 apply Qmult_comp.
415 replace (1 + 2 * Z.of_nat n)%Z with (Z.of_nat (1 + 2 * n)).
416 reflexivity. rewrite <- (Nat2Z.inj_mul 2), <- (Nat2Z.inj_add 1).
417 reflexivity. pose proof (fact_neq_0 (1+2*n)).
418 destruct (fact (1+2*n)). exfalso; apply H0; reflexivity.
419 simpl. destruct n0. reflexivity.
420 rewrite <- Pos2SuccNat.id_succ, Nat2Pos.id.
421 reflexivity. discriminate.
422 (* Finish equality *)
423 rstepr ((nring 1[/]nring (R:=IR) (fact (S n'))[//]
424 nring_fac_ap_zero IR (S n'))[*](nexp IR (S n') (inj_Q IR a[-][0]))).
425 change (1+2*n)%nat with (S n').
426 stepr ((inj_Q IR (1 / Zpos (P_of_succ_nat (pred (fact (S n')))))[*](inj_Q IR (a^S n')))).
427 apply inj_Q_mult.
428 apply mult_wd.
429 rewrite <- POS_anti_convert.
430 assert (X:inj_Q IR (inject_Z (Z_of_nat (S (pred (fact (S n'))))))[#][0]).
431 stepr (inj_Q IR [0]).
432 assert (@cs_ap Q_as_CSetoid (inject_Z (Z_of_nat (S (pred (fact (S n')))))) 0).
433 discriminate.
434 destruct (ap_imp_less _ _ _ X).
435 apply less_imp_ap.
436 apply inj_Q_less.
437 assumption.
438 apply Greater_imp_ap.
439 apply inj_Q_less.
440 assumption.
441 apply (inj_Q_nring IR 0).
442 stepr ((inj_Q IR 1)[/](inj_Q IR (inject_Z (Z_of_nat (S (pred (fact (S n')))))))[//]X).
443 apply inj_Q_div.
444 apply div_wd.
445 apply (inj_Q_nring IR 1).
446 stepl (inj_Q IR (nring (fact (S n')))).
447 apply inj_Q_nring.
448 assert (Y:=lt_O_fact (S n')).
449 apply inj_Q_wd.
450 stepr ((fact (S n')):Q).
451 clear - n'.
452 induction (fact (S n')).
453 simpl; reflexivity.
454 rewrite inj_S.
455 unfold Z.succ.
456 simpl in *.
457 rewrite -> IHn0.
458 rewrite -> injz_plus.
459 reflexivity.
460 destruct (fact (S n')).
461 exfalso; auto with *.
462 simpl; reflexivity.
463 stepr ((inj_Q IR a)[^](S n')).
464 apply inj_Q_power.
465 change (inj_Q IR a[^]S n'[=](inj_Q IR a[-][0])[^]S n').
466 apply nexp_wd.
467 rational.
468 - intro p.
469 pose proof (Pos2Nat.is_pos p). destruct (Pos.to_nat p) eqn:des.
470 exfalso; inversion H0.
471 rewrite <- des. rewrite Pos2Nat.id. reflexivity.
472 Qed.
473
474 (** Sine's range can then be extended to [[-3^n,3^n]] by [n] applications
475 of the identity [sin(x) = 3*sin(x/3) - 4*(sin(x/3))^3]. *)
476 Section Sin_Poly.
477
478 Definition sin_poly_fun (x:Q) :Q := x*(3 - 4*x*x).
479
480 Global Instance: Proper ((=) ==> (=)) sin_poly_fun.
481 Proof. unfold sin_poly_fun. solve_proper. Qed.
482
483 Lemma sin_poly_fun_correct : forall (q:Q),
484 inj_Q IR (sin_poly_fun q)[=]Three[*]inj_Q IR q[-]Four[*](inj_Q IR q[^]3).
485 Proof.
486 intros q.
487 unfold sin_poly_fun.
488 stepr (inj_Q IR (3*q-4*q^3)).
489 apply inj_Q_wd.
490 simpl; ring.
491 rewrite inj_Q_minus.
492 apply cg_minus_wd.
493 stepr (inj_Q IR Three[*]inj_Q IR q).
494 apply inj_Q_mult.
495 apply mult_wdl.
496 apply (inj_Q_nring IR 3).
497 stepr (inj_Q IR Four[*]inj_Q IR (q^3)).
498 apply inj_Q_mult.
499 apply mult_wd.
500 apply (inj_Q_nring IR 4).
501 apply (inj_Q_power IR q 3).
502 Qed.
503
504 Definition sin_poly_modulus (e:Qpos) := Qpos2QposInf ((1#9)*e).
505
506 Lemma DthreeXMinusFourX3 : Derivative (clcr (inj_Q IR (-(1))) (inj_Q IR (1:Q)))
507 (inj_Q_less _ (-1) 1 eq_refl)
508 ((Three:IR){**}FId{-}(Four:IR){**}FId{^}3)
509 ((Three:IR){**}[-C-]([1]:IR){-}(Four:IR){**}((nring 3){**}([-C-][1]{*}FId{^}2))).
510 Proof.
511 apply Derivative_minus.
512 apply Derivative_scal.
513 apply Derivative_id.
514 apply Derivative_scal.
515 apply Derivative_nth.
516 apply Derivative_id.
517 Qed.
518
519 Lemma sin_poly_prf : is_UniformlyContinuousFunction (fun x => sin_poly_fun (QboundAbs (1#1) x)) sin_poly_modulus.
520 Proof.
521 apply (fun a => is_UniformlyContinuousD_Q
522 (Some (-(1))%Q) (Some (1:Q)) eq_refl _ _ DthreeXMinusFourX3 sin_poly_fun a (9#1)).
523 simpl; intros q _ _.
524 apply sin_poly_fun_correct.
525 simpl; intros x' _ [Hx0 Hx1].
526 set (x:=(inj_Q IR x')) in *.
527 stepr (Nine:IR); [| now (apply eq_symmetric; apply (inj_Q_nring IR 9))].
528 stepl (ABSIR (Three[-]Twelve[*]x[*]x)); [| now (apply AbsIR_wd; rational)].
529 apply AbsSmall_imp_AbsIR.
530 split.
531 apply shift_zero_leEq_minus'.
532 rstepr (Twelve[*]((nring 1)[-]x)[*](x[-][--](nring 1))).
533 repeat apply mult_resp_nonneg.
534 apply (nring_nonneg IR 12).
535 apply shift_zero_leEq_minus.
536 stepr (inj_Q IR (nring 1)); [| now apply inj_Q_nring].
537 assumption.
538 apply shift_zero_leEq_minus.
539 stepl (inj_Q IR (-(1))).
540 assumption.
541 stepr ([--](inj_Q IR 1)).
542 apply inj_Q_inv.
543 apply un_op_wd_unfolded.
544 apply (inj_Q_nring IR 1).
545 rstepr (Nine[-][0]:IR).
546 apply minus_resp_leEq_both.
547 apply nring_leEq.
548 lia.
549 rstepr (Twelve[*]x[^]2).
550 apply mult_resp_nonneg.
551 apply (nring_leEq IR 0 12).
552 lia.
553 apply sqr_nonneg.
554 Qed.
555
556 Definition sin_poly_uc : Q_as_MetricSpace --> Q_as_MetricSpace :=
557 Build_UniformlyContinuousFunction sin_poly_prf.
558
559 Definition sin_poly : CR --> CR
560 := uc_compose compress (Cmap QPrelengthSpace sin_poly_uc).
561
562 Lemma sin_poly_correct : forall x,
563 AbsSmall (inj_Q IR (1)) x
564 -> (IRasCR (Three[*]x[-]Four[*]x[^]3)==sin_poly (IRasCR x))%CR.
565 Proof.
566 intros x Hx.
567 assert (Y:Continuous (clcr (inj_Q IR (-(1))) (inj_Q IR (1:Q))) ((Three:IR){**}FId{-}(Four:IR){**}FId{^}3)).
568 eapply Derivative_imp_Continuous.
569 apply DthreeXMinusFourX3.
570 apply: (ContinuousCorrect
571 (I:=(clcr (inj_Q IR (-(1))) (inj_Q IR (1:Q))))
572 (inj_Q_less _ (-1) 1 eq_refl) Y);
573 [|repeat constructor|].
574 intros q Hq Hq0.
575 transitivity (IRasCR (inj_Q IR (sin_poly_fun q)));[|apply IRasCR_wd; apply sin_poly_fun_correct].
576 simpl.
577 change (' q)%CR with (Cunit_fun _ q).
578 rewrite -> compress_fun_correct.
579 rewrite -> Cmap_fun_correct.
580 rewrite -> MonadLaw3.
581 rewrite -> IR_inj_Q_as_CR.
582 rewrite -> CReq_Qeq.
583 simpl.
584 unfold sin_poly_fun.
585 setoid_replace (Qmax (- (1)) (Qmin 1 q)) with q.
586 reflexivity.
587 setoid_replace (Qmin 1 q) with q.
588 rewrite <- Qle_max_r.
589 apply leEq_inj_Q with IR.
590 destruct Hq0; assumption.
591 rewrite <- Qle_min_r.
592 apply leEq_inj_Q with IR.
593 destruct Hq0; assumption.
594 destruct Hx; split;[stepl [--](inj_Q IR (1:Q)); [| now apply eq_symmetric; apply inj_Q_inv] |];assumption.
595 Qed.
596
597 Lemma Sin_triple_angle : forall x, (Sin(Three[*]x)[=]Three[*]Sin x[-]Four[*]Sin x[^]3).
598 Proof.
599 intros x.
600 assert (H:Three[*]x[=]x[+]x[+]x) by rational.
601 csetoid_rewrite H.
602 csetoid_rewrite (Sin_plus (x[+]x) x).
603 csetoid_rewrite (Sin_plus x x).
604 csetoid_rewrite (Cos_plus x x).
605 set (sx:=Sin x).
606 set (cx:=Cos x).
607 rstepl ((cx[^]2)[*](Three[*]sx)[-]sx[^]3).
608 unfold cg_minus.
609 csetoid_replace (cx[^]2) ([1][-]sx[^]2).
610 rational.
611 apply cg_inv_unique_2.
612 rstepl ((cx[^]2[+]sx[^]2)[-][1]).
613 apply x_minus_x.
614 apply FFT.
615 Qed.
616
617 Lemma shrink_by_three : forall n a,
618 -(3^(S n))%Z <= a <= (3^(S n))%Z -> -(3^n)%Z <= a/3 <= (3^n)%Z.
619 Proof.
620 intros n a H0.
621 apply AbsSmall_Qabs. apply AbsSmall_Qabs in H0.
622 apply Qmult_lt_0_le_reg_r with (Qabs 3).
623 reflexivity. rewrite <- Qabs_Qmult.
624 unfold Qdiv. rewrite <- Qmult_assoc.
625 setoid_replace (/ 3 * 3) with 1 by reflexivity.
626 rewrite Qmult_1_r.
627 apply (Qle_trans _ _ _ H0). clear H0.
628 change (Qabs 3) with (inject_Z 3).
629 rewrite <- (inject_Z_mult (3^n) 3).
630 rewrite <- Zle_Qle.
631 change (S n) with (1+n)%nat.
632 rewrite (Nat2Z.inj_add 1 n).
633 rewrite ZBinary.Z.pow_add_r, Z.mul_comm.
634 apply Z.le_refl.
635 discriminate.
636 apply (Nat2Z.inj_le 0), Nat.le_0_l.
637 Qed.
638
639 Fixpoint rational_sin_bounded (n:nat) (a:Q) : -(3^n)%Z <= a <= (3^n)%Z -> CR :=
640 match n return -(3^n)%Z <= a <= (3^n)%Z -> CR with
641 | O => @rational_sin_small a
642 | S n' => fun H => sin_poly (rational_sin_bounded n' (shrink_by_three n' H))
643 end.
644
645 Lemma rational_sin_bounded_correct_aux a :
646 (sin_poly (IRasCR (Sin (inj_Q IR (a / 3)))) == IRasCR (Sin (inj_Q IR a)))%CR.
647 Proof.
648 rewrite <- sin_poly_correct; [|apply AbsIR_imp_AbsSmall;
649 (stepr (nring 1:IR); [| now apply eq_symmetric; apply (inj_Q_nring IR 1)]); rstepr ([1]:IR);
650 apply AbsIR_Sin_leEq_One].
651 apply IRasCR_wd.
652 stepl (Sin (inj_Q IR (a/3*3))).
653 apply Sin_wd.
654 apply inj_Q_wd.
655 simpl; field; discriminate.
656 generalize (a/3).
657 intros b; clear -b.
658 stepr (Sin (Three[*](inj_Q IR b))).
659 apply Sin_wd.
660 stepr ((inj_Q IR b)[*](inj_Q IR (3:Q))).
661 apply inj_Q_mult.
662 csetoid_replace (inj_Q IR (3:Q)) (Three:IR).
663 rational.
664 apply (inj_Q_nring IR 3).
665 apply Sin_triple_angle.
666 Qed.
667
668 Lemma rational_sin_bounded_correct :
669 forall (n:nat) (a:Q) (Ha : -(3^n #1) <= a <= (3^n #1)),
670 (@rational_sin_bounded n a Ha == IRasCR (Sin (inj_Q IR a)))%CR.
671 Proof.
672 induction n.
673 apply rational_sin_small_correct.
674 intros a Ha.
675 unfold rational_sin_bounded; fold rational_sin_bounded.
676 rewrite -> IHn.
677 apply rational_sin_bounded_correct_aux.
678 Qed.
679 End Sin_Poly.
680
681 Definition sin_bound (q:Q) : nat := Z.abs_nat (1 + Qdlog 3 (Qabs q)).
682
683 Lemma sin_bound_correct : forall q, -(3 ^ sin_bound q #1) ≤ q ≤ (3 ^ sin_bound q #1).
684 Proof.
685 intro q.
686 apply AbsSmall_Qabs.
687 unfold sin_bound.
688 destruct (Qlt_le_dec (Qabs q) 1).
689 - apply (Qle_trans _ 1).
690 apply Qlt_le_weak, q0.
691 rewrite Qdlog2_le1; simpl; try easy.
692 apply Qlt_le_weak, q0.
693 - assert (2 ≤ 3%Z) as H by discriminate.
694 pose proof (Qdlog_spec 3 (Qabs q) H q0) as [_ H0]. clear H.
695 unfold additional_operations.pow, stdlib_rationals.Q_pow in H0.
696 assert (0 <= 1 + Qdlog 3 (Qabs q))%Z.
697 { apply semirings.nonneg_plus_compat; [easy | now apply Qdlog_bounded_nonneg]. }
698 rewrite inj_Zabs_nat, Z.abs_eq.
699 apply Qlt_le_weak.
700 rewrite <- Zpower_Qpower in H0. apply H0.
701 exact H. exact H.
702 Qed.
703
704 (** Therefore sin works on all real numbers. *)
705 Definition rational_sin (a:Q) : CR :=
706 rational_sin_bounded (sin_bound a) (sin_bound_correct a).
707
708 Lemma rational_sin_correct : forall (a:Q),
709 (rational_sin a == IRasCR (Sin (inj_Q IR a)))%CR.
710 Proof.
711 intros; apply rational_sin_bounded_correct.
712 Qed.
713
714 #[global]
715 Instance: Proper ((=) ==> (=)) rational_sin.
716 Proof.
717 intros ? ? E.
718 rewrite ?rational_sin_correct.
719 now apply IRasCR_wd, Sin_wd, inj_Q_wd.
720 Qed.
721
722 Lemma rational_sin_poly (a : Q) :
723 sin_poly (rational_sin (a / 3)) = rational_sin a.
724 Proof.
725 rewrite ?rational_sin_correct.
726 apply rational_sin_bounded_correct_aux.
727 Qed.
728
729 Lemma rational_sin_correct_aux (a : Q) :
730 (- IRasCR (Sin (inj_Q IR (- a)%Q)) == IRasCR (Sin (inj_Q IR a)))%CR.
731 Proof.
732 rewrite <- IR_opp_as_CR.
733 apply IRasCR_wd.
734 csetoid_rewrite_rev (Sin_inv (inj_Q IR (-a))).
735 apply Sin_wd.
736 csetoid_rewrite_rev (inj_Q_inv IR (-a)).
737 apply inj_Q_wd.
738 simpl.
739 ring.
740 Qed.
741
742 Lemma rational_sin_opp (a : Q) :
743 (-rational_sin (-a) = rational_sin a)%CR.
744 Proof.
745 rewrite ?rational_sin_correct.
746 now apply rational_sin_correct_aux.
747 Qed.
748
749 (** Sine is uniformly continuous everywhere. *)
750 Definition sin_uc_prf : is_UniformlyContinuousFunction rational_sin Qpos2QposInf.
751 Proof.
752 apply (is_UniformlyContinuousFunction_wd) with (fun x => rational_sin x) (Qscale_modulus (1#1)).
753 reflexivity.
754 intros x.
755 simpl.
756 autorewrite with QposElim.
757 change (/1) with 1.
758 replace RHS with (proj1_sig x) by simpl; ring.
759 apply Qle_refl.
760 apply (is_UniformlyContinuousD None None I Sine Cosine (Derivative_Sin I) rational_sin).
761 intros q [] _.
762 apply rational_sin_correct.
763 intros x [] _.
764 stepr ([1]:IR).
765 apply: AbsIR_Cos_leEq_One.
766 rstepl (nring 1:IR).
767 apply eq_symmetric.
768 apply (inj_Q_nring IR 1).
769 Qed.
770
771 Definition sin_uc : Q_as_MetricSpace --> CR :=
772 Build_UniformlyContinuousFunction sin_uc_prf.
773
774 Definition sin_slow : CR --> CR := Cbind QPrelengthSpace sin_uc.
775
776 Lemma sin_slow_correct : forall x,
777 (IRasCR (Sin x) == sin_slow (IRasCR x))%CR.
778 Proof.
779 intros x.
780 apply: (ContinuousCorrect (I:proper realline)); [apply Continuous_Sin | | constructor].
781 intros q [] _.
782 transitivity (rational_sin q);[|apply rational_sin_correct].
783 unfold sin_slow.
784 rewrite -> (Cbind_fun_correct QPrelengthSpace sin_uc).
785 apply: BindLaw1.
786 Qed.
787
788 Definition sin (x:CR) := sin_slow (x - (compress (scale (2*Qceiling (approximate (x*(CRinv_pos (6#1) (scale 2 CRpi))) (Qpos2QposInf (1#2)) -(1#2))) CRpi)))%CR.
789
790 Lemma sin_correct : forall x,
791 (IRasCR (Sin x) == sin (IRasCR x))%CR.
792 Proof.
793 intros x.
794 unfold sin.
795 generalize (Qceiling (approximate (IRasCR x * CRinv_pos (6 # 1) (scale 2 CRpi))
796 (Qpos2QposInf (1 # 2)) - (1 # 2)))%CR.
797 intros z.
798 rewrite -> compress_correct.
799 rewrite <- CRpi_correct, <- CRmult_scale, <- IR_inj_Q_as_CR, <- IR_mult_as_CR,
800 <- IR_minus_as_CR, <- sin_slow_correct.
801 apply IRasCR_wd.
802 rewrite -> inj_Q_mult.
803 change (2:Q) with (@nring Q_as_CRing 2).
804 rewrite -> inj_Q_nring.
805 rstepr (Sin (x[+]([--](inj_Q IR z))[*](Two[*]Pi))).
806 setoid_replace (inj_Q IR z) with (zring z:IR).
807 rewrite <- zring_inv.
808 symmetry; apply Sin_periodic_Z.
809 rewrite <- inj_Q_zring.
810 apply inj_Q_wd.
811 symmetry; apply zring_Q.
812 Qed.
813
814 (* begin hide *)
815 #[global]
816 Hint Rewrite sin_correct : IRtoCR.
817 (* end hide *)