| 1 |
From Coq Require Import ZArith. |
| 2 |
Require Import CoRN.algebra.RSetoid. |
| 3 |
Require Import CoRN.metric2.Metric. |
| 4 |
Require Import CoRN.metric2.UniformContinuity. |
| 5 |
From Coq Require Import Program. |
| 6 |
Require Import MathClasses.misc.workaround_tactics |
| 7 |
CoRN.model.totalorder.QposMinMax |
| 8 |
CoRN.model.totalorder.QMinMax. |
| 9 |
From Coq Require Import Qround Qabs. |
| 10 |
Require Import CoRN.util.Qdlog CoRN.stdlib_omissions.Q |
| 11 |
CoRN.reals.fast.CRexp CoRN.reals.fast.CRstreams CoRN.reals.fast.CRAlternatingSum |
| 12 |
CoRN.reals.fast.Compress CoRN.reals.fast.CRpower |
| 13 |
CoRN.metric2.MetricMorphisms CoRN.reals.faster.ARAlternatingSum MathClasses.interfaces.abstract_algebra |
| 14 |
MathClasses.orders.minmax MathClasses.theory.nat_pow MathClasses.theory.int_pow. |
| 15 |
Require Export |
| 16 |
CoRN.reals.faster.ARArith. |
| 17 |
|
| 18 |
Section ARexp. |
| 19 |
Context `{AppRationals AQ}. |
| 20 |
|
| 21 |
Section exp_small_neg. |
| 22 |
Context {a : AQ} (Pa : -1 ≤ a ≤ 0). |
| 23 |
|
| 24 |
(* |
| 25 |
Split the stream |
| 26 |
(-a)^i / i! |
| 27 |
up into the streams |
| 28 |
(-a)^i and i! |
| 29 |
because we do not have exact division |
| 30 |
*) |
| 31 |
Definition ARexpStream (px : positive*(AQ*AQ)) : AQ*AQ |
| 32 |
:= (fst (snd px) * a, snd (snd px) * ZtoAQ (Zpos (fst px))). |
| 33 |
|
| 34 |
Lemma AQexp_small_neg_prf : -1 ≤ ('a : Q) ≤ 0. |
| 35 |
Proof. |
| 36 |
split. |
| 37 |
now apply rings.preserves_ge_negate1. |
| 38 |
now apply semirings.preserves_nonpos. |
| 39 |
Qed. |
| 40 |
|
| 41 |
(* |
| 42 |
The ARInfAltSum function computes the infinite alternating sum |
| 43 |
and takes care of: |
| 44 |
- Computing the length of the partial sum |
| 45 |
- Computing the precision of the approximate division |
| 46 |
*) |
| 47 |
Lemma expStream_pos : ∀ x : positive * (AQ * AQ), |
| 48 |
0 < snd (snd x) → 0 < snd (ARexpStream x). |
| 49 |
Proof. |
| 50 |
intros. unfold ARexpStream. simpl. |
| 51 |
assert (AQtoQ 0 == 0). |
| 52 |
apply rings.preserves_0. |
| 53 |
destruct aq_strict_order_embed. |
| 54 |
apply strict_order_embedding_reflecting. |
| 55 |
rewrite rings.preserves_mult, rings.preserves_0. |
| 56 |
apply (Qle_lt_trans _ (AQtoQ (snd (snd x)) * 0)). |
| 57 |
rewrite Qmult_0_r. apply Qle_refl. |
| 58 |
apply Qmult_lt_l. |
| 59 |
rewrite <- H6. apply strict_order_embedding_preserving, H5. |
| 60 |
pose proof AQtoQ_ZtoAQ. |
| 61 |
unfold cast in H7. rewrite H7. |
| 62 |
reflexivity. |
| 63 |
Qed. |
| 64 |
|
| 65 |
Lemma AQ0_lt_1 : 0 < 1. |
| 66 |
Proof. |
| 67 |
destruct aq_strict_order_embed. |
| 68 |
apply strict_order_embedding_reflecting. |
| 69 |
rewrite rings.preserves_0, rings.preserves_1. |
| 70 |
reflexivity. |
| 71 |
Qed. |
| 72 |
|
| 73 |
Lemma expStream_correct : ∀ p : positive, |
| 74 |
Str_pth _ (CRexp.expStream (AQtoQ a)) p (1%positive, 1%Q) |
| 75 |
== let (_, r) := iterate _ (fS ARexpStream) p (1%positive, (1, 1)) in |
| 76 |
AQtoQ (fst r) / AQtoQ (snd r). |
| 77 |
Proof. |
| 78 |
apply Pos.peano_ind. |
| 79 |
- unfold Str_pth. simpl. |
| 80 |
rewrite Qmult_1_l, Qmult_1_r. |
| 81 |
rewrite rings.mult_1_l, rings.mult_1_l. |
| 82 |
pose proof (AQtoQ_ZtoAQ 1). |
| 83 |
unfold cast in H5. rewrite H5. |
| 84 |
unfold stdlib_rationals.inject_Z_Q, inject_Z. |
| 85 |
unfold Qdiv. rewrite Qmult_1_r. reflexivity. |
| 86 |
- intros. unfold Str_pth. |
| 87 |
rewrite iterate_succ, iterate_succ. |
| 88 |
unfold Str_pth in H5. |
| 89 |
pose proof (fS_fst ARexpStream p (1,1)). |
| 90 |
pose proof (expStream_fst (AQtoQ a) p). |
| 91 |
destruct (iterate _ (CRexp.expStream (AQtoQ a)) p (1%positive, 1%Q)) as [u v]. |
| 92 |
destruct (iterate (positive * (AQ * AQ)) (fS ARexpStream) p (1%positive, (1, 1))). |
| 93 |
unfold snd in H5 at 1. simpl. |
| 94 |
unfold fst in H6. subst p0. |
| 95 |
rewrite H5. unfold fst in H7. clear H5 v. |
| 96 |
subst u. |
| 97 |
assert (forall i j : AQ, AQtoQ (i*j) == AQtoQ i * AQtoQ j). |
| 98 |
{ intros. rewrite rings.preserves_mult. reflexivity. } |
| 99 |
rewrite H5, H5. unfold Qdiv. |
| 100 |
rewrite Qinv_mult_distr. |
| 101 |
pose proof (AQtoQ_ZtoAQ). |
| 102 |
unfold cast in H6. rewrite H6. |
| 103 |
unfold stdlib_rationals.inject_Z_Q, inject_Z. |
| 104 |
setoid_replace (/ (Z.pos (Pos.succ p) # 1))%Q with (1#Pos.succ p). |
| 105 |
ring. reflexivity. |
| 106 |
Qed. |
| 107 |
|
| 108 |
Definition AQexp_small_neg : AR |
| 109 |
:= 1+ AltSeries ARexpStream expStream_pos |
| 110 |
positive (CRexp.expStream (AQtoQ a)) |
| 111 |
(1,1) (xH,1) expStream_correct _ |
| 112 |
(expStream_alt AQexp_small_neg_prf) |
| 113 |
AQ0_lt_1 (expStream_zl AQexp_small_neg_prf). |
| 114 |
|
| 115 |
Lemma AQexp_small_neg_correct |
| 116 |
: 'AQexp_small_neg = rational_exp_small_neg AQexp_small_neg_prf. |
| 117 |
Proof. |
| 118 |
unfold AQexp_small_neg, rational_exp_small_neg. |
| 119 |
rewrite ARtoCR_preserves_plus. |
| 120 |
rewrite ARtoCR_preserves_1. |
| 121 |
rewrite <- CRplus_translate. |
| 122 |
apply ucFun2_wd. reflexivity. |
| 123 |
apply AltSeries_correct. |
| 124 |
Qed. |
| 125 |
|
| 126 |
End exp_small_neg. |
| 127 |
|
| 128 |
(* |
| 129 |
Implement the range reduction |
| 130 |
exp(x) = exp(x/2) ^ 2 |
| 131 |
*) |
| 132 |
Fixpoint ARpower_2_iter (n : nat) (x : AR) : AR := |
| 133 |
match n with |
| 134 |
| O => x |
| 135 |
| S p => ARpower_N_bounded 2 1 (ARcompress (ARpower_2_iter p x)) |
| 136 |
end. |
| 137 |
|
| 138 |
Lemma ARpower_2_iter_wd : forall (n : nat) (x y : AR), |
| 139 |
x = y -> ARpower_2_iter n x = ARpower_2_iter n y. |
| 140 |
Proof. |
| 141 |
induction n. |
| 142 |
- intros. exact H5. |
| 143 |
- intros. simpl. apply Cmap_wd. reflexivity. |
| 144 |
pose proof ARcompress_correct. |
| 145 |
simpl in H6. |
| 146 |
rewrite H6, H6. |
| 147 |
apply IHn, H5. |
| 148 |
Qed. |
| 149 |
|
| 150 |
Lemma AQexp_neg_bounded_correct : ∀ (n : nat) a (abound : -1 ≤ a * (1 ≪ (-1)) ^ n ≤ 0), |
| 151 |
a ≤ 0 -> |
| 152 |
' ARpower_2_iter n (AQexp_small_neg abound) = rational_exp (' a). |
| 153 |
Proof. |
| 154 |
induction n. |
| 155 |
- intros. simpl. |
| 156 |
rewrite AQexp_small_neg_correct. |
| 157 |
rewrite rational_exp_small_neg_correct. |
| 158 |
rewrite rational_exp_correct. |
| 159 |
apply CRIR.IRasCR_wd, Exponential.Exp_wd. |
| 160 |
apply Q_in_CReals.inj_Q_wd. |
| 161 |
rewrite rings.preserves_mult. |
| 162 |
unfold pow. simpl. |
| 163 |
rewrite rings.preserves_1, Qmult_1_r. |
| 164 |
reflexivity. |
| 165 |
- intros a abound aneg. |
| 166 |
change (ARpower_2_iter (S n) (AQexp_small_neg abound)) |
| 167 |
with (ARpower_N_bounded 2 1 (ARcompress (ARpower_2_iter n (AQexp_small_neg abound)))). |
| 168 |
rewrite ARcompress_correct. |
| 169 |
rewrite ARtoCR_preserves_power_N_bounded. |
| 170 |
assert (-1 ≤ a * (1 ≪ (-1)) * (1 ≪ (-1)) ^ n ≤ 0) as abound_shift. |
| 171 |
{ setoid_replace (a * 1 ≪ (-1) * (1 ≪ (-1)) ^ n ) |
| 172 |
with (a * (1 ≪ (-1)) ^ S n). exact abound. |
| 173 |
unfold pow at 2. simpl. |
| 174 |
rewrite (rings.mult_assoc a). reflexivity. } |
| 175 |
specialize (IHn _ abound_shift). |
| 176 |
setoid_replace (' ARpower_2_iter n (AQexp_small_neg abound)) |
| 177 |
with (' ARpower_2_iter n (AQexp_small_neg abound_shift)). |
| 178 |
rewrite IHn. clear IHn. |
| 179 |
transitivity (CRpower_N_bounded 2 (1#1)%Qpos (rational_exp (' (a ≪ (-1))))). |
| 180 |
+ apply Cmap_wd. |
| 181 |
setoid_replace ('1 : Qpos) with (1#1)%Qpos. |
| 182 |
reflexivity. |
| 183 |
rewrite AQposAsQpos_preserves_1. reflexivity. |
| 184 |
setoid_replace (' (a * 1 ≪ (-1))) with (' (a ≪ (-1))). |
| 185 |
reflexivity. rewrite aq_shift_opp_1. |
| 186 |
rewrite rings.preserves_mult. |
| 187 |
rewrite aq_shift_opp_1. |
| 188 |
apply Qmult_comp. reflexivity. |
| 189 |
rewrite rings.preserves_1. reflexivity. |
| 190 |
+ rewrite aq_shift_opp_1. |
| 191 |
apply rational_exp_square. |
| 192 |
now apply semirings.preserves_nonpos. |
| 193 |
+ apply (order_reflecting (cast AQ Q)). |
| 194 |
rewrite rings.preserves_mult. |
| 195 |
rewrite rings.preserves_0. |
| 196 |
rewrite <- (Qmult_0_l (' (1 ≪ (-1)))). |
| 197 |
apply Qmult_le_compat_r. |
| 198 |
apply (order_preserving (cast AQ Q)) in aneg. |
| 199 |
rewrite rings.preserves_0 in aneg. |
| 200 |
exact aneg. |
| 201 |
rewrite aq_shift_opp_1. |
| 202 |
rewrite rings.preserves_1. discriminate. |
| 203 |
+ apply ARpower_2_iter_wd. |
| 204 |
apply (injective (cast AR CR)). |
| 205 |
rewrite AQexp_small_neg_correct, AQexp_small_neg_correct. |
| 206 |
apply rational_exp_small_neg_wd. |
| 207 |
setoid_replace (' (a * (1 ≪ (-1)) ^ S n)) |
| 208 |
with (' (a * 1 ≪ (-1) * (1 ≪ (-1)) ^ n)). |
| 209 |
reflexivity. |
| 210 |
unfold pow at 1. simpl. |
| 211 |
rewrite (rings.mult_assoc a). reflexivity. |
| 212 |
Qed. |
| 213 |
|
| 214 |
Section exp_neg. |
| 215 |
Context {a : AQ} (Pa : a ≤ 0). |
| 216 |
|
| 217 |
Lemma AQexp_neg_bound_correct : -2 ^ Z.to_nat (Z.log2_up (Qceiling(-'a))) ≤ a. |
| 218 |
Proof. |
| 219 |
apply (order_reflecting (cast AQ Q)). |
| 220 |
rewrite rings.preserves_negate. |
| 221 |
rewrite preserves_nat_pow. |
| 222 |
rewrite rings.preserves_2. |
| 223 |
rewrite <-(int_pow_nat_pow (f:=Z_of_nat)). |
| 224 |
assert ('a <= 0)%Q as H5. |
| 225 |
{ apply (order_preserving (cast AQ Q)) in Pa. |
| 226 |
rewrite rings.preserves_0 in Pa. exact Pa. } |
| 227 |
pose proof (rational_exp_bound_power_2 H5). |
| 228 |
rewrite Qpower.Zpower_Qpower in H6. |
| 229 |
apply H6. |
| 230 |
apply Nat2Z.is_nonneg. |
| 231 |
Qed. |
| 232 |
|
| 233 |
Lemma power_2_improve_bound_correct : forall (n:nat), |
| 234 |
-2 ^ n ≤ a -> |
| 235 |
-1 ≤ a*(1 ≪ (-1))^n ≤ 0. |
| 236 |
Proof. |
| 237 |
intros. |
| 238 |
assert ('a <= 0)%Q as aneg. |
| 239 |
{ apply (order_preserving (cast AQ Q)) in Pa. |
| 240 |
rewrite rings.preserves_0 in Pa. exact Pa. } |
| 241 |
pose proof (CRexp.power_2_improve_bound_correct n aneg) as H6. |
| 242 |
assert ('(-1) <= '(a * (1 ≪ (-1)) ^ n) <= '0 |
| 243 |
-> -1 ≤ a * (1 ≪ (-1)) ^ n ≤ 0). |
| 244 |
{ intros. split; apply (order_reflecting (cast AQ Q)); apply H7. } |
| 245 |
apply H7. clear H7. |
| 246 |
rewrite rings.preserves_mult. |
| 247 |
rewrite rings.preserves_negate. |
| 248 |
rewrite rings.preserves_1. |
| 249 |
rewrite rings.preserves_0. |
| 250 |
rewrite preserves_nat_pow. |
| 251 |
rewrite <-(int_pow_nat_pow (f:=Z_of_nat)). |
| 252 |
rewrite (aq_shift_correct 1 (-1)). |
| 253 |
rewrite rings.preserves_1. |
| 254 |
rewrite Qmult_1_l. apply H6. clear H6. |
| 255 |
apply (order_preserving (cast AQ Q)) in H5. |
| 256 |
refine (Qle_trans _ _ _ _ H5). |
| 257 |
rewrite rings.preserves_negate. |
| 258 |
rewrite preserves_nat_pow. |
| 259 |
rewrite <-(int_pow_nat_pow (f:=Z_of_nat)). |
| 260 |
rewrite Qpower.Zpower_Qpower. |
| 261 |
rewrite rings.preserves_2. |
| 262 |
apply Qle_refl. apply Nat2Z.is_nonneg. |
| 263 |
Qed. |
| 264 |
|
| 265 |
Definition AQexp_neg : AR |
| 266 |
:= ARpower_2_iter |
| 267 |
(Z.to_nat (Z.log2_up (Qceiling(-'a)))) |
| 268 |
(AQexp_small_neg |
| 269 |
(power_2_improve_bound_correct _ (AQexp_neg_bound_correct))). |
| 270 |
|
| 271 |
Lemma AQexp_neg_correct: 'AQexp_neg = rational_exp ('a). |
| 272 |
Proof. |
| 273 |
apply AQexp_neg_bounded_correct, Pa. |
| 274 |
Qed. |
| 275 |
|
| 276 |
(* We could use a number closer to 1/exp 1, for example 11 $ -5, but in practice this seems |
| 277 |
to make it slower. *) |
| 278 |
Program Definition AQexp_inv_pos_bound : AQ₊ := ((1 ≪ (-2)) ^ Z.abs_N (Qfloor ('a)))↾_. |
| 279 |
Next Obligation. solve_propholds. Qed. |
| 280 |
|
| 281 |
Lemma AQexp_inv_pos_bound_correct : |
| 282 |
'(cast (AQ₊) Q AQexp_inv_pos_bound) ≤ rational_exp ('a). |
| 283 |
Proof. |
| 284 |
change (cast Q CR (cast AQ Q ((1 ≪ (-2)) ^ Z.abs_N (Qfloor ('a)))) ≤ rational_exp ('a)). |
| 285 |
rewrite preserves_nat_pow. |
| 286 |
rewrite aq_shift_opp_2. |
| 287 |
rewrite rings.preserves_1, rings.mult_1_l. |
| 288 |
rewrite <-(int_pow_nat_pow (f:=cast N Z)). |
| 289 |
rewrite Z_of_N_abs, Z.abs_neq. |
| 290 |
apply (rational_exp_lower_bound (1#4)). |
| 291 |
now apply semirings.preserves_nonpos. |
| 292 |
apply CRpos_nonNeg. |
| 293 |
now CRsign.CR_solve_pos (1#1)%Qpos. |
| 294 |
change (Qfloor ('a) ≤ 0). |
| 295 |
apply (order_reflecting (cast Z Q)). |
| 296 |
transitivity ('a : Q). |
| 297 |
now apply Qfloor_le. |
| 298 |
now apply semirings.preserves_nonpos. |
| 299 |
Qed. |
| 300 |
End exp_neg. |
| 301 |
|
| 302 |
Lemma AQexp_prf1 {a : AQ} (pA : 0 ≤ a) : -a ≤ 0. |
| 303 |
Proof. now apply rings.flip_nonneg_negate. Qed. |
| 304 |
|
| 305 |
Lemma AQexp_prf2 {a : AQ} (pA : ¬0 ≤ a) : a ≤ 0. |
| 306 |
Proof. now apply orders.le_flip. Qed. |
| 307 |
|
| 308 |
(* |
| 309 |
Extend it to the full domain. |
| 310 |
*) |
| 311 |
Definition AQexp (a : AQ) : AR := |
| 312 |
match decide_rel (≤) 0 a with |
| 313 |
| left Pa => ARinv_pos (AQexp_inv_pos_bound (a:=-a)) (AQexp_neg (AQexp_prf1 Pa)) |
| 314 |
| right Pa => AQexp_neg (AQexp_prf2 Pa) |
| 315 |
end. |
| 316 |
|
| 317 |
Lemma AQexp_correct a : 'AQexp a = rational_exp ('a). |
| 318 |
Proof. |
| 319 |
unfold AQexp. |
| 320 |
case (decide_rel _); intros. |
| 321 |
rewrite ARtoCR_preserves_inv_pos. |
| 322 |
rewrite AQexp_neg_correct. |
| 323 |
rewrite rings.preserves_negate. |
| 324 |
apply rational_exp_opp. |
| 325 |
now apply semirings.preserves_nonneg. |
| 326 |
posed_rewrite <-(rings.preserves_negate (f:=cast AQ Q)). |
| 327 |
apply (AQexp_inv_pos_bound_correct (a:=-a)). |
| 328 |
now apply rings.flip_nonneg_negate. |
| 329 |
apply AQexp_neg_correct. |
| 330 |
Qed. |
| 331 |
|
| 332 |
Local Obligation Tactic := idtac. |
| 333 |
Program Definition ARexp_bounded_uc (z : Z) := unary_complete_uc |
| 334 |
QPrelengthSpace (cast AQ Q_as_MetricSpace) (λ x, AQexp (('z) ⊓ x)) (exp_bound_uc z) _. |
| 335 |
Next Obligation. |
| 336 |
intros. |
| 337 |
change ('AQexp ((' z) ⊓ x) = exp_bound_uc z (' x)). |
| 338 |
rewrite AQexp_correct, aq_preserves_min, AQtoQ_ZtoAQ. |
| 339 |
reflexivity. |
| 340 |
Qed. |
| 341 |
|
| 342 |
Definition ARexp_bounded (z : Z) := Cbind AQPrelengthSpace (ARexp_bounded_uc z). |
| 343 |
|
| 344 |
Lemma ARtoCR_preserves_exp_bounded z x : 'ARexp_bounded z x = exp_bounded z ('x). |
| 345 |
Proof. apply (preserves_unary_complete_fun QPrelengthSpace _ (λ x, AQexp (('z) ⊓ x))). Qed. |
| 346 |
|
| 347 |
Definition ARexp (x : AR) : AR |
| 348 |
:= ARexp_bounded (Qceiling ('approximate x (Qpos2QposInf (1#1)) + (1#1))) x. |
| 349 |
|
| 350 |
Lemma ARtoCR_preserves_exp x : 'ARexp x = exp ('x). |
| 351 |
Proof. unfold ARexp. apply ARtoCR_preserves_exp_bounded. Qed. |
| 352 |
End ARexp. |