Debian Codegraph @

reals/faster/ApproximateRationals.v

raw
1 Require Import CoRN.algebra.RSetoid.
2 Require Import CoRN.metric2.Metric.
3 Require Import CoRN.metric2.UniformContinuity.
4 Require
5 MathClasses.implementations.stdlib_rationals MathClasses.implementations.positive_semiring_elements.
6 From Coq Require Import Program.
7 Require Import CoRN.model.totalorder.QposMinMax
8 MathClasses.misc.workaround_tactics
9 CoRN.stdlib_omissions.Q CoRN.util.Qdlog CoRN.model.metric2.Qmetric.
10 From Coq Require Import Qabs.
11 Require Import CoRN.classes.Qclasses CoRN.model.totalorder.QMinMax
12 CoRN.algebra.RSetoid CoRN.metric2.MetricMorphisms
13 MathClasses.orders.minmax MathClasses.orders.dec_fields MathClasses.theory.abs MathClasses.theory.shiftl MathClasses.theory.int_pow.
14 Require Export
15 MathClasses.interfaces.abstract_algebra MathClasses.interfaces.additional_operations MathClasses.interfaces.orders.
16
17 (* We describe the approximate rationals as a ring that is dense in the rationals *)
18
19 (* Because [Q] is ``hard-wired'' nearly everywhere in CoRN, we take the easy
20 way and require all operations to be sound with respect to [Q]. *)
21 Class AppDiv AQ := app_div : AQ → AQ → Z → AQ.
22 Class AppApprox AQ := app_approx : AQ → Z → AQ.
23
24 Class AppRationals AQ {e plus mult zero one inv} `{Apart AQ} `{Le AQ} `{Lt AQ}
25 {AQtoQ : Cast AQ Q_as_MetricSpace}
26 `{!AppInverse AQtoQ} {ZtoAQ : Cast Z AQ} `{!AppDiv AQ} `{!AppApprox AQ}
27 `{!Abs AQ} `{!Pow AQ N} `{!ShiftL AQ Z}
28 `{∀ x y : AQ, Decision (x = y)} `{∀ x y : AQ, Decision (x ≤ y)} : Prop := {
29 aq_ring :: @Ring AQ e plus mult zero one inv ;
30 aq_trivial_apart :: TrivialApart AQ ;
31 aq_order_embed :: OrderEmbedding AQtoQ ;
32 aq_strict_order_embed :: StrictOrderEmbedding AQtoQ ;
33 aq_ring_morphism :: SemiRing_Morphism AQtoQ ;
34 aq_dense_embedding :: DenseEmbedding AQtoQ ;
35 aq_div : ∀ x y k, ball (2 ^ k) ('app_div x y k) ('x / 'y) ;
36 aq_compress : ∀ x k, ball (2 ^ k) ('app_approx x k) ('x) ;
37 aq_shift :: ShiftLSpec AQ Z (≪) ;
38 aq_nat_pow :: NatPowSpec AQ N (^) ;
39 aq_ints_mor :: SemiRing_Morphism ZtoAQ
40 }.
41
42 Lemma order_embedding_iff `{OrderEmbedding A B f} x y :
43 x ≤ y ↔ f x ≤ f y.
44 Proof. firstorder. Qed.
45
46
47 Lemma strict_order_embedding_iff `{StrictOrderEmbedding A B f} x y :
48 x < y ↔ f x < f y.
49 Proof. firstorder. Qed.
50
51 Section approximate_rationals_more.
52 Context `{AppRationals AQ}.
53
54 Lemma AQtoQ_ZtoAQ (x : Z) : cast AQ Q (cast Z AQ x) = cast Z Q x.
55 Proof. now apply (integers.to_ring_twice _ _ _). Qed.
56
57 Global Instance: Injective (cast AQ Q).
58 Proof.
59 destruct dense_injective.
60 split. 2: apply _.
61 intros. apply (injective x y).
62 unfold equiv. simpl.
63 rewrite H5. reflexivity.
64 Qed.
65
66 Global Instance: StrongSetoid AQ.
67 Proof strong_setoids.dec_strong_setoid.
68
69 Global Instance: StrongSetoid_Morphism (cast AQ Q).
70 Proof strong_setoids.dec_strong_morphism (cast AQ Q).
71
72 Global Instance: StrongInjective (cast AQ Q).
73 Proof strong_setoids.dec_strong_injective (cast AQ Q).
74
75 Global Instance: Injective (cast Z AQ).
76 Proof.
77 split; try apply _.
78 intros x y E.
79 apply (injective (cast Z Q)).
80 rewrite <-2!AQtoQ_ZtoAQ.
81 now rewrite E.
82 Qed.
83
84 Global Instance: FullPseudoSemiRingOrder (_ : Le AQ) (_ : Lt AQ).
85 Proof.
86 apply (projected_full_pseudo_ring_order (cast AQ Q)).
87 apply order_embedding_iff.
88 apply strict_order_embedding_iff.
89 Qed.
90
91 Lemma aq_opp : forall (x : AQ), '(-x) = -'x.
92 Proof.
93 intro x.
94 apply (Qplus_inj_l _ _ ('x)).
95 rewrite Qplus_opp_r.
96 assert ('zero0 = 0%Q) by (apply rings.preserves_0).
97 rewrite <- H5.
98 destruct aq_ring_morphism.
99 destruct semiringmor_plus_mor.
100 destruct monmor_sgmor.
101 rewrite <- preserves_sg_op.
102 destruct sgmor_setmor.
103 apply sm_proper.
104 unfold equiv.
105 destruct aq_ring, ring_group.
106 destruct abgroup_group.
107 apply negate_r.
108 Qed.
109
110 Lemma aq_shift_correct (x : AQ) (k : Z) : '(x ≪ k) = 'x * 2 ^ k.
111 Proof. rewrite preserves_shiftl. apply shiftl_int_pow. Qed.
112
113 Lemma aq_shift_1_correct (k : Z) : '((1:AQ) ≪ k) = 2 ^ k.
114 Proof. now rewrite aq_shift_correct, rings.preserves_1, rings.mult_1_l. Qed.
115
116 Lemma aq_shift_opp_1 (x : AQ) : '(x ≪ (-1 : Z)) = 'x / 2.
117 Proof. now rewrite aq_shift_correct. Qed.
118
119 Lemma aq_shift_opp_2 (x : AQ) : '(x ≪ (-2 : Z)) = 'x / 4.
120 Proof. now rewrite aq_shift_correct. Qed.
121
122 Lemma aq_div_dlog2 (x y : AQ) (ε : Q₊) :
123 ball (proj1_sig ε) ('app_div x y (Qdlog2 ('ε))) ('x / 'y).
124 Proof.
125 eapply ball_weak_le.
126 now apply Qpos_dlog2_spec.
127 now apply aq_div.
128 Qed.
129
130 Lemma aq_approx_dlog2 (x : AQ) (ε : Q₊) :
131 ball (proj1_sig ε) ('app_approx x (Qdlog2 ('ε))) ('x).
132 Proof.
133 eapply ball_weak_le.
134 now apply Qpos_dlog2_spec.
135 now apply aq_compress.
136 Qed.
137
138 Definition app_div_above (x y : AQ) (k : Z) : AQ := app_div x y k + 1 ≪ k.
139
140 Lemma aq_div_above (x y : AQ) (k : Z) : ('x / 'y : Q) ≤ 'app_div_above x y k.
141 Proof.
142 unfold app_div_above.
143 pose proof (aq_div x y k) as P.
144 apply in_Qball in P. destruct P as [_ P].
145 rewrite rings.preserves_plus.
146 rewrite aq_shift_correct.
147 now rewrite rings.preserves_1, left_identity.
148 Qed.
149
150 Global Instance: IntegralDomain AQ.
151 Proof.
152 split; try apply _.
153 intros E.
154 destruct (rings.is_ne_0 (1%mc:Q)).
155 rewrite <-(rings.preserves_1 (f:=cast AQ Q)).
156 rewrite <-(rings.preserves_0 (f:=cast AQ Q)).
157 now rewrite E.
158 intros x [? [y [? E]]].
159 destruct (no_zero_divisors ('x : Q)). split.
160 now apply rings.injective_ne_0.
161 exists ('y : Q). split.
162 now apply rings.injective_ne_0.
163 rewrite <-rings.preserves_mult, E.
164 apply rings.preserves_0.
165 Qed.
166
167 Lemma aq_lt_mid (x y : Q) : (x < y)%Q → { z : AQ | (x < 'z ∧ 'z < y)%Q }.
168 Proof with auto with qarith.
169 intros E.
170 destruct (Qpos_sub _ _ E) as [γ Eγ].
171 (* We need to pick a rational [x] such that [x < 1#2]. Since we do not
172 use this lemma for computations yet, we just pick [1#3]. However,
173 whenever we will it might be worth to reconsider. *)
174 exists (app_inverse (cast AQ Q) ((1#2) * (x + y)) ((1#3) * γ)%Qpos)%Q.
175 split.
176 apply Qlt_le_trans with (x + (1#6) * proj1_sig γ)%Q.
177 rewrite <-(rings.plus_0_r x) at 1.
178 apply Qplus_lt_r...
179 assert (Qeq (x + (1 # 6) * ` γ)
180 ((1 # 2) * (x + y) - proj1_sig ((1 # 3) * γ)%Qpos)%Q).
181 { rewrite Eγ. simpl. ring. }
182 rewrite H5. clear H5.
183 simpl.
184 apply (in_Qball (proj1_sig ((1#3)*γ)%Qpos)), ball_sym, dense_inverse.
185 apply Qle_lt_trans with (y - (1#6) * proj1_sig γ)%Q.
186 assert (Qeq (y - (1 # 6) * ` γ)
187 ((1 # 2) * (x + y) + proj1_sig ((1 # 3) * γ)%Qpos)).
188 { rewrite Eγ. simpl. ring. }
189 rewrite H5. clear H5. simpl.
190 apply (in_Qball (proj1_sig ((1#3)*γ)%Qpos)), ball_sym, dense_inverse.
191 apply (Qlt_le_trans _ (y-0)).
192 apply Qplus_lt_r.
193 apply Qopp_Qlt_0_r...
194 unfold Qminus. rewrite Qplus_0_r. apply Qle_refl.
195 Defined.
196
197 Instance: MeetSemiLattice_Morphism (cast AQ Q).
198 Proof.
199 split; try apply _; apply lattices.order_preserving_meet_sl_mor.
200 Qed.
201
202 Instance: JoinSemiLattice_Morphism (cast AQ Q).
203 Proof.
204 split; try apply _; apply lattices.order_preserving_join_sl_mor.
205 Qed.
206
207 Lemma aq_preserves_min x y : '(x ⊓ y) = Qmin ('x) ('y).
208 Proof.
209 rewrite lattices.preserves_meet; symmetry; apply Qmin_coincides.
210 Qed.
211
212 Lemma aq_preserves_max x y : '(x ⊔ y) = Qmax ('x) ('y).
213 Proof.
214 rewrite lattices.preserves_join; symmetry; apply Qmax_coincides.
215 Qed.
216
217 Global Program Instance AQposAsQ: Cast (AQ₊) Q := cast AQ Q ∘ cast (AQ₊) AQ.
218
219 Global Program Instance AQposAsQpos: Cast (AQ₊) (Q₊) := λ x, ('x : Q).
220 Next Obligation.
221 destruct x as [x Ex]. simpl.
222 posed_rewrite <-(rings.preserves_0 (f:=cast AQ Q)).
223 now apply (strictly_order_preserving (cast AQ Q)).
224 Qed.
225
226 Lemma AQposAsQpos_preserves_1 : cast (AQ₊) (Q₊) 1 = 1.
227 Proof. change (cast AQ Q 1 = 1). apply rings.preserves_1. Qed.
228
229 Lemma AQposAsQpos_preserves_4 : cast (AQ₊) (Q₊) 4 = 4.
230 Proof. change (cast AQ Q 4 = 4). apply rings.preserves_4. Qed.
231 End approximate_rationals_more.