Debian Codegraph @

reals/fast/CRFieldOps.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
23 Require Import CoRN.metric2.Metric.
24 Require Import CoRN.metric2.UniformContinuity.
25 Require Import CoRN.model.totalorder.QposMinMax.
26 Require Export CoRN.model.lattice.CRlattice.
27 Require Import CoRN.model.totalorder.QMinMax.
28 From Coq Require Import Qabs.
29 Require Import CoRN.model.metric2.Qmetric.
30 Require Import CoRN.metric2.ProductMetric.
31 Require Import MathClasses.interfaces.canonical_names.
32
33 (* Backwards compatibility for Hint Rewrite locality attributes *)
34 Set Warnings "-unsupported-attributes".
35
36 Set Implicit Arguments.
37
38 Local Open Scope Q_scope.
39 Local Open Scope uc_scope.
40 Opaque Qmin Qmax Qred.
41
42 (**
43 ** Strict Inequality
44 First we defined positivity. We define positivity to contain a
45 positive rational witness of a lower bound on x. This seems the best
46 way because this witness contains exactly the information needed
47 for functions (such as inverse and logorithm) that have domains
48 restricted to the positive reals.
49 *)
50 Definition CRpos (x:CR) := sig (fun e:Qpos => ' proj1_sig e <= x)%CR.
51
52 Lemma CRpos_wd : forall x y, (x==y)%CR -> (CRpos x) -> (CRpos y).
53 Proof.
54 intros x y Hxy [e H].
55 exists e.
56 abstract ( rewrite <- Hxy; assumption ).
57 Defined.
58
59 (** This is a characterization closer to Bishop's definiton. If we
60 replace [2*e] with [e], the theorem still holds, but it could be
61 very expensive to call. We prefer to avoid that. *)
62
63 Program Definition CRpos_char (e:Qpos) (x:CR)
64 (H: (2#1)*proj1_sig e <= (approximate x e))
65 : CRpos x := e.
66
67 Next Obligation.
68 change (CRle (inject_Q_CR (proj1_sig e)) x).
69 intros a.
70 simpl.
71 unfold Cap_raw.
72 simpl.
73 apply Qle_trans with (-(1#2)* proj1_sig a).
74 rewrite -> Qle_minus_iff.
75 ring_simplify.
76 apply Qmult_le_0_compat; auto with *.
77 rewrite -> Qle_minus_iff.
78 destruct (regFun_prf x e ((1#2)*a)%Qpos) as [_ X].
79 apply (Qle_trans _ (approximate x ((1 # 2) * a)%Qpos + (1#2)*proj1_sig a
80 + proj1_sig e + - ((2#1)*proj1_sig e))).
81 2: simpl; ring_simplify; apply Qle_refl.
82 rewrite <- Qle_minus_iff; apply Qle_trans with (approximate x e); try assumption; simpl in X.
83 rewrite -> Qle_minus_iff in X; rewrite -> Qle_minus_iff; autorewrite with QposElim in X.
84 apply (Qle_trans _ _ _ X).
85 ring_simplify. apply Qle_refl.
86 Qed.
87
88 (** Negative reals are defined similarly. *)
89 Definition CRneg (x:CR) := sig (fun e:Qpos => x <= ' (-proj1_sig e)%Q)%CR.
90
91 Lemma CRneg_wd : forall x y, (x==y)%CR -> (CRneg x) -> (CRneg y).
92 Proof.
93 intros x y Hxy [e H].
94 exists e.
95 abstract ( rewrite <- Hxy; assumption ).
96 Defined.
97
98 Program Definition CRneg_char (e:Qpos) (x:CR) (H: (approximate x e) <= -(2#1)*e): CRneg x := e.
99
100 Next Obligation.
101 change (x <= '(-proj1_sig e)%Q)%CR.
102 intros a; simpl; unfold Cap_raw; simpl; apply Qle_trans with (-(1#2)*proj1_sig a).
103 rewrite -> Qle_minus_iff; ring_simplify.
104 apply Qmult_le_0_compat; auto with *.
105 rewrite -> Qle_minus_iff.
106 destruct (regFun_prf x e ((1#2)*a)%Qpos) as [X _].
107 apply (Qle_trans _ ( - proj1_sig e + - approximate x ((1 # 2) * a)%Qpos
108 + (1 # 2) * proj1_sig a + approximate x e + - approximate x e)).
109 2: simpl; ring_simplify; apply Qle_refl.
110 rewrite <- Qle_minus_iff.
111 apply Qle_trans with (-(2#1)*proj1_sig e); try assumption.
112 simpl in X. rewrite -> Qle_minus_iff in X.
113 rewrite -> Qle_minus_iff.
114 apply (Qle_trans _ _ _ X).
115 simpl. ring_simplify. apply Qle_refl.
116 Qed.
117
118 (** Strict inequality is defined in terms of positivity. *)
119 Definition CRltT (x y:CR) := CRpos (y-x)%CR.
120
121 Infix "<" := CRltT : CR_scope.
122
123 Lemma CRltT_wd : forall x1 x2, (x1==x2 -> forall y1 y2, y1==y2 -> x1 < y1 -> x2 < y2)%CR.
124 Proof.
125 intros x1 x2 Hx y1 y2 Hy H.
126 refine (CRpos_wd _ _). 2:apply H.
127 abstract ( rewrite <- Hx; rewrite <- Hy; reflexivity ).
128 Defined.
129
130 (**
131 ** Apartness
132 *)
133 Definition CRapartT (x y:CR) := (sum (x < y) (y < x))%CR.
134
135 Notation "x >< y" := (CRapartT x y) (at level 70, no associativity) : CR_scope.
136
137 Lemma CRapartT_wd : forall x1 x2, (x1==x2 -> forall y1 y2, y1==y2 -> x1><y1 -> x2><y2)%CR.
138 Proof.
139 intros x1 x2 Hx y1 y2 Hy [H|H];[left;apply (CRltT_wd Hx Hy)|right;apply (CRltT_wd Hy Hx)];assumption.
140 Defined.
141 (**
142 ** Multiplication
143 The modulus of continuity for multiplication by a constant.
144 *)
145 Definition Qscale_modulus (a:Q) (e:Qpos) : QposInf :=
146 match a with
147 | 0 # _ => QposInfinity
148 | (Zpos an) # ad => Qpos2QposInf ((ad # an) * e)
149 | (Zneg an) # ad => Qpos2QposInf ((ad # an) * e)
150 end.
151
152 Lemma Qscale_modulus_elim : forall (P:QposInf -> Type) (x:Q) (e:Qpos),
153 (x==0 -> P QposInfinity)%Q ->
154 (forall y:Qpos, QAbsSmall (proj1_sig e/proj1_sig y)%Q (x)%Q -> (P y)) ->
155 P (Qscale_modulus x e).
156 Proof.
157 intros P [xn xd] e H1.
158 cut (forall xn:positive, (forall y : Qpos, QAbsSmall (proj1_sig e/proj1_sig y)%Q (Z.pos xn#xd)%Q -> P y) ->
159 P (Qscale_modulus (Z.pos xn # xd) e)).
160 intros H H2.
161 destruct xn as [|xn|xn].
162 apply H1.
163 constructor.
164 apply H.
165 assumption.
166 apply H.
167 intros y Hy.
168 apply H2.
169 change (Zneg xn # xd)%Q with (-(Zpos xn # xd))%Q.
170 apply QAbsSmall_opp, Hy.
171 clear xn H1.
172 intros xn H2.
173 simpl.
174 apply H2.
175 simpl.
176 unfold QAbsSmall.
177 setoid_replace (` e / ((Zpos xd # xn) * ` e)) with (Zpos xn # xd).
178 split. 2: apply Qle_refl.
179 apply (Qplus_le_l _ _ (Zpos xn # xd)). ring_simplify.
180 apply (Qpos_nonneg ((2#1)*(xn#xd))).
181 unfold Qdiv. rewrite Qinv_mult_distr.
182 rewrite <- (Qmult_comm (/ `e)), Qmult_assoc.
183 rewrite Qmult_inv_r, Qmult_1_l. reflexivity.
184 apply Qpos_nonzero.
185 Qed.
186
187 Lemma Qscale_modulus_pos (a e: Qpos): exists P,
188 Qscale_modulus (proj1_sig a) e
189 ≡ Qpos2QposInf (exist (Qlt 0) (/ proj1_sig a * proj1_sig e)%Q P).
190 Proof.
191 revert a.
192 intros [[[] ad] P]; try discriminate.
193 simpl. unfold Qpos_inv, Qpos_mult.
194 eauto.
195 Qed.
196
197 Lemma Qscale_uc_prf (a:Q) :
198 @is_UniformlyContinuousFunction
199 Q_as_MetricSpace Q_as_MetricSpace (fun b:Q => a*b) (Qscale_modulus a).
200 Proof.
201 revert a.
202 intros [[|an|an] ad] e b0 b1 H.
203 - simpl in *.
204 setoid_replace ((0 # ad)) with 0 by constructor.
205 rewrite Qmult_0_l, Qmult_0_l.
206 apply Qball_Reflexive, Qpos_nonneg.
207 - simpl.
208 simpl in *.
209 unfold Qball in *.
210 unfold QAbsSmall.
211 setoid_replace ((Zpos an # ad) * b0 - (Zpos an # ad) * b1)
212 with (b0 * (Zpos an # ad) - b1 * (Zpos an # ad))
213 by (unfold equiv, stdlib_rationals.Q_eq; ring).
214 unfold QAbsSmall in H.
215 setoid_replace ((Zpos ad # an) * ` e)
216 with (` e / (Zpos an # ad)) in H.
217 apply (Qball_Qmult_r e (an#ad)) in H.
218 exact H.
219 rewrite Qmult_comm. apply Qmult_comp; reflexivity.
220 - simpl.
221 setoid_replace ((Z.neg an # ad) * b0)
222 with (-((Z.pos an # ad) * b0)).
223 setoid_replace ((Z.neg an # ad) * b1)
224 with (-((Z.pos an # ad) * b1)).
225 apply Qball_opp.
226 simpl in H.
227 unfold Qball, QAbsSmall.
228 setoid_replace ((Zpos an # ad) * b0 - (Zpos an # ad) * b1)
229 with (b0*(Zpos an#ad)-b1*(Zpos an#ad))
230 by (unfold equiv, stdlib_rationals.Q_eq; ring).
231 setoid_replace ((Zpos ad # an) * ` e)
232 with (` e / (Zpos an # ad)) in H.
233 apply (Qball_Qmult_r e (an#ad)) in H. simpl in H.
234 apply H.
235 rewrite Qmult_comm. apply Qmult_comp; reflexivity.
236 destruct b1, Qnum; reflexivity.
237 destruct b0, Qnum; reflexivity.
238 Qed.
239
240 (** Scaling by a constant is [Qmult] lifted on one parameter. *)
241 Definition Qscale_uc (a:Q_as_MetricSpace) : Q_as_MetricSpace --> Q_as_MetricSpace :=
242 Build_UniformlyContinuousFunction (Qscale_uc_prf a).
243
244 Definition scale (a:Q) : CR --> CR := Cmap QPrelengthSpace (Qscale_uc a).
245
246 #[global]
247 Instance Qscale_uc_Proper: Proper (Qeq ==> @msp_eq _) Qscale_uc.
248 Proof.
249 intros x y E.
250 apply ucEq_equiv.
251 intros q. simpl.
252 apply Qball_0.
253 rewrite E. reflexivity.
254 Qed.
255
256 #[global]
257 Instance scale_Proper: Proper (Qeq ==> @msp_eq (UniformlyContinuousSpace CR CR)) scale.
258 Proof.
259 intros x y E.
260 apply ucEq_equiv.
261 intro z. simpl ucFun. rewrite E.
262 reflexivity.
263 Qed.
264
265 (** [CRboundAbs] clamps a real number between -c and c where c is
266 rational. *)
267 Definition QboundAbs (c:Qpos) : Q_as_MetricSpace --> Q_as_MetricSpace
268 := uc_compose (QboundBelow_uc (-proj1_sig c)) (QboundAbove_uc (proj1_sig c)).
269
270 Definition CRboundAbs (c:Qpos) : CR -> CR
271 := Cmap QPrelengthSpace (QboundAbs c).
272
273 Lemma QboundAbs_absorb: forall (a b:Qpos) (c:Q),
274 proj1_sig a <= proj1_sig b ->
275 QboundAbs b (QboundAbs a c) == QboundAbs a c.
276 Proof.
277 intros a b c H.
278 simpl.
279 rewrite -> Qmin_max_distr_r.
280 setoid_replace (Qmin (proj1_sig b) (-proj1_sig a)) with (-proj1_sig a).
281 rewrite -> Qmax_assoc.
282 rewrite <- Qmin_max_de_morgan.
283 rewrite -> Qmin_assoc.
284 setoid_replace (Qmin (proj1_sig b) (proj1_sig a)) with (proj1_sig a).
285 reflexivity.
286 rewrite <- Qle_min_r.
287 assumption.
288 rewrite <- Qle_min_r.
289 rewrite -> Qle_minus_iff.
290 ring_simplify.
291 destruct a,b. simpl. rewrite <- (Qplus_0_l 0).
292 apply Qplus_le_compat; apply Qlt_le_weak; assumption.
293 Qed.
294
295 (** Properties of CRboundAbs. *)
296 Lemma CRboundAbs_Eq : forall (a:Qpos) (x:CR),
297 ('(-proj1_sig a)%Q <= x -> x <= ' proj1_sig a ->
298 CRboundAbs a x == x)%CR.
299 Proof.
300 intros a x Ha Hb.
301 unfold CRboundAbs.
302 transitivity (uc_compose (Cmap QPrelengthSpace (QboundBelow_uc (-proj1_sig a))) (Cmap QPrelengthSpace (QboundAbove_uc (proj1_sig a))) x).
303 simpl (Cmap QPrelengthSpace (QboundAbs a) x).
304 simpl ((Cmap QPrelengthSpace (QboundBelow_uc (- ` a))
305 ∘ Cmap QPrelengthSpace (QboundAbove_uc (` a))) x).
306 repeat rewrite -> Cmap_fun_correct.
307 apply MonadLaw2.
308 simpl ((Cmap QPrelengthSpace (QboundBelow_uc (- ` a))
309 ∘ Cmap QPrelengthSpace (QboundAbove_uc (` a))) x).
310 change (boundBelow (-proj1_sig a) (boundAbove (proj1_sig a) x) == x)%CR.
311 assert (X:(boundAbove (proj1_sig a) x==x)%CR).
312 rewrite <- CRmin_boundAbove.
313 rewrite <- CRle_min_r.
314 assumption.
315 rewrite -> X.
316 rewrite <- CRmax_boundBelow.
317 rewrite <- CRle_max_r.
318 assumption.
319 Qed.
320
321 Lemma QboundAbs_elim : forall (z:Qpos) (a:Q) (P:Q->Prop),
322 ((proj1_sig z <= a)%Q -> P (proj1_sig z)) ->
323 ((a <= -proj1_sig z)%Q -> P (- proj1_sig z)%Q) ->
324 (QAbsSmall (proj1_sig z) a -> P (a)) ->
325 P (QboundAbs z a).
326 Proof.
327 intros z a P H1 H2 H3.
328 simpl.
329 apply Qmax_case; apply Qmin_case; intros Z0 Z1; try solve [apply H1;assumption|apply H2;assumption].
330 elim (Qle_not_lt _ _ Z1).
331 rewrite -> Qlt_minus_iff.
332 ring_simplify.
333 apply (Qpos_ispos ((2#1)*z)).
334 apply H3.
335 split;assumption.
336 Qed.
337
338 Lemma QboundAbs_abs : forall (z:Qpos) (a:Q),
339 Qabs (QboundAbs z a) == Qmin (Qabs a) (proj1_sig z).
340 Proof.
341 intros. apply QboundAbs_elim.
342 - intros. symmetry. rewrite Qabs_pos, Qabs_pos.
343 apply Qle_min_r, H. apply Qpos_nonneg.
344 apply (Qle_trans _ (`z)). apply Qpos_nonneg. exact H.
345 - intros. symmetry. rewrite Qabs_opp.
346 rewrite (Qabs_pos (`z)). apply Qle_min_r.
347 rewrite Qabs_neg, <- Qopp_involutive.
348 apply Qopp_le_compat, H.
349 apply (Qle_trans _ _ _ H). apply (Qopp_le_compat 0), Qpos_nonneg.
350 apply Qpos_nonneg.
351 - intros. symmetry. apply Qle_min_l.
352 apply AbsSmall_Qabs in H. exact H.
353 Qed.
354
355
356 (** The modulus of continuity for multiplication depends on the
357 bound, c, on the second argument. *)
358 Definition Qmult_modulus (c:Qpos)(e:Qpos) : QposInf
359 := Qpos2QposInf (e * Qpos_inv c).
360
361 Lemma Qmult_uc_prf (c:Qpos)
362 : @is_UniformlyContinuousFunction
363 Q_as_MetricSpace (Q_as_MetricSpace --> Q_as_MetricSpace)
364 (fun a:Q => uc_compose (Qscale_uc a) (QboundAbs c)) (Qmult_modulus c).
365 Proof with simpl in *; auto with *.
366 intros e a0 a1 H. split. apply Qpos_nonneg. intro b.
367 simpl in *.
368 set (b' := Qmax (- proj1_sig c) (Qmin (proj1_sig c) b)).
369 repeat rewrite -> (fun x => Qmult_comm x b').
370 apply Qscale_uc_prf.
371 assert (QposEq (e * Qpos_inv c) (Qpos_inv c*e)%Qpos)
372 by (unfold QposEq; simpl; ring).
373 apply (ball_wd _ H0 _ _ (reflexivity _) _ _ (reflexivity _)) in H. clear H0.
374 apply ball_ex_weak_le with (Qpos_inv c*e)%Qpos;[|assumption].
375 unfold b'.
376 destruct c as [[cn cd] cpos].
377 destruct cn as [|cn|cn]. inversion cpos. 2: inversion cpos.
378 apply Qmax_case. intros. apply Qle_refl. simpl.
379 apply Qmin_case. intros. apply Qle_refl.
380 intros H1 H2.
381 destruct b as [[|bn|bn] bd]...
382 - apply Qmult_le_r. destruct e; exact q.
383 apply Qle_shift_inv_r. reflexivity.
384 rewrite <- Qmult_1_l in H1.
385 apply Qle_shift_div_l in H1.
386 apply (Qle_trans _ _ _ H1). rewrite Qmult_comm.
387 apply Qmult_le_l. reflexivity. apply Z.le_refl. reflexivity.
388 - apply Qmult_le_r. destruct e; exact q.
389 apply Qle_shift_inv_r. reflexivity.
390 apply Qopp_le_compat in H2. rewrite Qopp_involutive in H2.
391 rewrite <- Qmult_1_l in H2.
392 apply Qle_shift_div_l in H2. 2: reflexivity.
393 apply (Qle_trans _ _ _ H2). rewrite Qmult_comm.
394 apply Qmult_le_l. reflexivity. apply Z.le_refl.
395 Qed.
396
397 (* begin hide *)
398 Arguments Qmult_uc_prf : clear implicits.
399 (* end hide *)
400 Definition Qmult_uc (c:Qpos)
401 : Q_as_MetricSpace --> Q_as_MetricSpace --> Q_as_MetricSpace
402 := Build_UniformlyContinuousFunction (Qmult_uc_prf c).
403
404 (** This multiplication function is correct when yBound is a bound
405 on the absolute value of the second CR argument. *)
406 Definition CRmult_bounded (yBound : Qpos) : CR --> CR --> CR
407 := Cmap2 QPrelengthSpace QPrelengthSpace (Qmult_uc yBound).
408
409 #[global]
410 Instance: Proper (QposEq ==> @msp_eq _) Qmult_uc.
411 Proof.
412 intros e1 e2 E.
413 simpl. split. discriminate.
414 intro a. simpl. split. discriminate.
415 intro b. simpl.
416 apply Qball_0.
417 unfold QposEq in E. rewrite E.
418 reflexivity.
419 Qed.
420
421 #[global]
422 Instance CRmult_bounded_wd : Proper (QposEq ==> @msp_eq _) CRmult_bounded.
423 Proof.
424 intros e1 e2 E.
425 simpl. split. discriminate.
426 intro x1. split. discriminate.
427 intro x2.
428 simpl (CRmult_bounded e1 x1 x2).
429 simpl (CRmult_bounded e2 x1 x2).
430 rewrite E. reflexivity.
431 Qed.
432
433 (** CR_b computes a rational bound on the absolute value of x *)
434
435 Lemma CR_b_pos (e : Qpos) (x : CR) : 0 < Qabs (approximate x e) + proj1_sig e.
436 Proof.
437 apply (Qle_lt_trans _ (Qabs (approximate x e) + 0)).
438 rewrite Qplus_0_r. apply Qabs_nonneg.
439 apply Qplus_lt_r, Qpos_ispos.
440 Qed.
441
442 Definition CR_b (e:Qpos) (x:CR) : Qpos
443 := exist (Qlt 0) (Qabs (approximate x e) + proj1_sig e)
444 (CR_b_pos _ _).
445
446 Lemma CR_b_lowerBound : forall e x, (' (-proj1_sig (CR_b e x))%Q <= x)%CR.
447 Proof.
448 intros e x e'.
449 unfold CR_b.
450 simpl.
451 unfold Cap_raw.
452 simpl.
453 rewrite -> Qle_minus_iff, Qopp_involutive, Qopp_involutive.
454 destruct (regFun_prf x ((1#2)*e')%Qpos e) as [H _].
455 simpl in H.
456 rewrite -> Qle_minus_iff in H.
457 ring_simplify in H.
458 apply (Qle_trans _ _ _ H).
459 rewrite -> Qle_minus_iff.
460 ring_simplify.
461 clear H.
462 apply Qabs_case; intros H.
463 apply (Qle_trans _ (approximate x e + 0)).
464 rewrite Qplus_0_r. exact H. rewrite <- Qplus_assoc.
465 apply Qplus_le_r.
466 apply (Qle_trans _ (0+approximate x e)).
467 rewrite Qplus_0_l. exact H.
468 apply Qplus_le_l. apply (Qpos_nonneg ((1#2)*e')).
469 ring_simplify. apply (Qpos_nonneg ((1#2)*e')).
470 Qed.
471
472 Lemma CR_b_upperBound : forall e x, (x <= 'proj1_sig (CR_b e x))%CR.
473 Proof.
474 intros e x e'.
475 unfold CR_b.
476 simpl.
477 unfold Cap_raw.
478 simpl.
479 rewrite -> Qle_minus_iff.
480 ring_simplify.
481 destruct (regFun_prf x ((1#2)*e')%Qpos e) as [_ H].
482 simpl in H.
483 rewrite -> Qle_minus_iff in H.
484 ring_simplify in H.
485 eapply Qle_trans.
486 apply H.
487 rewrite -> Qle_minus_iff.
488 ring_simplify.
489 clear H.
490 apply Qabs_case; intros H.
491 ring_simplify. apply (Qpos_nonneg ((1#2)*e')).
492 apply (Qplus_le_r _ _ ((2#1)*approximate x e)).
493 simpl. ring_simplify.
494 apply (Qle_trans _ 0).
495 rewrite <- (Qmult_0_r (2#1)). apply Qmult_le_l.
496 reflexivity. exact H. apply (Qpos_nonneg ((1#2)*e')).
497 Qed.
498
499 (** This version of multiply computes a bound on the second argument
500 just in time. It should be avoided in favour of the bounded version
501 whenever possible. *)
502 #[global]
503 Instance CRmult: Mult CR := λ x y, ucFun2 (CRmult_bounded (CR_b (1#1) y)) x y.
504
505 Infix "*" := CRmult : CR_scope.
506
507 Lemma CRmult_bounded_weaken : forall (c1 c2:Qpos) x y,
508 ((' (-proj1_sig c1)%Q <= y) -> (y <= ' proj1_sig c1)
509 -> (proj1_sig c1 <= proj1_sig c2)%Q ->
510 CRmult_bounded c1 x y == CRmult_bounded c2 x y)%CR.
511 Proof.
512 intros c1 c2 x y Hc1a Hc1b Hc2.
513 assert (Hy:=CRboundAbs_Eq _ Hc1a Hc1b).
514 set (y':= (CRboundAbs c1 y)) in *.
515 transitivity (ucFun2 (CRmult_bounded c2) x y'); [|rewrite -> Hy;reflexivity].
516 assert (H:forall x:Qpos, proj1_sig (x*c1*Qpos_inv c2)%Qpos <= proj1_sig x).
517 { intros a.
518 simpl.
519 rewrite <- (Qmult_1_r (`a)), <- Qmult_assoc, <- Qmult_assoc.
520 apply Qmult_le_l. destruct a; exact q.
521 rewrite Qmult_1_l. apply Qle_shift_div_r.
522 destruct c2; exact q. rewrite Qmult_1_l. exact Hc2. }
523 change (ucFun2 (CRmult_bounded c1) x y == ucFun2 (CRmult_bounded c2) x y')%CR.
524 rewrite <- (QreduceApprox_Eq x).
525 set (x''':=(QreduceApprox x)).
526 set (x':=faster x''' (fun x => (x * c1 * Qpos_inv c2)%Qpos) H).
527 transitivity (ucFun2 (CRmult_bounded c1) x' y).
528 unfold x'.
529 rewrite -> fasterIsEq.
530 reflexivity.
531 apply regFunEq_equiv, regFunEq_e; intros e.
532 intros.
533 simpl.
534 do 3 (unfold Cap_raw; simpl).
535 assert (X:=fun c => QboundAbs_absorb _ _ c Hc2).
536 unfold QboundAbs in X.
537 simpl in X.
538 rewrite -> X.
539 clear X.
540 assert (eq (Qpos_red ((1 # 2) * e * Qpos_inv c1 * c1 * Qpos_inv c2))
541 (Qpos_red ((1 # 2) * e * Qpos_inv c2))).
542 { apply Qpos_red_eq. unfold QposEq. simpl. field.
543 split. intro abs. destruct c2. simpl in abs.
544 apply (Qlt_not_le _ _ q). rewrite abs. apply Qle_refl.
545 intro abs. destruct c1. simpl in abs.
546 apply (Qlt_not_le _ _ q). rewrite abs. apply Qle_refl. }
547 simpl. simpl in H0. rewrite H0.
548 do 2 rewrite QposInf_bind_id. apply Qball_Reflexive.
549 apply (Qpos_nonneg (e+e)).
550 Qed.
551
552 Lemma CRmult_bounded_mult : forall (c:Qpos) (x y:CR),
553 (' (-proj1_sig c)%Q <= y -> y <= ' proj1_sig c ->
554 CRmult_bounded c x y == x*y)%CR.
555 Proof.
556 intros c x y Hc1 Hc2.
557 unfold CRmult.
558 set (d:=(CR_b (1 # 1) y)).
559 destruct (Qle_total (proj1_sig c) (proj1_sig d)).
560 apply CRmult_bounded_weaken; assumption.
561 symmetry.
562 apply CRmult_bounded_weaken; try assumption.
563 apply CR_b_lowerBound.
564 apply CR_b_upperBound.
565 Qed.
566 (* begin hide *)
567 Add Morphism CRmult with signature (@msp_eq _) ==> (@msp_eq _) ==> (@msp_eq _)
568 as CRmult_wd.
569 Proof.
570 intros x1 x2 Hx y1 y2 Hy.
571 unfold CRmult.
572 set (c:=(CR_b (1 # 1) y1)).
573 set (d:=(CR_b (1 # 1) y2)).
574 rewrite -> Hx.
575 rewrite -> Hy.
576 unfold d.
577 apply CRmult_bounded_mult; rewrite <- Hy.
578 apply CR_b_lowerBound.
579 apply CR_b_upperBound.
580 Qed.
581 (* end hide *)
582 Lemma CRmult_scale : forall (a:Q) (y:CR), ((' a)*y==scale a y)%CR.
583 Proof.
584 intros a y.
585 unfold CRmult.
586 unfold CRmult_bounded.
587 unfold ucFun2.
588 unfold Cmap2.
589 unfold inject_Q_CR.
590 change (msp_eq
591 (Cap_fun QPrelengthSpace
592 (Cmap_fun QPrelengthSpace (Qmult_uc (CR_b (1 ↾ eq_refl) y))
593 (Cunit_fun Q_as_MetricSpace a)) y)
594 (Cmap_fun QPrelengthSpace (Qscale_uc a) y)).
595 rewrite -> Cap_fun_correct.
596 repeat rewrite -> Cmap_fun_correct.
597 rewrite -> MonadLaw3.
598 rewrite -> StrongMonadLaw1.
599 change (msp_eq (Cmap_slow_fun (Qscale_uc a ∘ QboundAbs (CR_b (1 ↾ eq_refl) y)) y)
600 (Cmap_slow_fun (Qscale_uc a) y)).
601 transitivity (uc_compose (Cmap QPrelengthSpace (Qscale_uc a))
602 (Cmap QPrelengthSpace (QboundAbs (CR_b (1#1) y))) y).
603 simpl ((Cmap QPrelengthSpace (Qscale_uc a)
604 ∘ Cmap QPrelengthSpace (QboundAbs (CR_b (1 ↾ eq_refl) y))) y).
605 repeat rewrite -> Cmap_fun_correct.
606 apply MonadLaw2.
607 simpl ((Cmap QPrelengthSpace (Qscale_uc a)
608 ∘ Cmap QPrelengthSpace (QboundAbs (CR_b (1 ↾ eq_refl) y))) y).
609 repeat rewrite -> Cmap_fun_correct.
610 change (Cmap_slow (Qscale_uc a) (Cmap_slow_fun (QboundAbs (CR_b (1 # 1) y)) y) ==
611 Cmap_slow (Qscale_uc a) y)%CR.
612 apply uc_wd.
613 rewrite <- (Cmap_fun_correct (Y:=Q_as_MetricSpace) QPrelengthSpace).
614 apply CRboundAbs_Eq.
615 apply CR_b_lowerBound.
616 apply CR_b_upperBound.
617 Qed.
618 (* begin hide *)
619 #[global]
620 Hint Rewrite CRmult_scale : CRfast_compute.
621 (* end hide *)
622 Lemma scale_Qmult : forall a b:Q, (scale a ('b)=='(a*b)%Q)%CR.
623 Proof.
624 intros a b.
625 unfold scale.
626 change (msp_eq (Cmap_fun QPrelengthSpace (Qscale_uc a) (' b)%CR) (' (a * b)%Q)%CR).
627 rewrite -> Cmap_fun_correct.
628 apply MonadLaw3.
629 Qed.
630 (* begin hide *)
631 #[global]
632 Hint Rewrite scale_Qmult : CRfast_compute.
633 (* end hide *)
634 (**
635 ** Inverse
636 The modulus of continuity for inverse depends on a rational bound
637 away from 0 of x. *)
638 Definition Qinv_modulus (c:Qpos) (e:Qpos) : Qpos := (c*c*e)%Qpos.
639
640 Lemma Qpos_Qmax : forall (a:Qpos) (b:Q), 0<Qmax (proj1_sig a) b.
641 Proof.
642 intros a b.
643 apply Qmax_case; intros H.
644 destruct a; exact q.
645 apply Qlt_le_trans with (proj1_sig a).
646 destruct a; exact q.
647 assumption.
648 Qed.
649
650 Lemma Qinv_pos_uc_prf (c:Qpos) :
651 @is_UniformlyContinuousFunction
652 Q_as_MetricSpace Q_as_MetricSpace
653 (fun a:Q => /(Qmax (proj1_sig c) a) ) (Qinv_modulus c).
654 Proof.
655 intros e a0 a1 Ha.
656 simpl in *.
657 unfold Qball in *.
658 assert (forall (a:Qpos) (b:Q), 0 < Qmax (`a) b) as max_pos.
659 { intros. apply (Qlt_le_trans _ (`a)).
660 destruct a; exact q. apply Qmax_ub_l. }
661 assert ( 0 < Qmax (` c) a0 * Qmax (` c) a1).
662 { apply (Qle_lt_trans _ (Qmax (`c) a0 * 0)).
663 rewrite Qmult_0_r. apply Qle_refl.
664 apply Qmult_lt_l. apply max_pos. apply max_pos. }
665 apply AbsSmall_Qabs.
666 setoid_replace (/ Qmax (` c) a0 - / Qmax (` c) a1)
667 with ((Qmax (` c) a1 - Qmax (` c) a0) / (Qmax (` c) a0 * Qmax (` c) a1)).
668 2: unfold equiv, stdlib_rationals.Q_eq; field.
669 unfold Qdiv. rewrite Qabs_Qmult.
670 rewrite (Qabs_pos (/ ( Qmax (` c) a0 * Qmax (` c) a1))).
671 2: apply Qlt_le_weak, Qinv_lt_0_compat, H.
672 apply Qle_shift_div_r. exact H.
673 apply (Qle_trans _ _ _ (Qmax_contract _ _ _)).
674 apply AbsSmall_Qabs in Ha. rewrite Qabs_Qminus.
675 apply (Qle_trans _ _ _ Ha).
676 rewrite (Qmult_comm (`e)). apply Qmult_le_r.
677 apply Qpos_ispos.
678 apply (Qle_trans _ (`c * Qmax (`c) a1)).
679 apply Qmult_le_l. apply Qpos_ispos. apply Qmax_ub_l.
680 apply Qmult_le_r. apply max_pos. apply Qmax_ub_l.
681 split; intro abs. specialize (max_pos c a1).
682 rewrite abs in max_pos. exact (Qlt_irrefl 0 max_pos).
683 specialize (max_pos c a0).
684 rewrite abs in max_pos. exact (Qlt_irrefl 0 max_pos).
685 Qed.
686
687 Arguments Qinv_pos_uc_prf : clear implicits.
688
689 Definition Qinv_pos_uc (c:Qpos) : Q_as_MetricSpace --> Q_as_MetricSpace :=
690 Build_UniformlyContinuousFunction (Qinv_pos_uc_prf c).
691
692 Lemma Qinv_pos_uc_wd : forall (c1 c2:Qpos),
693 (proj1_sig c1 <= proj1_sig c2)
694 -> forall x, (proj1_sig c2 <= x) -> msp_eq (Qinv_pos_uc c1 x) (Qinv_pos_uc c2 x).
695 Proof.
696 intros c1 c2 Hc x Hx.
697 simpl.
698 setoid_replace (Qmax (proj1_sig c2) x) with x by (rewrite <- Qle_max_r; assumption).
699 setoid_replace (Qmax (proj1_sig c1) x) with x.
700 apply Qball_Reflexive. discriminate.
701 rewrite <- Qle_max_r.
702 apply Qle_trans with (proj1_sig c2); assumption.
703 Qed.
704
705 (** [CRinv_pos] works for inputs greater than c *)
706 Definition CRinv_pos (c:Qpos) : CR --> CR := (Cmap QPrelengthSpace (Qinv_pos_uc c)).
707
708 Lemma CRinv_pos_weaken : forall (c1 c2:Qpos),
709 proj1_sig c1 <= proj1_sig c2
710 -> forall (x:CR), (' proj1_sig c2 <= x -> CRinv_pos c1 x == CRinv_pos c2 x)%CR.
711 Proof.
712 intros c1 c2 Hc x Hx.
713 assert (X:((boundBelow (proj1_sig c2) x)==x)%CR).
714 rewrite <- CRmax_boundBelow.
715 rewrite <- CRle_max_r.
716 assumption.
717 rewrite <- X.
718 rewrite <- (QreduceApprox_Eq x).
719 pose (f:=(fun e:Qpos => (c1*c1*Qpos_inv c2*Qpos_inv c2)*e)%Qpos).
720 assert (Y:forall e:Qpos, proj1_sig (f e) <= proj1_sig e).
721 { intros e.
722 unfold f. simpl.
723 rewrite <- (Qmult_1_l (`e)) at 2.
724 apply Qmult_le_r. apply Qpos_ispos.
725 apply Qle_shift_div_r. apply Qpos_ispos.
726 apply Qle_shift_div_r. apply Qpos_ispos.
727 rewrite Qmult_1_l.
728 apply (Qle_trans _ (`c1*`c2)).
729 apply Qmult_le_l. apply Qpos_ispos. exact Hc.
730 apply Qmult_le_r. apply Qpos_ispos. exact Hc. }
731 transitivity (CRinv_pos c2 (boundBelow (proj1_sig c2) (faster (QreduceApprox x) f Y))).
732 apply regFunEq_equiv, regFunEq_e.
733 intros e.
734 assert (Z:=Qinv_pos_uc_wd _ _ Hc).
735 simpl in Z.
736 simpl.
737 rewrite -> Z;[|apply Qmax_ub_l].
738 unfold Qinv_modulus.
739 replace (Qpos_red (c1 * c1 * e)) with (Qpos_red (f (c2 * c2 * e)%Qpos)); [apply ball_refl|].
740 apply (Qpos_nonneg (e+e)).
741 apply Qpos_red_eq.
742 unfold f.
743 unfold QposEq.
744 simpl.
745 field.
746 apply Qpos_nonzero.
747 rewrite -> fasterIsEq.
748 reflexivity.
749 Qed.
750
751 #[global]
752 Instance CRinv_pos_uc_Proper : Proper (QposEq ==> @msp_eq _ ==> @msp_eq _) Qinv_pos_uc.
753 Proof.
754 intros [c1 ?] [c2 ?] E x1 x2 F. unfold QposEq in E. simpl in *.
755 apply Qball_0. apply Qball_0 in F.
756 rewrite E, F. reflexivity.
757 Qed.
758
759 #[global]
760 Instance: Proper (QposEq ==> @msp_eq _) CRinv_pos.
761 Proof.
762 intros c1 c2 E.
763 apply ucEq_equiv. intro x.
764 simpl (CRinv_pos c1 x).
765 simpl (CRinv_pos c2 x).
766 setoid_replace (Qinv_pos_uc c1) with (Qinv_pos_uc c2).
767 easy.
768 apply ucEq_equiv.
769 intros y. now apply CRinv_pos_uc_Proper.
770 Qed.
771
772 Lemma CRinv_pos_Qinv : forall (c:Qpos) x,
773 (proj1_sig c <= x)%Q -> (CRinv_pos c (' x) == (' (/x)))%CR.
774 Proof.
775 intros c x H.
776 apply regFunEq_equiv, regFunEq_e.
777 intros e.
778 simpl.
779 setoid_replace (Qmax (proj1_sig c) x) with x.
780 apply Qball_Reflexive.
781 apply (Qpos_nonneg (e+e)).
782 rewrite <- Qle_max_r.
783 assumption.
784 Qed.
785
786 (** [CRinvT] works for inputs apart from 0 *)
787 Definition CRinvT (x:CR)(x_: (x >< 0)%CR) : CR.
788 Proof.
789 revert x_.
790 intros [[c H]|[c H]].
791 exact ((-(CRinv_pos c (-x)))%CR).
792 exact (CRinv_pos c x).
793 Defined.
794
795 Arguments CRinvT : clear implicits.
796
797 Lemma CRinvT_pos_inv : forall (c:Qpos) (x:CR) x_,
798 ('proj1_sig c <= x ->
799 CRinv_pos c x == CRinvT x x_)%CR.
800 Proof.
801 intros c x [[e He]|[e He]] H.
802 assert (X:(' proj1_sig e <= -x)%CR).
803 rewrite <- (doubleSpeed_Eq x).
804 intros d.
805 eapply Qle_trans.
806 apply He.
807 simpl.
808 do 2 (unfold Cap_raw;simpl).
809 ring_simplify.
810 apply Qle_refl.
811 assert (' proj1_sig c <= ' (- proj1_sig e)%Q)%CR.
812 eapply CRle_trans.
813 apply H.
814 intros d.
815 eapply Qle_trans.
816 apply X.
817 simpl.
818 do 2 (unfold Cap_raw;simpl).
819 rewrite -> Qle_minus_iff.
820 ring_simplify.
821 apply Qle_refl.
822 assert (0 < proj1_sig c) as cpos.
823 { destruct c; exact q. }
824 elim (Qlt_not_le _ _ cpos).
825 assert (Y:=H0 (e)%Qpos).
826 simpl in Y.
827 do 2 (unfold Cap_raw in Y ;simpl in Y).
828 rewrite -> Qle_minus_iff in Y.
829 ring_simplify in Y.
830 rewrite -> Qle_minus_iff.
831 ring_simplify;assumption.
832 assert (' proj1_sig e <= x)%CR.
833 rewrite <- (doubleSpeed_Eq x).
834 intros d.
835 eapply Qle_trans.
836 apply He.
837 simpl.
838 do 2 (unfold Cap_raw;simpl).
839 ring_simplify.
840 apply Qle_refl.
841 destruct (Qle_total (proj1_sig c) (proj1_sig e));
842 [|symmetry]; apply CRinv_pos_weaken; assumption.
843 Qed.
844
845 Lemma CRinvT_wd : forall (x y:CR) x_ y_, (x == y -> CRinvT x x_ == CRinvT y y_)%CR.
846 Proof.
847 assert (X:forall x, (0 + x == x)%CR).
848 intros x.
849 transitivity (doubleSpeed x);[|apply doubleSpeed_Eq].
850 apply regFunEq_equiv, regFunEq_e.
851 intros e.
852 simpl.
853 unfold Cap_raw; simpl.
854 rewrite Qplus_0_l.
855 apply Qball_Reflexive. apply (Qpos_nonneg (e+e)).
856 assert (Y:forall x, (x + - 0 == x)%CR).
857 intros x.
858 transitivity (doubleSpeed x);[|apply doubleSpeed_Eq].
859 apply regFunEq_equiv, regFunEq_e.
860 intros e.
861 simpl.
862 unfold Cap_raw; simpl.
863 rewrite Qplus_0_r.
864 apply Qball_Reflexive. apply (Qpos_nonneg (e+e)).
865 intros x y [[c x_]|[c x_]] [[d y_]|[d y_]] H.
866 change (-(CRinv_pos c (-x))== (-(CRinv_pos d (-y))))%CR.
867 rewrite -> H in *.
868 rewrite -> X in *. intros.
869 apply CRopp_wd.
870 destruct (Qle_total (proj1_sig c) (proj1_sig d));
871 [|symmetry]; apply CRinv_pos_weaken; try assumption.
872 assert (0 < proj1_sig c) as cpos.
873 { destruct c; exact q. }
874 elim (Qlt_not_le _ _ cpos).
875 rewrite -> X in *.
876 rewrite -> Y in *.
877 rewrite -> H in *.
878 assert (Z:=Qplus_le_compat _ _ _ _ (x_ ((1#2)*d)%Qpos) (y_ ((1#2)*d)%Qpos)).
879 simpl in Z.
880 unfold Cap_raw in Z; simpl in Z.
881 autorewrite with QposElim in Z.
882 rewrite -> Qle_minus_iff in Z.
883 ring_simplify in Z.
884 rewrite -> Qle_minus_iff.
885 ring_simplify.
886 assumption.
887 assert (0 < proj1_sig c) as cpos.
888 { destruct c; exact q. }
889 elim (Qlt_not_le _ _ cpos).
890 rewrite -> X in *.
891 rewrite -> Y in *.
892 rewrite -> H in *.
893 assert (Z:=Qplus_le_compat _ _ _ _ (x_ ((1#2)*d)%Qpos) (y_ ((1#2)*d)%Qpos)).
894 simpl in Z.
895 unfold Cap_raw in Z; simpl in Z.
896 autorewrite with QposElim in Z.
897 rewrite -> Qle_minus_iff in Z.
898 ring_simplify in Z.
899 rewrite -> Qle_minus_iff.
900 ring_simplify.
901 assumption.
902 change (CRinv_pos c x== (CRinv_pos d y))%CR.
903 rewrite -> H in *.
904 rewrite -> Y in *.
905 destruct (Qle_total (proj1_sig c) (proj1_sig d));
906 [|symmetry]; apply CRinv_pos_weaken; try assumption.
907 Qed.
908
909 Lemma CRinvT_irrelevant : forall x x_ x__, (CRinvT x x_ == CRinvT x x__)%CR.
910 Proof.
911 intros.
912 apply CRinvT_wd.
913 reflexivity.
914 Qed.
915
916 (* Non-curried equivalent version of multiplication. *)
917
918 Lemma QboundAbs_contract : forall (c : Qpos) (j k : Q),
919 Qabs (QboundAbs c j - QboundAbs c k) <= Qabs (j-k).
920 Proof.
921 intros. apply QboundAbs_elim.
922 - intros. apply QboundAbs_elim.
923 + intros. unfold Qminus. rewrite Qplus_opp_r. apply Qabs_nonneg.
924 + intros. unfold Qminus. rewrite Qopp_involutive.
925 rewrite Qabs_pos, Qabs_pos.
926 apply Qplus_le_compat. exact H.
927 rewrite <- Qopp_involutive. apply Qopp_le_compat. exact H0.
928 apply (Qle_trans _ (`c + `c)).
929 apply (Qpos_nonneg (c+c)).
930 apply Qplus_le_compat. exact H.
931 rewrite <- Qopp_involutive. apply Qopp_le_compat. exact H0.
932 apply (Qpos_nonneg (c+c)).
933 + intros [H0 H1]. rewrite Qabs_pos.
934 2: unfold Qminus; rewrite <- Qle_minus_iff; exact H1.
935 apply (Qle_trans _ (j-k)).
936 apply Qplus_le_l. exact H. apply Qle_Qabs.
937 - intros. apply QboundAbs_elim.
938 + intros.
939 setoid_replace (- `c - `c) with (-(`c+`c))
940 by (unfold equiv, stdlib_rationals.Q_eq; ring).
941 rewrite Qabs_opp.
942 rewrite Qabs_pos. 2: apply (Qpos_nonneg (c+c)).
943 rewrite Qabs_Qminus. rewrite Qabs_pos.
944 apply Qplus_le_compat. exact H0.
945 rewrite <- Qopp_involutive. apply Qopp_le_compat. exact H.
946 apply (Qle_trans _ (`c + `c)).
947 apply (Qpos_nonneg (c+c)).
948 apply Qplus_le_compat. exact H0.
949 rewrite <- Qopp_involutive. apply Qopp_le_compat. exact H.
950 + intros. unfold Qminus.
951 rewrite Qopp_involutive, Qplus_comm, Qplus_opp_r.
952 apply Qabs_nonneg.
953 + intros [H0 H1].
954 setoid_replace (- `c - k) with (-(`c+k))
955 by (unfold equiv, stdlib_rationals.Q_eq; ring).
956 rewrite Qabs_opp. rewrite Qabs_pos, Qabs_Qminus.
957 apply (Qle_trans _ (k-j)).
958 rewrite Qplus_comm.
959 apply Qplus_le_r. rewrite <- Qopp_involutive.
960 apply Qopp_le_compat. exact H. apply Qle_Qabs.
961 apply (Qplus_le_l _ _ (-`c)). ring_simplify.
962 ring_simplify in H0. exact H0.
963 - intros [H0 H1]. apply QboundAbs_elim.
964 + intros. rewrite Qabs_Qminus, Qabs_pos.
965 rewrite Qabs_Qminus, Qabs_pos. apply Qplus_le_l, H.
966 unfold Qminus. rewrite <- Qle_minus_iff.
967 exact (Qle_trans _ _ _ H1 H). unfold Qminus.
968 rewrite <- Qle_minus_iff. exact H1.
969 + intros. unfold Qminus. rewrite Qopp_involutive, Qabs_pos.
970 apply (Qle_trans _ (j-k)). apply Qplus_le_r.
971 rewrite <- Qopp_involutive. apply Qopp_le_compat. exact H.
972 apply Qle_Qabs. apply (Qplus_le_l _ _ (`c)) in H0.
973 ring_simplify in H0. rewrite Qplus_comm. exact H0.
974 + intros [H2 H3]. apply Qle_refl.
975 Qed.
976
977 Lemma Qmult_uc_uncurry (c:Qpos)
978 : @is_UniformlyContinuousFunction
979 (ProductMS Q_as_MetricSpace Q_as_MetricSpace)
980 Q_as_MetricSpace
981 (fun ab => QboundAbs c (fst ab) * QboundAbs c (snd ab))
982 (fun e => Qmult_modulus c ((1#2)*e)).
983 Proof.
984 assert (forall i j k l : Q, Qabs (i*j-k*l) <= Qabs j * Qabs(i-k) + Qabs(j-l)*Qabs k)%Q
985 as multMaj.
986 { intros.
987 setoid_replace (i*j-k*l)%Q with (j*(i-k)+ (j-l)*k)%Q
988 by (unfold equiv, stdlib_rationals.Q_eq; ring).
989 apply (Qle_trans _ _ _ (Qabs_triangle _ _)).
990 rewrite Qabs_Qmult, Qabs_Qmult. apply Qle_refl. }
991 assert (forall i:Q, Qabs (QboundAbs c i) <= ` c) as bound.
992 { intro i. apply Qabs_Qle_condition. split.
993 apply Qmax_ub_l. apply Qmax_lub.
994 apply (Qle_trans _ 0). apply (Qopp_le_compat 0).
995 apply Qpos_nonneg. apply Qpos_nonneg. apply Qmin_lb_l. }
996 simpl. unfold Qmult_modulus.
997 intros e1 [i j] [k l] [H H0]. simpl.
998 simpl in H, H0.
999 apply AbsSmall_Qabs.
1000 apply AbsSmall_Qabs in H.
1001 apply AbsSmall_Qabs in H0.
1002 apply (Qle_trans _ _ _ (multMaj _ _ _ _)).
1003 apply (Qle_trans _ (`c * (Qabs (QboundAbs c i - QboundAbs c k))
1004 + `c * (Qabs (QboundAbs c j - QboundAbs c l)))).
1005 - apply Qplus_le_compat.
1006 apply Qmult_le_compat_r. 2: apply Qabs_nonneg.
1007 apply bound.
1008 rewrite Qmult_comm. apply Qmult_le_compat_r.
1009 2: apply Qabs_nonneg. apply bound.
1010 - apply (Qle_trans _ ((1#2)*`e1+(1#2)*`e1)).
1011 apply Qplus_le_compat.
1012 apply (Qle_trans _ (`c * Qabs (i-k))).
1013 apply Qmult_le_l. apply Qpos_ispos. apply QboundAbs_contract.
1014 rewrite Qmult_comm.
1015 apply (Qmult_le_r _ _ (/ `c)).
1016 apply Qinv_lt_0_compat, Qpos_ispos.
1017 rewrite <- Qmult_assoc, Qmult_inv_r, Qmult_1_r.
1018 exact H. apply Qpos_nonzero.
1019 apply (Qle_trans _ (`c * Qabs (j-l))).
1020 apply Qmult_le_l. apply Qpos_ispos. apply QboundAbs_contract.
1021 rewrite Qmult_comm.
1022 apply (Qmult_le_r _ _ (/ `c)).
1023 apply Qinv_lt_0_compat, Qpos_ispos.
1024 rewrite <- Qmult_assoc, Qmult_inv_r, Qmult_1_r.
1025 exact H0. apply Qpos_nonzero.
1026 ring_simplify. apply Qle_refl.
1027 Qed.
1028
1029 Definition Qmult_uncurry (c : Qpos)
1030 : (ProductMS Q_as_MetricSpace Q_as_MetricSpace) --> Q_as_MetricSpace
1031 := Build_UniformlyContinuousFunction (@Qmult_uc_uncurry c).
1032
1033 Lemma CRmult_uncurry_eq : forall (c:Qpos) (x y : CR),
1034 (' (-proj1_sig c)%Q <= x)%CR
1035 -> (x <= ' (proj1_sig c)%Q)%CR
1036 -> (CRmult_bounded c x y
1037 == (Cmap (ProductMS_prelength QPrelengthSpace QPrelengthSpace)
1038 (Qmult_uncurry c) (undistrib_Complete (x,y))))%CR.
1039 Proof.
1040 (* Cannot use Cmap2_curry, because CRmult_bounded is not
1041 exactly Qmult_uc_uncurry, the first factor is not bounded. *)
1042 intros.
1043 transitivity (CRmult_bounded c (CRboundAbs c x) y).
1044 apply (ucFun2_wd (CRmult_bounded c) x (CRboundAbs c x)).
1045 symmetry. apply (CRboundAbs_Eq c H H0). reflexivity.
1046 intros e1 e2. rewrite Qplus_0_r. simpl.
1047 unfold Cap_raw; simpl.
1048 assert (forall i, eq (QposInf_bind (λ e : Qpos, e) i) i) as bind_id.
1049 { intro i. destruct i; reflexivity. }
1050 rewrite bind_id. clear bind_id.
1051 assert (forall i j k l : Q, Qabs (i*j-k*l) <= Qabs i * Qabs(j-l) + Qabs(i-k)*Qabs l)%Q
1052 as multMaj.
1053 { intros.
1054 setoid_replace (i*j-k*l)%Q with (i*(j-l)+ (i-k)*l)%Q
1055 by (unfold equiv, stdlib_rationals.Q_eq; ring).
1056 apply (Qle_trans _ _ _ (Qabs_triangle _ _)).
1057 rewrite Qabs_Qmult, Qabs_Qmult. apply Qle_refl. }
1058 apply AbsSmall_Qabs.
1059 apply (Qle_trans _ _ _ (multMaj _ _ _ _)).
1060 apply (Qle_trans _ ((1#2)*`e1 + (1#2)*`e2 +((1#2)*`e1 +(1#2)*`e2))).
1061 2: ring_simplify; apply Qle_refl.
1062 apply Qplus_le_compat.
1063 - apply (Qle_trans
1064 _ ( Qabs
1065 (approximate y
1066 (Qscale_modulus
1067 (QboundAbs c (approximate x (Qmult_modulus c ((1 # 2) * e1))))
1068 ((1 # 2) * e1)) -
1069 (approximate y (Qmult_modulus c ((1 # 2) * e2))))
1070 * Qabs (QboundAbs c (approximate x (Qmult_modulus c ((1 # 2) * e1)))))).
1071 rewrite Qmult_comm.
1072 apply Qmult_le_compat_r.
1073 apply QboundAbs_contract. apply Qabs_nonneg.
1074 unfold Qscale_modulus.
1075 simpl (Qmult_modulus c ((1 # 2) * e1)).
1076 destruct (QboundAbs c (approximate x (Qmult_modulus c ((1 # 2) ↾ @eq_refl comparison Datatypes.Lt * e1)))) eqn:des.
1077 destruct Qnum.
1078 + setoid_replace (0#Qden) with (0#1) by reflexivity.
1079 rewrite Qmult_0_r. apply (Qpos_nonneg ((1#2)*e1+(1#2)*e2)).
1080 + rewrite Qmult_comm, Qabs_pos. 2: discriminate.
1081 apply (Qle_trans _ ((Zpos p#Qden) *
1082 ((Zpos Qden # p)%Q * ((1 # 2)%Q * `e1)
1083 + (1 # 2) * `e2 / `c))).
1084 apply Qmult_le_l. reflexivity.
1085 pose proof (regFun_prf y ((Zpos Qden # p)%Q ↾ eq_refl * ((1 # 2)%Q ↾ eq_refl * e1))%Qpos
1086 ((1 # 2) * e2 * Qpos_inv c)%Qpos) as H3.
1087 apply AbsSmall_Qabs in H3. exact H3.
1088 rewrite Qmult_plus_distr_r.
1089 rewrite Qmult_assoc.
1090 setoid_replace ((Zpos p # Qden) * (Zpos Qden # p))%Q with (1#1)%Q
1091 by (unfold equiv, stdlib_rationals.Q_eq; unfold Qeq; simpl; rewrite Pos.mul_1_r, Pos.mul_comm; reflexivity).
1092 rewrite Qmult_1_l. apply Qplus_le_r.
1093 unfold Qdiv. rewrite Qmult_assoc.
1094 apply Qle_shift_div_r. apply Qpos_ispos.
1095 rewrite Qmult_comm. apply Qmult_le_l.
1096 apply (Qpos_ispos ((1#2)*e2)).
1097 rewrite <- des. apply Qmax_lub.
1098 apply (Qle_trans _ 0). apply (Qopp_le_compat 0).
1099 apply Qpos_nonneg. apply Qpos_nonneg. apply Qmin_lb_l.
1100 + rewrite Qmult_comm, Qabs_neg. 2: discriminate.
1101 setoid_replace (- (Z.neg p # Qden)) with (Zpos p # Qden) by reflexivity.
1102 apply (Qle_trans _ ((Zpos p#Qden) *
1103 ((Zpos Qden # p)%Q * ((1 # 2)%Q * `e1)
1104 + (1 # 2) * `e2 / `c))).
1105 apply Qmult_le_l. reflexivity.
1106 pose proof (regFun_prf y ((Zpos Qden # p)%Q ↾ eq_refl * ((1 # 2)%Q ↾ eq_refl * e1))%Qpos
1107 ((1 # 2) * e2 * Qpos_inv c)%Qpos) as H3.
1108 apply AbsSmall_Qabs in H3. exact H3.
1109 rewrite Qmult_plus_distr_r.
1110 rewrite Qmult_assoc.
1111 setoid_replace ((Zpos p # Qden) * (Zpos Qden # p))%Q with (1#1)%Q
1112 by (unfold equiv, stdlib_rationals.Q_eq; unfold Qeq; simpl; rewrite Pos.mul_1_r, Pos.mul_comm; reflexivity).
1113 rewrite Qmult_1_l. apply Qplus_le_r.
1114 unfold Qdiv. rewrite Qmult_assoc.
1115 apply Qle_shift_div_r. apply Qpos_ispos.
1116 rewrite Qmult_comm. apply Qmult_le_l.
1117 apply (Qpos_ispos ((1#2)*e2)).
1118 rewrite <- (Qopp_involutive (`c)).
1119 setoid_replace (Zpos p # Qden) with (-(Z.neg p # Qden)) by reflexivity.
1120 apply Qopp_le_compat.
1121 rewrite <- des. apply Qmax_ub_l.
1122 - apply (Qle_trans _ (Qabs
1123 (approximate x (Qmult_modulus c ((1 # 2) * e1)) -
1124 approximate x (Qmult_modulus c ((1 # 2) * e2)))
1125 * Qabs (QboundAbs c (approximate y (Qmult_modulus c ((1 # 2) ↾ eq_refl * e2)))))).
1126 apply Qmult_le_compat_r. 2: apply Qabs_nonneg.
1127 apply QboundAbs_contract.
1128 rewrite QboundAbs_abs.
1129 apply (Qle_trans _ (`c * Qabs
1130 (approximate x (Qmult_modulus c ((1 # 2) * e1)) -
1131 approximate x (Qmult_modulus c ((1 # 2) * e2))))).
1132 rewrite Qmult_comm.
1133 apply Qmult_le_compat_r. 2: apply Qabs_nonneg.
1134 apply Qmin_lb_r.
1135 apply (Qle_trans _ (`c * ((1#2)*`e1 / `c + (1#2)*`e2 / `c))).
1136 apply Qmult_le_l. apply Qpos_ispos.
1137 unfold Qmult_modulus.
1138 pose proof (regFun_prf x ((1 # 2) * e1 * Qpos_inv c)%Qpos
1139 ((1 # 2) * e2 * Qpos_inv c)%Qpos) as H3.
1140 apply AbsSmall_Qabs in H3. exact H3.
1141 rewrite Qmult_plus_distr_r.
1142 apply Qplus_le_compat.
1143 unfold Qdiv. rewrite Qmult_assoc.
1144 apply Qle_shift_div_r. apply Qpos_ispos.
1145 rewrite Qmult_comm. apply Qle_refl.
1146 unfold Qdiv. rewrite Qmult_assoc.
1147 apply Qle_shift_div_r. apply Qpos_ispos.
1148 rewrite Qmult_comm. apply Qle_refl.
1149 Qed.
1150
1151 (* Request bounds on all left factors : x and CRmult_bounded c x y. *)
1152 Lemma CRmult_uncurry_eq_3 : forall (c:Qpos) (x y z : CR),
1153 (' (- ` c)%Q <= x)%CR
1154 -> (x <= 'proj1_sig c)%CR
1155 -> (' (- ` c)%Q <= CRmult_bounded c x y)%CR
1156 -> (CRmult_bounded c x y <= 'proj1_sig c)%CR
1157 -> (CRmult_bounded c (CRmult_bounded c x y) z
1158 == Cmap (ProductMS_prelength
1159 (ProductMS_prelength QPrelengthSpace QPrelengthSpace)
1160 QPrelengthSpace)
1161 (uc_compose (Qmult_uncurry c) (together (Qmult_uncurry c) (uc_id Q_as_MetricSpace)))
1162 (undistrib_Complete (undistrib_Complete (x,y), z)))%CR.
1163 Proof.
1164 intros.
1165 assert (forall a, Qabs (QboundAbs c a) <= `c) as qbound_bound.
1166 { intros a. rewrite QboundAbs_abs. apply Qmin_lb_r. }
1167 rewrite (@CRmult_uncurry_eq c (CRmult_bounded c x y) z); try assumption.
1168 assert (msp_eq (undistrib_Complete (CRmult_bounded c x y, z))
1169 (undistrib_Complete ((Cmap (ProductMS_prelength QPrelengthSpace QPrelengthSpace)
1170 (Qmult_uncurry c) (undistrib_Complete (x,y))), z))) as H4.
1171 { intros e1 e2. split.
1172 apply (@CRmult_uncurry_eq c x y H H0).
1173 rewrite Qplus_0_r.
1174 apply regFun_prf. }
1175 rewrite H4. clear H4.
1176 rewrite fast_MonadLaw2.
1177 apply Cmap_wd. reflexivity.
1178 intros e1 e2. split.
1179 - simpl. apply AbsSmall_Qabs.
1180 assert (forall i j k l : Q, Qabs (i*j-k*l) <= Qabs i * Qabs(j-l) + Qabs(i-k)*Qabs l)%Q
1181 as multMaj.
1182 { intros.
1183 setoid_replace (i*j-k*l)%Q with (i*(j-l)+ (i-k)*l)%Q
1184 by (unfold equiv, stdlib_rationals.Q_eq; ring).
1185 apply (Qle_trans _ _ _ (Qabs_triangle _ _)).
1186 rewrite Qabs_Qmult, Qabs_Qmult. apply Qle_refl. }
1187 apply (Qle_trans _ ((1#2)*`e1 + (1#2)*`e2 +((1#2)*`e1 +(1#2)*`e2))).
1188 2: ring_simplify; apply Qle_refl.
1189 apply (Qle_trans _ _ _ (multMaj _ _ _ _)). clear multMaj.
1190 apply Qplus_le_compat.
1191 + apply (Qle_trans _ (`c *
1192 (Qabs
1193 (Qmax (- ` c)
1194 (Qmin (` c) (approximate y (Qmult_modulus c ((1 # 2) ↾ eq_refl * e1)))) -
1195 Qmax (- ` c)
1196 (Qmin (` c)
1197 (approximate y (Qpos_min ((1 # 2) ↾ eq_refl * e2 * Qpos_inv c) e2))))))).
1198 apply Qmult_le_compat_r. 2: apply Qabs_nonneg.
1199 apply qbound_bound.
1200 rewrite Qmult_comm.
1201 apply (Qle_trans _ (Qabs (approximate y (Qmult_modulus c ((1 # 2) ↾ eq_refl * e1)) - approximate y (Qpos_min ((1 # 2) ↾ eq_refl * e2 * Qpos_inv c) e2)) * `c)).
1202 apply Qmult_le_compat_r. 2: apply Qpos_nonneg.
1203 apply QboundAbs_contract.
1204 apply (Qle_trans _ (((1#2)*`e1 / `c + (1#2)*`e2 / `c) * `c)).
1205 apply Qmult_le_r. apply Qpos_ispos.
1206 unfold Qmult_modulus.
1207 pose proof (regFun_prf y ((1 # 2) * e1 * Qpos_inv c)%Qpos
1208 (Qpos_min ((1 # 2) * e2 * Qpos_inv c)%Qpos e2)) as H4.
1209 apply AbsSmall_Qabs in H4.
1210 apply (Qle_trans _ _ _ H4). clear H4. apply Qplus_le_r.
1211 rewrite Q_Qpos_min. simpl. apply Qmin_lb_l.
1212 rewrite Qmult_plus_distr_l.
1213 apply Qplus_le_compat.
1214 unfold Qdiv. rewrite Qmult_comm, Qmult_assoc.
1215 apply Qle_shift_div_r. apply Qpos_ispos.
1216 rewrite Qmult_comm. apply Qle_refl.
1217 unfold Qdiv. rewrite Qmult_comm, Qmult_assoc.
1218 apply Qle_shift_div_r. apply Qpos_ispos.
1219 rewrite Qmult_comm. apply Qle_refl.
1220 + rewrite Qmult_comm. apply (Qle_trans _ (`c *
1221 (Qabs
1222 (Qmax (- ` c)
1223 (Qmin (` c) (approximate x (Qmult_modulus c ((1 # 2) ↾ eq_refl * e1)))) -
1224 Qmax (- ` c)
1225 (Qmin (` c)
1226 (approximate x (Qpos_min ((1 # 2) ↾ eq_refl * e2 * Qpos_inv c) e2))))))).
1227 apply Qmult_le_compat_r. 2: apply Qabs_nonneg.
1228 apply qbound_bound.
1229 rewrite Qmult_comm.
1230 apply (Qle_trans _ (Qabs (approximate x (Qmult_modulus c ((1 # 2) ↾ eq_refl * e1)) - approximate x (Qpos_min ((1 # 2) ↾ eq_refl * e2 * Qpos_inv c) e2)) * `c)).
1231 apply Qmult_le_compat_r. 2: apply Qpos_nonneg.
1232 apply QboundAbs_contract.
1233 apply (Qle_trans _ (((1#2)*`e1 / `c + (1#2)*`e2 / `c) * `c)).
1234 apply Qmult_le_r. apply Qpos_ispos.
1235 unfold Qmult_modulus.
1236 pose proof (regFun_prf x ((1 # 2) * e1 * Qpos_inv c)%Qpos
1237 (Qpos_min ((1 # 2) * e2 * Qpos_inv c)%Qpos e2)) as H4.
1238 apply AbsSmall_Qabs in H4.
1239 apply (Qle_trans _ _ _ H4). clear H4. apply Qplus_le_r.
1240 rewrite Q_Qpos_min. simpl. apply Qmin_lb_l.
1241 rewrite Qmult_plus_distr_l.
1242 apply Qplus_le_compat.
1243 unfold Qdiv. rewrite Qmult_comm, Qmult_assoc.
1244 apply Qle_shift_div_r. apply Qpos_ispos.
1245 rewrite Qmult_comm. apply Qle_refl.
1246 unfold Qdiv. rewrite Qmult_comm, Qmult_assoc.
1247 apply Qle_shift_div_r. apply Qpos_ispos.
1248 rewrite Qmult_comm. apply Qle_refl.
1249 - simpl.
1250 assert (`e1 + proj1_sig (Qpos_min ((1 # 2) ↾ eq_refl * e2 * Qpos_inv c) e2)
1251 <= `e1 + `e2) as H4.
1252 { apply Qplus_le_r. apply Qpos_min_lb_r. }
1253 rewrite Qplus_0_r.
1254 apply (ball_weak_le _ _ _ H4). apply regFun_prf.
1255 Qed.
1256
1257 (* Request bounds on all left factors : x and y. *)
1258 Lemma CRmult_uncurry_eq_3r : forall (c:Qpos) (x y z : CR),
1259 (' (- ` c)%Q <= x)%CR
1260 -> (x <= 'proj1_sig c)%CR
1261 -> (' (- ` c)%Q <= y)%CR
1262 -> (y <= 'proj1_sig c)%CR
1263 -> (CRmult_bounded c x (CRmult_bounded c y z)
1264 == Cmap (ProductMS_prelength
1265 (ProductMS_prelength QPrelengthSpace QPrelengthSpace)
1266 QPrelengthSpace)
1267 (uc_compose (Qmult_uncurry c)
1268 (uc_compose (together (uc_id Q_as_MetricSpace) (Qmult_uncurry c)) (uc_assoc _ _ _)))
1269 (undistrib_Complete (undistrib_Complete (x,y), z)))%CR.
1270 Proof.
1271 intros.
1272 assert (forall a, Qabs (QboundAbs c a) <= `c) as qbound_bound.
1273 { intros a. rewrite QboundAbs_abs. apply Qmin_lb_r. }
1274 rewrite (@CRmult_uncurry_eq c x (CRmult_bounded c y z)); try assumption.
1275 assert (msp_eq (undistrib_Complete (x, CRmult_bounded c y z))
1276 (undistrib_Complete
1277 (x, Cmap (ProductMS_prelength QPrelengthSpace QPrelengthSpace)
1278 (Qmult_uncurry c) (undistrib_Complete (y,z))))) as H4.
1279 { intros e1 e2. split.
1280 rewrite Qplus_0_r.
1281 apply regFun_prf.
1282 apply (@CRmult_uncurry_eq c y z H1 H2). }
1283 rewrite H4. clear H4.
1284 rewrite fast_MonadLaw2.
1285 apply Cmap_wd. reflexivity.
1286 intros e1 e2. rewrite Qplus_0_r. split.
1287 - simpl.
1288 assert (`e1 + proj1_sig (Qpos_min e2 ((1 # 2) ↾ eq_refl * e2 * Qpos_inv c))
1289 <= `e1 + `e2) as H4.
1290 { apply Qplus_le_r. apply Qpos_min_lb_l. }
1291 apply (ball_weak_le _ _ _ H4). apply regFun_prf.
1292 - simpl. apply AbsSmall_Qabs.
1293 assert (forall i j k l : Q, Qabs (i*j-k*l) <= Qabs i * Qabs(j-l) + Qabs(i-k)*Qabs l)%Q
1294 as multMaj.
1295 { intros.
1296 setoid_replace (i*j-k*l)%Q with (i*(j-l)+ (i-k)*l)%Q
1297 by (unfold equiv, stdlib_rationals.Q_eq; ring).
1298 apply (Qle_trans _ _ _ (Qabs_triangle _ _)).
1299 rewrite Qabs_Qmult, Qabs_Qmult. apply Qle_refl. }
1300 apply (Qle_trans _ ((1#2)*`e1 + (1#2)*`e2 +((1#2)*`e1 +(1#2)*`e2))).
1301 2: ring_simplify; apply Qle_refl.
1302 apply (Qle_trans _ _ _ (multMaj _ _ _ _)). clear multMaj.
1303 apply Qplus_le_compat.
1304 + apply (Qle_trans _ (`c *
1305 (Qabs
1306 (Qmax (- ` c)
1307 (Qmin (` c) (approximate z (Qmult_modulus c ((1 # 2) ↾ eq_refl * e1)))) -
1308 Qmax (- ` c)
1309 (Qmin (` c)
1310 (approximate z (Qpos_min e2 ((1 # 2) ↾ eq_refl * e2 * Qpos_inv c)))))))).
1311 apply Qmult_le_compat_r. 2: apply Qabs_nonneg.
1312 apply qbound_bound.
1313 rewrite Qmult_comm.
1314 apply (Qle_trans _ (Qabs (approximate z (Qmult_modulus c ((1 # 2) ↾ eq_refl * e1)) - approximate z (Qpos_min e2 ((1 # 2) ↾ eq_refl * e2 * Qpos_inv c))) * `c)).
1315 apply Qmult_le_compat_r. 2: apply Qpos_nonneg.
1316 apply QboundAbs_contract.
1317 apply (Qle_trans _ (((1#2)*`e1 / `c + (1#2)*`e2 / `c) * `c)).
1318 apply Qmult_le_r. apply Qpos_ispos.
1319 unfold Qmult_modulus.
1320 pose proof (regFun_prf z ((1 # 2) * e1 * Qpos_inv c)%Qpos
1321 (Qpos_min e2 ((1 # 2) * e2 * Qpos_inv c)%Qpos)) as H4.
1322 apply AbsSmall_Qabs in H4.
1323 apply (Qle_trans _ _ _ H4). clear H4. apply Qplus_le_r.
1324 rewrite Q_Qpos_min. simpl. apply Qmin_lb_r.
1325 rewrite Qmult_plus_distr_l.
1326 apply Qplus_le_compat.
1327 unfold Qdiv. rewrite Qmult_comm, Qmult_assoc.
1328 apply Qle_shift_div_r. apply Qpos_ispos.
1329 rewrite Qmult_comm. apply Qle_refl.
1330 unfold Qdiv. rewrite Qmult_comm, Qmult_assoc.
1331 apply Qle_shift_div_r. apply Qpos_ispos.
1332 rewrite Qmult_comm. apply Qle_refl.
1333 + rewrite Qmult_comm. apply (Qle_trans _ (`c *
1334 (Qabs
1335 (Qmax (- ` c)
1336 (Qmin (` c) (approximate y (Qmult_modulus c ((1 # 2) ↾ eq_refl * e1)))) -
1337 Qmax (- ` c)
1338 (Qmin (` c)
1339 (approximate y (Qpos_min e2 ((1 # 2) ↾ eq_refl * e2 * Qpos_inv c)))))))).
1340 apply Qmult_le_compat_r. 2: apply Qabs_nonneg.
1341 apply qbound_bound.
1342 rewrite Qmult_comm.
1343 apply (Qle_trans _ (Qabs (approximate y (Qmult_modulus c ((1 # 2) ↾ eq_refl * e1)) - approximate y (Qpos_min e2 ((1 # 2) ↾ eq_refl * e2 * Qpos_inv c))) * `c)).
1344 apply Qmult_le_compat_r. 2: apply Qpos_nonneg.
1345 apply QboundAbs_contract.
1346 apply (Qle_trans _ (((1#2)*`e1 / `c + (1#2)*`e2 / `c) * `c)).
1347 apply Qmult_le_r. apply Qpos_ispos.
1348 unfold Qmult_modulus.
1349 pose proof (regFun_prf y ((1 # 2) * e1 * Qpos_inv c)%Qpos
1350 (Qpos_min e2 ((1 # 2) * e2 * Qpos_inv c)%Qpos)) as H4.
1351 apply AbsSmall_Qabs in H4.
1352 apply (Qle_trans _ _ _ H4). clear H4. apply Qplus_le_r.
1353 rewrite Q_Qpos_min. simpl. apply Qmin_lb_r.
1354 rewrite Qmult_plus_distr_l.
1355 apply Qplus_le_compat.
1356 unfold Qdiv. rewrite Qmult_comm, Qmult_assoc.
1357 apply Qle_shift_div_r. apply Qpos_ispos.
1358 rewrite Qmult_comm. apply Qle_refl.
1359 unfold Qdiv. rewrite Qmult_comm, Qmult_assoc.
1360 apply Qle_shift_div_r. apply Qpos_ispos.
1361 rewrite Qmult_comm. apply Qle_refl.
1362 Qed.
1363
1364 Lemma Qmult_uncurry_assoc : forall (i j k:Q) (b : Qpos),
1365 Qabs i <= `b
1366 -> Qabs j <= `b
1367 -> Qabs k <= `b
1368 -> Qabs (j*k) <= `b
1369 -> Qabs (i*j) <= `b
1370 -> Qmult_uncurry b (Qmult_uncurry b (i, j), k)
1371 == Qmult_uncurry b (i, Qmult_uncurry b (j,k)).
1372 Proof.
1373 intros. simpl.
1374 apply Qabs_Qle_condition in H.
1375 destruct H as [ilower iupper].
1376 apply Qabs_Qle_condition in H0.
1377 destruct H0 as [jlower jupper].
1378 apply Qabs_Qle_condition in H1.
1379 destruct H1 as [klower kupper].
1380 apply Qabs_Qle_condition in H2.
1381 destruct H2 as [jklower jkupper].
1382 apply Qabs_Qle_condition in H3.
1383 destruct H3 as [ijlower ijupper].
1384 assert (forall a:Q, a <= `b -> Qmin (`b) a == a)%Q as elim_min.
1385 { apply Qle_min_r. }
1386 assert (forall a:Q, -(`b) <= a -> Qmax (-(`b)) a == a)%Q as elim_max.
1387 { intros. apply Qle_max_r, H. }
1388 rewrite (elim_min j jupper).
1389 rewrite (elim_min i iupper).
1390 rewrite (elim_min k kupper).
1391 rewrite (elim_max j jlower).
1392 rewrite (elim_max i ilower).
1393 rewrite (elim_max k klower).
1394 rewrite (elim_min (j*k) jkupper).
1395 rewrite (elim_min (i*j) ijupper).
1396 rewrite (elim_max (j*k) jklower).
1397 rewrite (elim_max (i*j) ijlower).
1398 rewrite Qmult_assoc. reflexivity.
1399 Qed.
1400
1401 Lemma quarter_approx_le_abs_1 :
1402 forall (x : CR) (q : Q),
1403 Qabs (q - approximate x (Qpos2QposInf (1 # 4))) <= (3#4)
1404 -> Qabs q <= ` (CR_b (1 ↾ eq_refl) x + 1 ↾ eq_refl)%Qpos.
1405 Proof.
1406 intros. simpl.
1407 apply (Qle_trans _ _ _ (Qabs_triangle_reverse _ _)) in H.
1408 apply (Qplus_le_l _ _ (-Qabs (approximate x (Qpos2QposInf (1#4))))).
1409 apply (Qle_trans _ _ _ H). clear H q.
1410 pose proof (regFun_prf x (1#4)%Qpos (1#1)%Qpos).
1411 apply AbsSmall_Qabs in H.
1412 apply Qopp_le_compat in H. apply (Qplus_le_r _ _ (2#1)) in H.
1413 setoid_replace (2 + - (` ((1 # 4) ↾ eq_refl) + ` (1 ↾ eq_refl)))
1414 with (3#4) in H by reflexivity.
1415 rewrite <- Qplus_assoc, <- Qplus_assoc, Qplus_comm, Qplus_assoc.
1416 setoid_replace ((1#1)+(1#1)) with (2#1) by reflexivity.
1417 apply (Qle_trans _ _ _ H). clear H.
1418 rewrite <- Qplus_assoc. apply Qplus_le_r.
1419 setoid_replace (- Qabs (approximate x (Qpos2QposInf (1 # 4)))
1420 + Qabs (approximate x (Qpos2QposInf (1#1))))%Q
1421 with (- (Qabs (approximate x (Qpos2QposInf (1 # 4)))
1422 - Qabs (approximate x (Qpos2QposInf (1#1)))))
1423 by (unfold equiv, stdlib_rationals.Q_eq; ring).
1424 apply Qopp_le_compat, Qabs_triangle_reverse.
1425 Qed.
1426
1427 Lemma QboundAbs_lowerBound_2 : forall (a b : Qpos) (c d : Q),
1428 (- (`a * `b) <= QboundAbs a c * QboundAbs b d)%Q.
1429 Proof.
1430 intros. apply (Qle_trans _ (-Qabs (QboundAbs a c * QboundAbs b d))).
1431 apply Qopp_le_compat.
1432 rewrite Qabs_Qmult. rewrite QboundAbs_abs, QboundAbs_abs.
1433 apply (Qle_trans _ (`a * Qmin (Qabs d) (`b))).
1434 apply Qmult_le_compat_r. apply Qmin_lb_r.
1435 apply Qmin_glb. apply Qabs_nonneg. apply Qpos_nonneg.
1436 apply Qmult_le_l. apply Qpos_ispos. apply Qmin_lb_r.
1437 rewrite <- (Qopp_involutive (QboundAbs a c * QboundAbs b d)) at 2.
1438 apply Qopp_le_compat. rewrite <- Qabs_opp.
1439 apply Qle_Qabs.
1440 Qed.
1441
1442 Lemma QboundAbs_upperBound_2 : forall (a b : Qpos) (c d : Q),
1443 (QboundAbs a c * QboundAbs b d <= `a * `b)%Q.
1444 Proof.
1445 intros. apply (Qle_trans _ _ _ (Qle_Qabs _)).
1446 rewrite Qabs_Qmult. rewrite QboundAbs_abs, QboundAbs_abs.
1447 apply (Qle_trans _ (`a * Qmin (Qabs d) (`b))).
1448 apply Qmult_le_compat_r. apply Qmin_lb_r.
1449 apply Qmin_glb. apply Qabs_nonneg. apply Qpos_nonneg.
1450 apply Qmult_le_l. apply Qpos_ispos. apply Qmin_lb_r.
1451 Qed.
1452
1453 Lemma CR_b_lowerBound_2 : forall x y : CR,
1454 ('(-proj1_sig ((CR_b (1#1) x) * CR_b (1#1) y)%Qpos)%Q <= x * y)%CR.
1455 Proof.
1456 intros.
1457 rewrite <- (CRboundAbs_Eq (CR_b (1#1) x)
1458 (CR_b_lowerBound (1#1) x) (CR_b_upperBound (1#1) x)) at 2.
1459 unfold CRmult, ucFun2.
1460 intros e. simpl. unfold Cap_raw; simpl.
1461 unfold Cap_raw; simpl.
1462 apply (Qle_trans _ 0). apply (Qopp_le_compat 0), Qpos_nonneg.
1463 unfold Qminus. rewrite <- Qle_minus_iff.
1464 apply (QboundAbs_lowerBound_2 (CR_b (1#1) x) (CR_b (1#1) y)).
1465 Qed.
1466
1467 Lemma CR_b_upperBound_2 : forall x y : CR,
1468 (x * y <= 'proj1_sig ((CR_b (1#1) x) * CR_b (1#1) y)%Qpos)%CR.
1469 Proof.
1470 intros.
1471 rewrite <- (CRboundAbs_Eq (CR_b (1#1) x)
1472 (CR_b_lowerBound (1#1) x) (CR_b_upperBound (1#1) x)) at 1.
1473 unfold CRmult, ucFun2.
1474 intros e. simpl. unfold Cap_raw; simpl.
1475 unfold Cap_raw; simpl.
1476 apply (Qle_trans _ 0). apply (Qopp_le_compat 0), Qpos_nonneg.
1477 unfold Qminus. rewrite <- Qle_minus_iff.
1478 apply (QboundAbs_upperBound_2 (CR_b (1#1) x) (CR_b (1#1) y)).
1479 Qed.
1480
1481 Lemma CRle_Qle : forall (x y:Q), (inject_Q_CR x <= inject_Q_CR y)%CR <-> (x <= y)%Q.
1482 Proof.
1483 split.
1484 intros H.
1485 destruct (Qlt_le_dec y x) as [X|X];[|assumption].
1486 destruct (Qpos_sub _ _ X) as [c Hc].
1487 assert (Y:=(H ((1#2)*c)%Qpos)).
1488 simpl in Y.
1489 unfold Cap_raw in Y; simpl in Y.
1490 rewrite -> Qle_minus_iff in Y.
1491 rewrite -> Hc in Y.
1492 autorewrite with QposElim in Y.
1493 ring_simplify in Y.
1494 elim (Qle_not_lt _ _ Y).
1495 rewrite -> Qlt_minus_iff.
1496 ring_simplify.
1497 apply Q.Qmult_lt_0_compat; auto with *.
1498 intros H e.
1499 simpl.
1500 unfold Cap_raw; simpl.
1501 rewrite -> Qle_minus_iff in H.
1502 apply Qle_trans with (0%Q);[|assumption].
1503 rewrite -> Qle_minus_iff; ring_simplify.
1504 apply Qpos_nonneg.
1505 Qed.
1506
1507 Lemma CRmult_assoc_yfactor_le
1508 : forall (x y z : CR),
1509 let b := ((CR_b (1#1) x + (1#1))
1510 * (CR_b (1#1) y + (1#1)) * (CR_b (1#1) z + (1#1)))%Qpos in
1511 (` (CR_b (1 ↾ eq_refl) y) + 1 <= ` b)%Q.
1512 Proof.
1513 intros. unfold b. simpl.
1514 rewrite <- Qmult_assoc, (Qmult_comm (Qabs (approximate y (Qpos2QposInf (1#1))) + 1 + 1)).
1515 rewrite Qmult_assoc.
1516 rewrite <- Qmult_1_l, <- Qmult_1_l.
1517 rewrite Qmult_assoc.
1518 apply Qmult_le_compat_r.
1519 apply (Qpos_mult_le_compat (1#1) (1#1)).
1520 rewrite <- Qplus_0_l. apply Qplus_le_l, (Qpos_nonneg (CR_b (1#1) x)).
1521 rewrite <- Qplus_0_l. apply Qplus_le_l, (Qpos_nonneg (CR_b (1#1) z)).
1522 rewrite <- Qplus_assoc. apply (Qle_trans _ (0+2)).
1523 discriminate. apply Qplus_le_l. apply Qabs_nonneg.
1524 Qed.
1525
1526 Lemma CRmult_assoc_xfactor_le
1527 : forall (x y z : CR),
1528 let b := ((CR_b (1#1) x + (1#1))
1529 * (CR_b (1#1) y + (1#1)) * (CR_b (1#1) z + (1#1)))%Qpos in
1530 (` (CR_b (1 ↾ eq_refl) x) + 1 <= ` b)%Q.
1531 Proof.
1532 intros. unfold b. simpl.
1533 rewrite <- Qmult_assoc, Qmult_comm.
1534 rewrite <- Qmult_1_l, <- Qmult_1_l at 1.
1535 rewrite Qmult_assoc.
1536 apply Qmult_le_compat_r.
1537 apply (Qpos_mult_le_compat (1#1) (1#1)).
1538 rewrite <- Qplus_0_l. apply Qplus_le_l, (Qpos_nonneg (CR_b (1#1) y)).
1539 rewrite <- Qplus_0_l. apply Qplus_le_l, (Qpos_nonneg (CR_b (1#1) z)).
1540 rewrite <- Qplus_assoc. apply (Qle_trans _ (0+2)).
1541 discriminate. apply Qplus_le_l. apply Qabs_nonneg.
1542 Qed.
1543
1544 Lemma CRmult_assoc_zfactor_le
1545 : forall (x y z : CR),
1546 let b := ((CR_b (1#1) x + (1#1))
1547 * (CR_b (1#1) y + (1#1)) * (CR_b (1#1) z + (1#1)))%Qpos in
1548 (` (CR_b (1 ↾ eq_refl) z) + 1 <= ` b)%Q.
1549 Proof.
1550 intros. rewrite <- Qmult_1_l, <- Qmult_1_l, Qmult_assoc.
1551 apply Qmult_le_compat_r. 2: apply Qpos_nonneg.
1552 apply (Qpos_mult_le_compat (1#1) (1#1)).
1553 rewrite <- Qplus_0_l. apply Qplus_le_l, Qpos_nonneg.
1554 rewrite <- Qplus_0_l. apply Qplus_le_l, Qpos_nonneg.
1555 Qed.
1556
1557 (* Request bounds on all left factors : x, CRmult_bounded b x y, and y. *)
1558 Lemma CRmult_assoc_bounded (x y z : CR) :
1559 let b := ((CR_b (1#1) x + (1#1))
1560 * (CR_b (1#1) y + (1#1)) * (CR_b (1#1) z + (1#1)))%Qpos in
1561 (CRmult_bounded b (CRmult_bounded b x y) z
1562 == CRmult_bounded b x (CRmult_bounded b y z))%CR.
1563 Proof.
1564 intros.
1565 assert (' (- ` b)%Q <= x)%CR as xlower.
1566 { apply (@CRle_trans _ (' (-proj1_sig (CR_b (1#1) x))%Q)).
1567 2: apply (CR_b_lowerBound _ _).
1568 apply CRle_Qle. apply Qopp_le_compat.
1569 apply (Qle_trans _ ((` (CR_b (1#1)%Qpos x) + (1#1)))).
1570 rewrite <- Qplus_0_r at 1. apply Qplus_le_r. discriminate.
1571 apply CRmult_assoc_xfactor_le. }
1572 assert (x <= ' (` b)%Q)%CR as xupper.
1573 { apply (@CRle_trans _ (' (proj1_sig (CR_b (1#1) x))%Q)).
1574 apply CR_b_upperBound.
1575 apply CRle_Qle.
1576 apply (Qle_trans _ ((` (CR_b (1#1)%Qpos x) + (1#1)))).
1577 rewrite <- Qplus_0_r at 1. apply Qplus_le_r. discriminate.
1578 apply CRmult_assoc_xfactor_le. }
1579 assert (' (- ` b)%Q <= y)%CR as ylower.
1580 { apply (@CRle_trans _ (' (-proj1_sig (CR_b (1#1) y))%Q)).
1581 2: apply (CR_b_lowerBound _ _).
1582 apply CRle_Qle. apply Qopp_le_compat.
1583 apply (Qle_trans _ ((` (CR_b (1#1)%Qpos y) + (1#1)))).
1584 rewrite <- Qplus_0_r at 1. apply Qplus_le_r. discriminate.
1585 apply CRmult_assoc_yfactor_le. }
1586 assert (y <= ' (` b)%Q)%CR as yupper.
1587 { apply (@CRle_trans _ (' (proj1_sig (CR_b (1#1) y))%Q)).
1588 apply CR_b_upperBound.
1589 apply CRle_Qle.
1590 apply (Qle_trans _ ((` (CR_b (1#1)%Qpos y) + (1#1)))).
1591 rewrite <- Qplus_0_r at 1. apply Qplus_le_r. discriminate.
1592 apply CRmult_assoc_yfactor_le. }
1593 assert (` (CR_b (1 ↾ eq_refl) x + 1 ↾ eq_refl)%Qpos *
1594 ` (CR_b (1 ↾ eq_refl) y + 1 ↾ eq_refl)%Qpos <= ` b) as xyfactor_le.
1595 { rewrite <- Qmult_1_l.
1596 unfold b. simpl.
1597 rewrite (Qmult_comm ((Qabs (approximate x (Qpos2QposInf (1 ↾ eq_refl))) + 1 + 1) *
1598 (Qabs (approximate y (Qpos2QposInf (1 ↾ eq_refl))) + 1 + 1))).
1599 apply Qmult_le_compat_r.
1600 apply (Qle_trans _ (0+2)). discriminate.
1601 rewrite <- Qplus_assoc.
1602 apply Qplus_le_l, Qabs_nonneg.
1603 apply Qmult_le_0_compat.
1604 apply (Qle_trans _ (0+2)). discriminate.
1605 rewrite <- Qplus_assoc.
1606 apply Qplus_le_l, Qabs_nonneg.
1607 apply (Qle_trans _ (0+2)). discriminate.
1608 rewrite <- Qplus_assoc.
1609 apply Qplus_le_l, Qabs_nonneg. }
1610 rewrite CRmult_uncurry_eq_3r.
1611 rewrite CRmult_uncurry_eq_3.
1612 2: exact xlower. 2: exact xupper.
1613 4: exact xlower. 4: exact xupper.
1614 4: exact ylower. 4: exact yupper.
1615 (* Qmult_uncurry is not associative everywhere,
1616 so use Cmap_wd_loc. *)
1617 apply Cmap_wd_loc with (e:=(1#4)%Qpos). intros [[i j] k].
1618 intros H.
1619 specialize (H (1#4)%Qpos (1#4)%Qpos).
1620 destruct H,H.
1621 simpl in H1. simpl in H0.
1622 apply Qball_0.
1623 apply (@Qmult_uncurry_assoc i j k b).
1624 - clear H0 H1. simpl in H. apply AbsSmall_Qabs in H.
1625 apply (Qle_trans _ (proj1_sig (CR_b (1#1) x + (1#1))%Qpos)).
1626 setoid_replace ((1#4)+(1#4)+(1#4)) with (3#4) in H by reflexivity.
1627 apply quarter_approx_le_abs_1, H. clear H.
1628 apply CRmult_assoc_xfactor_le.
1629 - clear H H0.
1630 apply (Qle_trans _ (proj1_sig (CR_b (1#1) y + (1#1))%Qpos)).
1631 apply AbsSmall_Qabs in H1.
1632 setoid_replace ((1#4)+(1#4)+(1#4)) with (3#4) in H1 by reflexivity.
1633 apply quarter_approx_le_abs_1, H1. apply CRmult_assoc_yfactor_le.
1634 - clear H H1.
1635 apply (Qle_trans _ (proj1_sig (CR_b (1#1) z + (1#1))%Qpos)).
1636 apply AbsSmall_Qabs in H0.
1637 setoid_replace ((1#4)+(1#4)+(1#4)) with (3#4) in H0 by reflexivity.
1638 apply quarter_approx_le_abs_1, H0.
1639 apply CRmult_assoc_zfactor_le.
1640 - apply (Qle_trans _ (proj1_sig (CR_b (1#1) y + (1#1))%Qpos
1641 * proj1_sig (CR_b (1#1) z + (1#1))%Qpos)).
1642 rewrite Qabs_Qmult.
1643 apply (Qle_trans _ (proj1_sig (CR_b (1#1) y + (1#1))%Qpos * Qabs k)).
1644 apply Qmult_le_compat_r.
1645 apply AbsSmall_Qabs in H1.
1646 setoid_replace ((1#4)+(1#4)+(1#4)) with (3#4) in H1 by reflexivity.
1647 apply quarter_approx_le_abs_1, H1. apply Qabs_nonneg.
1648 apply Qmult_le_l. apply Qpos_ispos.
1649 apply AbsSmall_Qabs in H0.
1650 setoid_replace ((1#4)+(1#4)+(1#4)) with (3#4) in H0 by reflexivity.
1651 apply quarter_approx_le_abs_1, H0.
1652 rewrite <- Qmult_1_l, Qmult_assoc.
1653 apply Qmult_le_compat_r. 2: apply Qpos_nonneg.
1654 apply Qmult_le_compat_r. 2: apply Qpos_nonneg.
1655 simpl. rewrite <- Qplus_assoc.
1656 apply (Qle_trans _ (0+2)). discriminate.
1657 apply Qplus_le_l, Qabs_nonneg.
1658 - apply (Qle_trans _ (proj1_sig (CR_b (1#1) x + (1#1))%Qpos
1659 * proj1_sig (CR_b (1#1) y + (1#1))%Qpos)).
1660 rewrite Qabs_Qmult.
1661 apply (Qle_trans _ (proj1_sig (CR_b (1#1) x + (1#1))%Qpos * Qabs j)).
1662 apply Qmult_le_compat_r.
1663 simpl in H.
1664 apply AbsSmall_Qabs in H.
1665 setoid_replace ((1#4)+(1#4)+(1#4)) with (3#4) in H by reflexivity.
1666 apply quarter_approx_le_abs_1, H. apply Qabs_nonneg.
1667 apply Qmult_le_l. apply Qpos_ispos.
1668 apply AbsSmall_Qabs in H1.
1669 setoid_replace ((1#4)+(1#4)+(1#4)) with (3#4) in H1 by reflexivity.
1670 apply quarter_approx_le_abs_1, H1.
1671 exact xyfactor_le.
1672 - rewrite (@CRmult_bounded_mult b).
1673 2: exact ylower. 2: exact yupper.
1674 apply (@CRle_trans _ ('(-proj1_sig ((CR_b (1#1) x) * CR_b (1#1) y)%Qpos)%Q)).
1675 2: apply CR_b_lowerBound_2.
1676 apply CRle_Qle, Qopp_le_compat.
1677 apply (Qle_trans _ (proj1_sig (CR_b (1#1) x + (1#1))%Qpos
1678 * proj1_sig ((CR_b (1#1) y) + (1#1))%Qpos)).
1679 apply (Qpos_mult_le_compat (CR_b (1#1) x) (CR_b (1#1) y)).
1680 rewrite <- Qplus_0_r at 1. apply Qplus_le_r. discriminate.
1681 rewrite <- Qplus_0_r at 1. apply Qplus_le_r. discriminate.
1682 exact xyfactor_le.
1683 - rewrite (@CRmult_bounded_mult b).
1684 2: exact ylower. 2: exact yupper.
1685 apply (@CRle_trans _ ('(proj1_sig ((CR_b (1#1) x) * CR_b (1#1) y)%Qpos)%Q)).
1686 apply CR_b_upperBound_2.
1687 apply CRle_Qle.
1688 apply (Qle_trans _ (proj1_sig (CR_b (1#1) x + (1#1))%Qpos
1689 * proj1_sig ((CR_b (1#1) y) + (1#1))%Qpos)).
1690 apply (Qpos_mult_le_compat (CR_b (1#1) x) (CR_b (1#1) y)).
1691 rewrite <- Qplus_0_r at 1. apply Qplus_le_r. discriminate.
1692 rewrite <- Qplus_0_r at 1. apply Qplus_le_r. discriminate.
1693 exact xyfactor_le.
1694 Qed.
1695