| 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)). |