Debian Codegraph @

reals/faster/ACarith.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 Qabs.
5 Require Import CoRN.model.metric2.Qmetric
6 CoRN.metric2.ProductMetric
7 CoRN.model.totalorder.QposMinMax
8 CoRN.model.totalorder.QMinMax
9 CoRN.reals.faster.ARabs
10 CoRN.reals.faster.ARroot
11 CoRN.reals.faster.ARArith.
12
13 (** Basic definitions for the complex numbers. *)
14
15 Section ACcomplex.
16 Context `{AppRationals AQ}.
17
18 (* The instance of Setoid AR*AR is already in scope,
19 with u = v iff (fst u = fst v /\ snd u = snd v). *)
20
21 Definition ACball (u v : AR*AR) (e : Q) : Prop
22 := 0 <= e
23 /\ ARle ((fst u - fst v)*(fst u - fst v) + (snd u - snd v)*(snd u - snd v))
24 (inject_Q_AR (e*e)).
25
26 (* TODO the distance of ACball would be better. *)
27 Definition AC : MetricSpace := ProductMS AR AR.
28
29 Instance: Plus AC
30 := fun xy uv => pair (fst xy + fst uv) (snd xy + snd uv).
31
32 Instance: Mult AC
33 := fun xy uv => pair (fst xy*fst uv - snd xy*snd uv)
34 (fst xy*snd uv + snd xy*fst uv).
35
36 (* The square root of -1, imaginary number i. *)
37 Definition ACi : AC := pair 0 1.
38
39 Definition ACmodulus : AC -> AR
40 := fun z => ARsqrt (fst z*fst z + snd z*snd z).
41
42 Lemma ACplus_comm : forall u v : AC, u + v = v + u.
43 Proof.
44 intros u v. split; apply ARplus_comm.
45 Qed.
46
47 Lemma ACplus_assoc : forall u v w : AC,
48 (u + v) + w = u + (v + w).
49 Proof.
50 intros u v w. split; apply ARplus_assoc.
51 Qed.
52
53 Definition ACsqrt (z : AC) (yDec : {ARle 0 (snd z)} + {ARle (snd z) 0}) : AC
54 := pair (ARsqrt ((ACmodulus z + fst z) * inject_Q_AR (1#2)))
55 ((if yDec then 1 else -1)
56 * (ARsqrt ((ACmodulus z - fst z) * inject_Q_AR (1#2)))).
57
58 Add Ring AR : (rings.stdlib_ring_theory AR).
59
60 Lemma ARdouble : forall x : AR, x + x = 2*x.
61 Proof.
62 intro x. ring.
63 Qed.
64
65 Lemma ARmult_neg_one : forall x : AR, -1 * x = -x.
66 Proof.
67 intros. ring.
68 Qed.
69
70 Lemma ACsqrt_correct : forall (z : AC) (yDec : {ARle 0 (snd z)} + {ARle (snd z) 0}),
71 ACsqrt z yDec * ACsqrt z yDec = z.
72 Proof.
73 intros [x y] yDec.
74 assert (2 * inject_Q_AR (1 # 2) = 1) as twoHalf.
75 { unfold one.
76 pose proof inject_Q_AR_1.
77 unfold one in H5.
78 rewrite <- H5.
79 rewrite <- inject_Q_AR_plus, <- inject_Q_AR_mult.
80 apply inject_Q_AR_wd. reflexivity. }
81 assert (ARle 0 (ACmodulus (x, y) - x)) as modMinus.
82 { unfold ACmodulus, fst, snd.
83 rewrite <- (ARplus_opp_r x).
84 apply ARplus_le_compat_r.
85 apply (ARle_trans _ (ARsqrt (x*x))).
86 rewrite (ARsqrt_srq_abs x).
87 apply ARle_abs.
88 apply ARsqrt_inc.
89 apply ARsquare_pos.
90 rewrite <- (ARplus_0_r (x*x)) at 1.
91 apply ARplus_le_compat_l.
92 apply ARsquare_pos. }
93 assert (ARle 0 (ACmodulus (x, y) + x)) as modPlus.
94 { unfold ACmodulus, fst, snd.
95 rewrite <- (ARplus_opp_r x).
96 rewrite ARplus_comm.
97 apply ARplus_le_compat_r.
98 apply (ARle_trans _ (ARsqrt (x*x))).
99 rewrite (ARsqrt_srq_abs x).
100 rewrite <- ARabs_opp.
101 apply ARle_abs.
102 apply ARsqrt_inc.
103 apply ARsquare_pos.
104 rewrite <- (ARplus_0_r (x*x)) at 1.
105 apply ARplus_le_compat_l.
106 apply ARsquare_pos. }
107 assert (ARle 0 (inject_Q_AR (1 # 2))) as halfPos.
108 { rewrite <- inject_Q_AR_0.
109 apply inject_Q_AR_le.
110 discriminate. }
111 split.
112 - unfold mult, Mult_instance_0, ACsqrt, fst, snd.
113 rewrite (ARsqrt_correct ((ACmodulus (x, y) + x) * inject_Q_AR (1 # 2))).
114 rewrite (ARmult_comm (if yDec then 1 else -1)
115 (ARsqrt ((ACmodulus (x, y) - x) * inject_Q_AR (1 # 2)))).
116 rewrite ARmult_assoc.
117 rewrite <- (ARmult_comm (if yDec then 1 else -1)).
118 rewrite <- (ARmult_assoc (if yDec then 1 else -1)).
119 setoid_replace (ARmult (if yDec then 1 else -1) (if yDec then 1 else -1))
120 with AR1.
121 rewrite ARmult_1_l.
122 rewrite (ARsqrt_correct ((ACmodulus (x, y) - x) * inject_Q_AR (1 # 2))).
123 + setoid_replace ((ACmodulus (x, y) + x) * inject_Q_AR (1 # 2) -
124 (ACmodulus (x, y) - x) * inject_Q_AR (1 # 2))
125 with (x*(2*inject_Q_AR (1#2))) by ring.
126 rewrite twoHalf.
127 apply ARmult_1_r.
128 + apply AR_mult_0_le_compat. exact modMinus.
129 exact halfPos.
130 + destruct yDec. exact (ARmult_1_l AR1).
131 pose proof (ARmult_neg_one (-1)).
132 simpl in H5. rewrite H5. clear H5.
133 apply ARopp_involutive.
134 + apply AR_mult_0_le_compat. exact modPlus.
135 exact halfPos.
136 - unfold mult, Mult_instance_0, ACsqrt, fst, snd.
137 rewrite ARmult_comm, ARmult_assoc, ARdouble.
138 rewrite ARsqrt_mult, ARsqrt_mult.
139 assert (forall a b c : AR, a * c * (b * c) = c * c * (a * b)).
140 { intros. ring. }
141 rewrite H5. clear H5.
142 pose proof (ARsqrt_correct (inject_Q_AR (1 # 2))).
143 simpl in H5. rewrite H5. clear H5.
144 rewrite <- (ARsqrt_mult (ACmodulus (x, y) - x)).
145 setoid_replace ((ACmodulus (x, y) - x) * (ACmodulus (x, y) + x))
146 with (ACmodulus (x, y) * ACmodulus (x, y) - x*x)
147 by ring.
148 unfold ACmodulus, fst, snd.
149 rewrite (ARsqrt_correct (x*x+y*y)).
150 setoid_replace (x * x + y * y - x * x)
151 with (y*y) by ring.
152 rewrite ARsqrt_srq_abs.
153 setoid_replace (2 * ((if yDec then 1 else -1) * (inject_Q_AR (1 # 2) * ARabs y)))
154 with (2 * inject_Q_AR (1 # 2) * ((if yDec then 1 else -1) * ARabs y))
155 by ring.
156 rewrite twoHalf, ARmult_1_l.
157 simpl in yDec. destruct yDec.
158 rewrite ARmult_1_l.
159 rewrite ARabs_pos. reflexivity. exact a.
160 rewrite ARabs_neg.
161 rewrite ARmult_neg_one.
162 apply ARopp_involutive.
163 exact a.
164 apply (ARle_trans _ (x*x + 0)).
165 rewrite ARplus_0_r.
166 apply ARsquare_pos.
167 apply ARplus_le_compat_l, ARsquare_pos.
168 exact modMinus.
169 exact modPlus.
170 exact halfPos.
171 exact modPlus.
172 exact halfPos.
173 exact modMinus.
174 exact halfPos.
175 Qed.
176
177 End ACcomplex.