Debian Codegraph @

reals/faster/ARbigQ.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 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)).