| 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 Bignums.BigQ.BigQ |
| 6 |
CoRN.reals.fast.Compress CoRN.reals.faster.ARQ |
| 7 |
CoRN.metric2.MetricMorphisms CoRN.model.metric2.Qmetric CoRN.reals.faster.ARArith |
| 8 |
MathClasses.implementations.stdlib_rationals MathClasses.implementations.stdlib_binary_integers MathClasses.implementations.field_of_fractions |
| 9 |
MathClasses.implementations.fast_rationals MathClasses.implementations.fast_integers. |
| 10 |
|
| 11 |
#[global] |
| 12 |
Instance inject_Z_bigQ: Cast Z bigQ := cast bigZ bigQ ∘ cast Z bigZ. |
| 13 |
|
| 14 |
#[global] |
| 15 |
Instance bigQ_approx: AppApprox bigQ := λ x k, |
| 16 |
match k with |
| 17 |
| Zneg p => |
| 18 |
let k' := BigN.of_N (Npos p) in |
| 19 |
match x with |
| 20 |
| BigQ.Qz z => BigQ.Qz z |
| 21 |
| BigQ.Qq n d => BigQ.Qq (BigZ.div (BigZ.shiftl n (BigZ.Pos k')) (BigZ.Pos d)) (BigN.shiftl 1 k') |
| 22 |
end |
| 23 |
| _ => x |
| 24 |
end. |
| 25 |
|
| 26 |
Lemma bigQ_approx_Q_approx (x : bigQ) (k : Z) : |
| 27 |
'app_approx x k = app_approx ('x) k. |
| 28 |
Proof. |
| 29 |
unfold app_approx, Q_approx, approximateQ, bigQ_approx. |
| 30 |
destruct k as [|p|]; try reflexivity. |
| 31 |
destruct x as [n|n d]; simpl. |
| 32 |
rewrite Z.div_1_r, Qmake_Qdiv. simpl. |
| 33 |
now rewrite Q.Zmult_Qmult, Qdiv_mult_l by auto with zarith. |
| 34 |
unfold cast, BigQ_Rationals.inject_QType_Q, BigQ.to_Q. |
| 35 |
case_eq (BigN.shiftl 1 (BigN.of_pos p) =? BigN.zero)%bigN; intros Ep. |
| 36 |
apply BigNeqb_correct, BigN.shiftl_eq_0_iff in Ep. |
| 37 |
discriminate. |
| 38 |
case_eq (d =? BigN.zero)%bigN; intros Ed. |
| 39 |
apply BigNeqb_correct in Ed. |
| 40 |
setoid_replace (BigZ.Pos d) with 0%bigZ by assumption. |
| 41 |
now rewrite BigZ.spec_div, Zdiv_0_r, Zmult_0_l. |
| 42 |
rewrite BigZ.spec_div, BigZ.spec_shiftl, Z.shiftl_mul_pow2 by apply BigN.spec_pos. |
| 43 |
rewrite BigN.spec_shiftl, Z.shiftl_1_l. |
| 44 |
replace (BigZ.to_Z (BigZ.Pos (BigN.of_pos p))) with (Zpos p) by (symmetry; apply BigN.spec_of_pos). |
| 45 |
rewrite BigN.spec_of_pos. |
| 46 |
replace (Z2P (2 ^ Zpos p)) with (2 ^ p)%positive by now rewrite <- Zpower_Ppow. |
| 47 |
rewrite <-Zpower_Ppow. |
| 48 |
rewrite Z2P_correct. |
| 49 |
reflexivity. |
| 50 |
apply orders.lt_iff_le_ne. split. |
| 51 |
now apply BigN.spec_pos. |
| 52 |
intros E. symmetry in E. |
| 53 |
change (d == BigN.zero)%bigN in E. |
| 54 |
apply BigN.eqb_eq in E. |
| 55 |
rewrite E in Ed. discriminate. |
| 56 |
Qed. |
| 57 |
|
| 58 |
Lemma bigQ_approx_correct (x : bigQ) (k : Z) : Qball (2 ^ k) ('app_approx x k) ('x). |
| 59 |
Proof. |
| 60 |
rewrite bigQ_approx_Q_approx. |
| 61 |
now apply Q_approx_correct. |
| 62 |
Qed. |
| 63 |
|
| 64 |
#[global] |
| 65 |
Instance bigQ_div: AppDiv bigQ := λ x y, app_approx (x / y). |
| 66 |
|
| 67 |
Lemma bigQ_div_correct (x y : bigQ) (k : Z) : Qball (2 ^ k) ('app_div x y k) ('x / 'y). |
| 68 |
Proof. |
| 69 |
mc_setoid_replace ('x / 'y : Q) with ('(x / y) : Q). |
| 70 |
now apply bigQ_approx_correct. |
| 71 |
now rewrite rings.preserves_mult, dec_fields.preserves_dec_recip. |
| 72 |
Qed. |
| 73 |
|
| 74 |
#[global] |
| 75 |
Instance inverse_Q_bigQ: AppInverse (cast bigQ Q_as_MetricSpace) := λ x ε, 'x. |
| 76 |
|
| 77 |
#[global] |
| 78 |
Instance: DenseEmbedding (cast bigQ Q_as_MetricSpace). |
| 79 |
Proof. |
| 80 |
split; try apply _. |
| 81 |
- Set Printing Implicit. |
| 82 |
assert ( @Injective bigQ Q_as_MetricSpace BigQ_Rationals.QType_equiv |
| 83 |
Qeq |
| 84 |
(@cast bigQ Q_as_MetricSpace BigQ_Rationals.inject_QType_Q)). |
| 85 |
{ apply _. } |
| 86 |
destruct H. split. |
| 87 |
intros. apply Qball_0 in H. apply injective, H. |
| 88 |
split. apply _. apply _. |
| 89 |
intros x y xyeq. apply Qball_0. |
| 90 |
destruct injective_mor. apply sm_proper, xyeq. |
| 91 |
- intros. unfold app_inverse, inverse_Q_bigQ. |
| 92 |
rewrite (rationals.morphisms_involutive _ _). |
| 93 |
apply ball_refl. apply QposMinMax.Qpos_nonneg. |
| 94 |
Qed. |
| 95 |
|
| 96 |
#[global] |
| 97 |
Instance: AppRationals bigQ. |
| 98 |
Proof. |
| 99 |
split; try apply _. |
| 100 |
split; try apply _. |
| 101 |
intros. now apply bigQ_div_correct. |
| 102 |
intros. now apply bigQ_approx_correct. |
| 103 |
Qed. |
| 104 |
|
| 105 |
Notation ARbigQ := (AR (AQ:=bigQ)). |