Debian Codegraph @

reals/faster/ARQ.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 QArith.
5 Require Import CoRN.util.Qdlog.
6 From Coq Require Import ZArith.
7 Require Import CoRN.reals.fast.Compress
8 CoRN.metric2.MetricMorphisms CoRN.model.metric2.Qmetric CoRN.reals.faster.ARArith
9 CoRN.model.totalorder.QposMinMax.
10
11 #[global]
12 Instance Q_approx: AppApprox Q := λ (x : Q) (k : Z),
13 match k with
14 | Zneg p => approximateQ x (2 ^ p)
15 | _ => x
16 end.
17
18 Lemma Q_approx_correct (x : Q) (k : Z) : Qball (2 ^ k) (app_approx x k) x.
19 Proof.
20 destruct k as [|p|].
21 - apply ball_refl. discriminate.
22 - apply ball_refl. apply Qpower.Qpower_pos_positive. discriminate.
23 - unfold app_approx, Q_approx.
24 setoid_replace (2 ^ Zneg p)%Q with (1 # (2 ^ p))%Q.
25 now apply ball_sym, approximateQ_correct.
26 change (/ Qpower (inject_Z 2%Z) (Zpos p) == 1 # 2 ^ p).
27 rewrite <-Qpower.Zpower_Qpower; auto with zarith.
28 now rewrite <- Zpower_Ppow.
29 Qed.
30
31 #[global]
32 Instance Q_approx_div: AppDiv Q := λ x y k, app_approx (x / y) k.
33
34 #[global]
35 Instance inject_Q_Q: Cast Q Q_as_MetricSpace := Datatypes.id.
36 #[global]
37 Instance inverse_Q_Q: AppInverse inject_Q_Q := λ x ε, app_approx x (Qdlog2 (proj1_sig ε)).
38
39 #[global]
40 Instance: AppRationals Q.
41 Proof.
42 repeat (split; try apply _).
43 intros; assumption.
44 intros; assumption.
45 intros; assumption.
46 intros; assumption.
47 - intros. apply Qball_0. assumption.
48 - unfold inject_Q_Q, Datatypes.id. rewrite H.
49 ring_simplify. discriminate.
50 - unfold inject_Q_Q, Datatypes.id. rewrite H.
51 ring_simplify. discriminate.
52 - unfold inject_Q_Q, Datatypes.id.
53 unfold app_inverse, inverse_Q_Q.
54 pose proof (Q_approx_correct x (Qdlog2 (` ε))) as [H _].
55 refine (Qle_trans _ _ _ _ H).
56 apply Qopp_le_compat.
57 apply (Qpos_dlog2_spec ε).
58 - unfold inject_Q_Q, Datatypes.id.
59 unfold app_inverse, inverse_Q_Q.
60 pose proof (Q_approx_correct x (Qdlog2 (` ε))) as [_ H].
61 apply (Qle_trans _ _ _ H).
62 apply (Qpos_dlog2_spec ε).
63 - intros. apply Q_approx_correct.
64 - intros. apply Q_approx_correct.
65 - apply Q_approx_correct.
66 - apply Q_approx_correct.
67 Qed.
68
69 Notation ARQ := (AR (AQ:=Q)).