Debian Codegraph @

reals/fast/CRpower.v

raw
1 (*
2 Copyright © 2006-2008 Russell O’Connor
3 Copyright © 2020 Vincent Semeria
4
5 Permission is hereby granted, free of charge, to any person obtaining a copy of
6 this proof and associated documentation files (the "Proof"), to deal in
7 the Proof without restriction, including without limitation the rights to
8 use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
9 the Proof, and to permit persons to whom the Proof is furnished to do so,
10 subject to the following conditions:
11
12 The above copyright notice and this permission notice shall be included in all
13 copies or substantial portions of the Proof.
14
15 THE PROOF IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
17 FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR
18 COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
19 IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
20 CONNECTION WITH THE PROOF OR THE USE OR OTHER DEALINGS IN THE PROOF.
21 *)
22 From Coq Require Import ZArith.
23 Require Import CoRN.algebra.RSetoid.
24 Require Import CoRN.metric2.Metric.
25 Require Import CoRN.metric2.ProductMetric.
26 Require Import CoRN.reals.fast.CRArith.
27 From Coq Require Import Qpower.
28 From Coq Require Import Qabs.
29 Require Import CoRN.model.metric2.Qmetric.
30 Require Import CoRN.model.totalorder.QMinMax.
31 Require Import CoRN.model.totalorder.QposMinMax.
32 Require Import MathClasses.interfaces.canonical_names.
33 Require Import MathClasses.interfaces.additional_operations.
34
35 (* Backwards compatibility for Hint Rewrite locality attributes *)
36 Set Warnings "-unsupported-attributes".
37
38 Local Open Scope Q_scope.
39 Local Open Scope uc_scope.
40
41 (**
42 ** Natural Integer Powers
43 Positive integer powers is faster than repeated multiplication.
44
45 It is uniformly continuous on an interval [[-c,c]].
46 *)
47
48 (* We first define repeated multiplication to prove correctness. *)
49 Fixpoint CRpower_slow (x : CR) (n : nat) { struct n }
50 := match n with
51 | O => 1%CR
52 | S p => (x * CRpower_slow x p)%CR
53 end.
54
55 Lemma CRpower_slow_wd : forall (x y : CR) (n : nat),
56 msp_eq x y -> msp_eq (CRpower_slow x n) (CRpower_slow y n).
57 Proof.
58 induction n.
59 - intros. reflexivity.
60 - intros. simpl (CRpower_slow x (S n)).
61 rewrite (IHn H). rewrite H. reflexivity.
62 Qed.
63
64 Lemma Qpower_positive_abs_le : forall (q:Q) (c : Qpos) (n : positive),
65 Qabs q <= `c
66 -> Qabs (Qpower_positive q n) <= Qpower_positive (` c) n.
67 Proof.
68 intros q c.
69 induction n.
70 - intros. simpl (Qpower_positive q n~1).
71 rewrite Qabs_Qmult.
72 simpl (Qpower_positive (` c) n~1).
73 apply (Qle_trans _ (`c * Qabs (Qpower_positive q n * Qpower_positive q n))).
74 apply Qmult_le_compat_r. exact H.
75 apply Qabs_nonneg. apply Qmult_le_l.
76 apply Qpos_ispos.
77 rewrite Qabs_Qmult.
78 apply (Qle_trans _ (Qpower_positive (`c) n * Qabs (Qpower_positive q n))).
79 apply Qmult_le_compat_r. apply IHn. exact H.
80 apply Qabs_nonneg.
81 rewrite Qmult_comm.
82 apply Qmult_le_compat_r. apply IHn. exact H.
83 apply Qpower_pos_positive, Qpos_nonneg.
84 - intros. simpl (Qpower_positive q n~0).
85 rewrite Qabs_Qmult. simpl.
86 apply (Qle_trans _ (Qpower_positive (`c) n * Qabs (Qpower_positive q n))).
87 apply Qmult_le_compat_r. apply IHn. exact H.
88 apply Qabs_nonneg.
89 rewrite Qmult_comm.
90 apply Qmult_le_compat_r. apply IHn. exact H.
91 apply Qpower_pos_positive, Qpos_nonneg.
92 - intros. exact H.
93 Qed.
94
95 (* The derivative of fun z => z^p is fun z => p * z^(p-1)
96 which is bounded by p*c^(p-1) on [-c,c]. *)
97 Lemma Qdiff_power : forall (n : nat) (x y : Q) (c : Qpos),
98 (-`c <= x <= `c)
99 -> (-`c <= y <= `c)
100 -> Qabs (x^Z.of_nat n - y^Z.of_nat n)
101 <= Qabs(x-y) * (Z.of_nat n#1) * (`c) ^ (Z.pred (Z.of_nat n)).
102 Proof.
103 induction n.
104 - intros. apply Qmult_le_0_compat.
105 apply Qmult_le_0_compat. apply Qabs_nonneg.
106 discriminate. apply (Qpos_nonneg (Qpos_power c (Z.pred (Z.of_nat 0)))).
107 - intros. change (S n) with (1 + n)%nat.
108 rewrite Nat2Z.inj_add, Qpower_plus', Qpower_plus'.
109 simpl (x ^ Z.of_nat 1).
110 simpl (y ^ Z.of_nat 1).
111 setoid_replace (x * x ^ Z.of_nat n - y * y ^ Z.of_nat n)%Q
112 with ((x-y)*x ^ Z.of_nat n + y * (x ^ Z.of_nat n - y ^ Z.of_nat n))%Q
113 by (unfold equiv, stdlib_rationals.Q_eq; ring).
114 apply (Qle_trans _ _ _ (Qabs_triangle _ _)).
115 rewrite Qabs_Qmult, Qabs_Qmult.
116 apply (Qle_trans _ (Qabs (x-y) * (`c) ^ Z.of_nat n
117 + Qabs (x - y) * (Z.of_nat n # 1) * ` c ^ Z.pred (Z.of_nat n) * Qabs y)).
118 apply Qplus_le_compat.
119 + rewrite Qmult_comm, (Qmult_comm (Qabs (x-y))).
120 apply Qmult_le_compat_r. 2: apply Qabs_nonneg.
121 destruct n. apply Qle_refl.
122 apply Qpower_positive_abs_le.
123 apply AbsSmall_Qabs, H.
124 + rewrite Qmult_comm. apply Qmult_le_compat_r.
125 2: apply Qabs_nonneg. apply IHn. exact H. exact H0.
126 + clear IHn.
127 rewrite <- Qmult_assoc, <- Qmult_assoc, <- Qmult_plus_distr_r.
128 rewrite Qmult_comm, <- Qmult_assoc, (Qmult_comm (Qabs (x-y))).
129 apply Qmult_le_compat_r. 2: apply Qabs_nonneg.
130 apply (Qle_trans _ (` c ^ Z.of_nat n + (Z.of_nat n # 1) * (` c ^ (Z.of_nat n)))).
131 apply Qplus_le_r.
132 rewrite Qmult_comm, (Qmult_comm (Z.of_nat n # 1)).
133 apply Qmult_le_compat_r.
134 apply (Qle_trans _ (`c ^ Z.of_nat 1 * ` c ^ Z.pred (Z.of_nat n))).
135 rewrite Qmult_comm. apply Qmult_le_compat_r.
136 simpl. apply AbsSmall_Qabs. exact H0.
137 apply Qpower_pos. apply Qpos_nonneg.
138 rewrite <- Qpower_plus. 2: apply Qpos_nonzero.
139 replace (Z.of_nat 1 + Z.pred (Z.of_nat n))%Z with (Z.of_nat n).
140 apply Qle_refl.
141 rewrite Z.add_1_l. rewrite Z.succ_pred. reflexivity.
142 unfold Qle; simpl. rewrite Z.mul_1_r. apply Nat2Z.is_nonneg.
143 rewrite <- (Qmult_1_l (` c ^ Z.of_nat n)) at 1.
144 rewrite <- Qmult_plus_distr_l.
145 setoid_replace (1 + (Z.of_nat n # 1)) with (Z.of_nat 1 + Z.of_nat n#1).
146 rewrite Qmult_comm.
147 rewrite (Qmult_comm (Z.of_nat 1 + Z.of_nat n#1)).
148 apply Qmult_le_compat_r.
149 replace (Z.pred (Z.of_nat 1 + Z.of_nat n)) with (Z.of_nat n).
150 apply Qle_refl.
151 rewrite <- Nat2Z.inj_add. rewrite Nat2Z.inj_succ.
152 rewrite <- Zpred_succ. reflexivity.
153 rewrite <- Nat2Z.inj_add. discriminate.
154 unfold equiv, stdlib_rationals.Q_eq, Qeq, Qplus, Qnum, Qden.
155 simpl (1*1)%Z. rewrite Z.mul_1_r, Z.mul_1_r.
156 simpl (1*1)%positive. rewrite Z.mul_1_r. reflexivity.
157 + rewrite <- Nat2Z.inj_add. discriminate.
158 + rewrite <- Nat2Z.inj_add. discriminate.
159 Qed.
160
161 Section CRpower_N.
162
163 Variable n : N. (* Binary integers are faster than unary integers *)
164
165 (* To compute x^n, we bound x by c and the modulus becomes
166 fun e => e / (n * c^(n-1)) *)
167 Definition Qpower_N_modulus (c:Qpos) (e:Qpos) : QposInf :=
168 match n with
169 | N0 => QposInfinity
170 | Npos p => Qpos2QposInf (e* Qpos_inv ((p#1)*Qpos_power c (Z.pred (Zpos p))))
171 end.
172
173 Lemma Qpower_N_uc_prf (c:Qpos) :
174 @is_UniformlyContinuousFunction
175 Q_as_MetricSpace Q_as_MetricSpace
176 (fun x => Qpower (QboundAbs c x) (Z_of_N n)) (Qpower_N_modulus c).
177 Proof.
178 unfold Qpower_N_modulus.
179 destruct n as [|p].
180 - simpl. intros e x y E. apply ball_refl, Qpos_nonneg.
181 - clear n. intros e x y E. unfold ball_ex in E.
182 simpl (Z.of_N (N.pos p)).
183 apply AbsSmall_Qabs.
184 apply AbsSmall_Qabs in E.
185 assert (-` c <= QboundAbs c x ∧ QboundAbs c x <= ` c).
186 { split. apply Qmax_ub_l.
187 apply Qmax_lub.
188 apply (Qle_trans _ 0). apply (Qopp_le_compat 0), Qpos_nonneg.
189 apply Qpos_nonneg. apply Qmin_lb_l. }
190 assert (- ` c <= QboundAbs c y ∧ QboundAbs c y <= ` c).
191 { split. apply Qmax_ub_l.
192 apply Qmax_lub.
193 apply (Qle_trans _ 0). apply (Qopp_le_compat 0), Qpos_nonneg.
194 apply Qpos_nonneg. apply Qmin_lb_l. }
195 pose proof (positive_nat_Z p).
196 rewrite <- H1.
197 apply (Qle_trans _ _ _ (Qdiff_power (Pos.to_nat p) _ _ c H H0)).
198 clear H H0.
199 rewrite <- Qmult_assoc.
200 apply (Qle_trans _ (Qabs (x-y) * ((Z.pos p # 1) * ` c ^ Z.pred (Z.pos p)))).
201 rewrite H1.
202 apply Qmult_le_compat_r.
203 apply QboundAbs_contract.
204 apply (Qpos_nonneg ((p#1) * Qpos_power c (Z.pred (Z.pos p)))).
205 apply (Qle_trans _ (`e * / proj1_sig ((Z.pos p # 1)%Q ↾ eq_refl * Qpos_power c (Z.pred (Z.pos p)))%Qpos * ((Z.pos p # 1) * ` c ^ Z.pred (Z.pos p)))).
206 apply Qmult_le_compat_r.
207 apply E.
208 apply (Qpos_nonneg ((p#1) * Qpos_power c (Z.pred (Z.pos p)))).
209 rewrite Qmult_comm, Qmult_assoc.
210 apply Qle_shift_div_r.
211 apply (Qpos_ispos ((p#1) * Qpos_power c (Z.pred (Z.pos p)))).
212 rewrite Qmult_comm. apply Qle_refl.
213 Qed.
214
215 Definition Qpower_N_uc (c:Qpos) : Q_as_MetricSpace --> Q_as_MetricSpace :=
216 Build_UniformlyContinuousFunction (Qpower_N_uc_prf c).
217
218 (** CRpower_positive_bounded works on [[-c,c]]. *)
219 Definition CRpower_N_bounded (c:Qpos) : CR --> CR :=
220 Cmap QPrelengthSpace (Qpower_N_uc c).
221
222 End CRpower_N.
223
224 Lemma Cmap_wd_bounded
225 : forall (Y : MetricSpace)
226 (f g : Q_as_MetricSpace --> Y) (x : CR) (c : Qpos),
227 (forall q:Q, -`c <= q <= `c -> msp_eq (f q) (g q))
228 -> (- ' (proj1_sig c) <= x /\ x <= ' (proj1_sig c))%CR
229 -> msp_eq (Cmap_fun QPrelengthSpace f x) (Cmap_fun QPrelengthSpace g x).
230 Proof.
231 intros.
232 setoid_replace x with (CRboundAbs c x).
233 2: symmetry; apply CRboundAbs_Eq; apply H0.
234 pose (fun e => QposInf_min (mu f e) (mu g e)) as mufg.
235 assert (∀ e : Qpos, QposInf_le (mufg e) (mu f e)).
236 { intro e. unfold QposInf_le, mufg.
237 destruct (mu f e). 2: trivial.
238 simpl. destruct (mu g e). 2: apply Qle_refl.
239 apply Qpos_min_lb_l. }
240 pose proof (uc_prf_smaller f mufg H1). clear H1.
241 setoid_replace f with (Build_UniformlyContinuousFunction H2).
242 2: apply ucEq_equiv; intro q; reflexivity.
243 assert (∀ e : Qpos, QposInf_le (mufg e) (mu g e)).
244 { intro e. unfold QposInf_le, mufg.
245 destruct (mu g e). 2: trivial.
246 simpl. destruct (mu f e). 2: apply Qle_refl.
247 apply Qpos_min_lb_r. }
248 pose proof (uc_prf_smaller g mufg H1). clear H1.
249 setoid_replace g with (Build_UniformlyContinuousFunction H3).
250 2: apply ucEq_equiv; intro q; reflexivity.
251 intros e1 e2.
252 assert (forall y, eq (QposInf_bind (fun e : Qpos => e) y) y) as elim_bind.
253 { intro y. destruct y; reflexivity. }
254 simpl.
255 rewrite elim_bind, elim_bind. clear elim_bind.
256 assert (forall a, Qmax (- ` c) (Qmin (` c) a) <= ` c).
257 { intro a. apply Qmax_lub.
258 apply (Qle_trans _ 0). apply (Qopp_le_compat 0), Qpos_nonneg.
259 apply Qpos_nonneg. apply Qmin_lb_l. }
260 rewrite Qplus_0_r.
261 destruct (mufg e1) as [q|] eqn:des.
262 - rewrite H.
263 apply (mu_sum QPrelengthSpace e2 (cons e1 nil)
264 (Build_UniformlyContinuousFunction H3)).
265 simpl. rewrite des. simpl. destruct (mufg e2) eqn:des2.
266 simpl. apply AbsSmall_Qabs.
267 apply (Qle_trans _ (Qabs (approximate x q - approximate x q0))).
268 apply QboundAbs_contract.
269 apply AbsSmall_Qabs. apply (regFun_prf x).
270 simpl. trivial.
271 split. apply Qmax_ub_l. apply H1.
272 - rewrite <- H.
273 apply (mu_sum QPrelengthSpace e2 (cons e1 nil) f).
274 simpl. unfold mufg in des.
275 destruct (mu f e1) as [q|]. exfalso.
276 simpl in des. destruct (mu g e1); inversion des.
277 simpl. trivial.
278 split. apply Qmax_ub_l. apply H1.
279 Qed.
280
281 Lemma CRpower_N_bounded_step : forall (n:N) (c:Qpos) (x : CR),
282 (forall e, - (proj1_sig c) <= approximate x e)
283 -> (forall e, approximate x e <= proj1_sig c)
284 -> (CRpower_N_bounded (1+n) c x
285 == x * CRpower_N_bounded n c x)%CR.
286 Proof.
287 assert (forall i j : Q, i<=j -> Qmax i j == j)%Q as elim_max.
288 { intros. apply (Qle_max_r i j), H. }
289 assert (forall i j : Q, j<=i -> Qmin i j == j)%Q as elim_min.
290 { intros. apply (Qle_min_r i j), H. }
291 intros.
292 assert (x <= ' ` c)%CR as xupper.
293 { intro e. simpl. unfold Cap_raw. simpl.
294 apply (Qle_trans _ 0). apply (Qopp_le_compat 0), Qpos_nonneg.
295 rewrite <- Qle_minus_iff. apply H0. }
296 assert (- ' ` c <= x)%CR as xlower.
297 { intro e. simpl. unfold Cap_raw. simpl.
298 apply (Qle_trans _ 0). apply (Qopp_le_compat 0), Qpos_nonneg.
299 rewrite <- Qle_minus_iff. apply H. }
300 destruct n as [|n].
301 - setoid_replace (CRpower_N_bounded 0 c x) with 1%CR.
302 2: intros e1 e2; apply Qball_Reflexive; rewrite Qplus_0_r; apply (Qpos_nonneg (e1+e2)).
303 rewrite CRmult_1_r. simpl (1+0)%N.
304 intros e1 e2. simpl.
305 rewrite Qplus_0_r.
306 rewrite elim_min. 2: apply H0.
307 rewrite elim_max. 2: apply H.
308 setoid_replace (` e1 + ` e2)%Q
309 with (` (e1 * Qpos_inv (1 ↾ eq_refl * Qpos_power c 0))%Qpos + ` e2).
310 apply (regFun_prf x).
311 apply Qplus_comp. 2: reflexivity.
312 simpl. change (/ (1*1)) with 1.
313 rewrite Qmult_1_r. reflexivity.
314 - rewrite CRmult_comm.
315 pose (Qpos_max c (Qpos_power c (Z_of_N (N.pos n)))) as b.
316 rewrite <- (CRmult_bounded_mult c).
317 2: exact xlower. 2: exact xupper.
318 rewrite (CRmult_bounded_weaken c b).
319 2: exact xlower. 2: exact xupper. 2: apply Qpos_max_ub_l.
320 rewrite (CRmult_uncurry_eq b).
321 unfold CRpower_N_bounded.
322 transitivity (Cmap QPrelengthSpace
323 (uc_compose (Qmult_uncurry b)
324 (uc_compose (together (Qpower_N_uc (N.pos n) c)
325 (uc_id Q_as_MetricSpace))
326 (diag Q_as_MetricSpace)))
327 x).
328 + apply Cmap_wd_bounded with (c:=c).
329 intros q H1. destruct H1.
330 apply Qball_0.
331 change (Qpower_positive (Qmax (- ` c) (Qmin (` c) q)) (1+n)
332 ==
333 Qmax (- ` b) (Qmin (` b) (Qpower_positive (Qmax (- ` c) (Qmin (` c) q)) n)) *
334 Qmax (- ` b) (Qmin (` b) q)).
335 rewrite (elim_min _ q). 2: exact H2.
336 rewrite (elim_max _ q). 2: exact H1.
337 2: exact (conj xlower xupper).
338 rewrite (elim_min _ q).
339 rewrite (elim_max _ q).
340 rewrite Qpower_plus_positive. simpl.
341 rewrite Qmult_comm. apply Qmult_comp. 2: reflexivity.
342 assert (Qabs q <= `c).
343 { apply AbsSmall_Qabs. split. exact H1. exact H2. }
344 pose proof (Qpower_positive_abs_le q c n H3). clear H3.
345 apply AbsSmall_Qabs in H4. destruct H4.
346 rewrite elim_min, elim_max. reflexivity.
347 apply (Qle_trans _ (-(Qpower_positive (`c) n))).
348 apply Qopp_le_compat.
349 apply (Qpos_max_ub_r c (Qpower_positive (` c) n ↾ Qpos_power_ispos c (Z.pos n))).
350 exact H3.
351 apply (Qle_trans _ (Qpower_positive (`c) n)).
352 exact H4.
353 apply (Qpos_max_ub_r c (Qpower_positive (` c) n ↾ Qpos_power_ispos c (Z.pos n))).
354 apply (Qle_trans _ (-`c)). apply Qopp_le_compat, Qpos_max_ub_l.
355 exact H1.
356 apply (Qle_trans _ (`c)). apply H2. apply Qpos_max_ub_l.
357 + rewrite (fast_MonadLaw2 QPrelengthSpace
358 (ProductMS_prelength QPrelengthSpace QPrelengthSpace)).
359 apply Cmap_wd. apply ucEq_equiv. intro a; reflexivity.
360 intros e1 e2. split.
361 rewrite Qplus_0_r.
362 apply (mu_sum QPrelengthSpace e2 (cons e1 nil) (Qpower_N_uc (N.pos n) c)).
363 apply (@ball_weak_le Q_as_MetricSpace
364 (proj1_sig (Qpos_min
365 (e1 *
366 Qpos_inv
367 ((n # 1) *
368 Qpos_power c (Z.pred (Zpos n)) )) e1
369 + (e2 *
370 Qpos_inv
371 ((n # 1) *
372 Qpos_power c (Z.pred (Zpos n)) )))%Qpos)).
373 apply Qplus_le_l.
374 apply Qpos_min_lb_l.
375 apply (regFun_prf x).
376 apply (@ball_weak_le Q_as_MetricSpace
377 (proj1_sig (Qpos_min
378 (e1 *
379 Qpos_inv
380 ((n # 1) *
381 Qpos_power c (Z.pred (Zpos n)) )) e1
382 + e2)%Qpos)).
383 apply Qplus_le_l.
384 rewrite Qplus_0_r.
385 apply Qpos_min_lb_r.
386 apply (regFun_prf x).
387 + intro e. simpl.
388 unfold Cap_raw; simpl.
389 apply (Qle_trans _ 0).
390 apply (Qopp_le_compat 0), Qpos_nonneg.
391 rewrite <- Qle_minus_iff.
392 apply (Qle_trans _ (-Qpower_positive (` c) n)).
393 apply Qopp_le_compat.
394 apply (Qpos_max_ub_r c (Qpower_positive (` c) n ↾ Qpos_power_ispos c (Z.pos n))).
395 assert (forall i j :Q, -j <= i -> -i <= j).
396 { intros. rewrite <- (Qopp_involutive j).
397 apply Qopp_le_compat, H1. }
398 apply H1. clear H1.
399 apply (Qle_trans _ _ _ (Qle_Qabs _)).
400 rewrite Qabs_opp.
401 apply (Qpower_positive_abs_le
402 (Qmax (- ` c)
403 (Qmin (` c)
404 (approximate x
405 ((1 # 2) * e *
406 Qpos_inv
407 ((n # 1) *
408 Qpos_power c
409 (Z.pred (Zpos n)) ))%Qpos))) c n).
410 apply AbsSmall_Qabs. split. apply Qmax_ub_l.
411 apply Qmax_lub.
412 apply (Qle_trans _ 0). apply (Qopp_le_compat 0), Qpos_nonneg.
413 apply Qpos_nonneg. apply Qmin_lb_l.
414 + intro e. simpl.
415 unfold Cap_raw; simpl.
416 apply (Qle_trans _ 0).
417 apply (Qopp_le_compat 0), Qpos_nonneg.
418 rewrite <- Qle_minus_iff.
419 apply (Qle_trans _ _ _ (Qle_Qabs _)).
420 apply (Qle_trans _ (Qpower_positive (` c) n)).
421 apply (Qpower_positive_abs_le
422 (Qmax (- ` c)
423 (Qmin (` c)
424 (approximate x
425 ((1 # 2) * e *
426 Qpos_inv
427 ((n # 1) *
428 Qpos_power c
429 (Z.pred (Zpos n)) ))%Qpos))) c n).
430 apply AbsSmall_Qabs. split. apply Qmax_ub_l.
431 apply Qmax_lub.
432 apply (Qle_trans _ 0). apply (Qopp_le_compat 0), Qpos_nonneg.
433 apply Qpos_nonneg. apply Qmin_lb_l.
434 apply (Qpos_max_ub_r c (Qpower_positive (` c) n ↾ Qpos_power_ispos c (Z.pos n))).
435 Qed.
436
437 Lemma CRpower_N_bounded_correct : forall (n:N) (c:Qpos) (x : CR),
438 (- (' (proj1_sig c)) <= x /\ x <= 'proj1_sig c)%CR
439 -> (CRpower_slow x (N.to_nat n) == CRpower_N_bounded n c x)%CR.
440 Proof.
441 assert (∀ (n : nat) (c : Qpos) (x : CR),
442 (forall e, - (proj1_sig c) <= approximate x e)
443 -> (forall e, approximate x e <= proj1_sig c)
444 → msp_eq (CRpower_slow x n) (CRpower_N_bounded (N.of_nat n) c x)).
445 induction n.
446 - intros. intros e1 e2. simpl. apply Qball_Reflexive.
447 rewrite Qplus_0_r.
448 apply (Qpos_nonneg (e1+e2)).
449 - intros. change (S n) with (1+n)%nat.
450 rewrite Nnat.Nat2N.inj_add.
451 change (N.of_nat 1) with 1%N.
452 rewrite CRpower_N_bounded_step. 2: exact H.
453 change (CRpower_slow x (1 + n)) with (x * CRpower_slow x n)%CR.
454 apply CRmult_wd. reflexivity. apply IHn. exact H.
455 exact H0. exact H0.
456 - intros.
457 transitivity (CRpower_N_bounded (N.of_nat (N.to_nat n)) c x).
458 2: rewrite Nnat.N2Nat.id; reflexivity.
459 transitivity (CRpower_N_bounded (N.of_nat (N.to_nat n)) c (CRboundAbs c x)).
460 transitivity (CRpower_slow (CRboundAbs c x) (N.to_nat n)).
461 apply CRpower_slow_wd. symmetry.
462 apply CRboundAbs_Eq. apply H0. apply H0.
463 apply H. intro e. simpl. apply Qmax_ub_l.
464 intros e. apply Qmax_lub.
465 apply (Qle_trans _ 0). apply (Qopp_le_compat 0), Qpos_nonneg.
466 apply Qpos_nonneg. apply Qmin_lb_l.
467 apply Cmap_wd. apply ucEq_equiv; intro a; reflexivity.
468 apply CRboundAbs_Eq. apply H0. apply H0.
469 Qed.
470
471 Lemma CRpower_N_bounded_weaken : forall (n:N) (c1 c2:Qpos) x,
472 ((- (' (proj1_sig c1)) <= x /\ x <= 'proj1_sig c1)
473 -> (proj1_sig c1 <= proj1_sig c2)%Q ->
474 CRpower_N_bounded n c1 x == CRpower_N_bounded n c2 x)%CR.
475 Proof.
476 intros n c1 c2 x Hx Hc.
477 simpl in x.
478 rewrite <- CRpower_N_bounded_correct.
479 rewrite <- CRpower_N_bounded_correct.
480 reflexivity. 2: exact Hx. destruct Hx.
481 split.
482 - apply (@CRle_trans _ (-'(proj1_sig c1))%CR).
483 apply CRopp_le_compat, CRle_Qle, Hc. exact H.
484 - apply (CRle_trans H0). apply CRle_Qle, Hc.
485 Qed.
486
487
488 (** [CRpower_positive_bounded] is should be used when a known bound
489 on the absolute value of x is available. *)
490 #[global]
491 Instance CRpower_N: Pow CR N := λ x n, ucFun (CRpower_N_bounded n (CR_b (1#1) x)) x.
492 Arguments CRpower_N x%type n%N.
493
494 Lemma CRpower_N_bounded_N_power : forall (n : N) (c:Qpos) (x:CR),
495 ((- (' (proj1_sig c)) <= x /\ x <= 'proj1_sig c) ->
496 CRpower_N_bounded n c x == CRpower_N x n)%CR.
497 Proof.
498 intros n c x Hc.
499 assert (- ('proj1_sig (CR_b (1#1) x)) <= x
500 /\ x <= ('proj1_sig (CR_b (1#1) x)))%CR as Hx.
501 { split.
502 rewrite -> CRopp_Qopp.
503 apply CR_b_lowerBound.
504 apply CR_b_upperBound. }
505 unfold CRpower_N.
506 generalize (CR_b (1#1) x) Hx.
507 clear Hx.
508 intros d Hd.
509 destruct (Qlt_le_dec (proj1_sig c) (proj1_sig d)).
510 apply CRpower_N_bounded_weaken. exact Hc. apply Qlt_le_weak, q.
511 symmetry. apply CRpower_N_bounded_weaken; assumption.
512 Qed.
513
514 Lemma CRpower_N_correct : forall (n:N) x,
515 (CRpower_slow x (N.to_nat n) == CRpower_N x n)%CR.
516 Proof.
517 intros n x.
518 rewrite <- (CRpower_N_bounded_N_power n (CR_b (1#1) x)).
519 apply CRpower_N_bounded_correct.
520 split. apply (CR_b_lowerBound (1#1) x).
521 apply CR_b_upperBound.
522 split. apply (CR_b_lowerBound (1#1) x).
523 apply CR_b_upperBound.
524 Qed.
525
526 Lemma CRpower_N_correct' : forall (n:nat) x,
527 (CRpower_slow x n == CRpower_N x (N_of_nat n))%CR.
528 Proof.
529 intros n x.
530 etransitivity; [| apply CRpower_N_correct].
531 now rewrite Nnat.nat_of_N_of_nat.
532 Qed.
533
534 #[global]
535 Hint Rewrite CRpower_N_correct' : IRtoCR.
536
537 #[global]
538 Instance: Proper (eq ==> QposEq ==> @msp_eq _) Qpower_N_uc.
539 Proof.
540 intros p1 p2 Ep e1 e2 Ee. apply ucEq_equiv.
541 intro x.
542 apply ball_closed.
543 intros e epos.
544 simpl. unfold QposEq in Ee.
545 rewrite Ep, Ee.
546 apply Qball_Reflexive.
547 rewrite Qplus_0_l.
548 apply Qlt_le_weak, epos.
549 Qed.
550
551 #[global]
552 Instance: Proper (eq ==> QposEq ==> @msp_eq _) CRpower_N_bounded.
553 Proof.
554 intros p1 p2 Ep e1 e2 Ee.
555 apply ucEq_equiv.
556 intro x. simpl. rewrite Ep, Ee. reflexivity.
557 Qed.
558
559 #[global]
560 Instance: Proper (@msp_eq _ ==> eq ==> @msp_eq _) CRpower_N.
561 Proof.
562 intros x1 x2 Hx ? n Hn. subst.
563 transitivity (CRpower_N_bounded n (CR_b (1 # 1) x1) x2).
564 change (ucFun (CRpower_N_bounded n (CR_b (1#1) x1)) x1==ucFun (CRpower_N_bounded n (CR_b (1#1) x1)) x2)%CR.
565 apply uc_wd; assumption.
566 apply CRpower_N_bounded_N_power.
567 split; rewrite <- Hx.
568 rewrite -> CRopp_Qopp.
569 apply CR_b_lowerBound.
570 apply CR_b_upperBound.
571 Qed.
572 (* end hide *)
573
574 #[global]
575 Instance: NatPowSpec CR N _.
576 Proof.
577 split; unfold pow.
578 apply _.
579 intros x. change (cast Q CR 1 = CR1). now apply rings.preserves_1.
580 intros x n.
581 rewrite <- CRpower_N_correct.
582 rewrite Nnat.nat_of_Nplus.
583 simpl.
584 rewrite CRpower_N_correct. reflexivity.
585 Qed.