Debian Codegraph @

reals/faster/ARroot.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 Ring.
5 Require Import CoRN.stdlib_omissions.Z
6 CoRN.model.totalorder.QposMinMax
7 CoRN.metric2.Complete CoRN.model.metric2.Qmetric.
8 From Coq Require Import ZArith.
9 Require Import CoRN.util.Qdlog
10 CoRN.reals.fast.CRroot
11 CoRN.reals.faster.ARabs
12 MathClasses.interfaces.abstract_algebra MathClasses.theory.shiftl MathClasses.theory.nat_pow MathClasses.theory.int_pow.
13 Require Export
14 CoRN.reals.faster.ARArith.
15
16 Section ARsqrt.
17 Context `{AppRationals AQ}.
18
19 Add Ring AQ : (rings.stdlib_ring_theory AQ).
20 Add Ring Q : (rings.stdlib_ring_theory Q).
21 Add Ring Z : (rings.stdlib_ring_theory Z).
22 Add Ring AR : (rings.stdlib_ring_theory AR).
23
24 Section sqrt_mid.
25 Context `(Pa : 1 ≤ a ≤ 4).
26
27 Fixpoint AQsqrt_loop (n : nat) : AQ * AQ :=
28 match n with
29 | O => (a, 0)
30 | S n =>
31 let (r, s) := AQsqrt_loop n in
32 if decide_rel (≤) (s + 1) r
33 then ((r - (s + 1)) ≪ (2%mc:Z), (s + 2) ≪ (1%mc:Z))
34 else (r ≪ (2%mc:Z), s ≪ (1%mc:Z))
35 end.
36
37 Instance: Proper (=) AQsqrt_loop.
38 Proof. intros x y E. change (x ≡ y) in E. now rewrite E. Qed.
39
40 Lemma AQsqrt_loop_invariant1 (n : nat) :
41 snd (AQsqrt_loop n) ^ (2%mc:N) + 4 * fst (AQsqrt_loop n) = 4 * 4 ^ n * a.
42 Proof.
43 rewrite nat_pow_2.
44 induction n; unfold pow; simpl.
45 ring.
46 revert IHn; case (AQsqrt_loop n); intros r s IHn.
47 case (decide_rel (≤) (s + 1) r); intros; simpl in *;
48 rewrite shiftl_1, shiftl_2, <-(associativity 4), <-IHn; ring.
49 Qed.
50
51 Lemma AQsqrt_loop_invariant2 (n : nat) :
52 fst (AQsqrt_loop n) ≤ 2 * snd (AQsqrt_loop n) + 4.
53 Proof.
54 induction n; simpl.
55 now setoid_replace (2 * 0 + 4) with 4 by ring.
56 revert IHn; case (AQsqrt_loop n); intros r s IHn.
57 case (decide_rel (≤) (s + 1) r); intros; simpl in *.
58 rewrite shiftl_1, shiftl_2.
59 setoid_replace (2 * (2 * (s + 2)) + 4) with (4 * ((2 * s + 4) - (s + 1))) by ring.
60 apply (order_preserving (4 *.)).
61 now apply (order_preserving (+ _)).
62 rewrite shiftl_1, shiftl_2.
63 setoid_replace (2 * (2 * s) + 4) with (4 * (s + 1)) by ring.
64 apply (order_preserving (4 *.)).
65 now apply orders.le_flip.
66 Qed.
67
68 Lemma AQsqrt_loop_snd_lower_bound (n z : nat) :
69 snd (AQsqrt_loop n) * 2 ^ z ≤ snd (AQsqrt_loop (z + n)).
70 Proof.
71 induction z; unfold pow; simpl.
72 apply orders.eq_le. ring.
73 revert IHz. case (AQsqrt_loop (z + n)); intros r s IHz.
74 case (decide_rel (≤) _); intros; simpl in *.
75 rewrite shiftl_1.
76 setoid_replace (snd (AQsqrt_loop n) * (2 * 2 ^ z)) with (2 * (snd (AQsqrt_loop n) * 2 ^ z)) by ring.
77 apply (order_preserving (2 *.)).
78 apply semirings.plus_le_compat_r; [solve_propholds | assumption].
79 rewrite shiftl_1.
80 setoid_replace (snd (AQsqrt_loop n) * (2 * 2 ^ z)) with (2 * (snd (AQsqrt_loop n) * 2 ^ z)) by ring.
81 now apply (order_preserving (2 *.)).
82 Qed.
83
84 Lemma AQsqrt_loop_snd_upper_bound (n z : nat) :
85 snd (AQsqrt_loop (z + n)) ≤ (snd (AQsqrt_loop n) + 4) * 2 ^ z - 4.
86 Proof.
87 induction z; unfold pow; simpl.
88 apply orders.eq_le. ring.
89 revert IHz. case (AQsqrt_loop (z + n)); intros r s IHz.
90 case (decide_rel (≤)); simpl; intros E.
91 rewrite shiftl_1.
92 setoid_replace ((snd (AQsqrt_loop n) + 4) * (2 * 2 ^ z) - 4) with (2 * ((snd (AQsqrt_loop n) + 4) * 2 ^ z - 4 + 2)) by ring.
93 apply (order_preserving (2 *.)).
94 now apply (order_preserving (+2)).
95 rewrite shiftl_1.
96 setoid_replace ((snd (AQsqrt_loop n) + 4) * (2 * 2 ^ z) - 4) with (2 * ((snd (AQsqrt_loop n) + 4) * 2 ^ z - 4 + 2)) by ring.
97 apply (order_preserving (2 *.)).
98 apply semirings.plus_le_compat_r; [solve_propholds | assumption].
99 Qed.
100
101 Lemma AQsqrt_loop_snd_nonneg (n : nat) : 0 ≤ snd (AQsqrt_loop n).
102 Proof.
103 rewrite <-(rings.plus_0_r n) at 1.
104 etransitivity.
105 2: apply AQsqrt_loop_snd_lower_bound.
106 simpl. apply orders.eq_le. ring.
107 Qed.
108
109 Lemma AQsqrt_loop_fst_nonneg (n : nat) : 0 ≤ fst (AQsqrt_loop n).
110 Proof.
111 induction n; simpl.
112 transitivity 1; [solve_propholds | easy].
113 revert IHn; case (AQsqrt_loop n); intros r s IHn.
114 case (decide_rel (≤) (s + 1) r); intros; simpl in *.
115 rewrite shiftl_2.
116 apply nonneg_mult_compat; [solve_propholds |].
117 now apply rings.flip_nonneg_minus.
118 rewrite shiftl_2.
119 now apply (nonneg_mult_compat _ _ _).
120 Qed.
121
122 Lemma AQsqrt_loop_fst_upper_bound (n : nat) :
123 fst (AQsqrt_loop n) ≤ 2 ^ (3 + n).
124 Proof with auto.
125 transitivity (2 * snd (AQsqrt_loop n) + 4).
126 apply AQsqrt_loop_invariant2.
127 change (2 ^ (3 + n)) with (2 * (2 * (2 * 2 ^ n))).
128 setoid_replace (2 * snd (AQsqrt_loop n) + 4) with (2 * (snd (AQsqrt_loop n) + 2)) by ring.
129 apply (order_preserving (2 *.)).
130 setoid_replace (2 * (2 * 2 ^ n)) with ((4 * 2 ^ n - 2) + 2) by ring.
131 apply (order_preserving (+ 2)).
132 transitivity (4 * 2 ^ n - 4).
133 rewrite <-(rings.plus_0_r n) at 1.
134 rewrite <-(rings.plus_0_l 4) at 1.
135 now apply AQsqrt_loop_snd_upper_bound.
136 apply semirings.plus_le_compat.
137 now rewrite commutativity.
138 now apply rings.flip_le_negate, semirings.le_2_4.
139 Qed.
140
141 Definition AQsqrt_mid_bounded_raw (n : N) := snd (AQsqrt_loop ('n)) ≪ -((1 + 'n)%mc : Z).
142
143 Instance AQsqrt_mid_bounded_raw_proper: Proper ((=) ==> (=)) AQsqrt_mid_bounded_raw.
144 Proof. intros x y E. change (x ≡ y) in E. now subst. Qed.
145
146 Lemma AQsqrt_mid_bounded_raw_lower_bound (n : N) :
147 0 ≤ AQsqrt_mid_bounded_raw n.
148 Proof. unfold AQsqrt_mid_bounded_raw. apply shiftl_nonneg, AQsqrt_loop_snd_nonneg. Qed.
149
150 Lemma AQsqrt_mid_bounded_raw_upper_bound (n : N) :
151 AQsqrt_mid_bounded_raw n ≤ 4.
152 Proof.
153 unfold AQsqrt_mid_bounded_raw.
154 apply (order_reflecting (≪ 1 + 'n)).
155 rewrite shiftl_reverse by ring.
156 etransitivity.
157 rewrite <-(rings.plus_0_r ('n)).
158 now apply AQsqrt_loop_snd_upper_bound.
159 simpl.
160 apply rings.nonneg_minus_compat; [solve_propholds|].
161 rewrite rings.plus_0_l, shiftl_S.
162 apply semirings.ge_1_mult_le_compat_l.
163 now apply semirings.le_1_2.
164 solve_propholds.
165 apply orders.eq_le.
166 now rewrite shiftl_nat_pow_alt, preserves_nat_pow_exp.
167 Qed.
168
169 Lemma AQsqrt_mid_bounded_regular_aux1 (n m : N) :
170 m ≤ n → AQsqrt_mid_bounded_raw n - AQsqrt_mid_bounded_raw m ≤ 1 ≪ (1 - 'm : Z).
171 Proof.
172 intros E.
173 apply naturals.nat_le_plus in E.
174 destruct E as [z E]. rewrite commutativity in E.
175 change (n ≡ z + m) in E. subst.
176 unfold AQsqrt_mid_bounded_raw.
177 rewrite rings.preserves_plus.
178 etransitivity.
179 apply semirings.plus_le_compat; [| reflexivity].
180 apply (order_preserving (≪ _)).
181 etransitivity.
182 now apply AQsqrt_loop_snd_upper_bound.
183 apply rings.nonneg_minus_compat; [solve_propholds | reflexivity].
184 apply orders.eq_le.
185 rewrite <-(shiftl_nat_pow_alt (f:=cast nat Z)).
186 rewrite (naturals.to_semiring_twice _ _ (cast N Z)).
187 rewrite <-shiftl_exp_plus, rings.preserves_plus.
188 mc_setoid_replace (('z - (1 + ('z + 'm)))%mc : Z) with ((-(1 + 'm))%mc : Z) by ring.
189 rewrite shiftl_base_plus. ring_simplify.
190 mc_setoid_replace ((1 - ' m)%mc : Z) with ((2 - (1 + 'm))%mc : Z) by ring.
191 now rewrite shiftl_exp_plus, shiftl_2, rings.mult_1_r.
192 Qed.
193
194 Lemma AQsqrt_mid_bounded_regular_aux2 (n m : N) :
195 n ≤ m → AQsqrt_mid_bounded_raw n ≤ AQsqrt_mid_bounded_raw m.
196 Proof.
197 intros E.
198 apply naturals.nat_le_plus in E.
199 destruct E as [z E]. rewrite commutativity in E.
200 change (m ≡ z + n) in E. subst.
201 unfold AQsqrt_mid_bounded_raw.
202 rewrite 2!rings.preserves_plus.
203 mc_setoid_replace ((-(1 + 'n))%mc : Z) with (('z - (1 + ('z + 'n)))%mc : Z) by ring.
204 rewrite shiftl_exp_plus.
205 apply (order_preserving (≪ _)).
206 rewrite shiftl_nat_pow_alt, <-(preserves_nat_pow_exp (f:=cast N nat)).
207 now apply AQsqrt_loop_snd_lower_bound.
208 Qed.
209
210 Lemma AQsqrt_mid_bounded_spec (n : N) :
211 (AQsqrt_mid_bounded_raw n ^ (2%mc:N)) = a - fst (AQsqrt_loop ('n)) ≪ -(2 * 'n).
212 Proof.
213 unfold AQsqrt_mid_bounded_raw.
214 rewrite shiftl_base_nat_pow, rings.preserves_2.
215 apply (injective (≪ (2 + 2 * 'n))).
216 rewrite shiftl_reverse by ring.
217 rewrite shiftl_base_plus, shiftl_negate, <-shiftl_exp_plus.
218 mc_setoid_replace ((-(2 * 'n) + (2 + 2 * 'n))%mc : Z) with (2%mc : Z) by ring.
219 rewrite shiftl_exp_plus, ?shiftl_2, <-shiftl_mult_l.
220 rewrite <-(rings.preserves_2 (f:=cast N Z)), <-rings.preserves_mult.
221 rewrite shiftl_nat_pow_alt, nat_pow_exp_mult.
222 rewrite (commutativity a), associativity.
223 rewrite <-(preserves_nat_pow_exp (f:=cast N nat) _ n).
224 setoid_replace (2 ^ 2) with 4 by (rewrite nat_pow_2; ring).
225 apply (right_cancellation (+) (4 * fst (AQsqrt_loop (' n)))).
226 rewrite AQsqrt_loop_invariant1. ring.
227 Qed.
228
229 Lemma AQsqrt_mid_bounded_raw_square_upper_bound (n : N) :
230 AQsqrt_mid_bounded_raw n ^ (2:N) ≤ a.
231 Proof.
232 rewrite AQsqrt_mid_bounded_spec.
233 apply rings.nonneg_minus_compat; [| reflexivity].
234 now apply shiftl_nonneg, AQsqrt_loop_fst_nonneg.
235 Qed.
236
237 Definition AQsqrt_mid_raw (ε : Qpos)
238 := AQsqrt_mid_bounded_raw (plus (N_of_Z (-Qdlog2 (proj1_sig ε))) 3).
239
240 Instance: Proper (QposEq ==> (=)) AQsqrt_mid_raw.
241 Proof. unfold AQsqrt_mid_raw. intros [x?] [y?] E. change (x = y) in E. simpl. now rewrite E. Qed.
242
243 Lemma AQsqrt_mid_bounded_prf: is_RegularFunction_noInf _ (AQsqrt_mid_raw : Qpos → AQ_as_MetricSpace).
244 Proof.
245 assert (∀ n m, m ≤ n → ball (2 ^ (-cast N Z m - 2))
246 (AQsqrt_mid_bounded_raw (n + 3) : AQ_as_MetricSpace) (AQsqrt_mid_bounded_raw (m + 3))).
247 intros n m E.
248 simpl. apply Qball_Qabs. rewrite Qabs.Qabs_pos.
249 change ('AQsqrt_mid_bounded_raw (n + 3) - 'AQsqrt_mid_bounded_raw (m + 3) ≤ ((2 ^ (-'m - 2))%mc : Q)).
250 rewrite <-rings.preserves_minus, <-(rings.mult_1_l (2 ^ (-'m - 2))).
251 rewrite <-shiftl_int_pow.
252 rewrite <-(rings.preserves_1 (f:=cast AQ Q)), <-(preserves_shiftl (f:=cast AQ Q)).
253 apply (order_preserving _).
254 mc_setoid_replace ((-'m - 2)%mc : Z) with ((1 - '(m + 3))%mc : Z).
255 apply AQsqrt_mid_bounded_regular_aux1.
256 now refine (order_preserving (+ (3%mc:N)) _ _ _).
257 rewrite rings.preserves_plus, rings.preserves_3. ring.
258 change (0 ≤ (('AQsqrt_mid_bounded_raw (n + 3) - 'AQsqrt_mid_bounded_raw (m + 3))%mc : Q)).
259 apply rings.flip_nonneg_minus.
260 apply (order_preserving _).
261 apply AQsqrt_mid_bounded_regular_aux2.
262 now refine (order_preserving (+ (3:N)) _ _ _).
263 assert (∀ ε1 ε2 : Qpos, N_of_Z (-Qdlog2 (proj1_sig ε2)) ≤ N_of_Z (-Qdlog2 (proj1_sig ε1)) →
264 ball (proj1_sig ε1 + proj1_sig ε2) (AQsqrt_mid_raw ε1 : AQ_as_MetricSpace) (AQsqrt_mid_raw ε2)).
265 { intros ε1 ε2 E.
266 unfold AQsqrt_mid_raw.
267 eapply ball_weak_le; auto.
268 change ((2%mc:Q) ^ (-'N_of_Z (-Qdlog2 (proj1_sig ε2)) - 2)
269 ≤ proj1_sig ε1 + proj1_sig ε2).
270 apply semirings.plus_le_compat_l.
271 now apply orders.lt_le, Qpos_ispos.
272 destruct (total (≤) (proj1_sig ε2) 1).
273 rewrite N_of_Z_nonneg.
274 change (- (-Qdlog2 (proj1_sig ε2))%Z) with (- -Qdlog2 (proj1_sig ε2)).
275 rewrite rings.negate_involutive.
276 rewrite int_pow_exp_plus by solve_propholds.
277 transitivity ((2 ^ Qdlog2 (proj1_sig ε2))%mc : Q).
278 2: now apply Qdlog2_spec, Qpos_ispos.
279 rewrite <-(rings.mult_1_r (2 ^ Qdlog2 (proj1_sig ε2) : Q)) at 2.
280 now apply (order_preserving (_ *.)).
281 change (0 ≤ -Qdlog2 (proj1_sig ε2)).
282 now apply rings.flip_nonpos_negate, Qdlog2_nonpos.
283 transitivity (1:Q); auto.
284 rewrite N_of_Z_nonpos; [easy|].
285 change (-Qdlog2 (proj1_sig ε2) ≤ 0).
286 now apply rings.flip_nonneg_negate, Qdlog2_nonneg. }
287 intros ε1 ε2.
288 destruct (total (≤) (N_of_Z (-Qdlog2 (proj1_sig ε1)))
289 (N_of_Z (-Qdlog2 (proj1_sig ε2)))); auto.
290 apply ball_sym.
291 rewrite Qplus_comm. auto.
292 Qed.
293
294 Definition AQsqrt_mid : AR := mkRegularFunction (0 : AQ_as_MetricSpace) AQsqrt_mid_bounded_prf.
295
296 Lemma AQsqrt_mid_upper_bound : AQsqrt_mid ≤ 4.
297 Proof.
298 intros ε.
299 transitivity (0 : Q).
300 apply rings.flip_nonneg_negate.
301 now apply orders.lt_le, Qpos_ispos.
302 change ((0:Q) ≤ '(4 - AQsqrt_mid_raw ((1#2) * ε))).
303 apply semirings.preserves_nonneg, rings.flip_nonneg_minus.
304 now apply AQsqrt_mid_bounded_raw_upper_bound.
305 Qed.
306
307 Lemma AQsqrt_mid_nonneg : 0 ≤ AQsqrt_mid.
308 Proof.
309 intros ε.
310 transitivity (0 : Q).
311 apply rings.flip_nonneg_negate.
312 now apply orders.lt_le, Qpos_ispos.
313 change ((0:Q) ≤ '(AQsqrt_mid_raw ((1#2) * ε) - 0)).
314 apply semirings.preserves_nonneg, rings.flip_nonneg_minus.
315 now apply AQsqrt_mid_bounded_raw_lower_bound.
316 Qed.
317
318 Lemma AQsqrt_mid_spec : AQsqrt_mid ^ (2:N)= 'a.
319 Proof.
320 assert (∀ ε, Qball (proj1_sig ε) ('(AQsqrt_mid_raw ε ^ (2:N))) ('a)) as P.
321 { intros ε. apply Qball_Qabs. rewrite Qabs.Qabs_neg.
322 eapply Qle_trans.
323 2: now apply Qpos_dlog2_spec.
324 change (-( '(AQsqrt_mid_raw ε ^ 2) - 'a) ≤ ((2 ^ Qdlog2 (proj1_sig ε))%mc : Q)).
325 rewrite <-rings.negate_swap_r.
326 unfold AQsqrt_mid_raw. rewrite AQsqrt_mid_bounded_spec.
327 rewrite rings.preserves_minus, preserves_shiftl. ring_simplify.
328 apply shiftl_le_flip_l.
329 etransitivity.
330 apply (order_preserving _).
331 now apply AQsqrt_loop_fst_upper_bound.
332 rewrite preserves_nat_pow, rings.preserves_2.
333 rewrite <-(int_pow_nat_pow (f:=cast nat Z)).
334 rewrite shiftl_int_pow, <-int_pow_exp_plus by solve_propholds.
335 apply int_pow_exp_le; [apply semirings.le_1_2|].
336 rewrite rings.preserves_plus, (naturals.to_semiring_twice _ _ (cast N Z)).
337 rewrite (rings.preserves_plus _ 3), !rings.preserves_3.
338 apply (order_reflecting (+ -(3 + 3))). ring_simplify.
339 destruct (total (≤) (proj1_sig ε) 1).
340 rewrite N_of_Z_nonneg.
341 apply orders.eq_le.
342 change (-Qdlog2 (proj1_sig ε) = 2 * -Qdlog2 (proj1_sig ε) + Qdlog2 (proj1_sig ε)).
343 ring.
344 change (0 ≤ -Qdlog2 (proj1_sig ε)).
345 now apply rings.flip_nonpos_negate, Qdlog2_nonpos.
346 rewrite N_of_Z_nonpos.
347 now apply Qdlog2_nonneg.
348 change (-Qdlog2 (proj1_sig ε) ≤ 0).
349 now apply rings.flip_nonneg_negate, Qdlog2_nonneg.
350 change ('(AQsqrt_mid_raw ε ^ 2) - 'a ≤ (0:Q)).
351 apply rings.flip_nonpos_minus.
352 apply (order_preserving _).
353 now apply AQsqrt_mid_bounded_raw_square_upper_bound. }
354 rewrite <-(ARpower_N_bounded_N_power _ _ 4).
355 - intros ε1 ε2. rewrite Qplus_0_r. simpl.
356 rewrite lattices.meet_r, lattices.join_r.
357 + apply ball_weak. apply Qpos_nonneg.
358 apply ball_weak_le with (proj1_sig (ε1 * Qpos_inv (8 # 1))%Qpos).
359 change ('ε1 / (8#1) ≤ 'ε1).
360 rewrite <-(rings.mult_1_r ('ε1)) at 2.
361 apply Qmult_le_l. apply Qpos_ispos. discriminate.
362 assert (QposEq (ε1 * Qpos_inv ((2#1) * Qpos_power (' 4) 1))
363 (ε1 * Qpos_inv (8#1))).
364 unfold QposEq. simpl.
365 pose proof AQposAsQpos_preserves_4.
366 unfold equiv, sig_equiv, equiv, stdlib_rationals.Q_eq in H5.
367 simpl. rewrite H5. reflexivity.
368 rewrite H5. apply P.
369 + transitivity (0:AQ).
370 apply rings.flip_nonneg_negate. now apply semirings.le_0_4.
371 now apply AQsqrt_mid_bounded_raw_lower_bound.
372 + now apply AQsqrt_mid_bounded_raw_upper_bound.
373 - split.
374 transitivity (0:AR).
375 apply rings.flip_nonneg_negate.
376 apply (semirings.preserves_nonneg (f:=cast AQ AR)).
377 now apply semirings.le_0_4.
378 now apply AQsqrt_mid_nonneg.
379 now apply AQsqrt_mid_upper_bound.
380 Qed.
381
382 Lemma AQsqrt_mid_correct : 'AQsqrt_mid = rational_sqrt ('a).
383 Proof.
384 apply rational_sqrt_unique.
385 apply semirings.preserves_nonneg.
386 red. transitivity 1; [solve_propholds | intuition].
387 change ('AQsqrt_mid ^ (2 : N) = cast Q CR (cast AQ Q a)).
388 rewrite <-preserves_nat_pow.
389 rewrite AQsqrt_mid_spec.
390 now apply ARtoCR_inject.
391 change (0%CR) with (0%mc : CR).
392 rewrite <-(rings.preserves_0 (f:=cast AR CR)).
393 apply (order_preserving _).
394 now apply AQsqrt_mid_nonneg.
395 Qed.
396 End sqrt_mid.
397
398 Section sqrt_pos.
399 Context `(Pa : 0 < a).
400
401 Local Obligation Tactic := idtac.
402 Program Definition AQsqrt_pos :=
403 let n := Qdlog4 ('a) in ARscale (1 ≪ n) (AQsqrt_mid (a:=a ≪ (2 * -n)) _).
404 Next Obligation.
405 simpl. split.
406 apply (order_reflecting (cast AQ Q)).
407 rewrite rings.preserves_1, aq_shift_correct.
408 rewrite int_pow_exp_mult.
409 change (2 ^ 2 : Q) with (4 : Q).
410 apply (order_reflecting (.* 4 ^ Qdlog4 ('a))).
411 rewrite <-associativity, <-int_pow_exp_plus by (compute; discriminate).
412 rewrite rings.mult_1_l, rings.plus_negate_l, int_pow_0, rings.mult_1_r.
413 apply Qdlog4_spec.
414 now apply semirings.preserves_pos.
415 apply (order_reflecting (cast AQ Q)).
416 rewrite aq_shift_correct, rings.preserves_4.
417 rewrite int_pow_exp_mult.
418 change (2 ^ 2 : Q) with (4 : Q).
419 apply (order_reflecting (.* 4 ^ Qdlog4 ('a))).
420 rewrite <-associativity, <-int_pow_exp_plus by (compute; discriminate).
421 rewrite rings.plus_negate_l, int_pow_0, rings.mult_1_r.
422 rewrite <-int_pow_S by (compute; discriminate).
423 apply orders.lt_le, Qdlog4_spec.
424 now apply semirings.preserves_pos.
425 Qed.
426
427 Lemma AQsqrt_pos_correct : 'AQsqrt_pos = rational_sqrt ('a).
428 Proof.
429 unfold AQsqrt_pos.
430 rewrite ARtoCR_preserves_scale, AQsqrt_mid_correct.
431 transitivity (scale (2 ^ Qdlog4 (' a))
432 (rational_sqrt (' (a ≪ (2 * - Qdlog4 (' a)))))).
433 apply Cmap_wd.
434 rewrite aq_shift_correct, rings.preserves_1, rings.mult_1_l.
435 reflexivity. reflexivity.
436 rewrite aq_shift_correct.
437 rewrite int_pow_exp_mult.
438 apply rational_sqrt_scale.
439 apply semirings.preserves_nonneg.
440 now apply orders.lt_le.
441 Qed.
442 End sqrt_pos.
443
444 Program Definition AQsqrt (a : AQ) : AR :=
445 if decide_rel (≤) a 0 then 0 else AQsqrt_pos (a:=a) _.
446 Next Obligation. now apply orders.not_le_lt_flip. Qed.
447
448 Lemma AQsqrt_correct (a : AQ) : 'AQsqrt a = rational_sqrt ('a).
449 Proof.
450 unfold AQsqrt.
451 case (decide_rel _); intros E.
452 rewrite rational_sqrt_nonpos.
453 now apply rings.preserves_0.
454 now apply semirings.preserves_nonpos.
455 now apply AQsqrt_pos_correct.
456 Qed.
457
458 Local Obligation Tactic := idtac.
459 Require Import CoRN.metric2.MetricMorphisms.
460
461 Program Definition ARsqrt_uc := unary_complete_uc
462 QPrelengthSpace (cast AQ Q_as_MetricSpace) AQsqrt sqrt_uc _.
463 Next Obligation. intros a. apply AQsqrt_correct. Qed.
464
465 Definition ARsqrt := Cbind AQPrelengthSpace ARsqrt_uc.
466
467 Lemma ARtoCR_preserves_sqrt (x : AR) : 'ARsqrt x = CRsqrt ('x).
468 Proof. apply preserves_unary_complete_fun. Qed.
469
470 Lemma ARsqrt_correct : forall (x : AR),
471 ARle 0 x -> ARsqrt x * ARsqrt x = x.
472 Proof.
473 intros x xpos.
474 apply (injective (Eembed QPrelengthSpace (cast AQ Q_as_MetricSpace))).
475 change (Eembed QPrelengthSpace (cast AQ Q_as_MetricSpace) x)
476 with ('x).
477 change (Eembed QPrelengthSpace (cast AQ Q_as_MetricSpace) (ARsqrt x * ARsqrt x))
478 with ('(ARsqrt x * ARsqrt x)).
479 rewrite (ARtoCR_preserves_mult (ARsqrt x) (ARsqrt x)).
480 rewrite ARtoCR_preserves_sqrt.
481 apply CRsqrt_sqr.
482 rewrite <- ARtoCR_preserves_0.
483 apply (ARtoCR_preserves_le 0 x), xpos.
484 Qed.
485
486 Lemma ARsqrt_mult : forall (x y : AR),
487 ARle 0 x -> ARle 0 y -> ARsqrt (x*y) = ARsqrt x * ARsqrt y.
488 Proof.
489 intros.
490 apply (injective (Eembed QPrelengthSpace (cast AQ Q_as_MetricSpace))).
491 change (Eembed QPrelengthSpace (cast AQ Q_as_MetricSpace) (ARsqrt (x*y)))
492 with ('(ARsqrt (x*y))).
493 change (Eembed QPrelengthSpace (cast AQ Q_as_MetricSpace) (ARsqrt x * ARsqrt y))
494 with ('(ARsqrt x * ARsqrt y)).
495 rewrite (ARtoCR_preserves_mult (ARsqrt x) (ARsqrt y)).
496 rewrite ARtoCR_preserves_sqrt.
497 rewrite ARtoCR_preserves_sqrt.
498 rewrite ARtoCR_preserves_sqrt.
499 rewrite <- CRsqrt_mult.
500 rewrite ARtoCR_preserves_mult. reflexivity.
501 rewrite <- ARtoCR_preserves_0.
502 apply (ARtoCR_preserves_le 0 x), H5.
503 rewrite <- ARtoCR_preserves_0.
504 apply (ARtoCR_preserves_le 0 y), H6.
505 Qed.
506
507 Lemma ARsqrt_srq_abs :
508 forall x : AR, ARsqrt (x*x) = ARabs x.
509 Proof.
510 (* Goal is a negation, use excluded middle x is positive or not.
511 When positive, ARsqrt(x*x) = ARsqrt x*ARsqrt x = x. *)
512 assert (forall x : AR, ARle 0 x -> ARsqrt (x*x) = ARabs x) as posCase.
513 { intros.
514 rewrite ARsqrt_mult, ARsqrt_correct.
515 rewrite ARabs_pos. reflexivity.
516 exact H5. exact H5.
517 exact H5. exact H5. }
518 intros. apply ball_stable.
519 intro abs. assert (~(ARle 0 x)).
520 - intro H5. contradict abs.
521 apply posCase, H5.
522 - contradict H5.
523 apply ARle_not_lt. intro H5.
524 contradict abs.
525 change (ARsqrt (x*x) = ARabs x).
526 rewrite <- ARabs_opp.
527 setoid_replace (x * x) with (-x * -x) by ring.
528 apply posCase.
529 destruct (ARtoCR_preserves_ltT x 0) as [c _].
530 specialize (c H5).
531 apply ARtoCR_preserves_le.
532 rewrite ARtoCR_preserves_0.
533 rewrite <- CRopp_0.
534 rewrite ARtoCR_preserves_opp.
535 apply CRopp_le_compat.
536 rewrite <- ARtoCR_preserves_0.
537 apply CRlt_le_weak, c.
538 Qed.
539
540 Lemma ARsqrt_inc :
541 forall x y : AR,
542 ARle 0 x -> ARle x y -> ARle (ARsqrt x) (ARsqrt y).
543 Proof.
544 intros.
545 apply ARtoCR_preserves_le.
546 rewrite ARtoCR_preserves_sqrt.
547 rewrite ARtoCR_preserves_sqrt.
548 apply CRsqrt_inc.
549 rewrite <- ARtoCR_preserves_0.
550 apply (ARtoCR_preserves_le 0 x), H5.
551 apply (ARtoCR_preserves_le x y), H6.
552 Qed.
553
554 End ARsqrt.