| 1 |
From Coq Require Import ZArith Qround Qpower. |
| 2 |
Require Import MathClasses.interfaces.abstract_algebra |
| 3 |
MathClasses.theory.nat_pow |
| 4 |
MathClasses.theory.int_pow |
| 5 |
CoRN.algebra.RSetoid |
| 6 |
CoRN.metric2.Metric |
| 7 |
CoRN.metric2.MetricMorphisms |
| 8 |
CoRN.metric2.UniformContinuity |
| 9 |
CoRN.model.totalorder.QMinMax |
| 10 |
CoRN.util.Qdlog |
| 11 |
CoRN.stdlib_omissions.Q |
| 12 |
CoRN.reals.fast.CRsin |
| 13 |
CoRN.reals.fast.CRstreams |
| 14 |
CoRN.reals.fast.CRAlternatingSum |
| 15 |
CoRN.reals.fast.Compress |
| 16 |
CoRN.reals.faster.ARAlternatingSum. |
| 17 |
Require Export |
| 18 |
CoRN.reals.faster.ARArith. |
| 19 |
|
| 20 |
Local Open Scope mc_scope. |
| 21 |
|
| 22 |
Section ARsin. |
| 23 |
Context `{AppRationals AQ}. |
| 24 |
|
| 25 |
Lemma AQmult_lt_0_compat : forall a b : AQ, 0 < a -> 0 < b -> 0 < a*b. |
| 26 |
Proof. |
| 27 |
intros. |
| 28 |
apply (strictly_order_reflecting (cast AQ Q)). |
| 29 |
pose proof (rings.preserves_0 (f:=cast AQ Q)). |
| 30 |
rewrite H7. |
| 31 |
rewrite rings.preserves_mult. |
| 32 |
rewrite <- (Qmult_0_l ('b)). |
| 33 |
apply Qmult_lt_compat_r. |
| 34 |
rewrite <- H7. |
| 35 |
apply (strictly_order_preserving (cast AQ Q)), H6. |
| 36 |
rewrite <- H7. |
| 37 |
apply (strictly_order_preserving (cast AQ Q)), H5. |
| 38 |
Qed. |
| 39 |
|
| 40 |
Lemma ZtoQ : forall n:positive, AQtoQ (ZtoAQ (Zpos n)) == (Zpos n#1). |
| 41 |
Proof. |
| 42 |
induction n. |
| 43 |
- change (Z.pos n~1) with (1+2*Z.pos n)%Z. |
| 44 |
pose proof (rings.preserves_plus (f:=cast Z AQ) 1 (2*Z.pos n)). |
| 45 |
rewrite H5. clear H5. |
| 46 |
rewrite rings.preserves_plus, rings.preserves_1. |
| 47 |
rewrite rings.preserves_1. |
| 48 |
pose proof (rings.preserves_mult (f:=cast Z AQ) 2 (Z.pos n)). |
| 49 |
rewrite H5. clear H5. |
| 50 |
rewrite rings.preserves_mult, IHn. |
| 51 |
rewrite rings.preserves_2, rings.preserves_2. |
| 52 |
unfold Qeq; simpl. rewrite Pos.mul_1_r. reflexivity. |
| 53 |
- change (Z.pos n~0) with (2*Z.pos n)%Z. |
| 54 |
pose proof (rings.preserves_mult (f:=cast Z AQ) 2 (Z.pos n)). |
| 55 |
rewrite H5. |
| 56 |
rewrite rings.preserves_mult, IHn. |
| 57 |
rewrite rings.preserves_2. |
| 58 |
pose proof (rings.preserves_2 (f:=cast AQ Q)). |
| 59 |
rewrite H6. reflexivity. |
| 60 |
- pose proof (rings.preserves_1 (f:=cast Z AQ)). |
| 61 |
rewrite H5. rewrite rings.preserves_1. reflexivity. |
| 62 |
Qed. |
| 63 |
|
| 64 |
Local Open Scope uc_scope. |
| 65 |
|
| 66 |
|
| 67 |
Section sin_small. |
| 68 |
(* First define (sin a) as a decreasing alternating series on the segment [-1,1]. |
| 69 |
a = num/den and -1 <= a <= 1. *) |
| 70 |
|
| 71 |
Context {num den : AQ} (Pnd : -den ≤ num ≤ den) (dpos : 0 < den). |
| 72 |
|
| 73 |
(* |
| 74 |
Split the stream |
| 75 |
(-1)^i a^(2i+1) / (2i+1)! |
| 76 |
up into the streams |
| 77 |
(-1)^i a^(2i+1) and (2i+1)! |
| 78 |
because we do not have exact division |
| 79 |
*) |
| 80 |
Definition ARsinStream (px : positive*(AQ*AQ)) : AQ*AQ |
| 81 |
:= (- fst (snd px) * num * num, |
| 82 |
snd (snd px) * den * den * ZtoAQ (Zpos (fst px)~0) * ZtoAQ (Zpos (fst px)~1)). |
| 83 |
|
| 84 |
Lemma sinStream_pos : ∀ x : positive * (AQ * AQ), |
| 85 |
0 < snd (snd x) → 0 < snd (ARsinStream x). |
| 86 |
Proof. |
| 87 |
assert (0 = ZtoAQ 0) as zero_int. |
| 88 |
{ destruct H4. destruct aq_ints_mor, semiringmor_plus_mor. |
| 89 |
rewrite preserves_mon_unit. reflexivity. } |
| 90 |
intros. destruct x; simpl. |
| 91 |
simpl in H5. |
| 92 |
apply AQmult_lt_0_compat. |
| 93 |
apply AQmult_lt_0_compat. |
| 94 |
apply AQmult_lt_0_compat. |
| 95 |
apply AQmult_lt_0_compat. |
| 96 |
exact H5. exact dpos. exact dpos. |
| 97 |
rewrite zero_int. |
| 98 |
apply (strictly_order_preserving (cast Z AQ)). |
| 99 |
reflexivity. |
| 100 |
rewrite zero_int. |
| 101 |
apply (strictly_order_preserving (cast Z AQ)). |
| 102 |
reflexivity. |
| 103 |
Qed. |
| 104 |
|
| 105 |
Lemma sinStream_correct : ∀ p : positive, |
| 106 |
Str_pth _ (sinStream (AQtoQ num / AQtoQ den)) |
| 107 |
p (1%positive, AQtoQ num / AQtoQ den) |
| 108 |
== let (_, r) := iterate _ (fS ARsinStream) p (1%positive, (num, den)) in |
| 109 |
AQtoQ (fst r) / AQtoQ (snd r). |
| 110 |
Proof. |
| 111 |
assert (forall n:Z, AQtoQ (ZtoAQ n) == (n#1)). |
| 112 |
{ intro n. destruct n as [|n|n]. |
| 113 |
pose proof (rings.preserves_0 (f:=cast Z AQ)). rewrite H5. clear H5. |
| 114 |
rewrite rings.preserves_0. reflexivity. |
| 115 |
apply ZtoQ. change (Z.neg n) with (-Z.pos n)%Z. |
| 116 |
pose proof (rings.preserves_negate (f:=cast Z AQ)). |
| 117 |
rewrite H5. clear H5. rewrite rings.preserves_negate. |
| 118 |
rewrite ZtoQ. reflexivity. } |
| 119 |
apply Pos.peano_ind. |
| 120 |
- unfold Str_pth. simpl. |
| 121 |
do 6 rewrite rings.preserves_mult. |
| 122 |
rewrite rings.preserves_negate. |
| 123 |
rewrite H5, H5. |
| 124 |
unfold dec_recip, stdlib_rationals.Q_recip. |
| 125 |
unfold mult, stdlib_rationals.Q_mult. |
| 126 |
unfold negate, stdlib_rationals.Q_opp. |
| 127 |
field. intro abs. |
| 128 |
apply (strictly_order_preserving (cast AQ Q)) in dpos. |
| 129 |
rewrite rings.preserves_0, abs in dpos. |
| 130 |
exact (Qlt_irrefl 0 dpos). |
| 131 |
- intros p IHp. unfold Str_pth. unfold Str_pth in IHp. |
| 132 |
rewrite iterate_succ, iterate_succ. |
| 133 |
pose proof (sinStream_fst (AQtoQ num / AQtoQ den) p) as H7. |
| 134 |
unfold dec_recip, stdlib_rationals.Q_recip. |
| 135 |
unfold dec_recip, stdlib_rationals.Q_recip in IHp. |
| 136 |
unfold mult, stdlib_rationals.Q_mult. |
| 137 |
unfold mult, stdlib_rationals.Q_mult in IHp. |
| 138 |
unfold Qdiv in H7. unfold Qdiv. |
| 139 |
unfold Qdiv in IHp. |
| 140 |
unfold Q_as_MetricSpace, msp_car. |
| 141 |
unfold Q_as_MetricSpace, msp_car in IHp. |
| 142 |
destruct (iterate _ (sinStream (AQtoQ num * / AQtoQ den)%Q) p |
| 143 |
(1%positive, (AQtoQ num * / AQtoQ den)%Q)). |
| 144 |
simpl in H7. simpl in IHp. subst p0. |
| 145 |
unfold sinStream, snd, fst. rewrite IHp. clear IHp. |
| 146 |
pose proof (fS_fst ARsinStream p (num, den)). |
| 147 |
destruct (iterate _ (fS ARsinStream) p (1%positive, (num, den))) as [p0 p1]. |
| 148 |
simpl in H6. simpl. subst p0. |
| 149 |
do 6 rewrite rings.preserves_mult. |
| 150 |
rewrite rings.preserves_negate. |
| 151 |
unfold mult, stdlib_rationals.Q_mult. |
| 152 |
unfold negate, stdlib_rationals.Q_opp. |
| 153 |
rewrite ZtoQ, ZtoQ. |
| 154 |
rewrite <- (Qmult_assoc (AQtoQ (snd p1) * AQtoQ den * AQtoQ den)). |
| 155 |
rewrite Qinv_mult_distr. |
| 156 |
setoid_replace (/ ((Z.pos (Pos.succ p)~0 # 1) * (Z.pos (Pos.succ p)~1 # 1))) |
| 157 |
with (1 # (Pos.succ p * (Pos.succ p)~1)~0) by reflexivity. |
| 158 |
do 2 rewrite Qinv_mult_distr. ring. |
| 159 |
Qed. |
| 160 |
|
| 161 |
Lemma AQsin_small_Qprf : -1 ≤ AQtoQ num / AQtoQ den ≤ 1. |
| 162 |
Proof. |
| 163 |
split. |
| 164 |
- apply Qle_shift_div_l. |
| 165 |
pose proof (rings.preserves_0 (f:=cast AQ Q)). |
| 166 |
rewrite <- H5. |
| 167 |
apply (strictly_order_preserving (cast AQ Q)), dpos. |
| 168 |
setoid_replace (-1 * AQtoQ den) with (-AQtoQ den) by reflexivity. |
| 169 |
rewrite <- rings.preserves_negate. |
| 170 |
apply (order_preserving (cast AQ Q)), Pnd. |
| 171 |
- apply Qle_shift_div_r. |
| 172 |
pose proof (rings.preserves_0 (f:=cast AQ Q)). |
| 173 |
rewrite <- H5. |
| 174 |
apply (strictly_order_preserving (cast AQ Q)), dpos. |
| 175 |
rewrite Qmult_1_l. |
| 176 |
apply (order_preserving (cast AQ Q)), Pnd. |
| 177 |
Qed. |
| 178 |
|
| 179 |
Definition AQsin_small : msp_car AR |
| 180 |
:= CRtoAR (inject_Q_CR (AQtoQ num / AQtoQ den)) |
| 181 |
+ AltSeries ARsinStream sinStream_pos |
| 182 |
positive (CRsin.sinStream (AQtoQ num / AQtoQ den)) |
| 183 |
(num,den) (xH,AQtoQ num / AQtoQ den) sinStream_correct _ |
| 184 |
(sinStream_alt AQsin_small_Qprf) |
| 185 |
dpos (sinStream_zl AQsin_small_Qprf). |
| 186 |
|
| 187 |
Lemma AQsin_small_correct : 'AQsin_small = rational_sin (AQtoQ num / AQtoQ den). |
| 188 |
Proof. |
| 189 |
rewrite rational_sin_correct, |
| 190 |
<- (rational_sin_small_correct AQsin_small_Qprf). |
| 191 |
unfold AQsin_small, rational_sin_small. |
| 192 |
rewrite ARtoCR_preserves_plus. |
| 193 |
apply ucFun2_wd. |
| 194 |
pose proof CRAR_id. unfold cast in H5. |
| 195 |
unfold cast. rewrite H5. |
| 196 |
reflexivity. |
| 197 |
apply AltSeries_correct. |
| 198 |
Qed. |
| 199 |
|
| 200 |
End sin_small. |
| 201 |
|
| 202 |
Lemma AQsin_small_pos_wd : |
| 203 |
forall (n1 n2 d1 d2 : AQ) (p1 : -d1 ≤ n1 ≤ d1) (p2 : -d2 ≤ n2 ≤ d2) |
| 204 |
(d1pos : 0 < d1) (d2pos : 0 < d2), |
| 205 |
n1 = n2 |
| 206 |
-> d1 = d2 |
| 207 |
-> AQsin_small p1 d1pos = AQsin_small p2 d2pos. |
| 208 |
Proof. |
| 209 |
assert (forall x y, ARtoCR x = ARtoCR y -> x = y) as H5. |
| 210 |
{ intros x y H5. exact H5. } |
| 211 |
intros. apply H5. |
| 212 |
rewrite (AQsin_small_correct p1 d1pos). |
| 213 |
rewrite (AQsin_small_correct p2 d2pos). |
| 214 |
rewrite H6, H7. reflexivity. |
| 215 |
Qed. |
| 216 |
|
| 217 |
(** Sine's range can then be extended to [[0,3^n]] by [n] applications |
| 218 |
of the identity [sin(x) = 3*sin(x/3) - 4*(sin(x/3))^3]. *) |
| 219 |
Definition AQsin_poly_fun (x : AQ) : AQ := x * (3 - 4 * x ^ (2%mc:N)). |
| 220 |
|
| 221 |
Lemma AQsin_poly_fun_correct (q : AQ) : |
| 222 |
'AQsin_poly_fun q = sin_poly_fun ('q). |
| 223 |
Proof. |
| 224 |
unfold AQsin_poly_fun, sin_poly_fun. |
| 225 |
rewrite nat_pow_2. |
| 226 |
rewrite rings.preserves_mult, rings.preserves_minus, ?rings.preserves_mult. |
| 227 |
rewrite rings.preserves_3, rings.preserves_4. |
| 228 |
now rewrite <-(associativity _ ('q) ('q : Q)). |
| 229 |
Qed. |
| 230 |
|
| 231 |
(* AQsin_poly_fun is not uniformly continuous because of x^3, but it will |
| 232 |
only be applied to sine values in [-1,1], a range on which it is |
| 233 |
uniformly continuous. *) |
| 234 |
Lemma AQsin_poly_fun_bound_correct |
| 235 |
: forall q : AQ, msp_eq (' AQsin_poly_fun (ucFun (AQboundAbs_uc 1) q)) |
| 236 |
(sin_poly_fun (Qmax (- (1)) (Qmin 1 (' q)))). |
| 237 |
Proof. |
| 238 |
intro q. apply Qball_0. |
| 239 |
rewrite AQsin_poly_fun_correct. |
| 240 |
f_equiv. |
| 241 |
unfold AQboundAbs_uc. simpl. |
| 242 |
change ('1) with (1:AQ). |
| 243 |
rewrite ?aq_preserves_max, ?aq_preserves_min. |
| 244 |
now rewrite ?rings.preserves_negate, ?rings.preserves_1. |
| 245 |
Qed. |
| 246 |
|
| 247 |
Definition AQsin_poly_uc : msp_car (AQ_as_MetricSpace --> AQ_as_MetricSpace) |
| 248 |
:= unary_uc (cast AQ (msp_car Q_as_MetricSpace)) |
| 249 |
(λ q : AQ, AQsin_poly_fun (ucFun (AQboundAbs_uc 1) q)) |
| 250 |
sin_poly_uc AQsin_poly_fun_bound_correct. |
| 251 |
|
| 252 |
Definition ARsin_poly : msp_car (AR --> AR) |
| 253 |
:= uc_compose ARcompress (Cmap AQPrelengthSpace AQsin_poly_uc). |
| 254 |
|
| 255 |
Lemma ARtoCR_preserves_sin_poly (x : msp_car AR) |
| 256 |
: 'ucFun ARsin_poly x = ucFun sin_poly ('x). |
| 257 |
Proof. |
| 258 |
change ('ucFun ARcompress (ucFun (Cmap AQPrelengthSpace AQsin_poly_uc) x) |
| 259 |
= ucFun compress (ucFun (Cmap QPrelengthSpace sin_poly_uc) ('x))). |
| 260 |
rewrite ARcompress_correct, compress_correct. |
| 261 |
now apply preserves_unary_fun. |
| 262 |
Qed. |
| 263 |
|
| 264 |
(* When x = sin y, this function computes sin (y*3^n). *) |
| 265 |
Fixpoint ARsin_poly_iter (n : nat) (x : msp_car AR) : msp_car AR := |
| 266 |
match n with |
| 267 |
| O => x |
| 268 |
| S n' => ucFun ARsin_poly (ARsin_poly_iter n' x) |
| 269 |
end. |
| 270 |
|
| 271 |
Definition AQsin_bounded {n : nat} {num den : AQ} |
| 272 |
(Pnd : - (den * 3^n) ≤ num ≤ den * 3^n) |
| 273 |
(dpos : 0 < den * 3^n) : msp_car AR |
| 274 |
:= ARsin_poly_iter n (AQsin_small Pnd dpos). |
| 275 |
|
| 276 |
Lemma ARsin_poly_iter_wd : forall n x y, |
| 277 |
x = y -> ARsin_poly_iter n x = ARsin_poly_iter n y. |
| 278 |
Proof. |
| 279 |
induction n. |
| 280 |
- intros. exact H5. |
| 281 |
- intros. |
| 282 |
change (ucFun ARsin_poly (ARsin_poly_iter n x) |
| 283 |
= ucFun ARsin_poly (ARsin_poly_iter n y)). |
| 284 |
rewrite (IHn x y H5). |
| 285 |
reflexivity. |
| 286 |
Qed. |
| 287 |
|
| 288 |
Lemma AQsin_bounded_correct {n : nat} {num den : AQ} |
| 289 |
(Pnd : -(den * 3^n) ≤ num ≤ den * 3^n) (dpos : 0 < den * 3^n) : |
| 290 |
'AQsin_bounded Pnd dpos = rational_sin ('num / 'den). |
| 291 |
Proof. |
| 292 |
revert num den dpos Pnd. |
| 293 |
induction n; intros. |
| 294 |
- unfold AQsin_bounded. simpl. |
| 295 |
rewrite AQsin_small_correct. |
| 296 |
change (3^0%nat) with 1. |
| 297 |
rewrite rings.mult_1_r. reflexivity. |
| 298 |
- unfold AQsin_bounded. |
| 299 |
change (' ucFun ARsin_poly (ARsin_poly_iter n (AQsin_small Pnd dpos)) |
| 300 |
= rational_sin (' num / ' den)). |
| 301 |
rewrite ARtoCR_preserves_sin_poly. |
| 302 |
unfold AQsin_bounded in IHn. |
| 303 |
assert (le (-(den * 3 * 3 ^ n)) num /\ num ≤ den * 3 * 3 ^ n) as H5. |
| 304 |
{ rewrite <- (associativity den 3). exact Pnd. } |
| 305 |
assert (0 < den * 3 * 3 ^ n) as H6. |
| 306 |
{ rewrite <- (associativity den 3). exact dpos. } |
| 307 |
setoid_replace (ARsin_poly_iter n (AQsin_small Pnd dpos)) |
| 308 |
with (ARsin_poly_iter n (AQsin_small H5 H6)). |
| 309 |
rewrite IHn. |
| 310 |
change (Qdiv ('num) ('(den * 3))) with (('num : Q) / '(den * 3)). |
| 311 |
rewrite rings.preserves_mult, rings.preserves_3. |
| 312 |
rewrite dec_fields.dec_recip_distr, associativity. |
| 313 |
apply rational_sin_poly. |
| 314 |
apply ARsin_poly_iter_wd. |
| 315 |
apply AQsin_small_pos_wd. reflexivity. |
| 316 |
rewrite <- (associativity den 3). reflexivity. |
| 317 |
Qed. |
| 318 |
|
| 319 |
Definition AQsin_bound (a : AQ) : nat := CRsin.sin_bound ('a). |
| 320 |
|
| 321 |
Lemma AQsin_bound_correct : forall (a:AQ), |
| 322 |
-(1 * 3 ^ AQsin_bound a) ≤ a ≤ 1 * 3 ^ AQsin_bound a. |
| 323 |
Proof. |
| 324 |
intro a. unfold AQsin_bound. |
| 325 |
pose proof (CRsin.sin_bound_correct ('a)). |
| 326 |
split; apply (order_reflecting (cast AQ Q)). |
| 327 |
- rewrite rings.preserves_negate. |
| 328 |
destruct H4, aq_ring, ring_monoid. |
| 329 |
destruct commonoid_mon. rewrite monoid_left_id. |
| 330 |
rewrite preserves_nat_pow. |
| 331 |
rewrite rings.preserves_3. |
| 332 |
rewrite <-(int_pow_nat_pow (f:=cast nat Z)). |
| 333 |
rewrite <- (Zpower_Qpower 3). |
| 334 |
apply H5. apply (Nat2Z.inj_le 0), Nat.le_0_l. |
| 335 |
- destruct H4, aq_ring, ring_monoid. |
| 336 |
destruct commonoid_mon. rewrite monoid_left_id. |
| 337 |
rewrite preserves_nat_pow. |
| 338 |
rewrite rings.preserves_3. |
| 339 |
rewrite <-(int_pow_nat_pow (f:=cast nat Z)). |
| 340 |
rewrite <- (Zpower_Qpower 3). |
| 341 |
apply H5. apply (Nat2Z.inj_le 0), Nat.le_0_l. |
| 342 |
Qed. |
| 343 |
|
| 344 |
Lemma AQsin_bound_pos : forall a, 0 < 1 * 3 ^ AQsin_bound a. |
| 345 |
Proof. |
| 346 |
intro a. |
| 347 |
destruct H4, aq_ring, ring_monoid. |
| 348 |
destruct commonoid_mon. rewrite monoid_left_id. |
| 349 |
apply (strictly_order_reflecting (cast AQ Q)). |
| 350 |
rewrite preserves_nat_pow. |
| 351 |
rewrite rings.preserves_3. |
| 352 |
rewrite <- (int_pow_nat_pow (f:=cast nat Z)). |
| 353 |
rewrite rings.preserves_0. |
| 354 |
apply (Qpower_0_lt 3 (Z.of_nat (AQsin_bound a))). |
| 355 |
reflexivity. |
| 356 |
Qed. |
| 357 |
|
| 358 |
Definition AQsin (a:AQ) : msp_car AR |
| 359 |
:= AQsin_bounded (AQsin_bound_correct a) (AQsin_bound_pos a). |
| 360 |
|
| 361 |
Lemma AQsin_correct : forall a, 'AQsin a = rational_sin ('a). |
| 362 |
Proof. |
| 363 |
intro a. |
| 364 |
mc_setoid_replace ('a : Q) with (('a / '1)%mc : Q). |
| 365 |
now apply AQsin_bounded_correct. |
| 366 |
rewrite rings.preserves_1, dec_fields.dec_recip_1. |
| 367 |
rewrite Qmult_1_r. reflexivity. |
| 368 |
Qed. |
| 369 |
|
| 370 |
Lemma AQsin_prf {a : AQ} (pA : ¬0 ≤ a) : 0 ≤ -a. |
| 371 |
Proof. apply rings.flip_nonpos_negate. now apply orders.le_flip. Qed. |
| 372 |
|
| 373 |
Definition ARsin_uc : msp_car (AQ_as_MetricSpace --> AR) |
| 374 |
:= unary_complete_uc |
| 375 |
QPrelengthSpace (cast AQ (msp_car Q_as_MetricSpace)) AQsin sin_uc AQsin_correct. |
| 376 |
|
| 377 |
Definition ARsin : msp_car (AR --> AR) |
| 378 |
:= Cbind AQPrelengthSpace ARsin_uc. |
| 379 |
|
| 380 |
Lemma ARtoCR_preserves_sin x : ' ucFun ARsin x = ucFun sin_slow ('x). |
| 381 |
Proof. apply preserves_unary_complete_fun. Qed. |
| 382 |
|
| 383 |
End ARsin. |