Debian Codegraph @

reals/faster/ARbigD.v

raw
1 Require Import CoRN.algebra.RSetoid.
2 Require Import CoRN.metric2.Metric.
3 Require Import CoRN.metric2.UniformContinuity.
4 From Coq Require Import Program QArith ZArith.
5 Require Import Bignums.BigZ.BigZ
6 CoRN.model.totalorder.QposMinMax
7 CoRN.metric2.MetricMorphisms CoRN.model.metric2.Qmetric CoRN.util.Qdlog CoRN.reals.faster.ARArith
8 MathClasses.theory.int_pow MathClasses.theory.nat_pow
9 MathClasses.interfaces.rationals MathClasses.implementations.stdlib_rationals MathClasses.interfaces.integers MathClasses.implementations.stdlib_binary_integers MathClasses.implementations.fast_integers MathClasses.implementations.dyadics.
10
11 Add Field Q : (dec_fields.stdlib_field_theory Q).
12
13 Notation bigD := (Dyadic bigZ).
14 #[global]
15 Instance inject_bigZ_Q: Cast bigZ Q_as_MetricSpace := inject_Z ∘ BigZ.to_Z.
16 #[global]
17 Instance inject_Z_bigD: Cast Z bigD := dy_inject ∘ BigZ.of_Z.
18 #[global]
19 Instance inject_N_bigZ: Cast N bigZ := BigZ.of_Z ∘ Z_of_N.
20 #[global]
21 Instance inject_bigD_Q: Cast bigD Q_as_MetricSpace := DtoQ inject_bigZ_Q.
22
23 (* these casts ^^ are semiring (and thus setoid) morphims *)
24 #[global]
25 Instance: SemiRing_Morphism inject_bigZ_Q.
26 Proof. unfold inject_bigZ_Q. apply _. Qed.
27
28 #[global]
29 Instance: SemiRing_Morphism inject_Z_bigD.
30 Proof. unfold inject_Z_bigD. apply _. Qed.
31
32 #[global]
33 Instance: SemiRing_Morphism inject_N_bigZ.
34 Proof. unfold inject_N_bigZ. apply _. Qed.
35
36 #[global]
37 Instance: SemiRing_Morphism inject_bigD_Q.
38 Proof. unfold inject_bigD_Q. apply _. Qed.
39
40 Lemma inject_bigD_Q_correct
41 : forall x : bigD, cast bigD Q x = 'mant x * 2 ^ (cast bigZ Z (expo x)).
42 Proof.
43 intro x. unfold cast at 1, inject_bigD_Q.
44 unfold inject_bigZ_Q.
45 rewrite (DtoQ_correct _ _ (reflexivity x)).
46 unfold DtoQ_slow.
47 now rewrite (preserves_int_pow_exp (f:=cast bigZ Z)).
48 Qed.
49
50 (*
51 We use BigZ.div and BigZ.shiftl because we don't have any theory on euclid and shiftr
52 in math-classes yet. Moreover, BigZ.shiftl behaves as shiftr on its negative domain,
53 which is quite convenient here.
54 *)
55 #[global]
56 Program Instance bigD_div: AppDiv bigD := λ x y k,
57 BigZ.div (BigZ.shiftl (mant x) (-('k - 1) + expo x - expo y)) (mant y) ▼ ('k - 1).
58
59 Lemma Qdiv_bounded_Zdiv (x y : Z) :
60 'Z.div x y ≤ ('x / 'y : Q) < 'Z.div x y + 1.
61 Proof.
62 rewrite Qround.Zdiv_Qdiv.
63 split.
64 now apply Qround.Qfloor_le.
65 rewrite <-(rings.preserves_1 (f:=cast Z Q)).
66 rewrite <-rings.preserves_plus.
67 now apply Qround.Qlt_floor.
68 Qed.
69
70 Lemma Qpow_bounded_Zshiftl (x n : Z) :
71 'Z.shiftl x n ≤ cast Z Q x * 2 ^ n < 'Z.shiftl x n + 1.
72 Proof.
73 destruct (total (≤) 0 n) as [En | En].
74 rewrite Z.shiftl_mul_pow2 by trivial.
75 rewrite inject_Z_mult.
76 rewrite Qpower.Zpower_Qpower by trivial.
77 split; try reflexivity.
78 apply semirings.pos_plus_lt_compat_r.
79 now apply (semirings.lt_0_1 (R:=Q)).
80 rewrite Z.shiftl_div_pow2 by trivial.
81 assert (('x * 2 ^ n : Q) = 'x / 'Zpower 2 (-n)).
82 rewrite Qpower.Zpower_Qpower.
83 rewrite <-Qpower.Qpower_opp, Z.opp_involutive.
84 reflexivity.
85 now apply rings.flip_nonpos_negate in En.
86 split.
87 transitivity ('x / 'Zpower 2 (-n) : Q).
88 now apply Qdiv_bounded_Zdiv.
89 apply orders.eq_le. now symmetry.
90 apply orders.le_lt_trans with ('x / 'Zpower 2 (-n) : Q).
91 now apply orders.eq_le.
92 now apply Qdiv_bounded_Zdiv.
93 Qed.
94
95 Lemma bigD_div_correct (x y : bigD) (k : Z) : Qball (2 ^ k) ('app_div x y k) ('x / 'y).
96 Proof.
97 assert (∀ xm xe ym ye : Z,
98 (('xm * 2 ^ xe)%mc : Q) / (('ym * 2 ^ ye)%mc : Q) = ('xm * 2 ^ (-(k - 1) + xe - ye)) / 'ym * 2 ^ (k - 1)) as E1.
99 intros.
100 rewrite 2!int_pow_exp_plus by solve_propholds.
101 rewrite dec_fields.dec_recip_distr.
102 rewrite 2!int_pow_negate.
103 transitivity (('xm / 'ym * 2 ^ xe / 2 ^ ye * (2 ^ (k - 1) / 2 ^ (k - 1)))%mc : Q); [| ring].
104 rewrite dec_recip_inverse by solve_propholds. ring.
105 assert (∀ xm xe ym ye : Z,
106 'Z.div (Z.shiftl xm (-(k - 1) + xe - ye)) ym * 2 ^ (k - 1) - 2 ^ k ≤ ('xm * 2 ^ xe) / ('ym * 2 ^ ye : Q)) as Pleft.
107 clear x y.
108 assert (∀ z : Q, z * 2 ^ (k - 1) - 2 ^ k = ((z - 1) - 1) * 2 ^ (k - 1)) as E2.
109 intros.
110 mc_setoid_replace k with ((k - 1) + 1) at 2 by ring.
111 rewrite (int_pow_exp_plus (k - 1)) by solve_propholds.
112 ring_simplify. apply sm_proper. now rewrite commutativity.
113 intros. rewrite E1, E2.
114 apply (order_preserving (.* _)).
115 apply rings.flip_le_minus_l.
116 apply semirings.plus_le_compat_r; [easy |].
117 transitivity (('Z.shiftl xm (-(k - 1) + xe - ye) / 'ym - 1)%mc : Q).
118 apply (order_preserving (+ -1)). now apply Qdiv_bounded_Zdiv.
119 destruct (orders.le_or_lt 0 ym) as [E | E].
120 apply rings.flip_le_minus_l.
121 apply semirings.plus_le_compat_r; [easy |].
122 apply (maps.order_preserving_flip_nonneg (.*.) (/ 'ym : Q)).
123 apply dec_fields.nonneg_dec_recip_compat.
124 now apply semirings.preserves_nonneg.
125 now apply Qpow_bounded_Zshiftl.
126 transitivity ((('Z.shiftl xm (-(k - 1) + xe - ye) + 1) / 'ym)%mc : Q).
127 rewrite rings.plus_mult_distr_r.
128 apply semirings.plus_le_compat; [reflexivity |].
129 rewrite rings.mult_1_l.
130 apply rings.flip_le_negate.
131 rewrite rings.negate_involutive, dec_fields.dec_recip_negate.
132 apply dec_fields.flip_le_dec_recip_l; [solve_propholds |].
133 rewrite <-rings.preserves_negate.
134 apply semirings.preserves_ge_1.
135 apply rings.flip_le_negate.
136 rewrite rings.negate_involutive.
137 now apply nat_int.le_iff_lt_plus_1.
138 apply semirings.flip_nonpos_mult_r.
139 apply dec_fields.nonpos_dec_recip_compat.
140 apply semirings.preserves_nonpos.
141 now apply orders.lt_le.
142 now apply orders.lt_le, Qpow_bounded_Zshiftl.
143 assert (∀ xm xe ym ye : Z,
144 ('xm * 2 ^ xe) / ('ym * 2 ^ ye : Q) ≤ '(Z.div (Z.shiftl xm (-(k - 1) + xe - ye)) ym) * 2 ^ (k - 1) + 2 ^ k) as Pright.
145 clear x y.
146 assert (∀ z : Q, z * 2 ^ (k - 1) + 2 ^ k = ((z + 1) + 1) * 2 ^ (k - 1)) as E2.
147 intros.
148 mc_setoid_replace k with ((k - 1) + 1) at 2 by ring.
149 rewrite (int_pow_exp_plus (k - 1)) by solve_propholds.
150 ring_simplify. apply sm_proper. now apply commutativity.
151 intros. rewrite E1, E2.
152 apply (order_preserving (.* _)).
153 transitivity (('Z.shiftl xm (-(k - 1) + xe - ye) / 'ym + 1)%mc : Q).
154 2: now apply (order_preserving (+1)); apply orders.lt_le, Qdiv_bounded_Zdiv.
155 destruct (orders.le_or_lt ym 0) as [E3 | E3].
156 apply semirings.plus_le_compat_r; [easy |].
157 apply semirings.flip_nonpos_mult_r.
158 apply dec_fields.nonpos_dec_recip_compat.
159 now apply semirings.preserves_nonpos.
160 now apply Qpow_bounded_Zshiftl.
161 transitivity ((('Z.shiftl xm (-(k - 1) + xe - ye) + 1) / ' ym)%mc : Q).
162 apply (maps.order_preserving_flip_nonneg (.*.) ((/ 'ym)%mc : Q)).
163 apply dec_fields.nonneg_dec_recip_compat.
164 apply semirings.preserves_nonneg.
165 now apply orders.lt_le.
166 now apply orders.lt_le, Qpow_bounded_Zshiftl.
167 rewrite rings.plus_mult_distr_r.
168 apply semirings.plus_le_compat; [reflexivity |].
169 rewrite rings.mult_1_l.
170 apply dec_fields.flip_le_dec_recip_l; [solve_propholds |].
171 apply semirings.preserves_ge_1.
172 now apply nat_int.lt_iff_plus_1_le in E3.
173 unfold cast. rewrite 3!inject_bigD_Q_correct.
174 destruct x as [xm xe], y as [ym ye]. simpl.
175 unfold cast, inject_bigZ_Q, cast, "∘". simpl. BigZ.zify.
176 apply in_Qball. split. apply Pleft. apply Pright.
177 Qed.
178
179 #[global]
180 Instance inverse_Q_bigD: AppInverse inject_bigD_Q := λ x ε,
181 app_div ('Qnum x) ('(Zpos (Qden x))) (Qdlog2 (proj1_sig ε)).
182
183 #[global]
184 Instance bigD_approx : AppApprox bigD := λ x k,
185 BigZ.shiftl (mant x) (-('k - 1) + expo x) ▼ ('k - 1).
186
187 Lemma bigD_approx_correct (x : bigD) (k : Z) : Qball (2 ^ k) ('app_approx x k) ('x).
188 Proof.
189 setoid_replace (app_approx x k) with (app_div x 1 k).
190 setoid_replace ('x : Q) with (('x / '1)%mc : Q).
191 now apply bigD_div_correct.
192 rewrite rings.preserves_1, dec_fields.dec_recip_1.
193 now rewrite rings.mult_1_r.
194 unfold app_div, bigD_div.
195 simpl. rewrite BigZ.div_1_r.
196 setoid_replace (-('k - 1) + expo x - 0) with (-('k - 1) + expo x); [reflexivity |].
197 now rewrite rings.negate_0, rings.plus_0_r.
198 Qed.
199
200 #[global]
201 Instance: DenseEmbedding inject_bigD_Q.
202 Proof.
203 split; try apply _.
204 - assert (@Injective bigD Q_as_MetricSpace _ Qeq inject_bigD_Q).
205 { apply _. }
206 destruct H. split.
207 intros. apply Qball_0 in H. apply injective, H.
208 split. apply _. apply _.
209 intros x y xyeq. apply Qball_0.
210 destruct injective_mor. apply sm_proper, xyeq.
211 - intros [n d] ε.
212 unfold app_inverse, inverse_Q_bigD.
213 apply ball_weak_le with (proj1_sig (Qpos_power 2 (Qdlog2 (proj1_sig ε)))).
214 now apply (Qpos_dlog2_spec ε).
215 simpl.
216 rewrite (Qmake_Qdiv n d).
217 rewrite 2!(integers.to_ring_unique_alt inject_Z (inject_bigD_Q ∘ dy_inject ∘ BigZ.of_Z)).
218 apply bigD_div_correct.
219 Qed.
220
221 #[global]
222 Instance bigD_Zshiftl: ShiftL bigD Z := λ x n, x ≪ 'n.
223
224 #[global]
225 Instance: Proper ((=) ==> (=) ==> (=)) bigD_Zshiftl.
226 Proof. unfold bigD_Zshiftl. solve_proper. Qed.
227
228 #[global]
229 Instance: ShiftLSpec bigD Z bigD_Zshiftl.
230 Proof.
231 split; try apply _; unfold shiftl, bigD_Zshiftl.
232 intros x. rewrite rings.preserves_0. now apply shiftl_0.
233 intros x n. rewrite rings.preserves_plus. now apply shiftl_S.
234 Qed.
235
236 (*
237 This function is more or less a copy of dy_pow, but uses [N] instead of [BigZ⁺] for the exponent.
238 An alternative definition would have been bigD_Npow x n = dy_pow x (N_to_BigZ_NonNeg n).
239 However, then the exponent would be translated from [N] into [BigZ] and back again, due to the
240 definition of [BigZ.pow].
241 *)
242 #[global]
243 Instance bigD_Npow: Pow bigD N := λ x n, (mant x) ^ n ▼ 'n * expo x.
244
245 #[global]
246 Instance: NatPowSpec bigD N bigD_Npow.
247 Proof.
248 split; unfold "^", bigD_Npow, equiv, dy_equiv, DtoQ_slow.
249 intros [xm xe] [ym ye] E1 e1 e2 E2. simpl in *.
250 rewrite E2. clear e1 E2.
251 rewrite 2!(preserves_nat_pow (f:=integers.integers_to_ring bigZ Q)).
252 rewrite 2!(commutativity ('e2 : bigZ)).
253 rewrite 2!int_pow_exp_mult.
254 rewrite 2!(int_pow_nat_pow (f:=cast N bigZ)).
255 rewrite <-2!nat_pow_base_mult.
256 now rewrite E1.
257 intros [xm xe]. simpl.
258 rewrite rings.preserves_0, left_absorb.
259 now rewrite nat_pow_0.
260 intros [xm xe] n. simpl.
261 rewrite nat_pow_S.
262 rewrite rings.preserves_plus, rings.preserves_1.
263 now rewrite distribute_r, left_identity.
264 Qed.
265
266 #[global]
267 Instance bigD_appRat : AppRationals bigD.
268 Proof.
269 split; try apply _; intros.
270 split; apply _.
271 now apply bigD_div_correct.
272 now apply bigD_approx_correct.
273 Qed.
274
275 Notation ARbigD := (AR (AQ:=bigD)).