import ContractExact namespace Submission open ExactRuntime FloatLib.Floats.Formats.BinaryInterchange FloatLib.Floats local notation "Qz" =>List.range local notation "Qy" =>Real.sqrt local notation "Qx" =>if_neg local notation "Qw" =>if_pos local notation "Qv" =>ExactRuntime.mantOf_lt_24 open Float renaming ofBits→Zz open Nat renaming mod_eq_of_lt→Zy,shiftRight_eq_div_pow→Zu,and_two_pow_sub_one_eq_mod→Zt,shiftLeft_eq→Zp,mul_le_mul_right→Zj,cast_nonneg→Zg,lt_or_ge→Z6,zero_add→Z4,pos_of_ne_zero→Yt,mul_lt_mul_of_pos_right→Yo,le_trans→Yn,pow_succ→Yi,le_div_iff_mul_le→Yg,lor_comm→Ya,mul_comm→Y5,shiftLeft_add_eq_or_of_lt→Xy,div_lt_iff_lt_mul→Xx,log2_self_le→Xw,lt_log2_self→Xv,le_mul_of_pos_left→Xu,toUInt32→Xm,sub_zero→Xl,lt_of_le_of_lt→X6,div_eq_of_lt→X2,mul_ne_zero→X0,div_eq_of_lt_le→Wm,add_mul_mod_self_left→Wk open Bool renaming false_eq_true→Zx,and_eq_true→Yh open UInt64 renaming ofNat→Zw,toNat_and→Zh,toNat_shiftRight→Z7,toNat_ofNat'→Z1,toNat_sub_of_le→Yz,toFloat→Y7,toNat_add→X8,toNat_or→X4 open FloatLib.Numerics renaming binaryRadix→Zv open Float.Model.Format renaming binary64→Zs open List renaming map_cons→Zr,sum_cons→Zq,map_congr_left→Zn,foldl_cons→Zk,map_map→Ze,sum_nonneg→Yp,map_nil→Y9,length_map→Y8,length_cons→Y6,sum_toFinset→Y3,nodup_range→Y2,mem_cons_self→Xh,mem_cons_of_mem→Xg,mem_toFinset→Xf,sum_map_mul_left→Xe,map_append→Xd,sum_append→Xc,sum_nil→Xb,length_range→X9,getElem_map→Wr,sum_le_sum→Wj,range_eq_range'→Wh open FloatLib.Floats.Formats.Flocq renaming bpow→Zo open Float.Model.UnpackedFloat renaming isFinite→Zm,abs→Zf,unpack→Zc,unpackExponent→Z3,compare→Yu,mul→Ys,add→Wy,pack→Wv,ofUInt32→Wu,unpackSign→Wt,ofUInt64→Wn,sub→Wd open UInt32 renaming toNat_and→Zl,ofNat→Zi,toNat_ofNat'→Yv,toNat_toUSize→Yf,toFloat→Yd,toNat_shiftRight→Yb,toNat→Xj,toNat_or→X7 open System.Platform renaming numBits→Zd open FloatArray renaming emptyWithCapacity→Zb,size→Z0 open FloatLib.Numerics.Radix renaming toReal→Za open Model renaming modelSignBit→Z9,unpackedToReal_finite→Z2,toDyadic?_ieee_eq_model→Yy,toReal→Yw,roundDyadic→Yr,unpackedToDyadic?→Ym,unpackedToReal→Yl,toModel_ofFloatModel→Ye,roundRat→Xz,expField→Xr,abs_roundAt_sub_le→Xp,roundAt_mono→Xi,ofUInt32→Wi open Array renaming mkEmpty→Z8,replicate→Z5,getElem_ofFn→Yk,length_toList→Ws open BitVec renaming eq_of_toNat_eq→Yx,toNat→Xo,toNat_append→X1 open Float.Model renaming pack→Yq open USize renaming le_size→Yj,toNat_add→Xn open Int renaming cast_natCast→Y4,natAbs_natCast→X5 open Model.Proof renaming mul_eq_spec→Xt open Model.Spec renaming mul→Xs open FloatFormat renaming expAllOnesNat→Xq,ieeeMaxNormalExponent→Wf open Function renaming comp→Xa open ExecFloat.Binary renaming toModel_ofFloat→Wz open ExactRuntime renaming toWord→Wl section open FloatLib.Numerics end open ExactRuntime FloatLib.Floats.Formats.BinaryInterchange FloatLib.Floats section open FloatLib.Numerics end section open Float.Model Float.Model.UnpackedFloat open FloatLib.Floats.Formats.BinaryInterchange FloatLib.Floats namespace Bridge end Bridge namespace Bridge end Bridge namespace Bridge end Bridge namespace Bridge end Bridge end section open FloatLib.Numerics FloatLib.Floats.Formats.BinaryInterchange FloatLib.Floats end section open Float.Model Float.Model.UnpackedFloat set_option maxRecDepth 8192 in end namespace FP64 open FloatLib.Floats.Formats.BinaryInterchange FloatLib.Floats structure FC where xc:FloatArray IX:Array UInt32 structure FQ2 where s0:Float s1:Float structure FQ3 where s0:Float s1:Float o:UInt32 structure FQ9 where s0:Float s1:Float s2:Float s3:Float s4:Float s5:Float s6:Float s7:Float o:UInt32 structure FQR where s:Float c:Float structure FS8 where s0:Float s1:Float s2:Float s3:Float s4:Float s5:Float s6:Float s7:Float c0:Float c1:Float c2:Float c3:Float c4:Float c5:Float c6:Float c7:Float structure LR where mu:Float M:Float d:UInt64 deriving Inhabited lemma AA (x:Model FloatFormat.binary64) (s:Float.Model.UnpackedFloat.Sign) (m:Nat) (e:Int) (hm:0< m) (h:Model.toModel x= .finite s m e hm):2^52≤ m∨e= -1074:=by have a:FloatFormat.binary64.toModel.mantissaBitsWithoutImplicit=52:=rfl have he:FloatFormat.binary64.toModel.exponentBits=11:=rfl unfold Model.toModel Zc at h simp only [] at h split at h ·split at h<;>cases h ·split at h ·split at h ·cases h ·right injection h with d b c subst c rename_i f _ rw [f] simp [Float.Model.Format.exponentBias,a,he] ·left injection h with d b c subst b rw [X1] simp only [a,BitVec.toNat_ofNat] exact Yn (by decide) (Nat.left_le_or) lemma AB (m1 m2:Nat) (e1 e2:Int) (b:0< m1) (c:0< m2) (d:2^52≤ m1∨e1= -1074) (e:2^52≤ m2∨e2= -1074): e1+e2≤(FloatFormat.toModel FloatFormat.binary64).targetExponent (Float.Model.totalExponent (m1*m2) (e1+e2)):=by have f:(FloatFormat.toModel FloatFormat.binary64).mantissaBits=53:=rfl have g:(FloatFormat.toModel FloatFormat.binary64).minExponent= -1074:=rfl unfold Float.Model.Format.targetExponent Float.Model.totalExponent rw [f,g] have a:m1*m2≠0:=X0 b.ne' c.ne' rcases d with d | d ·have:52≤(m1*m2).log2:=(Nat.le_log2 a).mpr (Yn d (Nat.le_mul_of_pos_right _ c)) omega ·rcases e with e | e ·have:52≤(m1*m2).log2:=(Nat.le_log2 a).mpr (Yn e (Xu _ b)) omega ·omega lemma AC (x y:Model FloatFormat.binary64) (i:(Model.toModel x).isFinite=true) (j:(Model.toModel y).isFinite=true): Model.mul x y=Model.ofModel FloatFormat.binary64 (Ys (FloatFormat.toModel FloatFormat.binary64) (Model.toModel x) (Model.toModel y)):=by have a:FloatFormat.binary64.isIEEE=true:=by decide cases b:Model.toModel x<;>cases c:Model.toModel y<;> simp only [b,c,Zm,Zx] at i j case zero.zero s1 s2=> rw [Xt,Xs,Yy _ a x, Yy _ a y,b,c] cases s1<;>cases s2<;>rfl case zero.finite s1 s2 m2 e2 d=> rw [Xt,Xs,Yy _ a x, Yy _ a y,b,c] cases s1<;>cases s2<;>rfl case finite.zero s1 m1 e1 e s2=> rw [Xt,Xs,Yy _ a x, Yy _ a y,b,c] cases s1<;>cases s2<;>simp [Ym]<;>rfl case finite.finite s1 m1 e1 e s2 m2 e2 d=> have f:=AB m1 m2 e1 e2 e d (AA x _ _ _ _ b) (AA y _ _ _ _ c) rw [Xt,Xs,Yy _ a x, Yy _ a y,b,c] simp only [Ym,Ys] have g:(m1==0)=false:=by simp [e.ne'] have h:(m2==0)=false:=by simp [d.ne'] simp only [g,h,Bool.or_false,Zx,ite_false] rw [Model.roundWithAccuracy_exact_eq_round_of_le_targetExponent _ _ _ _ f] simp only [Yr,a,ite_true,Model.ieeeRoundDyadic] congr 2 cases s1<;>cases s2<;>rfl lemma AD (x y:Float) (a:x.isFinite=true) (b:y.isFinite=true): ExecFloat.Binary.toModel (ExecFloat.Binary.ofFloat (x*y))= Model.mul (ExecFloat.Binary.toModel (ExecFloat.Binary.ofFloat x)) (ExecFloat.Binary.toModel (ExecFloat.Binary.ofFloat y)):=by rw [Wz,Wz, Wz] change Model.ofFloatModel (Float.Model.mul x.toModel y.toModel)=_ rw [Float.Model.mul,Model.ofFloatModel_pack] have h:=AC (Model.ofFloatModel x.toModel) (Model.ofFloatModel y.toModel) (by simpa only [Ye,Float.isFinite,Float.Model.isFinite] using a) (by simpa only [Ye,Float.isFinite,Float.Model.isFinite] using b) rw [Ye,Ye] at h exact h.symm lemma AE (z:Model FloatFormat.binary64): Model.isFinite z=(Model.toModel z).isFinite:=by have he:=Model.unpackExponent_toNat z have b:=Model.toNat_neg_one_exponentBits FloatFormat.binary64 have hm:Model.isFinite z=(Xr z !=Xq FloatFormat.binary64):=rfl rw [hm] unfold Model.toModel Zc simp only [] by_cases h:Z3 (spec:=FloatFormat.toModel FloatFormat.binary64) (Model.toModelBits z)= -BitVec.ofNat _ 1 ·rw [Qw h] have a:Xr z=Xq FloatFormat.binary64:=by rw [←he,h,b] rw [a] split<;>rfl ·rw [Qx h] have a:Xr z≠Xq FloatFormat.binary64:=by intro c;apply h;apply Yx;rw [he,c,←b] have d:(Xr z !=Xq FloatFormat.binary64)=true:=by simpa using a rw [d] split ·split<;>rfl ·rfl def FB (f:Float):Model FloatFormat.binary64:=Model.ofFloatModel f.toModel noncomputable def vr (f:Float):ℝ:=Model.toReal (FB f) lemma AF (f:Float):Model.isFinite (FB f)=f.isFinite:=by rw [AE];rfl lemma AG (x y:Float) (a:x.isFinite=true) (b:y.isFinite=true): FB (x+y)=Model.add (FB x) (FB y):= ExecFloat.Binary.toModel_ofFloat_add_of_isFinite x y a b lemma AH (x y:Float) (a:x.isFinite=true) (b:y.isFinite=true): FB (x*y)=Model.mul (FB x) (FB y):= AD x y a b lemma AI (x y:Float) (a:x.isFinite=true) (b:y.isFinite=true) (h:(x+y).isFinite=true): vr (x+y)=Model.roundAt FloatFormat.binary64 (vr x+vr y):=by unfold vr rw [AG x y a b] apply Model.toReal_add_eq_roundAt _ _ (by decide) (by rw [AF];exact a) (by rw [AF];exact b) rw [←AG x y a b,AF];exact h lemma AJ (x y:Float) (a:x.isFinite=true) (b:y.isFinite=true) (h:(x*y).isFinite=true): vr (x*y)=Model.roundAt FloatFormat.binary64 (vr x*vr y):=by unfold vr rw [AH x y a b] apply Model.toReal_mul_eq_roundAt _ _ (by decide) (by rw [AF];exact a) (by rw [AF];exact b) rw [←AH x y a b,AF];exact h lemma AK (w:Float.Model.UnpackedFloat) (h:w.isFinite=false): (Yq w).unpack.isFinite=false:=by cases w with | notANumber=>decide | infinity s=>cases s<;>decide | zero s=>simp [Zm] at h | finite s m e hm=>simp [Zm] at h lemma AL (u v:Float.Model.UnpackedFloat) (h:u.isFinite=false∨v.isFinite=false): (Wy Zs u v).isFinite=false:=by cases u<;>cases v<;> simp only [Zm,Bool.true_eq_false,or_self] at h<;> simp only [Wy]<;>(try split)<;>rfl lemma AM (u v:Float.Model.UnpackedFloat) (h:u.isFinite=false∨v.isFinite=false): (Ys Zs u v).isFinite=false:=by cases u<;>cases v<;>simp_all [Ys,Zm] lemma AN (f g:Float) (h:(f+g).isFinite=true): f.isFinite=true∧g.isFinite=true:=by change (Yq (Wy Zs f.toModel.unpack g.toModel.unpack)).unpack.isFinite=true at h change f.toModel.unpack.isFinite=true∧g.toModel.unpack.isFinite=true generalize f.toModel.unpack=u at h⊢ generalize g.toModel.unpack=v at h⊢ cases a:u.isFinite<;>cases b:v.isFinite all_goals first | exact ⟨rfl,rfl⟩ | (rw [AK _ (AL u v (by simp [a,b]))] at h;exact absurd h (by decide)) lemma AO (f g:Float) (h:(f*g).isFinite=true): f.isFinite=true∧g.isFinite=true:=by change (Yq (Ys Zs f.toModel.unpack g.toModel.unpack)).unpack.isFinite=true at h change f.toModel.unpack.isFinite=true∧g.toModel.unpack.isFinite=true generalize f.toModel.unpack=u at h⊢ generalize g.toModel.unpack=v at h⊢ cases a:u.isFinite<;>cases b:v.isFinite all_goals first | exact ⟨rfl,rfl⟩ | (rw [AK _ (AM u v (by simp [a,b]))] at h;exact absurd h (by decide)) open FloatLib.Floats.Formats.Flocq in lemma AP (z:ℝ): Model.ulpAt FloatFormat.binary64 z≤2^(-52:ℤ)* |z| +2^(-1074:ℤ):=by have a:FloatFormat.binary64.minSubnormalExponent= -1074:=rfl have f:(FloatFormat.binary64.fracWidth:ℤ)=52:=rfl have b: ∀e:ℤ,bpow Zv e=(2:ℝ)^e:=by intro e;simp [bpow,Zv,Za] have g:(0:ℝ)≤2^(-52:ℤ)* |z| :=by positivity unfold Model.ulpAt by_cases c:z=0 ·subst c have i:=ulp_zero_FLT (β:=Zv) FloatFormat.binary64.minSubnormalExponent (FloatFormat.binary64.fracWidth+1) (by positivity) have j:ulp Zv (Model.fexpOf FloatFormat.binary64) 0= bpow Zv FloatFormat.binary64.minSubnormalExponent:=i rw [j,a,b] simp ·rw [ulp.of_ne_zero _ _ z c] simp only [cexp,Model.fexpOf,fltExp,a,f] have d:=bpow_magnitude_sub_one_le Zv z c rw [b] at d rw [b] rcases le_total (magnitude Zv z - (52+1)) (-1074) with h | h ·rw [max_eq_right h] linarith ·rw [max_eq_left h] have e1:(2:ℝ)^(magnitude Zv z - (52+1))= 2^(-52:ℤ)*2^(magnitude Zv z - 1):=by rw [←zpow_add₀ (by norm_num:(2:ℝ)≠0)];congr 1;ring rw [e1] have:(0:ℝ)≤2^(-1074:ℤ):=by positivity have k:(0:ℝ)≤2^(-52:ℤ):=by positivity nlinarith [mul_le_mul_of_nonneg_left d k] lemma AQ (r z:ℝ) (he: |r - z| ≤Model.ulpAt FloatFormat.binary64 z/2): |r - z| ≤2^(-52:ℤ)* |r| +2^(-1074:ℤ):=by have e:=AP z have h: |z| ≤ |r| + |r - z| :=by calc |z| = |r - (r - z)| :=by ring_nf _≤ |r| + |r - z| :=abs_sub _ _ generalize Model.ulpAt FloatFormat.binary64 z=U at he e have c:0≤ |r - z| :=abs_nonneg _ generalize p: |r - z| =d at he h c⊢ generalize n: |r| =a at h⊢ generalize q: |z| =b at h e have i:0≤a:=by rw [←n];exact abs_nonneg r have j:(2:ℝ)^(-52:ℤ)=2*2^(-53:ℤ):=by rw [show (-52:ℤ)=1+(-53) by norm_num,zpow_add₀ (by norm_num:(2:ℝ)≠0)];norm_num have k:(2:ℝ)^(-1074:ℤ)=2*2^(-1075:ℤ):=by rw [show (-1074:ℤ)=1+(-1075) by norm_num,zpow_add₀ (by norm_num:(2:ℝ)≠0)];norm_num rw [j,k] at e⊢ generalize f:(2:ℝ)^(-53:ℤ)=u at e⊢ generalize l:(2:ℝ)^(-1075:ℤ)=η at e⊢ have g:0≤u:=by rw [←f];positivity have m:u≤1/4:=by rw [←f];norm_num have o:0≤η:=by rw [←l];positivity have p1:=mul_le_mul_of_nonneg_left h g have p2:=mul_le_mul_of_nonneg_right m c have p3:=mul_nonneg g i nlinarith [p1,p2,p3] lemma AR (x y:Float) (a:x.isFinite=true) (b:y.isFinite=true) (h:(x+y).isFinite=true): |vr (x+y) - (vr x+vr y)| ≤2^(-52:ℤ)* |vr (x+y)| +2^(-1074:ℤ):=by have c:=AI x y a b h have he:=Xp FloatFormat.binary64 (vr x+vr y) rw [←c] at he exact AQ _ _ he lemma AS (f:Float):vr f=Yl f.toModel.unpack:=by unfold vr FB rw [Model.toReal_eq_unpackedToReal_toModel (by decide),Ye] open FloatLib.Floats.Formats.Flocq in lemma AT (n e:ℤ) (a:n.natAbs<2^53) (b: -1074≤e): Model.roundAt FloatFormat.binary64 ((n:ℝ)*2^e)=(n:ℝ)*2^e:=by unfold Model.roundAt apply round_preserves_generic have c:=(generic_format_FLT_iff (β:=Zv) FloatFormat.binary64.minSubnormalExponent (FloatFormat.binary64.fracWidth+1) (by positivity) ((n:ℝ)*2^e)).mpr apply c refine ⟨by positivity,⟨n,e⟩, ?_, ?_, ?_⟩ ·simp [toReal,bpow,Zv,Za] ·exact a ·exact b lemma AU (x y:Float) (a:x.isFinite=true) (b:y.isFinite=true) (h:(x*y).isFinite=true) (n e:ℤ) (c:n.natAbs<2^53) (d: -1074≤e) (f:vr x*vr y=(n:ℝ)*2^e):vr (x*y)=vr x*vr y:=by rw [AJ x y a b h,f,AT n e c d] open Float.Model (Format UnpackedFloat totalExponent) in lemma AV (spec:Format) (sign:UnpackedFloat.Sign) (n:Nat) (e:Int) (b:n≠0) (he:spec.targetExponent (totalExponent n e)=e): UnpackedFloat.round spec sign n e= .finite sign n e (Yt b):=by have a (em:UnpackedFloat.ExtendedMantissa):em>>>0=em:=rfl simp [UnpackedFloat.round,UnpackedFloat.decreaseExponent,he,UnpackedFloat.roundWithAccuracy, UnpackedFloat.shiftToTargetExponent,UnpackedFloat.shiftToExponent, UnpackedFloat.ExtendedMantissa.ofMantissaAndAccuracy, UnpackedFloat.ExtendedMantissa.roundedMantissa,UnpackedFloat.ExtendedMantissa.accuracy, UnpackedFloat.Accuracy.roundToNearestEven,a,b] open Float.Model (Format UnpackedFloat totalExponent) in lemma AW (spec:Format) (n:Nat) (b:n≠0): UnpackedFloat.ofNat spec n=UnpackedFloat.round spec .positive n 0:=by have a:(0:Int)<(n:Int):=by omega simp [UnpackedFloat.ofNat,UnpackedFloat.ofInt,UnpackedFloat.normalize,Int.compare_eq_gt.mpr a] open Float.Model (Format UnpackedFloat totalExponent) in lemma AX (m:UInt32) (g:m≠0): (Yd m).toModel.unpack= .finite .positive (m.toNat<<<(52 - m.toNat.log2)) (-((52 - m.toNat.log2:Nat):Int)) (by have:m.toNat≠0:=by intro h;apply g;exact UInt32.toNat_inj.mp (by simpa using h) simp [Zp];omega):=by have hm:m.toNat≠0:=by intro h;apply g;exact UInt32.toNat_inj.mp (by simpa using h) have d:m.toNat<2^32:=m.toNat_lt have c:m.toNat.log2<32:=(Nat.log2_lt hm).2 d set k:=52 - m.toNat.log2 with l have a:m.toNat<<>>63=0 then .positive else .negative open Float.Model (Format UnpackedFloat) in lemma Ab (u:UInt64) (he:((u>>>52)&&&0x7ff).toNat≠2047): UnpackedFloat.unpack Format.binary64 u.toBitVec= if k:((u>>>52)&&&0x7ff).toNat=0 then (if a:(u&&&0xfffffffffffff).toNat=0 then .zero (FD u) else .finite (FD u) (u&&&0xfffffffffffff).toNat (-1074) (Yt a)) else .finite (FD u) ((u&&&0xfffffffffffff).toNat+2^52) (((u>>>52)&&&0x7ff).toNat - 1075:Int) (by omega):=by have b:((u>>>52)&&&0x7ff).toNat=u.toNat/2^52 % 2048:=by rw [Zh,Z7,show (0x7ff:UInt64).toNat=2^11 - 1 from rfl, Zt] simp [Zu] have c:(u&&&0xfffffffffffff).toNat=u.toNat % 2^52:=by rw [Zh,show (0xfffffffffffff:UInt64).toNat=2^52 - 1 from rfl, Zt] have l:=u.toNat_lt have ex:(Z3 (spec:=Format.binary64) u.toBitVec).toNat= u.toNat/2^52 % 2048:=by simp [Z3,Zu] have mx:(Float.Model.UnpackedFloat.unpackMantissa (spec:=Format.binary64) u.toBitVec).toNat= u.toNat % 2^52:=by simp [Float.Model.UnpackedFloat.unpackMantissa] have sx:Float.Model.UnpackedFloat.Sign.ofBitVec (Wt (spec:=Format.binary64) u.toBitVec)=FD u:=by unfold Float.Model.UnpackedFloat.Sign.ofBitVec FD have:(Wt (spec:=Format.binary64) u.toBitVec).toNat= u.toNat/2^63 % 2:=by simp [Wt,Zu] have d:(u>>>63=0)↔u.toNat/2^63 % 2=0:=by rw [←UInt64.toNat_inj] simp [Z7,Zu] (clear* - ex c l mx;omega) by_cases f:u.toNat/2^63 % 2=0 ·rw [Qw (d.mpr f),Qw];apply Yx;rw [this,f];rfl ·rw [Qx (fun h=>f (d.mp h)),Qx] intro h have j:=congrArg Xo h rw [this] at j exact f (by simpa using j) unfold Zc simp only [] rw [sx] have g:Z3 (spec:=Format.binary64) u.toBitVec≠ -1#11:=by intro h;have:=congrArg Xo h;rw [ex] at this;simp at this;(clear* - ex b he this;omega) rw [Qx g] by_cases e:((u>>>52)&&&0x7ff).toNat=0 ·rw [dif_pos e] have i:Z3 (spec:=Format.binary64) u.toBitVec=0#11:=by apply Yx;rw [ex];simp;(clear* - ex e b;omega) rw [Qw i] by_cases a:(u&&&0xfffffffffffff).toNat=0 ·rw [dif_pos a,dif_pos] apply Yx;rw [mx];simp;(clear* - c a mx;omega) ·rw [dif_neg a,dif_neg] ·congr 1 ·rw [mx,c] ·simp [Float.Model.Format.exponentBias];(clear* - ex e b;omega) ·intro h;have:=congrArg Xo h;rw [mx] at this;simp at this;(clear* - c a mx this;omega) ·rw [dif_neg e] have i:Z3 (spec:=Format.binary64) u.toBitVec≠0#11:=by intro h;have:=congrArg Xo h;rw [ex] at this;simp at this;(clear* - ex e b this;omega) rw [Qx i] have eb:Format.binary64.exponentBias=1023:=rfl have em:Format.binary64.mantissaBitsWithoutImplicit=52:=rfl congr 1 ·rw [X1,mx,c] have m:(1#1).toNat=1:=rfl rw [m,show (1:Nat)<<<52=2^52*1 by decide] rw [←Nat.two_pow_add_eq_or_of_lt (Nat.mod_lt _ (by decide)) 1] (clear* -;omega) ·rw [ex,b] (clear* - eb;omega) lemma Ac (u:UInt64): (Zz u).toModel.unpack=Zc Zs u.toBitVec:= Model.unpack_pack_unpack _ _ def FE (i:Nat):UInt64:= UInt64.ofNat ((if i<256 then 0 else 2^63)+ (if i % 256=0 then 0 else if i % 256=255 then 2047*2^52 else (i % 256+873)*2^52)) lemma Ad (i:Nat) (a:i<512): (FE i).toNat=(if i<256 then 0 else 2^63)+ (if i % 256=0 then 0 else if i % 256=255 then 2047*2^52 else (i % 256+873)*2^52):=by unfold FE rw [Z1,Zy] have:i % 256<256:=Nat.mod_lt _ (by decide) split<;>split<;>(try split)<;>omega lemma Ae (u:UInt64): ((u>>>52)&&&0x7ff).toNat=u.toNat/2^52 % 2048∧ (u&&&0xfffffffffffff).toNat=u.toNat % 2^52∧ (FD u=if u.toNat/2^63=0 then .positive else .negative):=by refine ⟨?_, ?_, ?_⟩ ·rw [Zh,Z7,show (0x7ff:UInt64).toNat=2^11 - 1 from rfl, Zt] simp [Zu] ·rw [Zh,show (0xfffffffffffff:UInt64).toNat=2^52 - 1 from rfl, Zt] ·unfold FD have:(u>>>63=0)↔u.toNat/2^63=0:=by rw [←UInt64.toNat_inj];simp [Z7,Zu] by_cases h:u.toNat/2^63=0 ·rw [Qw (this.mpr h),Qw h] ·rw [Qx (fun a=>h (this.mp a)),Qx h] lemma Ag (u:UInt64) (s:Bool) (E:Nat) (e:1≤E) (f:E≤2046) (a:u.toNat=(if s then 2^63 else 0)+E*2^52): (Zz u).toModel.unpack= .finite (if s then .negative else .positive) (2^52) ((E:Int) - 1075) (by positivity):=by rw [Ac] obtain ⟨fe,ff,fs⟩:=Ae u have b:((u>>>52)&&&0x7ff).toNat=E:=by rw [fe,a];split<;>omega have c:(u&&&0xfffffffffffff).toNat=0:=by rw [ff,a];split<;>omega rw [Ab u (by rw [b];omega),dif_neg (by rw [b];omega)] have d:FD u=if s then .negative else .positive:=by rw [fs,a];cases s<;>simp<;>omega rw [d] congr 1 ·rw [c];simp ·rw [b] open ExactRuntime def FF:FloatArray:=⟨Array.ofFn (n:=512) fun i=>Float.ofBits (FE i.val)⟩ lemma Ah:FF.size=512:=by simp [FF,Z0] lemma Ai (w:UInt32):(w>>>23).toUSize.toNat=w.toNat/2^23:=by rw [Yf,Yb];simp [Zu] lemma Aj (w:UInt32):w.toNat/2^23<512:=by have:=w.toNat_lt;omega lemma Ak (w:UInt32) (h:(w>>>23).toUSize.toNat>>23).toUSize h=Zz (FE (w.toNat/2^23)):=by have a:(w>>>23).toUSize.toNat<512:=by rw [Ai];exact Aj w have e1:FF.uget (w>>>23).toUSize h= (Array.ofFn (n:=512) fun i=>Zz (FE i.val))[(w>>>23).toUSize.toNat]'(by simpa using a):=rfl rw [e1,Yk] simp only [Ai] @[inline] def FG (w:UInt32):Float:= ((w&&&0x7FFFFF) ||| 0x800000).toFloat* FF.uget (w>>>23).toUSize (by rw [Ah,Ai];exact Aj w) noncomputable def FH (w:UInt32):ℝ:=(sv w:ℝ)*2^((idxOf w:ℤ) - 149) lemma Al (w:UInt32):(expOf w).toNat=w.toNat/2^23 % 256:=by unfold expOf rw [Zl,Yb,show (0xFF:UInt32).toNat=2^8 - 1 from rfl, Zt] simp [Zu] lemma Am (w:UInt32):(fracOf w).toNat=w.toNat % 2^23:=by unfold fracOf rw [Zl,show (0x7FFFFF:UInt32).toNat=2^23 - 1 from rfl, Zt] lemma An (w:UInt32):signOf w=decide (256≤w.toNat/2^23):=by unfold signOf have d:=w.toNat_lt have c:w&&&0x80000000=if w.toNat.testBit 31 then (0x80000000:UInt32) else 0:=by apply UInt32.toNat_inj.mp rw [Zl,show (0x80000000:UInt32).toNat=2^31 from rfl,Nat.and_two_pow] cases w.toNat.testBit 31<;>rfl rw [c,Nat.testBit_eq_decide_div_mod_eq] by_cases h:2^31≤w.toNat ·have a:w.toNat/2147483648 % 2=1:=by omega have b:256≤w.toNat/8388608:=by omega simp [a,b] ·have a:w.toNat/2147483648 % 2=0:=by omega have b: ¬256≤w.toNat/8388608:=by omega simp [a,b] lemma Ao (w:UInt32):((w&&&0x7FFFFF) ||| 0x800000).toNat=w.toNat % 2^23+2^23:=by rw [X7,←fracOf,Am] have a:w.toNat % 2^23<2^23:=Nat.mod_lt _ (by decide) rw [show (0x800000:UInt32).toNat=2^23*1 from rfl,Ya, ←Nat.two_pow_add_eq_or_of_lt a 1] omega lemma Ap (f:Float):f.isFinite=f.toModel.unpack.isFinite:=rfl lemma Aq:(2:ℝ)^(200:ℤ)≤Yw (Model.posMaxFinite FloatFormat.binary64):=by rw [Model.toReal_posMaxFinite] have a:FloatFormat.binary64.maxNormalExponent=1023:=by decide have c:Model.pow2 FloatFormat.binary64.fracWidth=2^52:=by decide have b:(Int.ofNat FloatFormat.binary64.fracWidth)=52:=rfl rw [c,a,b] have d:Model.bpow (1023 - 52)=(2:ℝ)^(971:ℤ):=by simp [Model.bpow,Zo,Zv, Za] rw [d] have e:(2:ℝ)^(52:ℕ)≤((2^52+FloatFormat.binary64.maxFiniteFracField:ℕ):ℝ):=by push_cast linarith [(Zg (α:=ℝ) FloatFormat.binary64.maxFiniteFracField)] have f:(2:ℝ)^(148:ℤ)≤(2:ℝ)^(971:ℤ):=zpow_le_zpow_right₀ (by norm_num) (by norm_num) calc (2:ℝ)^(200:ℤ)=(2:ℝ)^(52:ℕ)*(2:ℝ)^(148:ℤ):=by rw [show (200:ℤ)=(52:ℕ)+148 by norm_num,zpow_add₀ (by norm_num:(2:ℝ)≠0),zpow_natCast] _≤((2^52+FloatFormat.binary64.maxFiniteFracField:ℕ):ℝ)*(2:ℝ)^(971:ℤ):= mul_le_mul e f (by positivity) (by positivity) lemma Ar (x y:Float) (a:x.isFinite=true) (b:y.isFinite=true) (c: |vr x| * |vr y| ≤2^(200:ℤ)):(x*y).isFinite=true:=by rw [←AF,AH x y a b] apply Model.isFinite_mul_of_abs_mul_le_posMaxFinite _ _ (by decide) (by rw [AF];exact a) (by rw [AF];exact b) exact c.trans Aq lemma As (a b:ℤ):(2:ℝ)^a*2^b=2^(a+b):= (zpow_add₀ (by norm_num:(2:ℝ)≠0) a b).symm lemma At (u:UInt64) (s:Bool) (E:Nat) (c:1≤E) (d:E≤2046) (e:u.toNat=(if s then 2^63 else 0)+E*2^52): (Zz u).isFinite=true∧ vr (Zz u)=(if s then -1 else 1)*(2:ℝ)^((E:ℤ) - 1023):=by have a:=Ag u s E c d e refine ⟨by rw [Ap,a];rfl, ?_⟩ rw [AS,a,Z2] have f:Zo Zv ((E:ℤ) - 1075)= (2:ℝ)^((E:ℤ) - 1075):=by simp [Zo,Zv,Za] rw [f] have b:((2^52:ℕ):ℝ)*(2:ℝ)^((E:ℤ) - 1075)=2^((E:ℤ) - 1023):=by rw [show ((2^52:ℕ):ℝ)=(2:ℝ)^(52:ℤ) by norm_num,As];congr 1;ring cases s ·simp only [Zx,ite_false,Z9,one_mul];exact b ·simp only [ite_true,Z9];rw [mul_assoc,b] lemma Au (u:UInt64) (c:((u>>>52)&&&0x7ff).toNat=2047): (Zz u).isFinite=false:=by rw [Ap,Ac] have ex:(Z3 (spec:=Zs) u.toBitVec).toNat= u.toNat/2^52 % 2048:=by simp [Z3,Zu] have b:=(Ae u).1 have a:Z3 (spec:=Zs) u.toBitVec= -1#11:=by apply Yx;rw [ex];simp;omega unfold Zc simp only [] rw [Qw a] split<;>rfl lemma Av (i:Nat) (a:i<512): (((FE i>>>52)&&&0x7ff).toNat=if i % 256=0 then 0 else if i % 256=255 then 2047 else i % 256+873)∧ ((FE i&&&0xfffffffffffff).toNat=0):=by obtain ⟨fe,ff, -⟩:=Ae (FE i) rw [fe,ff,Ad i a] have:i % 256<256:=Nat.mod_lt _ (by decide) constructor<;>(split<;>split<;>(try split)<;>omega) lemma Aw (w:UInt32): FG w=((w&&&0x7FFFFF) ||| 0x800000).toFloat*Zz (FE (w.toNat/2^23)):=by unfold FG;rw [Ak] lemma Ax (w:UInt32) (p:(expOf w).toNat≠0) (A:(expOf w).toNat≠255): (FG w).isFinite=true∧vr (FG w)=FH w:=by have e:=Aj w have he:=Al w have u:=An w have q:(FE (w.toNat/2^23)).toNat= (if decide (256≤w.toNat/2^23) then 2^63 else 0)+(w.toNat/2^23 % 256+873)*2^52:=by rw [Ad _ e] have f: ¬(w.toNat/2^23 % 256=0):=by omega have b: ¬(w.toNat/2^23 % 256=255):=by omega rw [Qx f,Qx b] by_cases h:256≤w.toNat/2^23 ·rw [Qx (by omega: ¬w.toNat/2^23<256), show decide (256≤w.toNat/2^23)=true from decide_eq_true h,Qw rfl] ·rw [Qw (by omega:w.toNat/2^23<256), show decide (256≤w.toNat/2^23)=false from decide_eq_false h,Qx (by simp)] obtain ⟨g,c⟩:=At _ _ _ (by omega) (by omega) q have hm:=Ao w have i:=AZ ((w&&&0x7FFFFF) ||| 0x800000) have a:=Aa ((w&&&0x7FFFFF) ||| 0x800000) rw [hm] at a rw [Aw] set E:=w.toNat/2^23 % 256 with v have j:((E+873:ℕ):ℤ) - 1023=(E:ℤ) - 150:=by push_cast;ring rw [j] at c have d: |vr ((w&&&0x7FFFFF) ||| 0x800000).toFloat| * |vr (Zz (FE (w.toNat/2^23)))| ≤2^(200:ℤ):=by rw [a,c] have r:((w.toNat % 2^23+2^23:ℕ):ℝ)≤2^(24:ℤ):=by have:w.toNat % 2^23+2^23≤2^24:=by omega calc ((w.toNat % 2^23+2^23:ℕ):ℝ)≤((2^24:ℕ):ℝ):=by exact_mod_cast this _=2^(24:ℤ):=by norm_num have x:(2:ℝ)^((E:ℤ) - 150)≤2^(176:ℤ):= zpow_le_zpow_right₀ (by norm_num) (by omega) have k:(0:ℝ)≤((w.toNat % 2^23+2^23:ℕ):ℝ):=Zg _ rw [abs_of_nonneg k,abs_mul,abs_of_nonneg (by positivity:(0:ℝ)≤2^((E:ℤ) - 150))] have l: |(if decide (256≤w.toNat/2^23)=true then (-1:ℝ) else 1)| =1:=by split<;>simp rw [l,one_mul] calc ((w.toNat % 2^23+2^23:ℕ):ℝ)*2^((E:ℤ) - 150)≤2^(24:ℤ)*2^(176:ℤ):= mul_le_mul r x (by positivity) (by positivity) _=2^(200:ℤ):=by rw [As];norm_num have m:=Ar _ _ i g d refine ⟨m, ?_⟩ have n:mantOf w=w.toNat % 2^23+2^23:=by unfold mantOf have:expOf w≠0:=fun h=>p (by rw [h];rfl) rw [Qx this,Am];omega have o:((idxOf w:ℕ):ℤ) - 149=(E:ℤ) - 150:=by unfold idxOf have:expOf w≠0:=fun h=>p (by rw [h];rfl) rw [Qx this];rw [he] at p⊢;push_cast;omega generalize B:w.toNat % 2^23+2^23=M at a n have t:M<2^24:=by omega have s:((sv w:ℤ):ℝ)=(if decide (256≤w.toNat/2^23)=true then (-1:ℝ) else 1)*(M:ℝ):=by unfold sv;rw [n,u] split<;>simp have y:(if decide (256≤w.toNat/2^23)=true then -(M:ℤ) else (M:ℤ)).natAbs<2^53:=by split<;>simp<;>omega have z:vr ((w&&&0x7FFFFF) ||| 0x800000).toFloat*vr (Zz (FE (w.toNat/2^23)))= (((if decide (256≤w.toNat/2^23)=true then -(M:ℤ) else (M:ℤ)):ℤ):ℝ)*2^((E:ℤ) - 150):=by rw [a,c];split<;>simp<;>ring rw [AU _ _ i g m _ ((E:ℤ) - 150) y (by omega) z,a,c] unfold FH rw [o,s];ring lemma Ay (w:UInt32) (g:(expOf w).toNat=0): (FG w).isFinite=true∧vr (FG w)=0:=by have a:=Aj w have he:=Al w obtain ⟨fe,ff⟩:=Av (w.toNat/2^23) a rw [Qw (by omega)] at fe have b:(Zz (FE (w.toNat/2^23))).toModel.unpack= .zero (FD (FE (w.toNat/2^23))):=by rw [Ac,Ab _ (by rw [fe];omega),dif_pos fe,dif_pos ff] have c:(Zz (FE (w.toNat/2^23))).isFinite=true:=by rw [Ap,b];rfl have d:vr (Zz (FE (w.toNat/2^23)))=0:=by rw [AS,b,Model.unpackedToReal_zero] have e:=AZ ((w&&&0x7FFFFF) ||| 0x800000) rw [Aw] have f:=Ar _ _ e c (by rw [d];simp) refine ⟨f, ?_⟩ rw [AJ _ _ e c f,d,mul_zero,Model.roundAt_zero] lemma Az (w:UInt32) (h:(expOf w).toNat=255):(FG w).isFinite=false:=by have a:=Aj w have he:=Al w obtain ⟨fe, -⟩:=Av (w.toNat/2^23) a rw [Qx (by omega),Qw (by omega)] at fe have b:=Au _ fe rw [Aw] rw [Ap] at b⊢ change (Yq (Ys Zs _ _)).unpack.isFinite=false exact AK _ (AM _ _ (Or.inr b)) def FI (i:Nat):UInt64:= UInt64.ofNat ((if i<256 then 0 else 2^63)+ (if i % 256=255 then 2047*2^52 else (max (i % 256) 1+873)*2^52)) lemma A0 (i:Nat) (a:i<512): (FI i).toNat=(if i<256 then 0 else 2^63)+ (if i % 256=255 then 2047*2^52 else (max (i % 256) 1+873)*2^52):=by unfold FI rw [Z1,Zy] have:i % 256<256:=Nat.mod_lt _ (by decide) split<;>split<;>omega def FJ:FloatArray:=⟨Array.ofFn (n:=512) fun i=>Float.ofBits (FI i.val)⟩ lemma A4:FJ.size=512:=by simp [FJ,Z0] lemma A5 (w:UInt32) (h:(w>>>23).toUSize.toNat>>23).toUSize h=Zz (FI (w.toNat/2^23)):=by have a:(w>>>23).toUSize.toNat<512:=by rw [Ai];exact Aj w have e1:FJ.uget (w>>>23).toUSize h= (Array.ofFn (n:=512) fun i=>Zz (FI i.val))[(w>>>23).toUSize.toNat]'(by simpa using a):=rfl rw [e1,Yk] simp only [Ai] @[inline] def FK (w:UInt32):UInt32:= (w&&&0x7FFFFF) ||| (if (w>>>23)&&&0xFF==0 then 0 else 0x800000) @[inline] def FL (w:UInt32):Float:= (FK w).toFloat*FJ.uget (w>>>23).toUSize (by rw [A4,Ai];exact Aj w) lemma A6 (w:UInt32):FL w=(FK w).toFloat*Zz (FI (w.toNat/2^23)):=by unfold FL;rw [A5] lemma A7 (w:UInt32):(FK w).toNat=mantOf w:=by unfold FK mantOf have a:((w>>>23)&&&0xFF==0)=decide (expOf w=0):=by unfold expOf;by_cases h:((w>>>23)&&&0xFF)=0<;>simp [h] rw [a] by_cases h:expOf w=0 ·rw [Qw h];simp [h,fracOf] ·rw [Qx h];simp only [h,decide_false,Zx,ite_false] rw [show (w&&&0x7FFFFF ||| 0x800000)=(w&&&0x7FFFFF) ||| 0x800000 from rfl,Ao,Am] omega lemma A8 (w:UInt32) (B:(expOf w).toNat≠255): (FL w).isFinite=true∧vr (FL w)=FH w:=by have e:=Aj w have he:=Al w have t:=An w set E:=w.toNat/2^23 % 256 with u have p:(FI (w.toNat/2^23)).toNat= (if decide (256≤w.toNat/2^23) then 2^63 else 0)+(max E 1+873)*2^52:=by rw [A0 _ e] have b: ¬(w.toNat/2^23 % 256=255):=by omega rw [Qx b] by_cases h:256≤w.toNat/2^23 ·rw [Qx (by omega: ¬w.toNat/2^23<256), show decide (256≤w.toNat/2^23)=true from decide_eq_true h,Qw rfl] ·rw [Qw (by omega:w.toNat/2^23<256), show decide (256≤w.toNat/2^23)=false from decide_eq_false h,Qx (by simp)] have q:max E 1+873≤2046:=by have:E<256:=Nat.mod_lt _ (by decide) omega obtain ⟨g,c⟩:=At _ _ _ (by omega) q p have i:((max E 1+873:ℕ):ℤ) - 1023=((max E 1:ℕ):ℤ) - 150:=by push_cast;ring rw [i] at c have j:=AZ (FK w) have a:=Aa (FK w) rw [A7] at a have k:mantOf w<2^24:=Qv w rw [A6] have d: |vr (FK w).toFloat| * |vr (Zz (FI (w.toNat/2^23)))| ≤2^(200:ℤ):=by rw [a,c] have r:((mantOf w:ℕ):ℝ)≤2^(24:ℤ):=by have:mantOf w≤2^24:=by omega calc ((mantOf w:ℕ):ℝ)≤((2^24:ℕ):ℝ):=by exact_mod_cast this _=2^(24:ℤ):=by norm_num have v:(2:ℝ)^(((max E 1:ℕ):ℤ) - 150)≤2^(176:ℤ):=by apply zpow_le_zpow_right₀ (by norm_num) have:E<256:=Nat.mod_lt _ (by decide) omega rw [abs_of_nonneg (Zg _),abs_mul, abs_of_nonneg (by positivity:(0:ℝ)≤2^(((max E 1:ℕ):ℤ) - 150))] have l: |(if decide (256≤w.toNat/2^23)=true then (-1:ℝ) else 1)| =1:=by split<;>simp rw [l,one_mul] calc ((mantOf w:ℕ):ℝ)*2^(((max E 1:ℕ):ℤ) - 150)≤2^(24:ℤ)*2^(176:ℤ):= mul_le_mul r v (by positivity) (by positivity) _=2^(200:ℤ):=by rw [As];norm_num have m:=Ar _ _ j g d refine ⟨m, ?_⟩ have n:((idxOf w:ℕ):ℤ) - 149=((max E 1:ℕ):ℤ) - 150:=by unfold idxOf by_cases o:expOf w=0 ·rw [Qw o] have:E=0:=by rw [←he,o];rfl rw [this];simp ·rw [Qx o] have:E≠0:=fun x=>o (UInt32.toNat_inj.mp (by rw [he,x];rfl)) rw [he];push_cast;omega generalize y:mantOf w=M at a k have s:((sv w:ℤ):ℝ)=(if decide (256≤w.toNat/2^23)=true then (-1:ℝ) else 1)*(M:ℝ):=by unfold sv;rw [y,t] split<;>simp have z:(if decide (256≤w.toNat/2^23)=true then -(M:ℤ) else (M:ℤ)).natAbs<2^53:=by split<;>simp<;>omega have A:vr (FK w).toFloat*vr (Zz (FI (w.toNat/2^23)))= (((if decide (256≤w.toNat/2^23)=true then -(M:ℤ) else (M:ℤ)):ℤ):ℝ)* 2^(((max E 1:ℕ):ℤ) - 150):=by rw [a,c];split<;>simp<;>ring have f:(-1074:ℤ)≤((max E 1:ℕ):ℤ) - 150:=by omega rw [AU _ _ j g m _ _ z f A,a,c] unfold FH rw [n,s];ring lemma A9 (w:UInt32) (h:(expOf w).toNat=255):(FL w).isFinite=false:=by have a:=Aj w have he:=Al w have c:=A0 _ a have b:w.toNat/2^23 % 256=255:=by omega have fe:((FI (w.toNat/2^23)>>>52)&&&0x7ff).toNat=2047:=by rw [(Ae _).1,c] simp only [b,ite_true] split<;>omega have d:=Au _ fe rw [A6] rw [Ap] at d⊢ change (Yq (Ys Zs _ _)).unpack.isFinite=false exact AK _ (AM _ _ (Or.inr d)) noncomputable def FM:List Float→Float→ℝ | [],_=>0 | x::l,s=>(2^(-52:ℤ)* |vr (s+x)| +2^(-1074:ℤ))+FM l (s+x) lemma BA (l:List Float) (s:Float) (h:(l.foldl (· + ·) s).isFinite=true): s.isFinite=true∧(∀x∈l,x.isFinite=true)∧ |vr (l.foldl (· + ·) s) - (vr s+(l.map vr).sum)| ≤FM l s:=by induction l generalizing s with | nil=>simp [FM] at h⊢;exact h | cons x l ih=> simp only [Zk] at h⊢ obtain ⟨a,e,he⟩:=ih (s+x) h obtain ⟨c,d⟩:=AN s x a refine ⟨c, ?_, ?_⟩ ·intro y b rcases List.mem_cons.mp b with rfl | b ·exact d ·exact e y b ·have f:=AR s x c d a simp only [Zr,Zq,FM] calc |vr (List.foldl (· + ·) (s+x) l) - (vr s+(vr x+(List.map vr l).sum))| = |(vr (List.foldl (· + ·) (s+x) l) - (vr (s+x)+(List.map vr l).sum))+ (vr (s+x) - (vr s+vr x))| :=by ring_nf _≤ |vr (List.foldl (· + ·) (s+x) l) - (vr (s+x)+(List.map vr l).sum)| + |vr (s+x) - (vr s+vr x)| :=abs_add_le _ _ _≤FM l (s+x)+(2^(-52:ℤ)* |vr (s+x)| +2^(-1074:ℤ)):=add_le_add he f _=(2^(-52:ℤ)* |vr (s+x)| +2^(-1074:ℤ))+FM l (s+x):=by ring lemma BB (a b:USize) (h:a.toNat+b.toNat<2^32): (a+b).toNat=a.toNat+b.toNat:=by rw [Xn] have:2^32≤USize.size:=Yj have c:USize.size=2^Zd:=rfl exact Zy (by omega) lemma BC (t n:USize) (h:tFloat.ofBits (FN i.val)⟩ lemma BE:FO.size=256:=by simp [FO,Z0] def FP (i:Nat):UInt64:=UInt64.ofNat ((i % 256+844)*2^52) def FQ:FloatArray:=⟨Array.ofFn (n:=256) fun i=>Float.ofBits (FP i.val)⟩ lemma BF:FQ.size=256:=by simp [FQ,Z0] def FR:Float:=Float.ofBits (UInt64.ofNat (971*2^52)) def FS:Float:=Float.ofBits (UInt64.ofNat (972*2^52)) def FT:Float:=Float.ofBits (UInt64.ofNat (898*2^52)) def FU:Float:=Float.ofBits (UInt64.ofNat (723*2^52)) lemma BG (o:UInt32):(((o>>>23)&&&0xFF).toUSize).toNat<256:=by rw [Yf,Zl] exact X6 Nat.and_le_right (by decide) @[inline] def FV (o:UInt32):Float:= FO.uget ((o>>>23)&&&0xFF).toUSize (by rw [BE];exact BG o) def FW (X:Array UInt32) (xo n o st k:Nat) (A:FloatArray) (s:Float):FloatArray×Float:= if k>>52)&&&0x7FF if h:897≤eT∧eT≤1150 then let q:=bT&&&0x1FFFFFFF let hi:=(bT>>>29)&&&0x7FFFFF let up:=decide (0x10000000>>63==1 if relu&&neg then 0 else (if neg then (0x80000000:UInt64) else 0) ||| ((eT - 896)<<<23) ||| (hi+(if up then 1 else 0)) else 0x100000000 else 0x100000000 open ExactRuntime lemma BJ (m:Nat) (h:m<2^32):m.toUSize.toNat=m:=by have:2^32≤USize.size:=Yj have a:USize.size=2^Zd:=rfl simp only [Nat.toUSize] exact Zy (by omega) @[inline] def Ff (s:Bool) (p:Nat):Int:=if s then -(p:Int) else (p:Int) def Fg (fa fb:Nat→Word) (index:Nat):Nat→Nat→Nat | 0,m=>m | count+1,m=>Fg fa fb (index+1) count (min m (idxOf (fa index)+idxOf (fb index))) def Fh (fa fb:Nat→Word) (m index:Nat):Nat→Int | 0=>0 | count+1=>Ff (Bool.xor (signOf (fa index)) (signOf (fb index))) ((mantOf (fa index)*mantOf (fb index))<<<(idxOf (fa index)+idxOf (fb index) - m))+ Fh fa fb m (index+1) count def Fi (fa fb:Nat→Word) (index:Nat):Nat→Bool | 0=>true | count+1=>(expOf (fa index) !=255&&expOf (fb index) !=255)&&Fi fa fb (index+1) count def Fj:DotFn:=fun n fa fb=> if Fi fa fb 0 n then let m:=Fg fa fb 0 n 1024 let S:=Fh fa fb m 0 n if S≠0 then finishWord S ((m:Int) - 298) false else dotOf n fa fb else dotOf n fa fb def Fk:DotFn:=Fj def Fl (inW:Nat) (relu:Bool) (X W b:Array Word) (i j:Nat):Word:= act relu (Fk (inW+1) (fun t=>if t< inW then X[i*inW+t]! else oneW) (fun t=>if t< inW then W[j*inW+t]! else b[j]!)) @[inline] def Fm (inW:Nat) (relu:Bool) (X W b:Array Word) (i j:Nat) (r:UInt64):Word:= if r<0x100000000 then r.toUInt32 else Fl inW relu X W b i j def Fn (inW:Nat) (relu:Bool) (W:Array Word) (j:Nat) (bd:Float) (x:FloatArray) (off st:Nat) (sx:Float) (hW:j*inW+inW≤W.size) (hWs:W.size<2^32) (hxs:x.size<2^32) (hx: ∀t,t< inW→ off+st*tby rw [BJ _ hoff,BJ _ hst] rw [BJ _ hin] at ht exact hx t ht) hxs (by rw [BJ _ (by omega),BJ _ hin];exact hW) hWs 0 0 0 let T:=q.s+bd Fe relu T (FS*((q.c+T.abs)+bd.abs)+sx*FT+FU) @[inline] def Fo (inW:Nat) (relu:Bool) (W:Array Word) (j:Nat) (bd:Float) (x:FloatArray) (off st:Nat) (sx C K ob s:Float) (ok:Bool) (hW:j*inW+inW≤W.size) (hWs:W.size<2^32) (hxs:x.size<2^32) (hx: ∀t,t< inW→ off+st*tomega have hr1:j*inW+inW≤W.size:=Nat.le_trans (BK j outW inW hj) hW have hr2:j2*inW+inW≤W.size:=Nat.le_trans (BK j2 outW inW hj2) hW have hm1:j*inW<2^32:=by omega have hm2:j2*inW<2^32:=by omega have hx1: ∀t,t< inW→0+1*tby omega have hw1:(j*inW).toUSize.toNat+inW.toUSize.toNat≤W.size:=by rw [BJ _ hm1,BJ _ (by omega)];exact hr1 have hw2:(j2*inW).toUSize.toNat+inW.toUSize.toNat≤W.size:=by rw [BJ _ hm2,BJ _ (by omega)];exact hr2 let r:FQ3:=if gath then let g:=Fb c.xc c.IX W (j*inW).toUSize (j2*inW).toUSize c.IX.size.toUSize inW.toUSize (by rw [BJ _ hIs];exact hc) (by rw [BJ _ hIs]) (fun k hk=>by rw [BJ _ (by omega)];exact hIX k hk) hw1 hw2 hWs 0 0 0 ⟨g.s0,g.s1,FY W (j*inW).toUSize inW.toUSize hw1 hWs 0 0 ||| FY W (j2*inW).toUSize inW.toUSize hw2 hWs 0 0⟩ else Fa x W (j*inW).toUSize (j2*inW).toUSize inW.toUSize (by rw [BJ _ (by omega)];exact hx) hw1 hw2 hWs 0 0 0 0 let z:=r.o let ok:=(z>>>23)&&&0xFF !=0xFF let ob:=FV z let b0:=FL b[j]! let b1:=FL b[j2]! let C:=sx*FT+FU let d0:=Fo inW relu W j b0 x 0 1 sx C K ob r.s0 ok hr1 hWs hxs hx1 (by omega) (by decide) (by decide) let d1:=Fo inW relu W j2 b1 x 0 1 sx C K ob r.s1 ok hr2 hWs hxs hx1 (by omega) (by decide) (by decide) let out:=(out.set! (i*outW+j) (Fm inW relu X W b i j d0)).set! (i*outW+j2) (Fm inW relu X W b i j2 d1) Fp inW outW relu X W b i x c hIX gath sx K hW hWs hin hx hxs hc hIs (j+2) out else out termination_by outW - j def FS8.of (sx:Array Float):FS8:= let g:=fun k=>sx[k]! ⟨g 0,g 1,g 2,g 3,g 4,g 5,g 6,g 7,g 0*FT+FU,g 1*FT+FU,g 2*FT+FU, g 3*FT+FU,g 4*FT+FU,g 5*FT+FU,g 6*FT+FU,g 7*FT+FU⟩ @[inline] def Fq (inW outW:Nat) (relu:Bool) (X W b:Array Word) (i j k:Nat) (bd:Float) (x8:FloatArray) (sxk ck K ob s:Float) (hW:j*inW+inW≤W.size) (hWs:W.size<2^32) (hxs:x8.size<2^32) (hx:8*inW≤x8.size) (hin:inW<2^32) (hk:k<8) (o:Array Word): Array Word:= o.set! ((i+k)*outW+j) (Fm inW relu X W b (i+k) j (Fo inW relu W j bd x8 k 8 sxk ck K ob s true hW hWs hxs (fun t ht=>by omega) hin (by decide) (by omega))) def Fr (inW outW:Nat) (relu:Bool) (X W b:Array Word) (i:Nat) (x8:FloatArray) (sx:FS8) (K:Float) (hW:outW*inW≤W.size) (hWs:W.size<2^32) (hin:inW<2^20) (hx:8*inW≤x8.size) (hxs:x8.size<2^32) (j:Nat) (out:Array Word):Array Word:= if hj:j unfold FX;simp only [Qw a];simp only [w] at b;rw [Qw b] exact ih h | case2 k xc IX a w b ih=> unfold FX;simp only [Qw a];simp only [w] at b;rw [Qx b] apply ih intro v c rcases Array.mem_push.mp c with c | c ·exact h v c ·subst c;rw [Xm,Yv,Zy (by omega)];exact a | case3 k xc IX a=> unfold FX;simp only [Qx a];exact h def Fu (rows inW outW:Nat) (relu:Bool) (X W b:Array Word) (K:Float) (hW:outW*inW≤W.size) (hWs:W.size<2^32) (hin:inW<2^20) (i:Nat) (out:Array Word):Array Word:= if i+8≤rows then let q:=Ft X inW i 0 ⟨Array.replicate (8*inW) 0⟩ #[] let out:=if h:8*inW≤q.1.size∧q.1.size≤4294967295 then Fr inW outW relu X W b i q.1 (FS8.of q.2) K hW hWs hin h.1 (by omega) 0 out else Fs inW outW relu X W b i 8 0 out Fu rows inW outW relu X W b K hW hWs hin (i+8) out else if iby simp at hv) let out:=if h:inW≤r.1.size∧r.1.size≤4294967295∧c.IX.size≤c.xc.size∧c.IX.size≤4294967295 then Fp inW outW relu X W b i r.1 c (fun k hk=>hc _ (Array.getElem_mem hk)) (8*c.IX.size<7*inW) r.2 K hW hWs hin h.1 (by omega) h.2.2.1 (by omega) 0 out else Fs inW outW relu X W b i 1 0 out Fu rows inW outW relu X W b K hW hWs hin (i+1) out else out termination_by rows - i def Fv (rows inW outW:Nat) (relu:Bool) (X W b:Array Word):Array Word:= if h:rows*inW≤X.size∧outW*inW≤W.size∧outW≤b.size∧0< inW∧inW<1048576∧ X.size≤4294967295∧W.size≤4294967295 then Fu rows inW outW relu X W b ((inW+9).toUInt64.toFloat*FR) h.2.1 (by omega) (by omega) 0 (Array.replicate (rows*outW) 0) else linearWith dotOf rows inW outW relu X W b end FP64 namespace FP64 open FloatLib.Floats.Formats.BinaryInterchange FloatLib.Floats ExactRuntime lemma BM (x:FloatArray) (t:USize) (h:t.toNatx.data[t]! *FG W[wo+t]!) lemma BU (t n:Nat) (h:t rw [Fa];simp only [dif_pos h] obtain ⟨i1,i2,i3,i4⟩:=ih have l:=BC t n h have e:xv=x.data[t.toNat]! :=BM _ _ _ have f:w0=W[wo.toNat+t.toNat]! :=by simp only [w0];rw [BN,BB _ _ (by omega)] have g:w1=W[wo2.toNat+t.toNat]! :=by simp only [w1];rw [BN,BB _ _ (by omega)] refine ⟨?_, ?_, ?_, ?_⟩ ·rw [i1,l,Fx,Fx,BU _ _ j,Zr,Zk,e,f] ·rw [i2,l,Fx,Fx,BU _ _ j,Zr,Zk,e,g] ·exact le_trans (BP _ _).1 i3 ·intro k m i rcases Z6 t.toNat k with p | p ·exact i4 k (by omega) i ·have:k=t.toNat:=by omega subst this have a1:=BP o (w0 ||| w1) have a2:=BP w0 w1 rw [←f,←g] exact ⟨le_trans (le_trans a2.1 a1.2) i3,le_trans (le_trans a2.2 a1.2) i3⟩ | case2 t s0 s1 o h=> rw [Fa];simp only [dif_neg h] have:n.toNat - t.toNat=0:=by have:=USize.lt_iff_toNat_lt.not.mp h;omega refine ⟨by simp [Fx,this],by simp [Fx,this],le_refl _,fun k r q=>absurd q (by omega)⟩ def Fy (xc:FloatArray) (IX W:Array UInt32) (wo k0 n:Nat):List Float:= (List.range' k0 (n - k0)).map (fun k=>xc.data[k]! *FG W[wo+IX[k]!.toNat]!) lemma BW (xc:FloatArray) (IX W:Array UInt32) (wo wo2 n m:USize) (i:n.toNat≤xc.size) (j:n.toNat≤IX.size) (c: ∀k (g:k rw [Fb];simp only [dif_pos h] obtain ⟨i1,i2⟩:=ih have o:=BC k n h have f:xv=xc.data[k.toNat]! :=BM _ _ _ have b:ix=IX[k.toNat]! :=BN _ _ _ have e0:W.uget (wo+ix.toUSize) q=W[wo.toNat+(IX[k.toNat]!).toNat]! :=by rw [BN,BB _ _ (by rw [a];omega),a,b] have e1:W.uget (wo2+ix.toUSize) r=W[wo2.toNat+(IX[k.toNat]!).toNat]! :=by rw [BN,BB _ _ (by rw [a];omega),a,b] refine ⟨?_, ?_⟩ ·simp only [w0] at i1;rw [i1,o,Fy,Fy,BU _ _ g,Zr,Zk,f,e0] ·simp only [w1] at i2;rw [i2,o,Fy,Fy,BU _ _ g,Zr,Zk,f,e1] | case2 k s0 s1 h=> rw [Fb];simp only [dif_neg h] have:n.toNat - k.toNat=0:=by have:=USize.lt_iff_toNat_lt.not.mp h;omega exact ⟨by simp [Fy,this],by simp [Fy,this]⟩ def Fz (x:FloatArray) (W:Array UInt32) (r wo t0 n:Nat):List Float:= (List.range' t0 (n - t0)).map (fun t=>x.data[8*t+r]! *FG W[wo+t]!) lemma BX (x:FloatArray) (t:USize) (r:Nat) (a:r<8) (h:8*t.toNat+r<2^32) (b:(t*8+r.toUSize).toNat intro r simp only [r] rw [Fc];simp only [dif_pos h] have v:=BC t n h have c:w=W[wo.toNat+t.toNat]! :=by simp only [w];rw [BN,BB _ _ (by omega)] have y:d=FG W[wo.toNat+t.toNat]! :=by simp only [d,c] obtain ⟨e,f,g⟩:=BT o w p obtain ⟨i0,i1,i2,i3,i4,i5,i6,i7,i8,i9,i10⟩:=ih e have C:8*t.toNat+7<2^32:=by omega have st: ∀(rr:Nat) (q:rr<8) (s:Float) (i:(t*8+rr.toUSize).toNat intro r simp only [r] rw [Fc];simp only [dif_neg h] have:n.toNat - t.toNat=0:=by have:=USize.lt_iff_toNat_lt.not.mp h;omega simp only [Fz,this,List.range'_zero,Y9,List.foldl_nil,true_and] exact ⟨p,le_refl _,fun k D B=>absurd B (by omega)⟩ def F0:List Float→Float→List Float | [],_=>[] | y::l,s=>(s+y)::F0 l (s+y) def F1 (x:FloatArray) (W:Array UInt32) (off st wo t0 n:Nat):List Float:= (List.range' t0 (n - t0)).map (fun t=>x.data[off+st*t]! *FG W[wo+t]!) lemma BZ (x:FloatArray) (W:Array UInt32) (off st wo n:USize) (f: ∀t,ta+y.abs) c:=by induction t,s,c using Fd.induct x W off st wo n f b g d with | case1 t s c h i k s' ih=> rw [Fd];simp only [dif_pos h] obtain ⟨i1,i2⟩:=ih have j:=BC t n h have e:s' =s+x.data[off.toNat+st.toNat*t.toNat]! *FG W[wo.toNat+t.toNat]! :=by simp only [s'];rw [BM,BN,BH _ _ _ (by omega),BB _ _ (by omega)] refine ⟨?_, ?_⟩ ·rw [i1,j,F1,F1,BU _ _ i,Zr,Zk,e] ·rw [i2,j,F1,F1,BU _ _ i,Zr,F0,Zk,←e] | case2 t s c h=> rw [Fd];simp only [dif_neg h] have:n.toNat - t.toNat=0:=by have:=USize.lt_iff_toNat_lt.not.mp h;omega exact ⟨by simp [F1,this],by simp [F1,this,F0]⟩ lemma Ba (W:Array UInt32) (wo n:USize) (b:wo.toNat+n.toNat≤W.size) (a:W.size<2^32) (t:USize) (o:UInt32): Fw o≤Fw (FY W wo n b a t o)∧ ∀k,t.toNat≤k→k rw [FY];simp only [dif_pos h] obtain ⟨i1,i2⟩:=ih have j:=BC t n h have e:W.uget (wo+t) (by rw [BB _ _ (by omega)];omega)=W[wo.toNat+t.toNat]! :=by rw [BN,BB _ _ (by omega)] rw [e] at i1 i2⊢ refine ⟨le_trans (BP _ _).1 i1, ?_⟩ intro k d c rcases Z6 t.toNat k with f | f ·exact i2 k (by omega) c ·have:k=t.toNat:=by omega subst this;exact le_trans (BP _ _).2 i1 | case2 t o h=> rw [FY];simp only [dif_neg h] exact ⟨le_refl _,fun k l g=>absurd g (by have:=USize.lt_iff_toNat_lt.not.mp h;omega)⟩ lemma Bb (A:Array Float) (i p:Nat) (v:Float): (A.set! i v)[p]! =if i=p∧ia (b▸c) simp [this] def F2 (X:Array UInt32) (xo k n:Nat):List Float:= (List.range' k (n - k)).map (fun t=>(FL X[xo+t]!).abs) lemma Bc (X:Array UInt32) (xo n o st k:Nat) (A:FloatArray) (s:Float) (r:1≤ st): (FW X xo n o st k A s).1.size=A.size∧ (∀j,k≤j→j rw [FW];simp only [Qw c] obtain ⟨i1,i2,i3,i4⟩:=ih have f:(A.set! (o+k*st) v).size=A.size:=by rcases A with ⟨d⟩;simp [FloatArray.set!,Z0] have a: ∀p,(A.set! (o+k*st) v).data[p]! =if o+k*st=p∧o+k*stby have:j*stq j (by omega) b),a] have: ¬(o+k*st=p∧o+k*stq k (le_refl _) c e.symm rw [Qx this] ·rw [i4,F2,F2,BU _ _ c,Zr,Zk] | case2 k A s c=> rw [FW];simp only [Qx c] exact ⟨by simp,fun j u t=>absurd t (by omega),fun p _=>by simp,by simp [F2,show n - k=0 by omega]⟩ lemma Bd {α:Type} [Inhabited α] (xs:Array α) (x:α) (i:Nat) (h:i rw [Ft];simp only [Qw f] obtain ⟨i1,i2,i3,i4,i5,i6⟩:=ih obtain ⟨f1,f2,f3,f4⟩:=Bc X ((i+r)*inW) inW r 8 0 A 0 (by decide) simp only [q] at i1 i2 i3 i4 i5 i6 refine ⟨by rw [i1,f1], ?_, ?_, ?_, ?_, ?_⟩ ·intro r' t g a n s rcases Z6 r r' with b | h ·exact i2 r' t b a n (by rw [f1];exact s) ·have:r' =r:=by omega subst this rw [i3 _ (fun r'' t' k c d=>by omega)] have:=f2 t (Nat.zero_le _) n (by omega) rw [show r' +t*8=8*t+r' by ring] at this exact this ·intro p o rw [i3 p (fun r'' t' k c d=>o r'' t' (by omega) c d), f3 p (fun j _ l e=>o r j (le_refl _) f l (by rw [e];ring))] ·rw [i4];simp;omega ·intro q' m rw [i5 q' (by simp;omega),Bd _ _ _ m] ·intro r' g a rcases Z6 r r' with b | h ·have:=i6 r' b a rw [Array.size_push] at this rw [show sx.size+(r' - r)=sx.size+1+(r' - (r+1)) by omega];exact this ·have:r' =r:=by omega subst this rw [show sx.size+(r' - r')=sx.size by omega,i5 sx.size (by simp),Be,f4] | case2 r A sx f=> rw [Ft];simp only [Qx f] exact ⟨by simp,fun r' t g a=>absurd a (by omega),fun p _=>by simp,by simp;omega, fun q _=>by simp,fun r' g a=>absurd a (by omega)⟩ def F3 (X:Array UInt32) (xo k n:Nat):List Nat:= (List.range' k (n - k)).filter (fun t=>X[xo+t]! &&&0x7FFFFFFF !=0) lemma Bg (X:Array UInt32) (xo n k:Nat) (xc:FloatArray) (IX:Array UInt32): (FX X xo n k xc IX).IX.toList=IX.toList++(F3 X xo k n).map Xm∧ (FX X xo n k xc IX).xc.data.toList=xc.data.toList++(F3 X xo k n).map (fun t=>FL X[xo+t]!):=by induction k,xc,IX using FX.induct X xo n with | case1 k xc IX a w b ih=> unfold FX;simp only [Qw a];simp only [w] at b;rw [Qw b] obtain ⟨i1,i2⟩:=ih rw [i1,i2,F3,F3,BU _ _ a,List.filter_cons] simp [b] | case2 k xc IX a w b ih=> unfold FX;simp only [Qw a];simp only [w] at b;rw [Qx b] obtain ⟨i1,i2⟩:=ih rw [i1,i2,F3,F3,BU _ _ a,List.filter_cons] have:(X[xo+k]! &&&0x7FFFFFFF !=0)=true:=by simpa using b rw [Qw this] rcases xc with ⟨d⟩ simp [FloatArray.push];rfl | case3 k xc IX a=> unfold FX;simp only [Qx a] simp [F3,show n - k=0 by omega] lemma Bh (m:Nat) (h:m<2^32):(m.toUInt32).toNat=m:=by rw [Xm,Yv,Zy h] lemma Bi (X:Array UInt32) (xo k n:Nat): ∀t∈F3 X xo k n,tFL X[xo+t]! *FG W[wo+t]!):=by intro c obtain ⟨e,f⟩:=Bg X xo n 0 (Zb n) (Z8 n) simp only [c] at* set L:=F3 X xo 0 n with i have e1:(FX X xo n 0 (Zb n) (Z8 n)).IX.toList=L.map Xm:=by rw [e];simp have e2:(FX X xo n 0 (Zb n) (Z8 n)).xc.data.toList= L.map (fun t=>FL X[xo+t]!):=by rw [f];simp [Zb] have a:(FX X xo n 0 (Zb n) (Z8 n)).IX.size=L.length:=by rw [←Ws,e1,Y8] rw [Fy,a,Xl] apply List.ext_getElem ·simp ·intro k b g simp only [Wr,List.getElem_range',Nat.one_mul,Z4] have d:krfl ·split ·split<;>rfl ·rfl lemma Bm (a:Float):(Float.abs a).toModel.unpack=a.toModel.unpack.abs:=by show (Yq (a.toModel.unpack.abs)).unpack=a.toModel.unpack.abs have b:a.toModel.unpack=Zc Zs a.toBits.toBitVec:=rfl rw [b,Bl] show Zc Zs (UInt64.ofBitVec (Wv Zs _)).toBitVec=_ rw [UInt64.toBitVec_ofBitVec,Model.unpack_pack_unpack] lemma Bn (e:ℤ):0exact ⟨rfl,by simp [Zf,Yl,Ym]⟩ | infinity s=>exact ⟨rfl,by simp [Zf,Yl,Ym]⟩ | zero s=>exact ⟨rfl,by simp [Zf,Yl,Ym]⟩ | finite s m e hm=> simp only [Zf] refine ⟨rfl, ?_⟩ rw [Z2,Z2] have b:=Bn e cases s<;>simp [Z9,abs_mul,abs_of_pos b] open Float.Model (Format UnpackedFloat totalExponent) in lemma Bp (m:UInt64) (g:m≠0) (d:m.toNat<2^53): (Y7 m).toModel.unpack= .finite .positive (m.toNat<<<(52 - m.toNat.log2)) (-((52 - m.toNat.log2:Nat):Int)) (by have:m.toNat≠0:=by intro h;apply g;exact UInt64.toNat_inj.mp (by simpa using h) simp [Zp];omega):=by have hm:m.toNat≠0:=by intro h;apply g;exact UInt64.toNat_inj.mp (by simpa using h) have c:m.toNat.log2<53:=(Nat.log2_lt hm).2 d set k:=52 - m.toNat.log2 with l have a:m.toNat<<>>52)&&&0x7ff).toNat=2047 ·exfalso have:=Au u d rw [Ap,Ac,h] at this simp [Zm] at this ·rw [Ab u d] at h have f:=(Ae u).2.1 have j:=(Ae u).1 have k:=u.toNat_lt split at h ·split at h ·exact absurd h (by simp) ·injection h with g b c subst b c refine ⟨by rw [f];omega,Or.inr rfl,le_refl _⟩ ·injection h with g b c subst b c refine ⟨by rw [f];omega,Or.inl (by omega),by omega⟩ lemma B0 (m m' :Nat) (e e' :Int) (c:m<2^53) (d:2^52≤ m' ∨e' = -1074) (he: -1074≤e) (f:ecases p<;>simp_all [Ordering.then] lemma B3 (E H:Float) (h:Float.abs Erw [f] at a;simp [Zf,Yu] at a | infinity s=> rw [f] at a cases b:H.toModel.unpack with | notANumber=>rw [b] at c;simp [Zm] at c | infinity s' =>rw [b] at c;simp [Zm] at c | zero s' =>rw [b] at a;simp [Zf,Yu] at a | finite s' m' e' d=> rw [b] at a;cases s' <;>simp [Zf,Yu] at a | zero s=> rw [f] at a refine ⟨rfl, ?_⟩ have j:Yl (Float.Model.UnpackedFloat.zero s)=0:=by simp [Yl,Ym] rw [j,abs_zero] cases b:H.toModel.unpack with | notANumber=>rw [b] at c;simp [Zm] at c | infinity s' =>rw [b] at c;simp [Zm] at c | zero s' =>rw [b] at a;simp [Zf,Yu] at a | finite s' m' e' d=> rw [b] at a cases s' ·simp [Zf,Yu] at a ·rw [Z2,B1] simp only [Z9,Zx,ite_false,one_mul] exact mul_pos (by exact_mod_cast d) (by positivity) | finite s m e hm=> rw [f] at a refine ⟨rfl, ?_⟩ obtain ⟨c1,c2,c3⟩:=Bz E s m e hm f rw [Z2,B1] have g: |(if Z9 s then (-1:ℝ) else 1)*(m:ℝ)*(2:ℝ)^e| =(m:ℝ)*2^e:=by cases s<;>simp [Z9,abs_mul,abs_of_pos (show (0:ℝ)<2^e by positivity)] rw [g] cases b:H.toModel.unpack with | notANumber=>rw [b] at c;simp [Zm] at c | infinity s' =>rw [b] at c;simp [Zm] at c | zero s' =>rw [b] at a;simp [Zf,Yu] at a | finite s' m' e' d=> rw [b] at a cases s' ·simp [Zf,Yu] at a ·obtain ⟨d1,d2,d3⟩:=Bz H _ m' e' d b simp only [Zf,Yu,Option.some.injEq, beq_iff_eq] at a rw [Z2,B1] simp only [Z9,Zx,ite_false,one_mul] apply B0 m m' e e' c1 d2 c3 rcases B2 _ _ a with i | ⟨i,k⟩ ·left;exact compare_lt_iff_lt.mp i ·right;exact ⟨compare_eq_iff_eq.mp i,compare_lt_iff_lt.mp k⟩ lemma B4 (u η δ V B R m e:ℝ) (a:0≤u) (l:u≤1/2) (g:0≤η) (d:0≤δ) (n:0≤V) (h:0≤B) (o:0≤R) (p:0≤ m) (v:u*(m+1)*(1+δ)≤δ*(1 - u)) (q:(1 - u)*V≤B+η) (he:e≤ m*u*(1+δ)*(V+R)+m*(1+δ)*η): (u*V+η)+e≤(m+1)*u*(1+δ)*(B+R)+(m+1)*(1+δ)*η:=by set c:=u*(1+m*(1+δ)) with b have i:0≤c:=by positivity have r:0≤δ - u*(m+1)*(1+δ):=by nlinarith [mul_nonneg d a] have k1:c≤(1 - u)*(m+1)*u*(1+δ):=by have e1:(1 - u)*(m+1)*u*(1+δ) - c=u*(δ - u*(m+1)*(1+δ)):=by rw [b];ring nlinarith [mul_nonneg a r] have k2:c≤(1 - u)*δ:=by have:c≤u*(m+1)*(1+δ):=by rw [b];nlinarith [mul_nonneg a d] linarith have w:c*(B+η)≤(1 - u)*((m+1)*u*(1+δ)*B+δ*η):=by have:=mul_le_mul_of_nonneg_right k1 h have:=mul_le_mul_of_nonneg_right k2 g nlinarith have x:c*((1 - u)*V)≤c*(B+η):=mul_le_mul_of_nonneg_left q i have f:0<1 - u:=by linarith have s:c*V≤(m+1)*u*(1+δ)*B+δ*η:=by have t:(1 - u)*(c*V)≤(1 - u)*((m+1)*u*(1+δ)*B+δ*η):=by nlinarith exact le_of_mul_le_mul_left t f have j:(u*V+η)+e≤c*V+η+m*u*(1+δ)*R+m*(1+δ)*η:=by rw [b];nlinarith have y:0≤u*(1+δ)*R:=by positivity have k:c*V+η+m*u*(1+δ)*R+m*(1+δ)*η≤ (m+1)*u*(1+δ)*(B+R)+(m+1)*(1+δ)*η:=by have:(m+1)*u*(1+δ)*(B+R)+(m+1)*(1+δ)*η= ((m+1)*u*(1+δ)*B+δ*η)+η+m*u*(1+δ)*R+m*(1+δ)*η+u*(1+δ)*R:=by ring rw [this];linarith linarith lemma B5 (l:List Float) (s:Float) (h:(l.foldl (· + ·) s).isFinite=true) (d:l.length≤2^20): FM l s≤(l.length:ℝ)*2^(-52:ℤ)*(1+2^(-30:ℤ))*(|vr s| +(l.map (fun x=> |vr x|)).sum)+ (l.length:ℝ)*(1+2^(-30:ℤ))*2^(-1074:ℤ):=by induction l generalizing s with | nil=>simp [FM] | cons x l ih=> simp only [Zk] at h simp only [Y6] at d⊢ obtain ⟨a, -, -⟩:=BA l (s+x) h obtain ⟨e,f⟩:=AN s x a have b:=ih (s+x) h (by omega) have he:=AR s x e f a have g:(1 - 2^(-52:ℤ))* |vr (s+x)| ≤(|vr s| + |vr x|)+2^(-1074:ℤ):=by have t1: |vr (s+x)| ≤ |vr s+vr x| + |vr (s+x) - (vr s+vr x)| :=by have:=abs_sub_abs_le_abs_sub (vr (s+x)) (vr s+vr x);linarith have t2:=abs_add_le (vr s) (vr x) nlinarith simp only [FM,Zr,Zq] have c:0≤(l.map (fun x=> |vr x|)).sum:=Yp (by simp) have i:(2:ℝ)^(-52:ℤ)*((l.length:ℝ)+1)*(1+2^(-30:ℤ))≤ 2^(-30:ℤ)*(1 - 2^(-52:ℤ)):=by have j:(l.length:ℝ)+1≤2^20:=by have:l.length+1≤2^20:=by omega exact_mod_cast this have e1:(2:ℝ)^(-52:ℤ)=1/2^52:=by norm_num have e2:(2:ℝ)^(-30:ℤ)=1/2^30:=by norm_num rw [e1,e2] have:(1/2^52:ℝ)*((l.length:ℝ)+1)*(1+1/2^30)≤(1/2^52)*2^20*(1+1/2^30):=by apply mul_le_mul_of_nonneg_right _ (by positivity) exact mul_le_mul_of_nonneg_left j (by positivity) linarith [show (1/2^52:ℝ)*2^20*(1+1/2^30)≤1/2^30*(1 - 1/2^52) by norm_num] push_cast have:=B4 (2^(-52:ℤ)) (2^(-1074:ℤ)) (2^(-30:ℤ)) |vr (s+x)| (|vr s| + |vr x|) ((l.map (fun x=> |vr x|)).sum) (l.length:ℝ) (FM l (s+x)) (by positivity) (by norm_num) (by positivity) (by positivity) (abs_nonneg _) (by positivity) c (Zg _) i g b linarith lemma B6 (l:List Float) (s:Float) (h:(l.foldl (· + ·) s).isFinite=true) (a:l.length≤2^20): FM l s≤(l.length:ℝ)*2^(-51:ℤ)*(|vr s| +(l.map (fun x=> |vr x|)).sum)+ 3*(l.length:ℝ)*2^(-1074:ℤ):=by have g:=B5 l s h a have k1:=mul_le_mul_of_nonneg_left (show (2:ℝ)^(-52:ℤ)*(1+2^(-30:ℤ))≤2^(-51:ℤ) by norm_num) (mul_nonneg (Zg l.length) (add_nonneg (abs_nonneg (vr s)) (Yp (by simp): 0≤(l.map (fun x=> |vr x|)).sum))) have k2:=mul_le_mul_of_nonneg_left (show (1:ℝ)+2^(-30:ℤ)≤3 by norm_num) (mul_nonneg (Zg l.length) (by positivity:(0:ℝ)≤2^(-1074:ℤ))) linarith section open Float.Model Float.Model.UnpackedFloat open FloatLib.Floats.Formats.BinaryInterchange FloatLib.Floats namespace Bridge lemma B7 (em:ExtendedMantissa) (n:Nat): (em>>>n).mantissa=em.mantissa/2^n:=by show (Nat.repeat ExtendedMantissa.shiftRightOne n em).mantissa=_ induction n with | zero=>simp [Nat.repeat] | succ n ih=> simp only [Nat.repeat,ExtendedMantissa.shiftRightOne,ih,Yi,Nat.div_div_eq_div_mul] lemma B8 (m k:Nat) (hm:m≠0):(m<<simp | succ k ih=> have a:m<<<(k+1)=2*(m<<simp [Accuracy.roundToNearestEven] | inexact o=>cases o<;>simp [Accuracy.roundToNearestEven] lemma CB (em:ExtendedMantissa):em.mantissa≤em.roundedMantissa:=by unfold ExtendedMantissa.roundedMantissa;exact CA _ _ end Bridge namespace Bridge def F4 (m:Nat):Nat:=(23 - (m.log2:Int)).toNat def m1 (m:Nat):Nat:=m<<>>F5 m def rm (m:Nat):Nat:=(F6 m).roundedMantissa def F7 (m:Nat):Nat:=(((rm m).log2:Int) - 23).toNat def fm (m:Nat):Nat:=(ExtendedMantissa.ofMantissaAndAccuracy (rm m) .exact>>>F7 m).mantissa lemma CC (m:Nat) (hm:m≠0):2^23≤(F6 m).mantissa∧(F6 m).mantissa<2^24:=by have a:=Xw hm have b:=Xv (n:=m) unfold F6 rw [B7] simp only [ExtendedMantissa.ofMantissaAndAccuracy,m1,F4,F5] rcases Z6 m.log2 23 with h | h ·have e0:(23 - (m.log2:Int)).toNat=23 - m.log2:=by omega have e1:((m.log2:Int) - 23).toNat=0:=by omega rw [e0,e1,Zp,pow_zero,Nat.div_one] constructor ·calc 2^23=2^m.log2*2^(23 - m.log2):=by rw [←pow_add];congr 1;omega _≤ m*2^(23 - m.log2):=Zj _ a ·calc m*2^(23 - m.log2)<2^(m.log2+1)*2^(23 - m.log2):= Yo b (by positivity) _=2^24:=by rw [←pow_add];congr 1;omega ·have e0:(23 - (m.log2:Int)).toNat=0:=by omega have e1:((m.log2:Int) - 23).toNat=m.log2 - 23:=by omega rw [e0,e1,Nat.shiftLeft_zero] constructor ·rw [Yg (by positivity),←pow_add] calc 2^(23+(m.log2 - 23))=2^m.log2:=by congr 1;omega _≤ m:=a ·rw [Xx (by positivity),←pow_add] calc m<2^(m.log2+1):=b _=2^(24+(m.log2 - 23)):=by congr 1;omega lemma CD (m:Nat) (a:Accuracy):a.roundToNearestEven m≤ m+1:=by cases a with | exact=>simp [Accuracy.roundToNearestEven] | inexact o=>cases o<;>simp [Accuracy.roundToNearestEven]<;>omega lemma CE (m:Nat) (hm:m≠0):2^23≤rm m∧rm m≤2^24:=by obtain ⟨c,d⟩:=CC m hm have a:=CB (F6 m) have b:(F6 m).roundedMantissa≤(F6 m).mantissa+1:=by unfold ExtendedMantissa.roundedMantissa;exact CD _ _ unfold rm;omega lemma CF (m:Nat) (hm:m≠0):23≤(rm m).log2∧(rm m).log2≤24:=by obtain ⟨b,c⟩:=CE m hm have a:rm m≠0:=by omega constructor ·exact (Nat.le_log2 a).2 b ·have:rm m<2^25:=by omega have:=(Nat.log2_lt a).2 this omega lemma CG (m:Nat) (hm:m≠0):2^23≤fm m∧fm m<2^24:=by obtain ⟨l1,l2⟩:=CF m hm have a:rm m≠0:=by have:=(CE m hm).1;omega have b:=Xw a have c:=Xv (n:=rm m) unfold fm rw [B7] simp only [ExtendedMantissa.ofMantissaAndAccuracy,F7] have e2:(((rm m).log2:Int) - 23).toNat=(rm m).log2 - 23:=by omega rw [e2] constructor ·rw [Yg (by positivity),←pow_add] calc 2^(23+((rm m).log2 - 23))=2^(rm m).log2:=by congr 1;omega _≤rm m:=b ·rw [Xx (by positivity),←pow_add] calc rm m<2^((rm m).log2+1):=c _=2^(24+((rm m).log2 - 23)):=by congr 1;omega end Bridge namespace Bridge lemma S1 (m:Nat) (e:Int) (hm:m≠0) (d: -149≤(m.log2:Int)+e - 23): shiftToTargetExponent Format.binary32 (m1 m) (e - (F4 m:Int)) .exact= (F6 m,e+m.log2 - 23):=by have b:(m1 m).log2=m.log2+F4 m:=B8 m _ hm unfold shiftToTargetExponent shiftToExponent have a:totalExponent (m1 m) (e - (F4 m:Int))=(m.log2:Int)+1+e:=by simp only [totalExponent,b];push_cast;ring rw [a,B9 _ (by omega)] have c:((m.log2:Int)+1+e - 24 - (e - (F4 m:Int))).toNat=F5 m:=by simp only [F4,F5];omega dsimp only rw [c] simp only [F6,Prod.mk.injEq,true_and] simp only [F4,F5];omega lemma S2 (m:Nat) (e:Int) (hm:m≠0) (c: -149≤(m.log2:Int)+e - 23): shiftToTargetExponent Format.binary32 (rm m) (e+m.log2 - 23) .exact= (ExtendedMantissa.ofMantissaAndAccuracy (rm m) .exact>>>F7 m,e+m.log2 - 23+F7 m):=by obtain ⟨l1,l2⟩:=CF m hm unfold shiftToTargetExponent shiftToExponent have a:totalExponent (rm m) (e+m.log2 - 23)=((rm m).log2:Int)+1+(e+m.log2 - 23):=by simp only [totalExponent] rw [a,B9 _ (by omega)] have b:(((rm m).log2:Int)+1+(e+m.log2 - 23) - 24 - (e+m.log2 - 23)).toNat=F7 m:=by simp only [F7];omega dsimp only rw [b] lemma CH (s:Sign) (m:Nat) (e:Int) (hm:m≠0) (d: -149≤(m.log2:Int)+e - 23): UnpackedFloat.round Format.binary32 s m e= .finite s (fm m) (e+m.log2 - 23+F7 m) (by have:=(CG m hm).1;omega):=by have f:Format.binary32.targetExponent (totalExponent m e)=(m.log2:Int)+e - 23:=by rw [B9 _ (by simp only [totalExponent];omega)];simp only [totalExponent];ring unfold UnpackedFloat.round decreaseExponent simp only [f] have a:(e - ((m.log2:Int)+e - 23)).toNat=F4 m:=by simp only [F4];omega rw [a] have b:m<<>>F7 m).mantissa=fm m from rfl, c,dite_false] end Bridge lemma CI (neg:Bool) (m:Nat) (e:Int): Yr Fmt ⟨neg,m,e⟩= Model.ofModel Fmt (UnpackedFloat.round Format.binary32 (Model.modelSign neg) m e):=by simp [Yr,Model.ieeeRoundDyadic,show Fmt.isIEEE=true by decide] rfl lemma CJ (s:Sign):s.toBitVec.toNat=if s= .negative then 1 else 0:=by cases s<;>rfl lemma CK (s:Sign) (M:Nat) (E:Int) (h:0simp [Zp]<;>omega namespace Bridge end Bridge end end FP64 namespace FP64 open Float.Model Float.Model.UnpackedFloat open FloatLib.Floats.Formats.BinaryInterchange FloatLib.Floats lemma CL (em:ExtendedMantissa): em.shiftRightOne=⟨em.mantissa/2,em.mantissa % 2 !=0,em.roundBit || em.stickyBit⟩:=rfl lemma CM (m n:Nat): (Nat.repeat ExtendedMantissa.shiftRightOne (n+1) (ExtendedMantissa.ofMantissaAndAccuracy m .exact)).mantissa= m/2^(n+1)∧ (Nat.repeat ExtendedMantissa.shiftRightOne (n+1) (ExtendedMantissa.ofMantissaAndAccuracy m .exact)).roundBit= (m/2^n % 2 !=0)∧ (Nat.repeat ExtendedMantissa.shiftRightOne (n+1) (ExtendedMantissa.ofMantissaAndAccuracy m .exact)).stickyBit= (m % 2^n !=0):=by induction n with | zero=> show (ExtendedMantissa.shiftRightOne _).mantissa=_∧(ExtendedMantissa.shiftRightOne _).roundBit=_∧ (ExtendedMantissa.shiftRightOne _).stickyBit=_ simp [CL,ExtendedMantissa.ofMantissaAndAccuracy,Nat.repeat,Nat.mod_one] | succ n ih=> rw [show Nat.repeat ExtendedMantissa.shiftRightOne (n+1+1) (ExtendedMantissa.ofMantissaAndAccuracy m .exact)= (Nat.repeat ExtendedMantissa.shiftRightOne (n+1) (ExtendedMantissa.ofMantissaAndAccuracy m .exact)).shiftRightOne from rfl] generalize Nat.repeat ExtendedMantissa.shiftRightOne (n+1) (ExtendedMantissa.ofMantissaAndAccuracy m .exact)=em at ih⊢ obtain ⟨i1,i2,i3⟩:=ih rw [CL] refine ⟨?_, ?_, ?_⟩ ·show em.mantissa/2=_;rw [i1,Nat.div_div_eq_div_mul,←Yi] ·show (em.mantissa % 2 !=0)=_;rw [i1] ·show (em.roundBit || em.stickyBit)=_ rw [i2,i3] have e:m % 2^(n+1)=m/2^n % 2*2^n+m % 2^n:=by rw [Yi,Nat.mod_mul,Y5];omega rw [e] have d:0<2^n:=by positivity by_cases a:m/2^n % 2=0 ·simp [a] ·have f:m/2^n % 2*2^n≠0:=X0 a (by omega) have b:m/2^n % 2*2^n+m % 2^n≠0:=by omega have c:m/2^n % 2=1:=by omega simp [c,b] namespace Bridge lemma CN (M N j:Nat) (e:2^23+1≤N) (n:N<2^24) (t:N*(2*2^j)rw [←a] rw [show 2*P*(M/(2*P))+M % (2*P)=M % (2*P)+(2*(M/(2*P)))*P by ring, Nat.add_mul_div_right _ _ g] have l:M % P=(M % (2*P)) % P:=by conv_lhs=>rw [←a] rw [show 2*P*(M/(2*P))+M % (2*P)=M % (2*P)+(2*(M/(2*P)))*P by ring, Nat.add_mul_mod_self_right] rcases Z6 M X with q | r · have q1:M/(2*P)=N - 1:=by apply Wm ·have:(N - 1)*(2*P)=X - 2*P:=by rw [m,Nat.sub_mul,one_mul] omega ·have:(N - 1+1)*(2*P)=X:=by rw [Nat.sub_add_cancel (by omega)] omega have s:M % (2*P)=M - (X - 2*P):=by have:(N - 1)*(2*P)=X - 2*P:=by rw [m,Nat.sub_mul,one_mul] rw [q1] at a;rw [Y5] at a;omega have r1:M % (2*P)/P=1:=by apply Wm<;>omega have r2:M % (2*P) % P≠0:=by rw [Nat.mod_eq_sub_mod (by omega)] rw [Zy (by omega)];omega rw [d,l,r1,q1] have e1:((1+2*(N - 1)) % 2 !=0)=true:=by have:(1+2*(N - 1)) % 2=1:=by omega simp [this] have e2:(M % (2*P) % P !=0)=true:=by simpa using r2 rw [e1,e2] simp [ExtendedMantissa.roundedMantissa,ExtendedMantissa.accuracy,Accuracy.roundToNearestEven] omega · have q1:M/(2*P)=N:=by apply Wm ·omega ·rw [Nat.add_mul,one_mul];omega have s:M % (2*P)=M - X:=by rw [q1] at a;rw [Y5] at a;omega have r1:M % (2*P)/P=0:=X2 (by omega) rw [d,r1,q1] have e1:((0+2*N) % 2 !=0)=false:=by have:(0+2*N) % 2=0:=by omega simp [this] rw [e1] cases (M % P !=0)<;>simp [ExtendedMantissa.roundedMantissa,ExtendedMantissa.accuracy,Accuracy.roundToNearestEven] lemma CO (M N j:Nat) (c:2^23+1≤N) (a:N<2^24) (g:N*(2*2^j)simp [Model.modelSign] end FP64 namespace FP64 open FloatLib.Floats.Formats.BinaryInterchange FloatLib.Floats ExactRuntime lemma CQ (T:Float) (b:1≤((T.toBits>>>52)&&&0x7ff).toNat) (c:((T.toBits>>>52)&&&0x7ff).toNat≤2046): T.isFinite=true∧vr T=(if T.toBits.toNat/2^63=0 then (1:ℝ) else -1)* (((T.toBits&&&0xfffffffffffff).toNat+2^52:ℕ):ℝ)*(2:ℝ)^((((T.toBits>>>52)&&&0x7ff).toNat:ℤ) - 1075):=by have a:=Ab T.toBits (by omega) rw [dif_neg (by omega)] at a rw [←By] at a refine ⟨by rw [Ap,a];rfl, ?_⟩ rw [AS,a,Z2,B1] obtain ⟨-, -,fs⟩:=Ae T.toBits rw [fs] split<;>simp [Z9]<;>push_cast<;>ring_nf lemma CR (u:UInt64): (u&&&0xfffffffffffff).toNat=((u>>>29)&&&0x7FFFFF).toNat*2^29+(u&&&0x1FFFFFFF).toNat:=by rw [Zh,Zh,Zh,Z7, show (0xfffffffffffff:UInt64).toNat=2^52 - 1 from rfl,show (0x7FFFFF:UInt64).toNat=2^23 - 1 from rfl, show (0x1FFFFFFF:UInt64).toNat=2^29 - 1 from rfl,Zt,Zt, Zt] simp only [show (29:UInt64).toNat % 64=29 from rfl,Zu] omega lemma CS (i:Nat) (a:i<256) (h:ib (Or.inl h) omega have q:a≠0:=fun h=>b (Or.inr (Or.inr ⟨rfl,h⟩)) have j:p3<2^28*P:=by rw [c];exact Yo e k have em:((2^28 - qN)*P:ℕ)=2^28*P - p3:=by rw [Nat.sub_mul,c] simp only [Zx,ite_false] at d⊢ rw [em] at d have eN:(2^23+a+0)*(2*(2^28*P))=2^52*P+2^29*p2:=by rw [i];ring rw [eN] rcases abs_lt.mp d with ⟨l,r⟩ cases neg ·simp only [Zx,ite_false,one_mul] at l r push_cast at l r have f:0≤S:=by omega refine ⟨by omega,by omega,by omega,by omega,by simp;omega⟩ ·simp only [ite_true,neg_one_mul] at l r push_cast at l r have f:S<0:=by omega refine ⟨by omega,by omega,by omega,by omega,by simp;omega⟩ · have e:2^28b (Or.inr (Or.inl ⟨rfl,h⟩)) have n:2^28*P>>52&&&2047).toNat=b.toNat/2^52 % 2048∧(b&&&536870911).toNat=b.toNat % 2^29∧ (b>>>29&&&8388607).toNat=b.toNat/2^29 % 2^23∧(b>>>63).toNat=b.toNat/2^63:=by refine ⟨?_, ?_, ?_, ?_⟩ ·rw [Zh,Z7,show (2047:UInt64).toNat=2^11 - 1 from rfl, Zt];simp [Zu] ·rw [Zh,show (536870911:UInt64).toNat=2^29 - 1 from rfl,Zt] ·rw [Zh,Z7,show (8388607:UInt64).toNat=2^23 - 1 from rfl, Zt];simp [Zu] ·rw [Z7];simp [Zu] lemma CW (x y k:Nat) (a:x<2^k) (b:y % 2^k=0):x ||| y=x+y:=by have:y=(y/2^k)<<rfl rw [a0,Nat.lor_assoc,Ya ((e.toNat - 896)*2^23),a1] rw [Ya,CW _ _ 31 (by omega) (by cases neg<;>simp)] ring lemma CY (ET:Nat) (h:777≤ET): (2:ℝ)^((ET:ℤ) - 1075)=((2^(ET - 777):ℕ):ℝ)*2^(-298:ℤ):=by rw [show ((ET:ℤ) - 1075)=((ET - 777:ℕ):ℤ)+(-298) by omega,zpow_add₀ (by norm_num),zpow_natCast, Nat.cast_pow,Nat.cast_ofNat] lemma CZ (V:Nat) (h:V<2^32):(V&&&2^31≠0)↔2^31≤V:=by rw [Nat.and_two_pow,Nat.testBit_eq_decide_div_mod_eq] by_cases a:V/2^31 % 2=1 ·rw [decide_eq_true a];simp only [Bool.toNat_true];omega ·rw [decide_eq_false a];simp only [Bool.toNat_false];omega lemma Ca (V:Nat) (h:V<2^32): ((Zi V)&&&0x80000000 !=0)=decide (2^31≤V):=by have a:(Zi V).toNat=V:=by rw [Yv,Zy h] apply Bool.eq_iff_iff.mpr rw [bne_iff_ne,decide_eq_true_iff,ne_eq,←UInt32.toNat_inj,Zl,a, show (0x80000000:UInt32).toNat=2^31 from rfl,show (0:UInt32).toNat=0 from rfl] exact CZ V h lemma Cb (V:Nat) (h:V<2^32):(expOf (Zi V)).toNat=V/2^23 % 256:=by have a:(Zi V).toNat=V:=by rw [Yv,Zy h] unfold expOf rw [Zl,Yb,a,show (0xFF:UInt32).toNat=2^8 - 1 from rfl, Zt,show (23:UInt32).toNat % 32=23 from rfl,Zu] lemma Cc (relu:Bool) (T E:Float) (S:ℤ) (nz:Bool) (bT:UInt64) (l:T.toBits=bT) (Q:T.isFinite=true→E.isFinite=true→ |(S:ℝ)*2^(-298:ℤ) - vr T| ≤vr E) (w:897≤((bT>>>52)&&&2047).toNat) (x:((bT>>>52)&&&2047).toNat≤1150) (up:Bool) (y:up=decide (268435456<(bT&&&536870911))) (n: ¬((bT&&&536870911)=268435456∨(up=true∧(bT>>>29&&&8388607)=8388607)∨ (up=false∧(bT>>>29&&&8388607)=0))) (K:((bT>>>52&&&2047) - 896).toUSize.toNat>>52&&&2047) - 896).toUSize K): S≠0∧act relu (finishWord S (-298) nz)=Zi (if relu&&(bT>>>63==1) then 0 else (if bT>>>63==1 then 2^31 else 0)+(((bT>>>52)&&&2047).toNat - 896)*2^23+ ((bT>>>29&&&8388607).toNat+if up then 1 else 0)):=by obtain ⟨f1,f2,f3,f4⟩:=CV bT have R:(bT&&&536870911).toNat<2^29:=by rw [f2];omega have o:(bT>>>29&&&8388607).toNat<2^23:=by rw [f3];omega have f:up=decide (2^28<(bT&&&536870911).toNat):=by rw [y];congr 1 have g: ¬((bT&&&536870911).toNat=2^28∨(up=true∧(bT>>>29&&&8388607).toNat=2^23 - 1)∨ (up=false∧(bT>>>29&&&8388607).toNat=0)):=by intro m;apply n rcases m with m | ⟨A,m⟩ | ⟨A,m⟩ ·left;exact UInt64.toNat_inj.mp (by rw [m];rfl) ·right;left;exact ⟨A,UInt64.toNat_inj.mp (by rw [m];rfl)⟩ ·right;right;exact ⟨A,UInt64.toNat_inj.mp (by rw [m];rfl)⟩ have p:(if up then (bT&&&536870911) - 268435456 else 268435456 - (bT&&&536870911):UInt64).toNat= if up then (bT&&&536870911).toNat - 2^28 else 2^28 - (bT&&&536870911).toNat:=by have c28:(268435456:UInt64).toNat=2^28:=rfl cases up ·simp only [Zx,ite_false] have:(bT&&&536870911).toNat≤2^28:=by have:=of_decide_eq_false f.symm;omega rw [Yz _ _ (UInt64.le_iff_toNat_le.mpr (by rw [c28];exact this)),c28] ·simp only [ite_true] have:2^28<(bT&&&536870911).toNat:=of_decide_eq_true f.symm rw [Yz _ _ (UInt64.le_iff_toNat_le.mpr (by rw [c28];omega)),c28] obtain ⟨thf,thv⟩:=CT _ _ (by rw [p];split<;>omega) w x K obtain ⟨Ef,Elt⟩:=B3 E _ z thf rw [thv,p] at Elt obtain ⟨Tf,Tv⟩:=CQ T (by rw [l];show 1≤((bT>>>52)&&&2047).toNat;omega) (by rw [l];show ((bT>>>52)&&&2047).toNat≤2046;omega) have U:=Q Tf Ef rw [l] at Tv have q:777≤((bT>>>52)&&&2047).toNat:=by omega have d:=CY _ q have B:=CR bT set P:=2^(((bT>>>52)&&&2047).toNat - 777) with W have C:0>>29&&&8388607).toNat with L set mN:=(if up then qN - 2^28 else 2^28 - qN) with M set neg:=(bT>>>63==1) with r have s:(if bT.toNat/2^63=0 then (1:ℝ) else -1)=((if neg then -1 else 1:ℤ):ℝ):=by have Y:bT.toNat/2^63<2:=by have:=bT.toNat_lt;omega have j:neg=true↔bT.toNat/2^63=1:=by rw [r,beq_iff_eq,←f4,←UInt64.toNat_inj];rfl by_cases u:bT.toNat/2^63=0 ·have:neg=false:=by cases e:neg;rfl;exact absurd (j.mp e) (by omega) rw [Qw u,this];simp ·have:neg=true:=j.mpr (by omega) rw [Qx u,this];simp rw [s,B] at Tv have b: |(S:ℝ)*2^(-298:ℤ) - vr T| <(mN:ℝ)*2^((((bT>>>52)&&&2047).toNat:ℤ) - 1075):=by exact lt_of_le_of_lt (U.trans (le_abs_self _)) Elt rw [Tv,d] at b have c2:((2:ℕ):ℝ)=2:=by norm_num simp only [c2] at b rw [d] at b have k:(0:ℝ)<2^(-298:ℤ):=by positivity have hint: |S - (if neg then -1 else 1)*(((2^52+a*2^29+qN)*P:ℕ):ℤ)| <((mN*P:ℕ):ℤ):=by have e1:(S:ℝ)*2^(-298:ℤ) - ((if neg then -1 else 1:ℤ):ℝ)*((a*2^29+qN+2^52:ℕ):ℝ)* ((P:ℝ)*2^(-298:ℤ))= ((S - (if neg then -1 else 1)*(((2^52+a*2^29+qN)*P:ℕ):ℤ):ℤ):ℝ)*2^(-298:ℤ):=by push_cast;ring have e2:(mN:ℝ)*(((P:ℕ):ℝ)*2^(-298:ℤ))=(((mN*P:ℕ):ℤ):ℝ)*2^(-298:ℤ):=by push_cast;ring rw [e1,e2,abs_mul,abs_of_pos k] at b have:=lt_of_mul_lt_mul_right b k.le exact_mod_cast this obtain ⟨n1,n2,n3,n4,n5⟩:=CU S P qN a neg up R o f g C hint set N:=2^23+a+(if up then 1 else 0) with Z set ET:=((bT>>>52)&&&2047).toNat with aa have D:a+(if up then 1 else 0)<2^23:=by cases up ·simpa using o ·have:a≠2^23 - 1:=fun h=>g (Or.inr (Or.inl ⟨rfl,h⟩)) simp only [ite_true];omega have O:2^(ET - 749)=2^28*P:=by rw [W,←Nat.pow_add,show 28+(ET - 777)=ET - 749 by omega] have hw:=CP (decide (S<0)) S.natAbs N (ET - 749) (-298) n1 n2 (by rw [O];exact n3) (by rw [O];exact n4) (by omega) (by omega) have t:S≠0:=by intro u;rw [u,Int.natAbs_zero,Z4] at n3 have:2^28*P≤N*(2*(2^28*P)):=by have F:2*(2^28*P)≤N*(2*(2^28*P)):=Xu _ (by omega) omega omega refine ⟨t, ?_⟩ have G:finishWord S (-298) nz=Wl (Yr ExactRuntime.Fmt ⟨decide (S<0),S.natAbs, -298⟩):=by simp only [finishWord,t,ite_false];rfl rw [G,hw,n5] have e1:((-298:ℤ)+((ET - 749:ℕ)+1)+150).toNat=ET - 896:=by omega have e2:N % 2^23=a+(if up then 1 else 0):=by rw [Z,show 2^23+a+(if up then 1 else 0)=(a+(if up then 1 else 0))+2^23*1 by ring, Wk,Zy D] rw [e1,e2] set V:=(if neg then 2^31 else 0)+(ET - 896)*2^23+(a+if up then 1 else 0) with H have i:V<2^32:=by have:(if neg then 2^31 else 0)≤2^31:=by split<;>omega rw [H];omega have ad:(Zi V).toNat=V:=by rw [Yv,Zy i] have c:(neg=true∧V=2^31+(ET - 896)*2^23+(a+if up then 1 else 0))∨ (neg=false∧V=(ET - 896)*2^23+(a+if up then 1 else 0)):=by rcases Bool.eq_false_or_eq_true neg with e | e ·left;refine ⟨e, ?_⟩;rw [H,e];simp ·right;refine ⟨e, ?_⟩;rw [H,e];simp have I:((Zi V)&&&0x80000000 !=0)=neg:=by rw [Ca V i] rcases c with ⟨e,v⟩ | ⟨e,v⟩ ·rw [e];exact decide_eq_true (by omega) ·rw [e];exact decide_eq_false (by omega) have J:expOf (Zi V)≠255:=by intro h have F:=congrArg Xj h rw [Cb V i,show (255:UInt32).toNat=255 from rfl] at F rcases c with ⟨e,v⟩ | ⟨e,v⟩<;>rw [v] at F<;>omega simp only [act,reluW] cases relu ·simp ·rw [I] cases neg ·simp ·simp [J] lemma Cd (w:UInt64) (h:w.toNat<2^32):w.toUInt32=Zi w.toNat:=by apply UInt32.toNat_inj.mp rw [UInt64.toNat_toUInt32,Yv,Zy h] lemma Ce (relu:Bool) (T E:Float) (S:ℤ) (nz:Bool) (p:T.isFinite=true→E.isFinite=true→ |(S:ℝ)*2^(-298:ℤ) - vr T| ≤vr E) (q:Fe relu T E<0x100000000): S≠0∧(Fe relu T E).toUInt32=act relu (finishWord S (-298) nz):=by have key: ∀(v:UInt64),Fe relu T E=v→v<0x100000000→ S≠0∧v.toUInt32=act relu (finishWord S (-298) nz):=by intro v c a unfold Fe at c simp only [] at c split at c next o=> split at c next j=>subst c;exact absurd a (by decide) next j=> have d:897≤((T.toBits>>>52)&&&2047).toNat:=UInt64.le_iff_toNat_le.mp o.1 have e:((T.toBits>>>52)&&&2047).toNat≤1150:=UInt64.le_iff_toNat_le.mp o.2 rcases f:decide (268435456 have l:=Cc relu T E S nz T.toBits rfl p d e false f.symm j _ k refine ⟨l.1, ?_⟩;rw [l.2];subst c have g:=(CV T.toBits).2.2.1 have m:(T.toBits>>>29&&&8388607).toNat<2^23:=by rw [g];omega have b:((T.toBits>>>29&&&8388607)+0).toNat=(T.toBits>>>29&&&8388607).toNat:=by simp by_cases n:(relu&&(T.toBits>>>63==1))=true ·simp only [n,ite_true];rfl ·simp only [n,Zx,ite_false] at a⊢ have i:=CX (T.toBits>>>63==1) (T.toBits>>>52&&&2047) ((T.toBits>>>29&&&8388607)+0) d e (by rw [b];omega) rw [Cd _ (by rw [i];have:=UInt64.lt_iff_toNat_lt.mp a;rw [i] at this;simpa using this),i,b] simp next k=>subst c;exact absurd a (by decide) ·rw [f] at c j simp only [ite_true] at c split at c next k=> have l:=Cc relu T E S nz T.toBits rfl p d e true f.symm j _ k refine ⟨l.1, ?_⟩;rw [l.2];subst c have g:=(CV T.toBits).2.2.1 have m:(T.toBits>>>29&&&8388607).toNat<2^23:=by rw [g];omega have r:(T.toBits>>>29&&&8388607).toNat≠2^23 - 1:=by intro h;apply j;right;left;exact ⟨rfl,UInt64.toNat_inj.mp (by rw [h];rfl)⟩ have b:((T.toBits>>>29&&&8388607)+1).toNat=(T.toBits>>>29&&&8388607).toNat+1:=by rw [X8,show (1:UInt64).toNat=1 from rfl,Zy (by omega)] by_cases n:(relu&&(T.toBits>>>63==1))=true ·simp only [n,ite_true];rfl ·simp only [n,Zx,ite_false] at a⊢ have i:=CX (T.toBits>>>63==1) (T.toBits>>>52&&&2047) ((T.toBits>>>29&&&8388607)+1) d e (by rw [b];omega) rw [Cd _ (by rw [i];have:=UInt64.lt_iff_toNat_lt.mp a;rw [i] at this;simpa using this),i,b] simp next k=>subst c;exact absurd a (by decide) next o=>subst c;exact absurd a (by decide) exact key _ rfl q lemma Cf (w:UInt32): |FH w| =(mantOf w:ℝ)*(2:ℝ)^((idxOf w:ℤ) - 149):=by unfold FH sv split<;>simp [abs_mul,abs_of_pos (show (0:ℝ)<2^((idxOf w:ℤ) - 149) by positivity)] lemma Cg (w:UInt32):Fw w=(expOf w).toNat:=by rw [Al];rfl lemma Ch (w:UInt32):(fracOf w).toNat<2^23:=by rw [Am];omega lemma Ci (w:UInt32): |FH w| <(2:ℝ)^((Fw w:ℤ) - 126):=by rw [Cf,Cg] have b:=Ch w unfold mantOf idxOf by_cases a:expOf w=0 ·simp only [a,ite_true] have:((Xj 0:ℕ):ℤ)=0:=rfl rw [this] have a1:((fracOf w).toNat:ℝ)<2^23:=by exact_mod_cast b calc ((fracOf w).toNat:ℝ)*(2:ℝ)^(((0:ℕ):ℤ) - 149)<2^23*(2:ℝ)^(((0:ℕ):ℤ) - 149):= mul_lt_mul_of_pos_right a1 (by positivity) _=(2:ℝ)^((0:ℤ) - 126):=by rw [show (2:ℝ)^23=2^(23:ℤ) by norm_num,As];norm_num ·simp only [a,ite_false] have c:(expOf w).toNat≠0:=fun h=>a (UInt32.toNat_inj.mp (by rw [h];rfl)) have a1:((2^23+(fracOf w).toNat:ℕ):ℝ)<2^24:=by exact_mod_cast (by omega:2^23+(fracOf w).toNat<2^24) calc ((2^23+(fracOf w).toNat:ℕ):ℝ)*(2:ℝ)^((((expOf w).toNat - 1:ℕ):ℤ) - 149) <2^24*(2:ℝ)^((((expOf w).toNat - 1:ℕ):ℤ) - 149):=mul_lt_mul_of_pos_right a1 (by positivity) _=(2:ℝ)^(((expOf w).toNat:ℤ) - 126):=by rw [show (2:ℝ)^24=2^(24:ℤ) by norm_num,As];congr 1;omega lemma Cj (w:UInt32) (b:(expOf w).toNat≠255): (FG w).isFinite=true∧ |vr (FG w)| ≤ |FH w| ∧ |FH w - vr (FG w)| ≤(2:ℝ)^(-126:ℤ):=by by_cases a:(expOf w).toNat=0 ·obtain ⟨f,v⟩:=Ay w a refine ⟨f,by rw [v];simp, ?_⟩ rw [v,sub_zero] have:=Ci w rw [Cg,a] at this exact this.le ·obtain ⟨f,v⟩:=Ax w a b exact ⟨f,by rw [v],by rw [v];simp⟩ lemma Ck (o:UInt32): (FV o).isFinite=true∧vr (FV o)=(2:ℝ)^((Fw o:ℤ) - 126):=by have he:((o>>>23)&&&0xFF).toNat=Fw o:=by unfold Fw;rw [Zl,Yb,show (0xFF:UInt32).toNat=2^8 - 1 from rfl, Zt,show (23:UInt32).toNat % 32=23 from rfl,Zu] have b:Fw o<256:=by unfold Fw;omega have a:FV o=Zz (FN (Fw o)):=by unfold FV rw [BM,Yf,he,getElem!_pos _ _ (by simpa [FO] using b)] simp [FO] rw [a] have:=At (FN (Fw o)) false (Fw o+897) (by omega) (by omega) (by simp only [FN];rw [Z1,Zy (by omega)];simp;omega) obtain ⟨f,v⟩:=this refine ⟨f, ?_⟩ rw [v];simp only [Zx,ite_false,one_mul] rw [show ((Fw o+897:ℕ):ℤ) - 1023=(Fw o:ℤ) - 126 by push_cast;ring] lemma Cl (x w:UInt32) (g:(expOf x).toNat≠255) (e:(expOf w).toNat≠255) (h:(FL x*FG w).isFinite=true):vr (FL x*FG w)=FH x*vr (FG w):=by obtain ⟨xf,xv⟩:=A8 x g obtain ⟨wf, -, -⟩:=Cj w e have a:vr (FL x)=(sv x:ℝ)*2^((idxOf x:ℤ) - 149):=by rw [xv];rfl by_cases f:(expOf w).toNat=0 ·have:=(Ay w f).2 rw [AU _ _ xf wf h 0 0 (by simp) (by norm_num) (by rw [this];simp),xv,this] ·have wv:=(Ax w f e).2 have b:vr (FG w)=(sv w:ℝ)*2^((idxOf w:ℤ) - 149):=by rw [wv];rfl have c:=Qv x have d:=Qv w rw [AU _ _ xf wf h (sv x*sv w) ((idxOf x:ℤ)+idxOf w - 298) ?_ (by omega) ?_,xv] ·rw [Int.natAbs_mul] have a1:(sv x).natAbs=mantOf x:=by unfold sv;split<;>simp have a2:(sv w).natAbs=mantOf w:=by unfold sv;split<;>simp rw [a1,a2] calc mantOf x*mantOf w<2^24*2^24:=Nat.mul_lt_mul'' c d _≤2^53:=by norm_num ·rw [a,b];push_cast rw [show ((idxOf x:ℤ)+idxOf w - 298)=((idxOf x:ℤ) - 149)+((idxOf w:ℤ) - 149) by ring, ←As];ring lemma Cm:Model.roundAt FloatFormat.binary64 0=0:=by have:=AT 0 0 (by simp) (by norm_num) rw [Int.cast_zero,zero_mul] at this;exact this lemma Cn (x y:Float) (a:x.isFinite=true) (b:y.isFinite=true) (h:(x+y).isFinite=true) (c:0≤vr x) (d:0≤vr y):0≤vr (x+y):=by rw [AI x y a b h,←Cm];exact Xi _ (by linarith) lemma Co (x y:Float) (a:x.isFinite=true) (b:y.isFinite=true) (h:(x*y).isFinite=true) (c:0≤vr x) (d:0≤vr y):0≤vr (x*y):=by rw [AJ x y a b h,←Cm];exact Xi _ (mul_nonneg c d) lemma Cp (r z u η:ℝ) (a:0≤u) (d:u≤1/2) (e:0≤η) (b:0≤r) (c:0≤z) (he: |r - z| ≤u* |r| +η):z*(1 - u) - η≤r:=by rw [abs_of_nonneg b] at he have f:=(abs_le.mp he).1 nlinarith [mul_nonneg a c,mul_nonneg a b,mul_nonneg a e,mul_nonneg (mul_nonneg a a) c] lemma Cq (x y:Float) (a:x.isFinite=true) (b:y.isFinite=true) (h:(x+y).isFinite=true) (c:0≤vr x) (d:0≤vr y): (vr x+vr y)*(1 - 2^(-52:ℤ)) - 2^(-1074:ℤ)≤vr (x+y):=by have he:=AR x y a b h exact Cp (vr (x+y)) (vr x+vr y) (2^(-52:ℤ)) (2^(-1074:ℤ)) (by positivity) (by norm_num) (by positivity) (Cn x y a b h c d) (by linarith) he lemma Cr (x y:Float) (a:x.isFinite=true) (b:y.isFinite=true) (h:(x*y).isFinite=true) (c:0≤vr x) (d:0≤vr y): vr x*vr y*(1 - 2^(-52:ℤ)) - 2^(-1074:ℤ)≤vr (x*y):=by have he:=Bs x y a b h exact Cp (vr (x*y)) (vr x*vr y) (2^(-52:ℤ)) (2^(-1074:ℤ)) (by positivity) (by norm_num) (by positivity) (Co x y a b h c d) (mul_nonneg c d) he lemma Cs:(0:Float).isFinite=true∧vr 0=0:=by have h:=Br 0 (by decide) have e:(0:Float)=Y7 0:=rfl rw [e];simpa using h lemma Ct (l:List Float) (h:(l.foldl (· + ·) 0).isFinite=true) (j:l.length≤2^20) (a: ∀x∈l,0≤vr x): 0≤vr (l.foldl (· + ·) 0)∧ (l.map vr).sum*(1 - l.length*2^(-52:ℤ)*(1+2^(-30:ℤ))) - l.length*(1+2^(-30:ℤ))*2^(-1074:ℤ) ≤vr (l.foldl (· + ·) 0):=by obtain ⟨o,p,he⟩:=BA l 0 h have g:=B5 l 0 h j rw [Cs.2,zero_add] at he simp only [Cs.2,abs_zero,zero_add] at g have b:(l.map (fun x=> |vr x|)).sum=(l.map vr).sum:=by congr 1;apply Zn;intro x k;exact abs_of_nonneg (a x k) rw [b] at g have d:0≤vr (l.foldl (· + ·) 0):=by suffices∀(l:List Float) (s:Float),(l.foldl (· + ·) s).isFinite=true→0≤vr s→ (∀x∈l,0≤vr x)→0≤vr (l.foldl (· + ·) s) from this l 0 h (by rw [Cs.2]) a intro l induction l with | nil=>intro s _ e _;simpa using e | cons x l ih=> intro s f e i simp only [Zk] at f⊢ obtain ⟨c, -, -⟩:=BA l (s+x) f obtain ⟨sf,xf⟩:=AN s x c exact ih (s+x) f (Cn s x sf xf c e (i x (Xh ..))) (fun y m=>i y (Xg _ m)) refine ⟨d, ?_⟩ have:=(abs_le.mp he).1 have n:0≤(l.map vr).sum:=Yp (by simpa using a) nlinarith end FP64 namespace FP64 lemma Cu:(2:ℝ)^(200:ℕ)*2^(-1074:ℤ)≤2^(-300:ℤ)*(1/4):=by have e1:(2:ℝ)^(200:ℕ)*2^(-1074:ℤ)=2^(-874:ℤ):=by rw [←zpow_natCast,As];norm_num have e2:(2:ℝ)^(-300:ℤ)*(1/4)=2^(-302:ℤ):=by rw [show (1/4:ℝ)=2^(-2:ℤ) by norm_num,As];norm_num rw [e1,e2];exact zpow_le_zpow_right₀ (by norm_num) (by norm_num) lemma Cv (n a ob b' :ℝ) (b:0≤n) (m:n≤2^20) (l:0≤a) (g:0≤ob) (d:ob≤2^129) (o:0≤b'): let u:ℝ:=2^(-52:ℤ) let η:ℝ:=2^(-1074:ℤ) let δ:ℝ:=2^(-30:ℤ) let c1:=1 - u let s:=a*(1 - n*u*(1+δ)) - n*(1+δ)*η let Kv:=(n+9)*u 2^(-126:ℤ)*a+(n+1)*u*(1+δ)*(ob*a+b')+(n+1)*(1+δ)*η≤ ((Kv*(((s*ob*c1 - η)+b')*c1 - η)*c1 - η)+((s*2^(-125:ℤ)*c1 - η+2^(-300:ℤ))*c1 - η))*c1 - η:=by intro u η δ c1 s Kv have p:u=1/2^52:=by simp [u] have q:δ=1/2^30:=by simp [δ] have e:(2:ℝ)^(-125:ℤ)=1/2^125:=by simp have f:(2:ℝ)^(-126:ℤ)=1/2^126:=by simp have h:0≤η:=by positivity have x:=Cu set τ:ℝ:=2^(-300:ℤ) with r simp only [s,Kv,c1] rw [p,q,e,f] have t:0≤(n+9)*(1/2^52)*(1 - 1/2^52)^4*(1 - n*(1/2^52)*(1+1/2^30)) - (n+1)*(1/2^52)*(1+1/2^30):=by nlinarith [mul_nonneg b (sub_nonneg.mpr m)] have v:0≤(n+9)*(1/2^52)*(1 - 1/2^52)^3 - (n+1)*(1/2^52)*(1+1/2^30):=by nlinarith have w:0≤(1/2^125)*(1 - 1/2^52)^3*(1 - n*(1/2^52)*(1+1/2^30)) - 1/2^126:=by nlinarith have c:(n+9)*(1/2^52)*(1 - 1/2^52)^4*(n*(1+1/2^30))*2^129+ (1/2^125)*(1 - 1/2^52)^3*(n*(1+1/2^30))+ ((n+9)*(1/2^52)*((1 - 1/2^52)^3+(1 - 1/2^52)^2)+2*(1 - 1/2^52)+ (1 - 1/2^52)^2+1)+(n+1)*(1+1/2^30)≤2^200:=by nlinarith [mul_nonneg b b] have i:(1/2:ℝ)≤(1 - 1/2^52)^2:=by norm_num have j:0≤(n+9)*(1/2^52)*(1 - 1/2^52)^4*(n*(1+1/2^30)*η):=by positivity have k:0≤τ:=by positivity nlinarith [mul_nonneg t (mul_nonneg l g),mul_nonneg v o,mul_nonneg w l, mul_le_mul_of_nonneg_left d j,mul_le_mul_of_nonneg_right c h,mul_le_mul_of_nonneg_left i k] end FP64 namespace FP64 open FloatLib.Floats.Formats.BinaryInterchange FloatLib.Floats ExactRuntime lemma Cw (n:Nat) (ps:List Nat) (a: ∀t∈ps,tf t - g t)).sum=(l.map f).sum - (l.map g).sum:=by induction l with | nil=>simp | cons x l ih=>simp only [Zr,Zq,ih];ring lemma C2 (l:List Nat) (f:Nat→ℝ): |(l.map f).sum| ≤(l.map (fun t=> |f t|)).sum:=by induction l with | nil=>simp | cons x l ih=> simp only [Zr,Zq] linarith [abs_add_le (f x) (List.map f l).sum,ih] lemma C3 (sx' ob' A1 A2 A3 C1 C E b' Kv s c1 η p125 p300:ℝ) (b:s≤ sx') (c:0≤ob') (a:0≤c1) (d:0≤Kv) (e:0≤p125) (l1:sx' *ob' *c1 - η≤A1) (l2:(A1+b')*c1 - η≤A2) (l3:Kv*A2*c1 - η≤A3) (l4:sx' *p125*c1 - η≤C1) (l5:(C1+p300)*c1 - η≤C) (l6:(A3+C)*c1 - η≤E): ((Kv*(((s*ob' *c1 - η)+b')*c1 - η)*c1 - η)+((s*p125*c1 - η+p300)*c1 - η))*c1 - η≤E:=by have m1:s*ob' *c1 - η≤A1:=by have:=mul_le_mul_of_nonneg_right b (mul_nonneg c a);linarith [mul_assoc s ob' c1,mul_assoc sx' ob' c1] have m2:((s*ob' *c1 - η)+b')*c1 - η≤A2:=by have:=mul_le_mul_of_nonneg_right (add_le_add_right m1 b') a;linarith have m3:Kv*(((s*ob' *c1 - η)+b')*c1 - η)*c1 - η≤A3:=by have:=mul_le_mul_of_nonneg_right (mul_le_mul_of_nonneg_left m2 d) a;linarith have m4:s*p125*c1 - η≤C1:=by have:=mul_le_mul_of_nonneg_right b (mul_nonneg e a);linarith [mul_assoc s p125 c1,mul_assoc sx' p125 c1] have m5:(s*p125*c1 - η+p300)*c1 - η≤C:=by have:=mul_le_mul_of_nonneg_right (add_le_add_right m4 p300) a;linarith have:=mul_le_mul_of_nonneg_right (add_le_add m3 m5) a;linarith lemma C4 (n :Nat) (hn:n<2^20) (xw ww:Nat→UInt32) (bw:UInt32) (ps:List Nat) (f: ∀t∈ps,t(FL (xw t)).abs)).foldl (· + ·) 0) (hT:T=(ps.map (fun t=>FL (xw t)*FG (ww t))).foldl (· + ·) 0+FL bw) (hE:E=K*(sx*ob+(FL bw).abs)+(sx*FT+FU)) (B:T.isFinite=true) (u:E.isFinite=true): (∀t,tFH (xw t)*FH (ww t))).sum+FH bw - vr T| ≤vr E:=by rw [hE] at u obtain ⟨m,X⟩:=AN _ _ u obtain ⟨C,h⟩:=AO _ _ m obtain ⟨i,q⟩:=AN _ _ h obtain ⟨c,r⟩:=AO _ _ i obtain ⟨j,D⟩:=AN _ _ X obtain ⟨-,e⟩:=AO _ _ j have Z:=BA _ 0 (l▸c) have v: ∀t,tFL (xw t)*FG (ww t)))++[FL bw]).foldl (· + ·) 0:=by rw [hT,List.foldl_append];rfl obtain ⟨-,F,o⟩:=BA _ 0 (w▸B) rw [←w] at o have G:(FL bw).isFinite=true:=F _ (List.mem_append_right _ (List.mem_singleton_self _)) have H: ∀t∈ps,(FL (xw t)*FG (ww t)).isFinite=true:=fun t b=> F _ (List.mem_append_left _ (List.mem_map.mpr ⟨t,b,rfl⟩)) have p: ∀t∈ps,(expOf (ww t)).toNat≠255:=by intro t b he have:=(AO _ _ (H t b)).2 rw [Az _ he] at this;exact absurd this (by decide) have I:(expOf bw).toNat≠255:=by intro he;rw [A9 _ he] at G;exact absurd G (by decide) refine ⟨v,p,I, ?_⟩ have z:=(A8 bw I).2 have J: ∀t∈ps,vr (FL (xw t)*FG (ww t))=FH (xw t)*vr (FG (ww t)):=fun t b=> Cl _ _ (v t (f t b)) (p t b) (H t b) have L:((Qz n).map (fun t=>FH (xw t)*FH (ww t))).sum= (ps.map (fun t=>FH (xw t)*FH (ww t))).sum:= Cw n ps f k _ (fun t b M=>by rw [(Cz _ (hz t b M)).1,zero_mul]) set a:=((Qz n).map (fun t=> |FH (xw t)|)).sum with ha have N:0≤a:=Yp (by simp) have d:0≤vr ob:=by rw [g.2];positivity have O:vr ob≤2^129:=by rw [g.2,show (2:ℝ)^129=2^(129:ℤ) by norm_num] exact zpow_le_zpow_right₀ (by norm_num) (by omega) have aa : |(ps.map (fun t=>FH (xw t)*FH (ww t))).sum - (ps.map (fun t=>FH (xw t)*vr (FG (ww t)))).sum| ≤2^(-126:ℤ)*a:=by rw [←C0 ps (fun t=>FH (xw t)*FH (ww t)) (fun t=>FH (xw t)*vr (FG (ww t)))] calc |(ps.map (fun t=>FH (xw t)*FH (ww t) - FH (xw t)*vr (FG (ww t)))).sum| ≤ (ps.map (fun t=> |FH (xw t)*FH (ww t) - FH (xw t)*vr (FG (ww t))|)).sum:= C2 ps (fun t=>FH (xw t)*FH (ww t) - FH (xw t)*vr (FG (ww t))) _ ≤ (ps.map (fun t=>2^(-126:ℤ)* |FH (xw t)|)).sum:=by apply Wj;intro t b rw [←mul_sub,abs_mul,mul_comm] exact mul_le_mul_of_nonneg_right (Cj _ (p t b)).2.2 (abs_nonneg _) _=2^(-126:ℤ)*(ps.map (fun t=> |FH (xw t)|)).sum:=by rw [Xe] _ ≤ 2^(-126:ℤ)*a:= mul_le_mul_of_nonneg_left (Cx n ps f k _ (fun t=>abs_nonneg _)) (by positivity) have P:((ps.map (fun t=>FL (xw t)*FG (ww t)))++[FL bw]).length≤n+1:=by simp;have:=Cy n ps f k;omega have hg:=B5 _ 0 (w▸B) (by omega) rw [Cs.2,abs_zero,zero_add] at hg rw [Cs.2,zero_add] at o have Q:(((ps.map (fun t=>FL (xw t)*FG (ww t)))++[FL bw]).map (fun x=> |vr x|)).sum≤ (vr ob)*a+ |FH bw| :=by rw [Xd,Xc] simp only [Zr,Y9,Zq,Xb,add_zero,z,Ze] have:(ps.map ((fun x=> |vr x|)∘fun t=>FL (xw t)*FG (ww t))).sum≤ (ps.map (fun t=>(vr ob)* |FH (xw t)|)).sum:=by apply Wj;intro t b simp only [Xa,J t b,abs_mul] rw [mul_comm] apply mul_le_mul_of_nonneg_right _ (abs_nonneg _) have h1:=(Cj _ (p t b)).2.1 have h2:=Ci (ww t) have h3:(2:ℝ)^((Fw (ww t):ℤ) - 126)≤2^((fo:ℤ) - 126):= zpow_le_zpow_right₀ (by norm_num) (by have:=Y t b;omega) rw [g.2];linarith rw [Xe] at this have h4:=Cx n ps f k _ (fun t=>abs_nonneg (FH (xw t))) nlinarith have R:(((ps.map (fun t=>FL (xw t)*FG (ww t)))++[FL bw]).map vr).sum= (ps.map (fun t=>FH (xw t)*vr (FG (ww t)))).sum+FH bw:=by rw [Xd,Xc,Ze] simp only [Zr,Y9,Zq,Xb,add_zero,z] have:ps.map (vr∘fun t=>FL (xw t)*FG (ww t))=ps.map (fun t=>FH (xw t)*vr (FG (ww t))):= Zn (fun t b=>by show vr (FL (xw t)*FG (ww t))=_;exact J t b) rw [this] rw [R] at o have S: |((Qz n).map (fun t=>FH (xw t)*FH (ww t))).sum+FH bw - vr T| ≤ 2 ^(-126:ℤ)*a+((n:ℝ)+1)*2^(-52:ℤ)*(1+2^(-30:ℤ))*((vr ob)*a+ |FH bw|)+ ((n:ℝ)+1)*(1+2^(-30:ℤ))*2^(-1074:ℤ):=by have hl:(((ps.map (fun t=>FL (xw t)*FG (ww t)))++[FL bw]).length:ℝ)≤(n:ℝ)+1:=by exact_mod_cast P have ab:0≤(((ps.map (fun t=>FL (xw t)*FG (ww t)))++[FL bw]).map (fun x=> |vr x|)).sum:= Yp (fun x hx=>by obtain ⟨y, -,rfl⟩:=List.mem_map.mp hx;exact abs_nonneg _) rw [L] calc |(ps.map (fun t=>FH (xw t)*FH (ww t))).sum+FH bw - vr T| ≤ |(ps.map (fun t=>FH (xw t)*FH (ww t))).sum - (ps.map (fun t=>FH (xw t)*vr (FG (ww t)))).sum| + |vr T - ((ps.map (fun t=>FH (xw t)*vr (FG (ww t)))).sum+FH bw)| :=by rw [abs_sub_comm (vr T)] have:=abs_add_le ((ps.map (fun t=>FH (xw t)*FH (ww t))).sum - (ps.map (fun t=>FH (xw t)*vr (FG (ww t)))).sum) ((ps.map (fun t=>FH (xw t)*vr (FG (ww t)))).sum+FH bw - vr T) ring_nf at this⊢;linarith _ ≤ 2 ^(-126:ℤ)*a+(((ps.map (fun t=>FL (xw t)*FG (ww t)))++[FL bw]).length:ℝ)*2^(-52:ℤ)* (1+2^(-30:ℤ))*(((ps.map (fun t=>FL (xw t)*FG (ww t)))++[FL bw]).map (fun x=> |vr x|)).sum+ (((ps.map (fun t=>FL (xw t)*FG (ww t)))++[FL bw]).length:ℝ)*(1+2^(-30:ℤ))*2^(-1074:ℤ):=by linarith [o.trans hg,aa] _ ≤ _ :=by have hk:(0:ℝ)≤2^(-52:ℤ)*(1+2^(-30:ℤ)):=by positivity have ae:(0:ℝ)≤(1+2^(-30:ℤ))*2^(-1074:ℤ):=by positivity nlinarith [mul_le_mul hl Q ab (by positivity),mul_le_mul_of_nonneg_right hl ae, mul_nonneg (mul_nonneg (by positivity:(0:ℝ)≤(n:ℝ)+1) hk) (add_nonneg (mul_nonneg d N) (abs_nonneg (FH bw)))] have A: ∀x∈(Qz n).map (fun t=>(FL (xw t)).abs),0≤vr x:=by intro x hx;obtain ⟨t, -,rfl⟩:=List.mem_map.mp hx;rw [(Bo _).2];exact abs_nonneg _ obtain ⟨sx0,sxlo⟩:=Ct _ (l▸c) (by simp;omega) A have U:(((Qz n).map (fun t=>(FL (xw t)).abs)).map vr).sum=a:=by rw [Ze,ha];congr 1 exact Zn (fun t b=>by show vr (FL (xw t)).abs= |FH (xw t)| rw [(Bo _).2,(A8 _ (v t (List.mem_range.mp b))).2]) rw [U,←l] at sxlo;rw [←l] at sx0 simp only [Y8,X9] at sxlo have s:0≤vr (FL bw).abs:=by rw [(Bo _).2];exact abs_nonneg _ have V:vr (FL bw).abs= |FH bw| :=by rw [(Bo _).2,z] have l1:=Cr sx ob c r i sx0 d have n1:=Co sx ob c r i sx0 d have l2:=Cq _ _ i q h n1 s have n2:=Cn _ _ i q h n1 s have W:0≤vr K:=by rw [hK.2];positivity have l3:=Cr _ _ C h m W n2 have n3:=Co _ _ C h m W n2 have c0:0≤vr FT:=by rw [Bw.2];positivity have l4:=Cr sx FT c e j sx0 c0 have n4:=Co sx FT c e j sx0 c0 have t0:0≤vr FU:=by rw [Bx.2];positivity have l5:=Cq _ _ j D X n4 t0 have n5:=Cn _ _ j D X n4 t0 have l6:=Cq _ _ m X u n3 n5 rw [V] at l2;rw [hK.2] at l3;rw [Bw.2] at l4;rw [Bx.2] at l5 have key:=Cv (n:ℝ) a (vr ob) |FH bw| (Zg _) (by exact_mod_cast (show n≤2^20 by omega)) N d O (abs_nonneg _) simp only at key rw [hE] refine S.trans (key.trans ?_) exact C3 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ sxlo d (by norm_num) (by positivity) (by positivity) l1 l2 l3 l4 l5 l6 lemma C5 (l:List Float) (s:Float): FM l s=((F0 l s).map (fun y=>2^(-52:ℤ)* |vr y| +2^(-1074:ℤ))).sum:=by induction l generalizing s with | nil=>simp [FM,F0] | cons x l ih=>simp only [FM,F0,Zr,Zq,ih] lemma C6 (l:List Float) (s:Float):(F0 l s).length=l.length:=by induction l generalizing s with | nil=>simp [F0] | cons x l ih=>simp [F0,ih] lemma C7 (l:List Float) (s:Float) (y:Float): F0 (l++[y]) s=F0 l s++[l.foldl (· + ·) s+y]:=by induction l generalizing s with | nil=>simp [F0] | cons x l ih=>simp [F0,ih] lemma C8 (n a P tt bb:ℝ) (i:0≤n) (w:n≤2^20) (j:0≤a) (k:0≤P) (l:0≤tt) (m:0≤bb): let u:ℝ:=2^(-52:ℤ) let η:ℝ:=2^(-1074:ℤ) let δ:ℝ:=2^(-30:ℤ) let c1:=1 - u let cc:=P*(1 - n*u*(1+δ)) - n*(1+δ)*η let s:=a*(1 - n*u*(1+δ)) - n*(1+δ)*η 2^(-126:ℤ)*a+u*(P+tt)+(n+1)*η≤ ((((2^(-51:ℤ)*((((cc+tt)*c1 - η)+bb)*c1 - η)*c1 - η)+(s*2^(-125:ℤ)*c1 - η))*c1 - η)+ 2^(-300:ℤ))*c1 - η:=by intro u η δ c1 cc s have o:u=1/2^52:=by simp [u] have p:δ=1/2^30:=by simp [δ] have e:(2:ℝ)^(-51:ℤ)=1/2^51:=by simp have c:(2:ℝ)^(-125:ℤ)=1/2^125:=by simp have d:(2:ℝ)^(-126:ℤ)=1/2^126:=by simp have f:0≤η:=by positivity have x:=Cu set τ:ℝ:=2^(-300:ℤ) with q simp only [cc,s,c1] rw [o,p,e,c,d] have r:0≤(1/2^51)*(1 - 1/2^52)^5*(1 - n*(1/2^52)*(1+1/2^30)) - 1/2^52:=by nlinarith have t:(0:ℝ)≤(1/2^51)*(1 - 1/2^52)^5 - 1/2^52:=by norm_num have v:0≤(1/2^125)*(1 - 1/2^52)^3*(1 - n*(1/2^52)*(1+1/2^30)) - 1/2^126:=by nlinarith have b:(n+1)+(1/2^51)*(1 - 1/2^52)^5*(n*(1+1/2^30))+ (1/2^125)*(1 - 1/2^52)^3*(n*(1+1/2^30))+10≤2^200:=by nlinarith have g:(1/2:ℝ)≤1 - 1/2^52:=by norm_num have h:0≤τ:=by positivity nlinarith [mul_nonneg r k,mul_nonneg t l,mul_nonneg v j, mul_nonneg (by norm_num:(0:ℝ)≤(1/2^51)*(1 - 1/2^52)^4) m, mul_le_mul_of_nonneg_right b f,mul_le_mul_of_nonneg_left g h] lemma C9 (cf tT D1 D2 D3 sx' D4 D5 E bb cc s c1 η:ℝ) (b:cc≤cf) (c:s≤ sx') (a:0≤c1) (l1:(cf+tT)*c1 - η≤D1) (l2:(D1+bb)*c1 - η≤D2) (l3:2^(-51:ℤ)*D2*c1 - η≤D3) (l4:sx' *2^(-125:ℤ)*c1 - η≤D4) (l5:(D3+D4)*c1 - η≤D5) (l6:(D5+2^(-300:ℤ))*c1 - η≤E): ((((2^(-51:ℤ)*((((cc+tT)*c1 - η)+bb)*c1 - η)*c1 - η)+(s*2^(-125:ℤ)*c1 - η))*c1 - η)+ 2^(-300:ℤ))*c1 - η≤E:=by have m1:(cc+tT)*c1 - η≤D1:=by have:=mul_le_mul_of_nonneg_right (add_le_add_right b tT) a;linarith have m2:(((cc+tT)*c1 - η)+bb)*c1 - η≤D2:=by have:=mul_le_mul_of_nonneg_right (add_le_add_right m1 bb) a;linarith have m3:2^(-51:ℤ)*((((cc+tT)*c1 - η)+bb)*c1 - η)*c1 - η≤D3:=by have:=mul_le_mul_of_nonneg_right (mul_le_mul_of_nonneg_left m2 (by positivity:(0:ℝ)≤2^(-51:ℤ))) a linarith have m4:s*2^(-125:ℤ)*c1 - η≤D4:=by have:=mul_le_mul_of_nonneg_right c (mul_nonneg (by positivity:(0:ℝ)≤2^(-125:ℤ)) a) linarith [mul_assoc s (2^(-125:ℤ):ℝ) c1,mul_assoc sx' (2^(-125:ℤ):ℝ) c1] have m5:((2^(-51:ℤ)*((((cc+tT)*c1 - η)+bb)*c1 - η)*c1 - η)+(s*2^(-125:ℤ)*c1 - η))*c1 - η≤D5:=by have:=mul_le_mul_of_nonneg_right (add_le_add m3 m4) a;linarith have:=mul_le_mul_of_nonneg_right (add_le_add_right m5 (2^(-300:ℤ))) a;linarith lemma DA (n :Nat) (hn:n<2^20) (xw ww:Nat→UInt32) (bw:UInt32) (sx T E:Float) (l:sx=((Qz n).map (fun t=>(FL (xw t)).abs)).foldl (· + ·) 0) (hT:T=((Qz n).map (fun t=>FL (xw t)*FG (ww t))).foldl (· + ·) 0+FL bw) (hE:E=FS*((((F0 ((Qz n).map (fun t=>FL (xw t)*FG (ww t))) 0).foldl (fun a y=>a+y.abs) 0)+T.abs)+(FL bw).abs)+sx*FT+FU) (R:T.isFinite=true) (s:E.isFinite=true): (∀t,tFH (xw t)*FH (ww t))).sum+FH bw - vr T| ≤vr E:=by set L:=(Qz n).map (fun t=>FL (xw t)*FG (ww t)) with hL set cf:=(F0 L 0).foldl (fun a y=>a+y.abs) 0 with S rw [hE] at s obtain ⟨m,U⟩:=AN _ _ s obtain ⟨f,g⟩:=AN _ _ m obtain ⟨o,h⟩:=AO _ _ f obtain ⟨i,p⟩:=AN _ _ h obtain ⟨j,B⟩:=AN _ _ i obtain ⟨d,e⟩:=AO _ _ g have V:=BA _ 0 (l▸d) have u: ∀t,t D _ (List.mem_append_left _ (List.mem_map.mpr ⟨t,List.mem_range.mpr b,rfl⟩)) have w: ∀t,t⟨u t b,w t b⟩,H, ?_⟩ have I:=(A8 bw H).2 have W: ∀t,t Cl _ _ (u t b) (w t b) (G t b) set a:=((Qz n).map (fun t=> |FH (xw t)|)).sum with ha have X:0≤a:=Yp (by simp) have ag : |((Qz n).map (fun t=>FH (xw t)*FH (ww t))).sum - ((Qz n).map (fun t=>FH (xw t)*vr (FG (ww t)))).sum| ≤2^(-126:ℤ)*a:=by rw [←C0 (Qz n) (fun t=>FH (xw t)*FH (ww t)) (fun t=>FH (xw t)*vr (FG (ww t)))] calc |((Qz n).map (fun t=>FH (xw t)*FH (ww t) - FH (xw t)*vr (FG (ww t)))).sum| ≤ ((Qz n).map (fun t=> |FH (xw t)*FH (ww t) - FH (xw t)*vr (FG (ww t))|)).sum:= C2 _ _ _ ≤ ((Qz n).map (fun t=>2^(-126:ℤ)* |FH (xw t)|)).sum:=by apply Wj;intro t b rw [←mul_sub,abs_mul,mul_comm] exact mul_le_mul_of_nonneg_right (Cj _ (w t (List.mem_range.mp b))).2.2 (abs_nonneg _) _=2^(-126:ℤ)*a:=by rw [Xe] have J:((L++[FL bw]).map vr).sum=((Qz n).map (fun t=>FH (xw t)*vr (FG (ww t)))).sum+FH bw:=by rw [Xd,Xc,hL,Ze] simp only [Zr,Y9,Zq,Xb,add_zero,I] have:(Qz n).map (vr∘fun t=>FL (xw t)*FG (ww t))= (Qz n).map (fun t=>FH (xw t)*vr (FG (ww t))):= Zn (fun t b=>by show vr (FL (xw t)*FG (ww t))=_;exact W t (List.mem_range.mp b)) rw [this] rw [Cs.2,zero_add,J] at v have Y:F0 (L++[FL bw]) 0=F0 L 0++[T]:=by rw [C7,←hT] set P:=((F0 L 0).map (fun y=> |vr y|)).sum with hP have Z:0≤P:=Yp (fun x K=>by obtain ⟨y, -,rfl⟩:=List.mem_map.mp K;exact abs_nonneg _) have c:(F0 L 0).length=n:=by rw [C6,hL];simp have M:FM (L++[FL bw]) 0=2^(-52:ℤ)*(P+ |vr T|)+((n:ℝ)+1)*2^(-1074:ℤ):=by rw [C5,Y,Xd,Xc] simp only [Zr,Y9,Zq,Xb,add_zero] have:((F0 L 0).map (fun y=>2^(-52:ℤ)* |vr y| +2^(-1074:ℤ))).sum= 2^(-52:ℤ)*P+(n:ℝ)*2^(-1074:ℤ):=by rw [List.sum_map_add,Xe,←hP,List.map_const',List.sum_replicate,c];simp rw [this];ring have N: |((Qz n).map (fun t=>FH (xw t)*FH (ww t))).sum+FH bw - vr T| ≤ 2^(-126:ℤ)*a+2^(-52:ℤ)*(P+ |vr T|)+((n:ℝ)+1)*2^(-1074:ℤ):=by have h2:=v.trans (le_of_eq M) calc |((Qz n).map (fun t=>FH (xw t)*FH (ww t))).sum+FH bw - vr T| ≤ |((Qz n).map (fun t=>FH (xw t)*FH (ww t))).sum - ((Qz n).map (fun t=>FH (xw t)*vr (FG (ww t)))).sum| + |vr T - (((Qz n).map (fun t=>FH (xw t)*vr (FG (ww t)))).sum+FH bw)| :=by rw [abs_sub_comm (vr T)] have:=abs_add_le (((Qz n).map (fun t=>FH (xw t)*FH (ww t))).sum - ((Qz n).map (fun t=>FH (xw t)*vr (FG (ww t)))).sum) (((Qz n).map (fun t=>FH (xw t)*vr (FG (ww t)))).sum+FH bw - vr T) ring_nf at this⊢;linarith _≤_:=by linarith have z: ∀x∈(Qz n).map (fun t=>(FL (xw t)).abs),0≤vr x:=by intro x K;obtain ⟨t, -,rfl⟩:=List.mem_map.mp K;rw [(Bo _).2];exact abs_nonneg _ obtain ⟨sx0,sxlo⟩:=Ct _ (l▸d) (by simp;omega) z have O:(((Qz n).map (fun t=>(FL (xw t)).abs)).map vr).sum=a:=by rw [Ze,ha];congr 1 exact Zn (fun t b=>by show vr (FL (xw t)).abs= |FH (xw t)| rw [(Bo _).2,(A8 _ (u t (List.mem_range.mp b))).2]) rw [O,←l] at sxlo;rw [←l] at sx0 simp only [Y8,X9] at sxlo have k:cf=((F0 L 0).map Float.abs).foldl (· + ·) 0:=by rw [S,List.foldl_map] have A: ∀x∈(F0 L 0).map Float.abs,0≤vr x:=by intro x K;obtain ⟨y, -,rfl⟩:=List.mem_map.mp K;rw [(Bo _).2];exact abs_nonneg _ obtain ⟨cf0,cflo⟩:=Ct _ (k▸j) (by rw [Y8,c];omega) A have Q:(((F0 L 0).map Float.abs).map vr).sum=P:=by rw [Ze,hP];congr 1 exact Zn (fun y _=>by show vr y.abs= |vr y|;rw [(Bo _).2]) rw [Q,←k] at cflo;rw [←k] at cf0 rw [Y8,c] at cflo have q:0≤vr T.abs:=by rw [(Bo _).2];exact abs_nonneg _ have r:0≤vr (FL bw).abs:=by rw [(Bo _).2];exact abs_nonneg _ have l1:=Cq _ _ j B i cf0 q have n1:=Cn _ _ j B i cf0 q have l2:=Cq _ _ i p h n1 r have n2:=Cn _ _ i p h n1 r have c0:0≤vr FS:=by rw [Bv.2];positivity have l3:=Cr _ _ o h f c0 n2 have n3:=Co _ _ o h f c0 n2 have c1' :0≤vr FT:=by rw [Bw.2];positivity have l4:=Cr _ _ d e g sx0 c1' have n4:=Co _ _ d e g sx0 c1' have l5:=Cq _ _ f g m n3 n4 have n5:=Cn _ _ f g m n3 n4 have t0:0≤vr FU:=by rw [Bx.2];positivity have l6:=Cq _ _ m U s n5 t0 rw [(Bo T).2] at l1;rw [(Bo (FL bw)).2,I] at l2;rw [Bv.2] at l3;rw [Bw.2] at l4 rw [Bx.2] at l6 have key:=C8 (n:ℝ) a P |vr T| |FH bw| (Zg _) (by exact_mod_cast (show n≤2^20 by omega)) X Z (abs_nonneg _) (abs_nonneg _) simp only at key rw [hE] refine N.trans (key.trans ?_) exact C9 _ _ _ _ _ _ _ _ _ _ _ _ _ _ cflo sxlo (by norm_num) l1 l2 l3 l4 l5 l6 lemma DB (a b:Array UInt32) (st c:Nat): dsum a b st c= ∑k∈Finset.range c, sv a[st+k]! *sv b[st+k]! *2^(idxOf a[st+k]! +idxOf b[st+k]!):=by induction c generalizing st with | zero=>simp [dsum] | succ c ih=> rw [dsum,ih (st+1),Finset.sum_range_succ'] simp only [Nat.add_zero,Nat.add_assoc,Nat.add_comm 1] ring lemma DC (A B:Array UInt32) (p:A.size=B.size) (b: ∀k,ksimp [Ff] lemma DE (fa fb:Nat→Word): ∀count index m0,Fg fa fb index count m0≤ m0∧ ∀k,index≤k→k< index+count→Fg fa fb index count m0≤ idxOf (fa k)+idxOf (fb k):=by intro count induction count with | zero=>intro index m0;exact ⟨le_rfl,fun k a b=>by omega⟩ | succ c ih=> intro index m0 obtain ⟨a,b⟩:=ih (index+1) (min m0 (idxOf (fa index)+idxOf (fb index))) simp only [Fg] refine ⟨le_trans a (min_le_left _ _),fun k d e=> ?_⟩ by_cases f:k=index ·subst f;exact le_trans a (min_le_right _ _) ·exact b k (by omega) (by omega) lemma DF (fa fb:Nat→Word) (m:Nat) (A B:Array UInt32): ∀count index, (∀k,index≤k→k< index+count→ A[k]! =fa k∧B[k]! =fb k∧m≤ idxOf (fa k)+idxOf (fb k))→ Fh fa fb m index count*2^m=dsum A B index count:=by intro count induction count with | zero=>intro index _;simp [Fh,dsum] | succ c ih=> intro index h obtain ⟨a,b,hm⟩:=h index le_rfl (by omega) simp only [Fh,dsum] rw [add_mul,ih (index+1) (fun k e f=>h k (by omega) (by omega)),a,b] congr 1 rw [DD,Zp] have d:(2:Int)^(idxOf (fa index)+idxOf (fb index))= 2^(idxOf (fa index)+idxOf (fb index) - m)*2^m:=by rw [←pow_add,Nat.sub_add_cancel hm] rw [d] unfold sv cases signOf (fa index)<;>cases signOf (fb index)<;>simp<;>push_cast<;>ring lemma DG (fa fb:Nat→Word): ∀count index,Fi fa fb index count=true→ ∀k,index≤k→k< index+count→expOf (fa k)≠255∧expOf (fb k)≠255:=by intro count induction count with | zero=>intro index _ k a b;omega | succ c ih=> intro index h k a b simp only [Fi,Yh,bne_iff_ne,ne_eq] at h by_cases d:k=index ·subst d;exact ⟨h.1.1,h.1.2⟩ ·exact ih (index+1) h.2 k (by omega) (by omega) lemma DH:Fj=dotOf:=by funext n fa fb unfold Fj split ·rename_i j simp only [] split ·rename_i l set A:=Array.ofFn (n:=n) fun i=>fa i.val with e set B:=Array.ofFn (n:=n) fun i=>fb i.val with f have a: ∀k,k⟨(a k (by omega)).1,(a k (by omega)).2,hm k (Nat.zero_le _) m⟩) have g:dsum A B 0 A.size≠0:=by rw [b,←h];exact mul_ne_zero l (pow_ne_zero _ two_ne_zero) show _=dotSpec A B rw [DC A B (by simp [e,f]) (fun k c=>by rw [b] at c rw [(a k c).1,(a k c).2];exact d k (Nat.zero_le _) (by omega)) g false,b,←h, ←finishWord_scale] congr 1 ·rfl ·rfl lemma DI:Fk=dotOf:=DH lemma DJ (n:Nat) (f:Nat→UInt32) (k:Nat) (a:kf i.val)[k]! =f k:=by rw [getElem!_pos _ k (by simpa using a),Yk] lemma DK:FH oneW=1:=by have a:sv oneW=2^23:=by decide have b:idxOf oneW=126:=by decide unfold FH;rw [a,b];norm_num lemma DL (n:Nat) (xw ww:Nat→UInt32) (bw:UInt32): let A:=Array.ofFn (n:=n+1) fun t=>if t.valif t.valFH (xw t)*FH (ww t))).sum+FH bw:=by intro A B have c:A.size=n+1:=by simp [A] rw [c,DB,Finset.sum_range_succ] push_cast rw [add_mul,Finset.sum_mul] have e1: ∀k,kby rw [Z4];exact DJ (n+1) (fun t=>if tby rw [Z4];exact DJ (n+1) (fun t=>if t have e:897≤((T.toBits>>>52)&&&2047).toNat:=UInt64.le_iff_toNat_le.mp i.1 have f:((T.toBits>>>52)&&&2047).toNat≤1150:=UInt64.le_iff_toNat_le.mp i.2 have g:=(CQ T (by omega) (by omega)).1 split at a next j=>subst a;exact absurd b (by decide) next j=> rcases c:decide (268435456 have d:((268435456:UInt64) - (T.toBits&&&536870911)).toNat≤2^28:=by rw [Yz _ _ (UInt64.le_iff_toNat_le.mpr (by have:=of_decide_eq_false c;rw [UInt64.lt_iff_toNat_lt] at this show (T.toBits&&&536870911).toNat≤(268435456:UInt64).toNat;omega))] exact Nat.sub_le _ _ obtain ⟨thf, -⟩:=CT _ _ d e f _ exact ⟨g,(B3 E _ h thf).1⟩ next h=>subst a;exact absurd b (by decide) ·rw [c] at a j simp only [ite_true] at a split at a next h=> have m:(T.toBits&&&536870911).toNat<2^29:=by rw [(CV _).2.1];omega have d:((T.toBits&&&536870911) - (268435456:UInt64)).toNat≤2^28:=by have k:=of_decide_eq_true c;rw [UInt64.lt_iff_toNat_lt] at k rw [Yz _ _ (UInt64.le_iff_toNat_le.mpr (by omega))] show (T.toBits&&&536870911).toNat - 268435456≤2^28;omega obtain ⟨thf, -⟩:=CT _ _ d e f _ exact ⟨g,(B3 E _ h thf).1⟩ next h=>subst a;exact absurd b (by decide) next i=>subst a;exact absurd b (by decide) exact key _ rfl l lemma DN (n:Nat) (relu:Bool) (xw ww:Nat→UInt32) (bw:UInt32) (T E:Float) (o:T.isFinite=true→E.isFinite=true→ (∀t,tFH (xw t)*FH (ww t))).sum+FH bw - vr T| ≤vr E) (m:Fe relu T E<0x100000000): (Fe relu T E).toUInt32= act relu (dotOf (n+1) (fun t=>if tif tif t.valif t.valby rw [d];exact b) m rw [p] congr 1 show finishWord (dsum A B 0 A.size) (-298) false=dotSpec A B have j:A.size=n+1:=by simp [f] symm apply DC A B (by simp [f,g]) ·intro k l rw [j] at l rw [f,g,DJ (n+1) (fun t=>if tif tq (by rw [h];rfl),fun h=>r (by rw [h];rfl)⟩ ·rw [Qx a,Qx a] exact ⟨by decide,fun h=>c (by rw [h];rfl)⟩ ·exact i lemma DO (n:Nat) (l:n<2^20) (relu:Bool) (xw ww:Nat→UInt32) (bw:UInt32) (ps:List Nat) (c: ∀t∈ps,t(FL (xw t)).abs)).foldl (· + ·) 0) (q:s=(ps.map (fun t=>FL (xw t)*FG (ww t))).foldl (· + ·) 0) (r:Fe relu (s+FL bw) (K*(sx*FV o+(FL bw).abs)+(sx*FT+FU))<0x100000000): (Fe relu (s+FL bw) (K*(sx*FV o+(FL bw).abs)+(sx*FT+FU))).toUInt32= act relu (dotOf (n+1) (fun t=>if tif t⟨g t j, ?_⟩,i,a⟩ by_cases k:t∈ps ·exact h t k ·exact b t j k lemma DP (n:Nat) (c:n<2^20): ((n+9).toUInt64.toFloat*FR).isFinite=true∧vr ((n+9).toUInt64.toFloat*FR)=((n:ℝ)+9)*2^(-52:ℤ):=by have b:(n+9).toUInt64.toNat=n+9:=by rw [Nat.toUInt64,Z1,Zy (by omega)] obtain ⟨uf,uv⟩:=Br (n+9).toUInt64 (by rw [b];omega) obtain ⟨cf,cv⟩:=Bu rw [b] at uv have a:=Ar _ _ uf cf (by rw [uv,cv,abs_of_nonneg (by positivity),abs_of_nonneg (by positivity)] have a1:((n+9:ℕ):ℝ)≤2^21:=by exact_mod_cast (show n+9≤2^21 by omega) calc ((n+9:ℕ):ℝ)*2^(-52:ℤ)≤2^21*2^(-52:ℤ):=mul_le_mul_of_nonneg_right a1 (by positivity) _≤2^(200:ℤ):=by rw [show (2:ℝ)^21=2^(21:ℤ) by norm_num,As] exact zpow_le_zpow_right₀ (by norm_num) (by norm_num)) refine ⟨a, ?_⟩ rw [AU _ _ uf cf a ((n+9:ℕ):ℤ) (-52) (by simp;omega) (by norm_num) (by rw [uv,cv];push_cast;ring), uv,cv] push_cast;ring lemma DQ (n:Nat) (c:n<2^20) (relu:Bool) (xw ww:Nat→UInt32) (bw:UInt32) (sx T E:Float) (b:sx=((Qz n).map (fun t=>(FL (xw t)).abs)).foldl (· + ·) 0) (d:T=((Qz n).map (fun t=>FL (xw t)*FG (ww t))).foldl (· + ·) 0+FL bw) (e:E=FS*((((F0 ((Qz n).map (fun t=>FL (xw t)*FG (ww t))) 0).foldl (fun a y=>a+y.abs) 0)+T.abs)+(FL bw).abs)+sx*FT+FU) (f:Fe relu T E<0x100000000): (Fe relu T E).toUInt32= act relu (dotOf (n+1) (fun t=>if tif tDA n c xw ww bw sx T E b d e Tf Ef) f def F8 (inW:Nat) (relu:Bool) (X W b:Array Word) (i j:Nat):Word:= act relu (dotOf (inW+1) (fun t=>if t< inW then X[i*inW+t]! else oneW) (fun t=>if t< inW then W[j*inW+t]! else b[j]!)) lemma DR (inW:Nat) (relu:Bool) (X W b:Array Word) (i j:Nat): Fl inW relu X W b i j=F8 inW relu X W b i j:=by unfold Fl F8;rw [DI] lemma DS (inW:Nat) (relu:Bool) (X W b:Array Word) (i j:Nat) (d:UInt64) (h:d<0x100000000→d.toUInt32=F8 inW relu X W b i j):Fm inW relu X W b i j d=F8 inW relu X W b i j:=by unfold Fm;split ·exact h (by assumption) ·exact DR _ _ _ _ _ _ _ lemma DT (n:Nat):List.range' 0 (n - 0)=Qz n:=by rw [Xl,Wh] lemma DU (inW:Nat) (relu:Bool) (X W b:Array Word) (i j:Nat) (bd:Float) (x:FloatArray) (off st:Nat) (sx:Float) (m:j*inW+inW≤W.size) (e:W.size<2^32) (f:x.size<2^32) (n: ∀t,t< inW→ off+st*t(FL X[i*inW+t]!).abs)).foldl (· + ·) 0) (k:Fn inW relu W j bd x off st sx m e f n c d a<0x100000000): (Fn inW relu W j bd x off st sx m e f n c d a).toUInt32=F8 inW relu X W b i j:=by unfold Fn at k⊢ simp only [] at k⊢ have h:=BZ x W off.toUSize st.toUSize (j*inW).toUSize inW.toUSize (fun t l=>by rw [BJ _ a,BJ _ d];rw [BJ _ c] at l;exact n t l) f (by rw [BJ _ (by omega),BJ _ c];exact m) e 0 0 0 have r:F1 x W off.toUSize.toNat st.toUSize.toNat (j*inW).toUSize.toNat (0:USize).toNat inW.toUSize.toNat= (Qz inW).map (fun t=>FL X[i*inW+t]! *FG W[j*inW+t]!):=by rw [BJ _ a,BJ _ d,BJ _ (by omega),BJ _ c, show (0:USize).toNat=0 from rfl,F1,DT] exact Zn (fun t l=>by rw [p t (List.mem_range.mp l)]) rw [r] at h obtain ⟨s,u⟩:=h rw [s,u,o] at k⊢ exact DQ inW g relu (fun t=>X[i*inW+t]!) (fun t=>W[j*inW+t]!) b[j]! sx _ _ q rfl rfl k lemma DV (inW:Nat) (relu:Bool) (X W b:Array Word) (i j:Nat) (bd:Float) (x:FloatArray) (off st:Nat) (sx C K ob s:Float) (ok:Bool) (q:j*inW+inW≤W.size) (d:W.size<2^32) (e:x.size<2^32) (r: ∀t,t< inW→ off+st*t(FL X[i*inW+t]!).abs)).foldl (· + ·) 0) (z:C=sx*FT+FU) (A:K=(inW+9).toUInt64.toFloat*FR) (ps:List Nat) (v: ∀t∈ps,t< inW) (w:ps.Nodup) (B: ∀t,t< inW→t∉ps→X[i*inW+t]! &&&0x7FFFFFFF=0) (l:ok=true→ ∀t,t< inW→t∉ps→(expOf W[j*inW+t]!).toNat≠255) (o:UInt32) (y: ∀t∈ps,Fw W[j*inW+t]! ≤Fw o) (p:ob=FV o) (D:s=(ps.map (fun t=>FL X[i*inW+t]! *FG W[j*inW+t]!)).foldl (· + ·) 0) (m:Fo inW relu W j bd x off st sx C K ob s ok q d e r f g a<0x100000000): (Fo inW relu W j bd x off st sx C K ob s ok q d e r f g a).toUInt32=F8 inW relu X W b i j:=by unfold Fo at m⊢ simp only [] at m⊢ cases ok with | false=> simp only [Zx,ite_false,lt_self_iff_false] at m⊢ exact DU inW relu X W b i j bd x off st sx q d e r f g a c h n k m | true=> simp only [ite_true] at m⊢ by_cases u:Fe relu (s+bd) (K*(sx*ob+bd.abs)+C)<0x100000000 ·rw [Qw u] rw [p,z,A,h] at u⊢ exact DO inW c relu (fun t=>X[i*inW+t]!) (fun t=>W[j*inW+t]!) b[j]! ps v w B (l rfl) o y _ sx s (DP inW c) k D u ·rw [Qx u] at m⊢ exact DU inW relu X W b i j bd x off st sx q d e r f g a c h n k m lemma DW {α:Type} [Inhabited α] (A:Array α) (i p:Nat) (v:α): (A.set! i v)[p]! =if i=p∧ia (b▸c) simp [this] lemma DX (X:Array UInt32) (xo k n:Nat):(F3 X xo k n).Nodup:= (List.nodup_range' ..).filter _ lemma DY (X:Array UInt32) (xo n t:Nat) (b:t(FL X[i*inW+t]!).abs)).foldl (· + ·) 0) (o:K=(inW+9).toUInt64.toFloat*FR) (ps:List Nat) (j: ∀t∈ps,t< inW) (k:ps.Nodup) (p: ∀t,t< inW→t∉ps→X[i*inW+t]! &&&0x7FFFFFFF=0) (a:((z>>>23)&&&0xFF !=0xFF)=true→ ∀t,t< inW→t∉ps→(expOf W[jj*inW+t]!).toNat≠255) (l: ∀t∈ps,Fw W[jj*inW+t]! ≤Fw z) (q:s=(ps.map (fun t=>FL X[i*inW+t]! *FG W[jj*inW+t]!)).foldl (· + ·) 0): Fm inW relu X W b i jj (Fo inW relu W jj (FL b[jj]!) x 0 1 sx (sx*FT+FU) K (FV z) s ((z>>>23)&&&0xFF !=0xFF) m c d n e (by decide) (by decide))=F8 inW relu X W b i jj:=by apply DS intro r exact DV inW relu X W b i jj _ x 0 1 sx _ K _ s _ m c d n e (by decide) (by decide) f rfl g h rfl o ps j k p a z l rfl q r def F9 (inW outW:Nat) (relu:Bool) (X W b:Array Word) (q:Nat):Word:= F8 inW relu X W b (q/outW) (q % outW) lemma Da (inW outW:Nat) (relu:Bool) (X W b:Array Word) (i j:Nat) (a:jomega rw [DW,DW] simp only [Array.size_set!,g] by_cases e2:i*outW+j2=q ·rw [Qw ⟨e2,by omega⟩,←e2,Da _ _ _ _ _ _ _ _ f,o] ·rw [Qx (fun h=>e2 h.1)] by_cases e1:i*outW+j=q ·rw [Qw ⟨e1,by omega⟩,←e1,Da _ _ _ _ _ _ _ _ m,n] ·rw [Qx (fun h=>e1 h.1)] apply c q _ e by_cases r:j+1FL X[i*inW+t]! *FG W[wo+t]!):=by subst b rw [Fx,DT] exact Zn (fun t c=>by rw [a t (List.mem_range.mp c)]) lemma Dd (rows inW outW:Nat) (relu:Bool) (X W b:Array Word) (i:Nat) (x:FloatArray) (c:FC) (n: ∀k (D:k(FL X[i*inW+t]!).abs)).foldl (· + ·) 0) (hK:K=(inW+9).toUInt64.toFloat*FR) (j:Nat) (out:Array Word) (hs:out.size=rows*outW) (y: ∀q,q< i*outW+j→q<(i+1)*outW→ out[q]! =F9 inW outW relu X W b q): (Fp inW outW relu X W b i x c n gath sx K S a o G p H v j out).size=rows*outW∧ ∀q,q<(i+1)*outW→ (Fp inW outW relu X W b i x c n gath sx K S a o G p H v j out)[q]! =F9 inW outW relu X W b q:=by induction j,out using Fp.induct inW outW relu X W b i x c n gath sx K S a o G p H v with | case1 j out R j2 al U V Y Z J f g r z ok ob b0 b1 C d0 d1 out' ih=> rw [Fp];simp only [dif_pos R] have l:inW.toUSize.toNat=inW:=BJ _ (by omega) have w:(j*inW).toUSize.toNat=j*inW:=BJ _ Y have m:(j2*inW).toUSize.toNat=j2*inW:=BJ _ Z have A: ∀t,t< inW→x.data[0+1*t]! =FL X[i*inW+t]! :=fun t d=>by rw [Z4,Nat.one_mul];exact E t d have facts: ∃ps:List Nat,(∀t∈ps,t< inW)∧ps.Nodup∧ (∀t,t< inW→t∉ps→X[i*inW+t]! &&&0x7FFFFFFF=0)∧ (((z>>>23)&&&0xFF !=0xFF)=true→ ∀t,t< inW→t∉ps→ (expOf W[j*inW+t]!).toNat≠255∧(expOf W[j2*inW+t]!).toNat≠255)∧ (∀t∈ps,Fw W[j*inW+t]! ≤Fw z∧Fw W[j2*inW+t]! ≤Fw z)∧ r.s0=(ps.map (fun t=>FL X[i*inW+t]! *FG W[j*inW+t]!)).foldl (· + ·) 0∧ r.s1=(ps.map (fun t=>FL X[i*inW+t]! *FG W[j2*inW+t]!)).foldl (· + ·) 0:=by cases gath · refine ⟨Qz inW, ?_,Y2, ?_, ?_, ?_, ?_, ?_⟩ ·intro t d;exact List.mem_range.mp d ·intro t d s;exact absurd (List.mem_range.mpr d) s ·intro _ t d s;exact absurd (List.mem_range.mpr d) s ·intro t d have:=(BV x W (j*inW).toUSize (j2*inW).toUSize inW.toUSize (by rw [l];exact G) f g a 0 0 0 0).2.2.2 t (by simp) (by rw [l];exact List.mem_range.mp d) simp only [w,m] at this exact this ·have:=(BV x W (j*inW).toUSize (j2*inW).toUSize inW.toUSize (by rw [l];exact G) f g a 0 0 0 0).1 have F:Fx x W (j*inW).toUSize.toNat (0:USize).toNat inW.toUSize.toNat= (Qz inW).map (fun t=>FL X[i*inW+t]! *FG W[j*inW+t]!):=by rw [w,l,show (0:USize).toNat=0 from rfl,Dc x W X i _ inW inW rfl E] rw [F] at this exact this ·have:=(BV x W (j*inW).toUSize (j2*inW).toUSize inW.toUSize (by rw [l];exact G) f g a 0 0 0 0).2.1 have F:Fx x W (j2*inW).toUSize.toNat (0:USize).toNat inW.toUSize.toNat= (Qz inW).map (fun t=>FL X[i*inW+t]! *FG W[j2*inW+t]!):=by rw [m,l,show (0:USize).toNat=0 from rfl,Dc x W X i _ inW inW rfl E] rw [F] at this exact this · have e:c.IX.size.toUSize.toNat=c.IX.size:=BJ _ v have hg:=BW c.xc c.IX W (j*inW).toUSize (j2*inW).toUSize c.IX.size.toUSize inW.toUSize (by rw [e];exact H) (by rw [e]) (fun k D=>by rw [l];exact n k D) f g a 0 0 0 have L: ∀wo,Fy c.xc c.IX W wo 0 c.IX.size=(F3 X (i*inW) 0 inW).map (fun t=>FL X[i*inW+t]! *FG W[wo+t]!):=by intro wo;rw [T];exact Bj X (i*inW) inW W wo (by omega) have M:=Ba W (j*inW).toUSize inW.toUSize f a 0 0 have N:=Ba W (j2*inW).toUSize inW.toUSize g a 0 0 have aa:z=FY W (j*inW).toUSize inW.toUSize f a 0 0 ||| FY W (j2*inW).toUSize inW.toUSize g a 0 0:=rfl have B: ∀t,t< inW→Fw W[j*inW+t]! ≤Fw z∧Fw W[j2*inW+t]! ≤Fw z:=by intro t d have a1:=M.2 t (by simp) (by rw [l];exact d) have a2:=N.2 t (by simp) (by rw [l];exact d) rw [w] at a1;rw [m] at a2 rw [aa] exact ⟨le_trans a1 (BP _ _).1,le_trans a2 (BP _ _).2⟩ refine ⟨F3 X (i*inW) 0 inW,Bi X (i*inW) 0 inW,DX X (i*inW) 0 inW, fun t d s=>DY X (i*inW) inW t d s, ?_,fun t d=>B t (Bi _ _ _ _ t d), ?_, ?_⟩ ·intro ab t d _ have ai:Fw z≠255:=by intro h;apply (show ((z>>>23)&&&0xFF)≠0xFF from by simpa using ab) apply UInt32.toNat_inj.mp rw [Zl,Yb,show (0xFF:UInt32).toNat=2^8 - 1 from rfl, Zt,show (23:UInt32).toNat % 32=23 from rfl,Zu] unfold Fw at h;rw [h];rfl have:=BO z obtain ⟨b1',b2'⟩:=B t d rw [Cg] at b1' b2' exact ⟨by omega,by omega⟩ ·have:r.s0=(Fb c.xc c.IX W (j*inW).toUSize (j2*inW).toUSize c.IX.size.toUSize inW.toUSize (by rw [e];exact H) (by rw [e]) (fun k D=>by rw [l];exact n k D) f g a 0 0 0).s0:=rfl rw [this,hg.1,e,show (0:USize).toNat=0 from rfl,w,L] ·have:r.s1=(Fb c.xc c.IX W (j*inW).toUSize (j2*inW).toUSize c.IX.size.toUSize inW.toUSize (by rw [e];exact H) (by rw [e]) (fun k D=>by rw [l];exact n k D) f g a 0 0 0).s1:=rfl rw [this,hg.2,e,show (0:USize).toNat=0 from rfl,m,L] obtain ⟨ps,O,P,hz,u,Q,ad,ae⟩:=facts have v1:=DZ inW relu X W b i j x sx K r.s0 z U a p J (by omega) o A I hK ps O P hz (fun h t d l=>(u h t d l).1) (fun t d=>(Q t d).1) ad have v2:=DZ inW relu X W b i j2 x sx K r.s1 z V a p J (by omega) o A I hK ps O P hz (fun h t d l=>(u h t d l).2) (fun t d=>(Q t d).2) ae obtain ⟨u1,u2⟩:=Db inW outW relu X W b rows i j hi R out (Fm inW relu X W b i j d0) (Fm inW relu X W b i j2 d1) hs y v1 v2 exact ih u1 u2 | case2 j out R=> rw [Fp];simp only [dif_neg R] have:(i+1)*outW=i*outW+outW:=by ring exact ⟨hs,fun q hq=>y q (by omega) hq⟩ lemma De (inW:Nat) (relu:Bool) (X W b:Array Word) (i j k:Nat) (w:k<8) (x8:FloatArray) (sxk K s:Float) (o:UInt32) (q:j*inW+inW≤W.size) (d:W.size<2^32) (e:x8.size<2^32) (x:8*inW≤x8.size) (f:inW<2^32) (g:inW<2^20) (l: ∀t,t< inW→x8.data[8*t+k]! =FL X[(i+k)*inW+t]!) (m:sxk=((Qz inW).map (fun t=>(FL X[(i+k)*inW+t]!).abs)).foldl (· + ·) 0) (r:K=(inW+9).toUInt64.toFloat*FR) (n: ∀t,t< inW→Fw W[j*inW+t]! ≤Fw o) (u:s=((Qz inW).map (fun t=>FL X[(i+k)*inW+t]! *FG W[j*inW+t]!)).foldl (· + ·) 0) (h: ∀t,t< inW→k+8*tby rw [show k+8*t=8*t+k by ring];exact l t a) m rfl r (Qz inW) (fun t a=>List.mem_range.mp a) Y2 (fun t a p=>absurd (List.mem_range.mpr a) p) (fun _ t a p=>absurd (List.mem_range.mpr a) p) o (fun t a=>n t (List.mem_range.mp a)) rfl u v lemma Df (inW outW:Nat) (relu:Bool) (X W b:Array Word) (rows i j k:Nat) (bd:Float) (x8:FloatArray) (sxk ck K ob s:Float) (l:j*inW+inW≤W.size) (a:W.size<2^32) (c:x8.size<2^32) (n:8*inW≤x8.size) (d:inW<2^32) (p:k<8) (r:i+kby omega) d (by decide) (by omega))=F8 inW relu X W b (i+k) j): (Fq inW outW relu X W b i j k bd x8 sxk ck K ob s l a c n d p o).size=rows*outW∧ ∀q,(S q∨q=(i+k)*outW+j)→qe h.1)] rcases g with g | g ·exact w q g m ·exact absurd g.symm e def QS (outW i j m q:Nat):Prop:= q< i*outW∨(∃k c,k<8∧c(FL X[(i+k)*inW+t]!).abs)).foldl (· + ·) 0) (x: ∀k t,k<8→t< inW→x8.data[8*t+k]! =FL X[(i+k)*inW+t]!) (H:K=(inW+9).toUInt64.toFloat*FR) (j:Nat) (out:Array Word) (G:out.size=rows*outW) (p: ∀q,QS outW i j 0 q→q rw [Fr];simp only [dif_pos g] have z:inW.toUSize.toNat=inW:=BJ _ (by omega) have u:(j*inW).toUSize.toNat=j*inW:=BJ _ hm obtain ⟨e0,e1,e2,e3,e4,e5,e6,e7, -, -,eo⟩:=BY x8 W (j*inW).toUSize inW.toUSize (by rw [z];exact f) (by rw [u,z];exact h) c d 0 0 0 0 0 0 0 0 0 0 (by decide) have D: ∀k,k<8→Fz x8 W k (j*inW).toUSize.toNat (0:USize).toNat inW.toUSize.toNat= (Qz inW).map (fun t=>FL X[(i+k)*inW+t]! *FG W[j*inW+t]!):=by intro k m rw [u,z,show (0:USize).toNat=0 from rfl,Fz,DT] exact Zn (fun t w=>by rw [x k t m (List.mem_range.mp w)]) have E: ∀t,t< inW→Fw W[j*inW+t]! ≤Fw r.o:=by intro t w;have:=eo t (by simp) (by rw [z];exact w) calc Fw W[j*inW+t]! =Fw W[(j*inW).toUSize.toNat+t]! :=by rw [u] _≤Fw r.o:=this have F: ∀k (m:k<8),∀s:Float, s=(Fz x8 W k (j*inW).toUSize.toNat (0:USize).toNat inW.toUSize.toNat).foldl (· + ·) 0→ Fm inW relu X W b (i+k) j (Fo inW relu W j bd x8 k 8 (sa[k]!) (sa[k]! *FT+FU) K ob s true h c d (fun t w=>by omega) l (by decide) (by omega))=F8 inW relu X W b (i+k) j:=by intro k m s y rw [D k m] at y exact De inW relu X W b i j k m x8 _ K s r.o h c d f l n (fun t w=>x k t m w) (C k m) H E y _ _ have v: ∀k (m:k<8),Fm inW relu X W b (i+k) j (Fo inW relu W j bd x8 k 8 (sa[k]!) (sa[k]! *FT+FU) K ob ([r.s0,r.s1,r.s2,r.s3,r.s4,r.s5,r.s6,r.s7][k]'(by simp;omega)) true h c d (fun t w=>by omega) l (by decide) (by omega))=F8 inW relu X W b (i+k) j:=by intro k m apply F k m interval_cases k ·exact e0 ·exact e1 ·exact e2 ·exact e3 ·exact e4 ·exact e5 ·exact e6 ·exact e7 obtain ⟨a1,b1⟩:=Df inW outW relu X W b rows i j 0 bd x8 (sa[0]!) (sa[0]! *FT+FU) K ob r.s0 h c d f l (by decide) (by omega) g out (QS outW i j 0) G (fun q e a=>p q e a) (v 0 (by decide)) obtain ⟨a2,b2⟩:=Df inW outW relu X W b rows i j 1 bd x8 (sa[1]!) (sa[1]! *FT+FU) K ob r.s1 h c d f l (by decide) (by omega) g out1 (QS outW i j 1) a1 (fun q e a=>b1 q (Dg outW i j 0 q e) a) (v 1 (by decide)) obtain ⟨a3,b3⟩:=Df inW outW relu X W b rows i j 2 bd x8 (sa[2]!) (sa[2]! *FT+FU) K ob r.s2 h c d f l (by decide) (by omega) g out2 (QS outW i j 2) a2 (fun q e a=>b2 q (Dg outW i j 1 q e) a) (v 2 (by decide)) obtain ⟨a4,b4⟩:=Df inW outW relu X W b rows i j 3 bd x8 (sa[3]!) (sa[3]! *FT+FU) K ob r.s3 h c d f l (by decide) (by omega) g out3 (QS outW i j 3) a3 (fun q e a=>b3 q (Dg outW i j 2 q e) a) (v 3 (by decide)) obtain ⟨a5,b5⟩:=Df inW outW relu X W b rows i j 4 bd x8 (sa[4]!) (sa[4]! *FT+FU) K ob r.s4 h c d f l (by decide) (by omega) g out4 (QS outW i j 4) a4 (fun q e a=>b4 q (Dg outW i j 3 q e) a) (v 4 (by decide)) obtain ⟨a6,b6⟩:=Df inW outW relu X W b rows i j 5 bd x8 (sa[5]!) (sa[5]! *FT+FU) K ob r.s5 h c d f l (by decide) (by omega) g out5 (QS outW i j 5) a5 (fun q e a=>b5 q (Dg outW i j 4 q e) a) (v 5 (by decide)) obtain ⟨a7,b7⟩:=Df inW outW relu X W b rows i j 6 bd x8 (sa[6]!) (sa[6]! *FT+FU) K ob r.s6 h c d f l (by decide) (by omega) g out6 (QS outW i j 6) a6 (fun q e a=>b6 q (Dg outW i j 5 q e) a) (v 6 (by decide)) obtain ⟨a8,b8⟩:=Df inW outW relu X W b rows i j 7 bd x8 (sa[7]!) (sa[7]! *FT+FU) K ob r.s7 h c d f l (by decide) (by omega) g out7 (QS outW i j 7) a7 (fun q e a=>b7 q (Dg outW i j 6 q e) a) (v 7 (by decide)) exact ih a8 (fun q e a=>b8 q (Dg outW i j 7 q (Dh outW i j q e)) a) | case2 j out g=> rw [Fr];simp only [dif_neg g] refine ⟨G,fun q e=>p q (Di outW i j q g e) ?_⟩ have:(i+8)*outW≤rows*outW:=Zj _ B omega lemma Dk (rows inW outW:Nat) (relu:Bool) (X W b:Array Word) (i n:Nat) (d:i+n≤rows) (q:Nat) (o:Array Word) (f:o.size=rows*outW) (a: ∀p,p< i*outW+q→p rw [Fs];simp only [Qw c] apply ih (by simp [f]) intro p l j rw [DW] by_cases e:i*outW+q=p ·rw [Qw ⟨e,by rw [f];omega⟩,←e,DR] have m:0by subst h;simp at c) unfold F9 rw [show i*outW+q=q+outW*i by ring,Nat.add_mul_div_left _ _ m,Wk,Nat.add_comm] ·rw [Qx (fun h=>e h.1)] exact a p (by omega) j | case2 q o c=> rw [Fs];simp only [Qx c] exact ⟨f,fun p l=>a p (by omega) (by omega)⟩ lemma Dl (X:Array UInt32) (xo n:Nat): F2 X xo 0 n=(Qz n).map (fun t=>(FL X[xo+t]!).abs):=by rw [F2,DT] lemma Dm (rows inW outW:Nat) (relu:Bool) (X W b:Array Word) (K:Float) (l:outW*inW≤W.size) (f:W.size<2^32) (g:inW<2^20) (w:K=(inW+9).toUInt64.toFloat*FR) (i:Nat) (out:Array Word) (m:out.size=rows*outW) (a: ∀p,p< i*outW→p rw [Fu];simp only [Qw j] obtain ⟨f1,f2, -,f4, -,f6⟩:=Bf X inW i 0 ⟨Z5 (8*inW) 0⟩ #[] have u:(⟨Z5 (8*inW) 0⟩:FloatArray).size=8*inW:=by simp [Z0] have n:(i+8)*outW≤rows*outW:=Zj _ j have step:out1.size=rows*outW∧ ∀p,p<(i+8)*outW→ out1[p]! =F9 inW outW relu X W b p:=by dsimp only [out1] split ·next h=> exact Dj rows inW outW relu X W b i q.1 q.2 K l f g h.1 (by omega) j (fun k s=>by have:=f6 k (Nat.zero_le _) s simp only [Array.size_empty,Z4,Xl] at this rw [this,Dl]) (fun k t s v=>f2 k t (Nat.zero_le _) s v (by rw [u];omega)) w 0 out m (fun p e d=>by rcases e with e | ⟨_,c,_,x,_⟩ | ⟨_,s,_⟩ ·exact a p e d ·omega ·omega) ·exact Dk rows inW outW relu X W b i 8 j 0 out m (fun p e d=>a p (by omega) d) exact ih step.1 (fun p e _=>step.2 p e) | case2 i out j o y r c x out1 ih=> rw [Fu];simp only [Qx j,Qw o] obtain ⟨g1,g2, -,g4⟩:=Bc X (i*inW) inW 0 1 0 ⟨Z5 inW 0⟩ 0 (le_refl 1) have u:(⟨Z5 inW 0⟩:FloatArray).size=inW:=by simp [Z0] have n:(i+1)*outW≤rows*outW:=Zj _ o have step:out1.size=rows*outW∧ ∀p,p<(i+1)*outW→ out1[p]! =F9 inW outW relu X W b p:=by dsimp only [out1] split ·next h=> exact Dd rows inW outW relu X W b i r.1 c _ _ r.2 K l f g h.1 (by omega) h.2.2.1 (by omega) o rfl (fun t v=>by have:=g2 t (Nat.zero_le _) v (by rw [u];omega);simpa using this) (by rw [g4,Dl]) w 0 out m (fun p e d=>a p (by omega) (by omega)) ·exact Dk rows inW outW relu X W b i 1 (by omega) 0 out m (fun p e d=>a p (by omega) d) exact ih step.1 (fun p e _=>step.2 p e) | case3 i out j o=> rw [Fu];simp only [Qx j,Qx o] have:rows*outW≤ i*outW:=Zj _ (by omega) exact ⟨m,fun p e=>a p (by omega) e⟩ lemma Dn:Fv=linearWith dotOf:=by funext rows inW outW relu X W b unfold Fv split ·next h=> obtain ⟨d,a⟩:=Dm rows inW outW relu X W b _ h.2.1 (by omega) (by omega) rfl 0 (Z5 (rows*outW) 0) (by simp) (fun p e=>by simp at e) apply Array.ext ·rw [d];simp [linearWith] ·intro q c f rw [←getElem!_pos _ q c,a q (by rw [d] at c;exact c)] simp only [linearWith,Yk] rfl ·rfl lemma Do (z:Model Fmt):ofW (toWord z)=z:=by have h:z.toNatBits<2^32:=Model.toNatBits_lt_two_pow z simp only [ofW,toWord,Wi,Yv,Zy h] exact Model.ofNatBits_toNatBits z lemma Dp (w:Word):toWord (ofW w)=w:=by apply UInt32.toNat_inj.mp simp only [toWord,ofW,Model.toNatBits,ofUInt32_bits,Yv] exact Zy w.toBitVec.isLt lemma Dq (T E:Float) (o:Fe false T E<0x100000000): ∃neg:Bool,∃e h:Nat,1≤e∧e≤254∧h<2^23∧ (Fe false T E).toNat=(if neg then 2^31 else 0)+e*2^23+h:=by have key: ∀(v:UInt64),Fe false T E=v→v<0x100000000→ ∃neg:Bool,∃e h:Nat,1≤e∧e≤254∧h<2^23∧ v.toNat=(if neg then 2^31 else 0)+e*2^23+h:=by intro v b c unfold Fe at b simp only [] at b split at b next k=> split at b next j=>subst b;exact absurd c (by decide) next j=> have d:897≤((T.toBits>>>52)&&&2047).toNat:=UInt64.le_iff_toNat_le.mp k.1 have f:((T.toBits>>>52)&&&2047).toNat≤1150:=UInt64.le_iff_toNat_le.mp k.2 have l:=(CV T.toBits).2.2.1 have g:(T.toBits>>>29&&&8388607).toNat<2^23:=by rw [l];omega rcases i:decide (268435456 subst b simp only [Bool.false_and,Zx,ite_false] have a:((T.toBits>>>29&&&8388607)+0).toNat=(T.toBits>>>29&&&8388607).toNat:=by simp have n:=CX (T.toBits>>>63==1) (T.toBits>>>52&&&2047) ((T.toBits>>>29&&&8388607)+0) d f (by rw [a];omega) refine ⟨T.toBits>>>63==1,((T.toBits>>>52)&&&2047).toNat - 896, (T.toBits>>>29&&&8388607).toNat,by omega,by omega,g, ?_⟩ rw [n,a] next m=>subst b;exact absurd c (by decide) ·rw [i] at b j simp only [ite_true] at b split at b next m=> subst b simp only [Bool.false_and,Zx,ite_false] have p:(T.toBits>>>29&&&8388607).toNat≠2^23 - 1:=by intro h;apply j;right;left;exact ⟨rfl,UInt64.toNat_inj.mp (by rw [h];rfl)⟩ have a:((T.toBits>>>29&&&8388607)+1).toNat=(T.toBits>>>29&&&8388607).toNat+1:=by rw [X8,show (1:UInt64).toNat=1 from rfl,Zy (by omega)] have n:=CX (T.toBits>>>63==1) (T.toBits>>>52&&&2047) ((T.toBits>>>29&&&8388607)+1) d f (by rw [a];omega) refine ⟨T.toBits>>>63==1,((T.toBits>>>52)&&&2047).toNat - 896, (T.toBits>>>29&&&8388607).toNat+1,by omega,by omega,by omega, ?_⟩ rw [n,a] next m=>subst b;exact absurd c (by decide) next k=>subst b;exact absurd c (by decide) exact key _ rfl o lemma Dr (T E:Float) (i:Fe false T E<0x100000000): Model.isFinite (ofW (Fe false T E).toUInt32)=true∧ Yw (ofW (Fe false T E).toUInt32)≠0:=by obtain ⟨neg,e,h,j,k,o,d⟩:=Dq T E i have c:(Fe false T E).toNat<2^32:=by rw [d];cases neg<;>simp<;>omega have l:(Fe false T E).toUInt32=Zi ((if neg then 2^31 else 0)+e*2^23+h):=by rw [Cd _ c,d] have m:(if neg then 2^31 else 0)+e*2^23+h<2^32:=by rw [←d];exact c have a:(expOf (Fe false T E).toUInt32).toNat=e:=by rw [l,Cb _ m];cases neg<;>simp<;>omega have b:expOf (Fe false T E).toUInt32≠255:=fun f=>by rw [f] at a;simp at a;omega have n:expOf (Fe false T E).toUInt32≠0:=fun f=>by rw [f] at a;simp at a;omega refine ⟨by simp [ofW,isFinite_ofUInt32,b], ?_⟩ rw [Model.toReal_eq,ofW,toDyadic_ofUInt32 _ b] simp only [Option.map_some,Option.getD_some] intro g rw [Model.Dyadic.toReal_eq_zero_iff] at g unfold decodeD at g simp only [n,ite_false] at g omega lemma Ds:(2:ℝ)^(127:ℤ)≤Yw (Model.posMaxFinite Fmt):=by rw [Model.toReal_posMaxFinite] have a:Fmt.maxNormalExponent=127:=by decide have c:Model.pow2 Fmt.fracWidth=2^23:=by decide have b:(Int.ofNat Fmt.fracWidth)=23:=rfl rw [c,a,b] have d:Model.bpow (127 - 23)=(2:ℝ)^(104:ℤ):=by simp [Model.bpow,Zo,Zv, Za] rw [d] have e:(2:ℝ)^(23:ℕ)≤((2^23+Fmt.maxFiniteFracField:ℕ):ℝ):=by push_cast linarith [(Zg (α:=ℝ) Fmt.maxFiniteFracField)] calc (2:ℝ)^(127:ℤ)=(2:ℝ)^(23:ℕ)*(2:ℝ)^(104:ℤ):=by rw [show (127:ℤ)=(23:ℕ)+104 by norm_num,zpow_add₀ (by norm_num:(2:ℝ)≠0),zpow_natCast] _≤((2^23+Fmt.maxFiniteFracField:ℕ):ℝ)*(2:ℝ)^(104:ℤ):= mul_le_mul_of_nonneg_right e (by positivity) lemma Dt (q:ℚ) (e:q≠0) (c: |(q:ℝ)| ≤2^(127:ℤ)): Model.isFinite (Xz Fmt (decide (q<0)) q.num.natAbs q.den)=true∧ Yw (Xz Fmt (decide (q<0)) q.num.natAbs q.den)=Model.roundAt Fmt (q:ℝ):=by have d:Model.signedScaledRatToReal (decide (q<0)) q.num.natAbs q.den 0=(q:ℝ):=by unfold Model.signedScaledRatToReal Model.scaledRatToReal rw [Rat.cast_def] by_cases a:q<0 ·simp only [decide_eq_true a,ite_true] have:(q.num.natAbs:ℝ)= -(q.num:ℝ):=by rw [Nat.cast_natAbs,Int.cast_abs,abs_of_neg (by exact_mod_cast Rat.num_neg.mpr a)] simp [this];ring ·simp only [decide_eq_false a,Zx,ite_false] have:(q.num.natAbs:ℝ)=(q.num:ℝ):=by rw [Nat.cast_natAbs,Int.cast_abs,abs_of_nonneg (by exact_mod_cast Rat.num_nonneg.mpr (not_lt.mp a))] simp [this] have b:Model.isFinite (Xz Fmt (decide (q<0)) q.num.natAbs q.den)=true:=by unfold Xz apply Model.isFinite_roundRatScaled_of_abs_le_posMaxFinite Fmt _ _ _ _ (by decide) q.den_nz rw [d];exact le_trans c Ds refine ⟨b, ?_⟩ unfold Xz at b⊢ rw [Model.toReal_roundRatScaled_eq_roundAt Fmt _ _ _ _ (by decide) (by simpa using e) q.den_nz b,d] lemma Du (T E:Float) (r:ℝ) (n:T.isFinite=true→E.isFinite=true→ |r - vr T| +2^(-298:ℤ)≤vr E) (j:Fe false T E<0x100000000): Model.isFinite (ofW (Fe false T E).toUInt32)=true∧Yw (ofW (Fe false T E).toUInt32)≠0∧ Model.roundAt Fmt r=Yw (ofW (Fe false T E).toUInt32):=by obtain ⟨Tf,Ef⟩:=DM false T E j have o:=n Tf Ef have l:(0:ℝ)<2^(-298:ℤ):=by positivity have c:(2:ℝ)^(298:ℤ)*2^(-298:ℤ)=1:=by rw [←zpow_add₀ (by norm_num:(2:ℝ)≠0)];norm_num set S1:ℤ:= ⌊r*2^(298:ℤ)⌋with d have e:=Int.floor_le (r*2^(298:ℤ)) have b:=Int.lt_floor_add_one (r*2^(298:ℤ)) rw [←d] at e b have k:(S1:ℝ)*2^(-298:ℤ)≤r:=by have:=mul_le_mul_of_nonneg_right e l.le rwa [mul_assoc,c,mul_one] at this have f:r<((S1+1:ℤ):ℝ)*2^(-298:ℤ):=by have:=mul_lt_mul_of_pos_right b l rw [mul_assoc,c,mul_one] at this push_cast;exact this have m: ∀S:ℤ,(S:ℝ)*2^(-298:ℤ)≤r+2^(-298:ℤ)→ r≤(S:ℝ)*2^(-298:ℤ)+2^(-298:ℤ)→ |(S:ℝ)*2^(-298:ℤ) - vr T| ≤vr E:=by intro S p q have: |(S:ℝ)*2^(-298:ℤ) - r| ≤2^(-298:ℤ):=by rw [abs_le];constructor<;>linarith calc |(S:ℝ)*2^(-298:ℤ) - vr T| ≤ |(S:ℝ)*2^(-298:ℤ) - r| + |r - vr T| :=abs_sub_le _ _ _ _≤vr E:=by linarith push_cast at f obtain ⟨n1,w1⟩:=Ce false T E S1 false (fun _ _=>m S1 (by linarith) (by linarith)) j obtain ⟨n2,w2⟩:=Ce false T E (S1+1) false (fun _ _=>m (S1+1) (by push_cast;linarith) (by push_cast;linarith)) j simp only [act,Zx,ite_false,finishWord,n1,n2] at w1 w2 have g:ofW (Fe false T E).toUInt32=Yr Fmt (ofIntDyadic S1 (-298)):=by rw [w1,Do] have h:ofW (Fe false T E).toUInt32=Yr Fmt (ofIntDyadic (S1+1) (-298)):=by rw [w2,Do] obtain ⟨a,i⟩:=Dr T E j refine ⟨a,i, ?_⟩ have r1:=Model.toReal_roundDyadic_eq_roundAt Fmt (by decide) _ (by rw [←g];exact a) have r2:=Model.toReal_roundDyadic_eq_roundAt Fmt (by decide) _ (by rw [←h];exact a) have d1:(ofIntDyadic S1 (-298)).toReal=(S1:ℝ)*2^(-298:ℤ):=by rw [←FloatLib.Numerics.Dyadic.cast_toRat,toRat_ofIntDyadic];push_cast;ring have d2:(ofIntDyadic (S1+1) (-298)).toReal=((S1:ℝ)+1)*2^(-298:ℤ):=by rw [←FloatLib.Numerics.Dyadic.cast_toRat,toRat_ofIntDyadic];push_cast;ring rw [d1,←g] at r1;rw [d2,←h] at r2 apply le_antisymm ·rw [r2];exact Xi Fmt f.le ·rw [r1];exact Xi Fmt k lemma Dv (T E:Float) (q:ℚ) (i:T.isFinite=true→E.isFinite=true→ |(q:ℝ) - vr T| +2^(-298:ℤ)≤vr E) (d: |(q:ℝ)| ≤2^(127:ℤ)) (j:Fe false T E<0x100000000): (Fe false T E).toUInt32=roundRational q:=by obtain ⟨c,b,a⟩:=Du T E q i j have f:q≠0:=by intro k;rw [k] at a;simp only [Rat.cast_zero,Model.roundAt_zero] at a;exact b a.symm obtain ⟨g,e⟩:=Dt q f d have h:=Model.eq_of_toReal_eq_of_nonzero g c (by rw [e,a]) (by rw [e,a];exact b) unfold roundRational rw [h,Dp] def GA:Float:=Float.ofBits (UInt64.ofNat (975*2^52)) def GB:Float:=Float.ofBits (UInt64.ofNat (726*2^52)) def GC:Float:=Float.ofBits (UInt64.ofNat (1149*2^52)) lemma Dw:GA.isFinite=true∧vr GA=2^(-48:ℤ):=by have:=Bt 975 (by decide) (by decide) rw [show ((975:ℕ):ℤ) - 1023= -48 by norm_num] at this;exact this lemma Dx:GB.isFinite=true∧vr GB=2^(-297:ℤ):=by have:=Bt 726 (by decide) (by decide) rw [show ((726:ℕ):ℤ) - 1023= -297 by norm_num] at this;exact this lemma Dy:GC.isFinite=true∧vr GC=2^(126:ℤ):=by have:=Bt 1149 (by decide) (by decide) rw [show ((1149:ℕ):ℤ) - 1023=126 by norm_num] at this;exact this lemma Dz (w:Word):((rationalWord w:ℚ):ℝ)=FH w:=by unfold rationalWord FH rw [decodeD_toRat];push_cast;ring @[inline] def GD (d:Word):Float:= (UInt64.ofNat (2^75/mantOf d)).toFloat*Float.ofBits (UInt64.ofNat ((1097 - idxOf d)*2^52)) lemma D0 (N md s w:ℝ) (b:0by rw [h] at t;simp at t have w:=fracOf_toNat_lt d have hm:mantOf d=2^23+(fracOf d).toNat:=by unfold mantOf;simp [e] have z:idxOf d=(expOf d).toNat - 1:=by unfold idxOf;simp [e] have o:2^23≤ mantOf d:=by omega have p:mantOf d<2^24:=Qv d have x:idxOf d≤253:=by omega have q:2^75/mantOf d≤2^52:=Nat.div_le_of_le_mul (by omega) have f:2^75/mantOf d*mantOf d≤2^75:=Nat.div_mul_le_self _ _ have g:2^75<(2^75/mantOf d+1)*mantOf d:=by have:=Nat.lt_div_mul_add (a:=2^75) (b:=mantOf d) (by omega) rw [Nat.add_mul,one_mul];exact this have u:(Zw (2^75/mantOf d)).toNat=2^75/mantOf d:=by rw [Z1,Zy (by omega)] obtain ⟨uf,uv⟩:=Br (Zw (2^75/mantOf d)) (by rw [u];omega) rw [u] at uv obtain ⟨pf,pv⟩:=Bt (1097 - idxOf d) (by omega) (by omega) have r:((1097 - idxOf d:ℕ):ℤ) - 1023=74 - (idxOf d:ℤ):=by omega rw [r] at pv have c:(GD d).isFinite=true:=by unfold GD apply Ar _ _ uf pf rw [uv,pv,abs_of_nonneg (by positivity),abs_of_nonneg (by positivity)] have a1:((2^75/mantOf d:ℕ):ℝ)≤2^(52:ℤ):=by have:((2^75/mantOf d:ℕ):ℝ)≤((2^52:ℕ):ℝ):=by exact_mod_cast q rw [show ((2^52:ℕ):ℝ)=(2:ℝ)^(52:ℤ) by norm_num] at this;exact this have a2:(2:ℝ)^(74 - (idxOf d:ℤ))≤2^(74:ℤ):=zpow_le_zpow_right₀ (by norm_num) (by omega) calc ((2^75/mantOf d:ℕ):ℝ)*2^(74 - (idxOf d:ℤ))≤2^(52:ℤ)*2^(74:ℤ):= mul_le_mul a1 a2 (by positivity) (by positivity) _≤2^(200:ℤ):=by rw [As];exact zpow_le_zpow_right₀ (by norm_num) (by norm_num) have i:vr (GD d)=((2^75/mantOf d:ℕ):ℝ)*2^(74 - (idxOf d:ℤ)):=by unfold GD at c⊢ rw [AU _ _ uf pf c ((2^75/mantOf d:ℕ):ℤ) (74 - (idxOf d:ℤ)) (by rw [X5];omega) (by omega) (by rw [uv,pv,Y4]),uv,pv] have j:FH d=(mantOf d:ℝ)*2^(-75:ℤ)/2^(74 - (idxOf d:ℤ)):=by unfold FH sv simp only [v,Zx,ite_false,Y4] rw [mul_div_assoc,←zpow_sub₀ (by norm_num:(2:ℝ)≠0)] congr 2;ring have s:(0:ℝ)<2^(74 - (idxOf d:ℤ)):=by positivity have k:(2:ℝ)^23≤(mantOf d:ℝ):=by exact_mod_cast o have l:(mantOf d:ℝ)<2^24:=by exact_mod_cast p have m:((2^75/mantOf d:ℕ):ℝ)*(mantOf d:ℝ)≤2^75:=by exact_mod_cast f have n:(2:ℝ)^75<(((2^75/mantOf d:ℕ):ℝ)+1)*(mantOf d:ℝ):=by exact_mod_cast g refine ⟨c, ?_, ?_⟩ ·rw [j];positivity ·rw [i] exact D0 _ _ _ _ s k l m n j @[inline] def GE (x g d:Word) (ri:Float):UInt64:= if x&&&0x7FFFFFFF=0 then 0 else if 0rcases abs_cases e with ⟨k,i⟩ | ⟨k,i⟩<;> rw [j] at b c<;>rw [k] at d g<;>linarith lemma EB (x g d:Word) (v:(expOf x).toNat≠255) (w:(expOf g).toNat≠255) (h:GE x g d (GD d)<0x100000000): (GE x g d (GD d)).toUInt32=roundRational (rationalWord x*rationalWord g/rationalWord d):=by unfold GE at h⊢ by_cases j:x&&&0x7FFFFFFF=0 ·simp only [j,ite_true] rw [D8 x j,zero_mul,zero_div,D7];rfl simp only [j,ite_false] at h⊢ by_cases b:0simp have q:(sv g).natAbs=mantOf g:=by unfold sv;split<;>simp rw [Int.natAbs_mul,p,q] calc mantOf x*mantOf g<2^24*2^24:=Nat.mul_lt_mul'' (Qv x) (Qv g) _≤2^53:=by norm_num ·omega ·rw [xv,gv];unfold FH;push_cast rw [mul_mul_mul_comm,As];congr 2;ring set Q:ℝ:=FH x*FH g/FH d with c have e:(((rationalWord x*rationalWord g/rationalWord d:ℚ)):ℝ)=Q:=by push_cast;rw [Dz,Dz,Dz] have eF:=Bs _ _ Pfin rf Ffin rw [←n,o] at eF have eR: |FH x*FH g*vr (GD d) - Q| ≤1/2^51* |Q| :=by have:FH x*FH g*vr (GD d) - Q=FH x*FH g*(vr (GD d) - 1/FH d):=by rw [c];field_simp rw [this,abs_mul] have r: |Q| = |FH x*FH g| *(1/FH d):=by rw [c,div_eq_mul_one_div,abs_mul,abs_of_pos (by positivity:(0:ℝ)<1/FH d)] rw [r] have e51:(2:ℝ)^(-51:ℤ)=1/2^51:=by simp rw [e51] at rerr calc |FH x*FH g| * |vr (GD d) - 1/FH d| ≤ |FH x*FH g| *(1/FH d*(1/2^51)):= mul_le_mul_of_nonneg_left rerr (abs_nonneg _) _=1/2^51*(|FH x*FH g| *(1/FH d)):=by ring have e52:(2:ℝ)^(-52:ℤ)=1/2^52:=by simp set t:ℝ:=(2:ℝ)^(-1074:ℤ) with s set sm:ℝ:=(2:ℝ)^(-298:ℤ) with a have f:0≤t:=by positivity have u:0 ?_⟩ have a:=AE y rw [h] at a unfold Model.toModel Zc at a simp only [] at a rw [Qw he] at a split at a<;>simp [Zm] at a lemma ED (x:Float) (k:x.isFinite=true) (i:0≤vr x): Model.isZero (FB x)=true∨Model.signBit (FB x)=false:=by by_cases j:Model.isZero (FB x)=true ·exact Or.inl j right have f:Model.isFinite (FB x)=true:=by rw [AF];exact k obtain ⟨d,g⟩:=Model.exists_toDyadic?_of_isFinite f have b:=Model.significand_ne_zero_of_toDyadic?_some_of_isZero_eq_false g (by simpa using j) rw [←Model.sign_eq_signBit_of_toDyadic?_some g] cases c:d.negative with | false=>rfl | true=> have a:(0:ℝ)linarith lemma EJ (a b:ℝ) (e:0≤a) (d:0t+g j) a:ℚ)):ℝ)=(a:ℝ)+(l.map (fun j=>((g j:ℚ):ℝ))).sum:=by intro l induction l with | nil=>intro a;simp | cons y l ih=>intro a;rw [Zk,ih];push_cast;simp [Zq];ring lemma EQ (w:Word) (h:0k (UInt32.toNat_inj.mp (by simpa using m)) refine ⟨l,a,b,fun i o=> ?_,fun j p=> ?_,fw eps e,f⟩ ·rw [getElem!_pos x i (by omega)];exact fw _ ((Array.all_eq_true.mp c) i (by omega)) ·rw [getElem!_pos g j (by omega)];exact fw _ ((Array.all_eq_true.mp d) j (by omega)) def GH (x:Array Word) (o n j:Nat) (acc:Float):Float:= if jFL x[o+k]!)).foldl (· + ·) acc:=by intro d induction d with | zero=>intro j acc a;rw [GH,Qx (by omega)];simp [show n - j=0 by omega] | succ d ih=> intro j acc a rw [GH,Qw (by omega),ih (j+1) _ (by omega),BU j n (by omega)] rfl lemma EV (x:Array Word) (o n:Nat): ∀d j acc,n - j=d→ GI x o n j acc=((List.range' j (n - j)).map (fun k=>(FL x[o+k]!).abs)).foldl (· + ·) acc:=by intro d induction d with | zero=>intro j acc a;rw [GI,Qx (by omega)];simp [show n - j=0 by omega] | succ d ih=> intro j acc a rw [GI,Qw (by omega),ih (j+1) _ (by omega),BU j n (by omega)] rfl def GJ:Float:=Float.ofBits (UInt64.ofNat (823*2^52)) def GK:Float:=Float.ofBits (UInt64.ofNat (1152*2^52)) def GM:Float:=Float.ofBits (UInt64.ofNat (963*2^52)) lemma EW:GJ.isFinite=true∧vr GJ=2^(-200:ℤ):=by have:=Bt 823 (by decide) (by decide) rw [show ((823:ℕ):ℤ) - 1023= -200 by norm_num] at this;exact this lemma EX:GK.isFinite=true∧vr GK=2^(129:ℤ):=by have:=Bt 1152 (by decide) (by decide) rw [show ((1152:ℕ):ℤ) - 1023=129 by norm_num] at this;exact this lemma EY:GM.isFinite=true∧vr GM=2^(-60:ℤ):=by have:=Bt 963 (by decide) (by decide) rw [show ((963:ℕ):ℤ) - 1023= -60 by norm_num] at this;exact this lemma EZ (nR SA Sx Tf Af r m t:ℝ) (j:1≤nR) (k:nR≤2^20) (b:0≤SA) (x:0≤t) (l:t≤1/2^240) (d: |Sx| ≤SA) (o: |Tf - Sx| ≤nR*(1/2^51)*SA+3*nR*t) (p: |Af - SA| ≤nR*(1/2^51)*SA+3*nR*t) (c:0cases v<;> simp only [Zm,Bool.true_eq_false,or_self] at h<;> simp only [Wd]<;>(try split)<;>rfl lemma Eb (f g:Float) (h:(f - g).isFinite=true): f.isFinite=true∧g.isFinite=true:=by change (Yq (Wd Zs f.toModel.unpack g.toModel.unpack)).unpack.isFinite=true at h change f.toModel.unpack.isFinite=true∧g.toModel.unpack.isFinite=true generalize f.toModel.unpack=u at h⊢ generalize g.toModel.unpack=v at h⊢ cases a:u.isFinite<;>cases b:v.isFinite all_goals first | exact ⟨rfl,rfl⟩ | (rw [AK _ (Ea u v (by simp [a,b]))] at h;exact absurd h (by decide)) lemma Ec (x y:Float) (a:x.isFinite=true) (b:y.isFinite=true): FB (x - y)=Model.sub (FB x) (FB y):= ExecFloat.Binary.toModel_ofFloat_sub_of_isFinite x y a b lemma Ed (x y:Float) (h:(x - y).isFinite=true): x.isFinite=true∧y.isFinite=true∧ |vr (x - y) - (vr x - vr y)| ≤2^(-52:ℤ)* |vr (x - y)| +2^(-1074:ℤ):=by obtain ⟨a,b⟩:=Eb x y h refine ⟨a,b, ?_⟩ have c:vr (x - y)=Model.roundAt FloatFormat.binary64 (vr x - vr y):=by unfold vr rw [Ec x y a b] apply Model.toReal_sub_eq_roundAt _ _ (by decide) (by rw [AF];exact a) (by rw [AF];exact b) rw [←Ec x y a b,AF];exact h have he:=Xp FloatFormat.binary64 (vr x - vr y) rw [←c] at he exact AQ _ _ he def GN (x:Array Word) (o n:Nat) (m:Float) (j:Nat) (acc:Float):Float:= if j(FL x[o+k]! - m)*(FL x[o+k]! - m))).foldl (· + ·) acc:=by intro d induction d with | zero=>intro j acc a;rw [GN,Qx (by omega)];simp [show n - j=0 by omega] | succ d ih=> intro j acc a rw [GN,Qw (by omega),ih (j+1) _ (by omega),BU j n (by omega)] rfl set_option maxHeartbeats 1000000 in lemma Eg (a m s q t u:ℝ) (f:0≤t) (g:t≤1) (h:t*2^250≤u) (r: |s - (a - m)| ≤1/2^52* |s| +t) (v: |q - s*s| ≤1/2^52* |q| +t) (l: |s| ≤2^130): |q - (a - m)^2| ≤1/2^49*(a - m)^2+u:=by set c:=a - m with w obtain ⟨x,y⟩:=abs_le.mp r obtain ⟨z,A⟩:=abs_le.mp v have b:=abs_nonneg c have i:=abs_nonneg (s - c) have B: |s| ≤ |c| + |s - c| :=by have:=abs_sub_abs_le_abs_sub s c;linarith have C: |c| ≤ |s| + |s - c| :=by have:=abs_sub_abs_le_abs_sub c s;rw [abs_sub_comm c s] at this;linarith have D: |s - c| ≤2*(1/2^52)* |c| +2*t:=by linarith have E: |c| ≤2^131:=by linarith have N: |s| + |c| ≤2* |c| + |s - c| :=by linarith have F: |s*s - c^2| ≤ |s - c| *(|s| + |c|):=by rw [show s*s - c^2=(s - c)*(s+c) by ring,abs_mul] exact mul_le_mul_of_nonneg_left (abs_add_le s c) i have G: |s - c| *(|s| + |c|)≤(2*(1/2^52)* |c| +2*t)*(2* |c| +(2*(1/2^52)* |c| +2*t)):= mul_le_mul D (by linarith) (by positivity) (by positivity) have j:c^2= |c| * |c| :=by rw [←sq_abs];ring have H: |c| *t≤2^131*t:=mul_le_mul_of_nonneg_right E f have I:t*t≤t:=mul_le_of_le_one_left f g have J: |s*s - c^2| ≤4*(1/2^52)*(1+1/2^50)*c^2+5*(2^131*t)+4*t:=by have n:0≤ |c| * |c| :=mul_nonneg b b calc |s*s - c^2| ≤ |s - c| *(|s| + |c|):=F _≤(2*(1/2^52)* |c| +2*t)*(2* |c| +(2*(1/2^52)* |c| +2*t)):=G _=4*(1/2^52)*(1+1/2^52)*(|c| * |c|)+(4+8*(1/2^52))*(|c| *t)+4*(t*t):=by ring _≤4*(1/2^52)*(1+1/2^50)*c^2+5*(2^131*t)+4*t:=by rw [←j];linarith [sq_nonneg c,H,I,f] have d:0≤ s*s:=mul_self_nonneg s have K: |q| ≤ s*s+ |q - s*s| :=by have:=abs_sub_abs_le_abs_sub q (s*s);rw [abs_of_nonneg d] at this;linarith have L: |q - s*s| *(1 - 1/2^52)≤1/2^52*(s*s)+t:=by linarith have O: |q - s*s| ≤1/2^52*(1+1/2^50)*(s*s)+2*t:=by have P:=abs_nonneg (q - s*s);linarith have e:s*s≤c^2+ |s*s - c^2| :=by have:=le_abs_self (s*s - c^2);linarith have o: |q - c^2| ≤ |q - s*s| + |s*s - c^2| :=by have:=abs_sub_le q (s*s) (c^2);linarith have p:0≤c^2:=sq_nonneg c have k:=abs_nonneg (s*s - c^2) have Q: |q - s*s| ≤1/2^52*(1+1/2^50)*(c^2+ |s*s - c^2|)+2*t:=by have:=mul_le_mul_of_nonneg_left e (by positivity:(0:ℝ)≤1/2^52*(1+1/2^50));linarith have M:2^131*t*2^250≤2^131*u:=by calc (2:ℝ)^131*t*2^250=2^131*(t*2^250):=by ring _≤2^131*u:=mul_le_mul_of_nonneg_left h (by positivity) linarith @[inline] def GO (x:Array Word) (o n:Nat) (eps:Word) (mu M:Float):UInt64:= let v:=GN x o n mu 0 0*GF n+FL eps if v.absrcases abs_cases M with ⟨hm,_⟩ | ⟨hm,_⟩<;> rw [b] at a1 a2<;>rw [hm] at m1 m2<;>linarith lemma Ei (f:Nat→ℝ): ∀l:List Nat, |(l.map f).sum| ≤(l.map (fun j=> |f j|)).sum:=by intro l induction l with | nil=>simp | cons y l ih=>simp only [Zr,Zq];exact le_trans (abs_add_le _ _) (by linarith) lemma Ej (f:Nat→ℝ) (a: ∀j,0≤f j): ∀l:List Nat,0≤(l.map f).sum:=by intro l;induction l with | nil=>simp | cons y l ih=>simp only [Zr,Zq];linarith [a y] lemma Ek (n:Nat) (x:Array Word) (r:Nat): ((rowMean n x r:ℚ):ℝ)=((Qz n).map (fun j=>FH x[r*n+j]!)).sum/n:=by unfold rowMean push_cast rw [EP] simp only [Rat.cast_zero,zero_add] congr 1;congr 1 apply Zn;intro j _;rw [Dz] lemma El (x:Array Word) (r n:Nat) (l:0FL x[r*n+k]!) with a set la:=(List.range' 0 (n - 0)).map (fun k=>(FL x[r*n+k]!).abs) with b have w:GH x (r*n) n 0 0=lt.foldl (· + ·) 0:=EU x (r*n) n n 0 0 (by simp) have q:GI x (r*n) n 0 0=la.foldl (· + ·) 0:=EV x (r*n) n n 0 0 (by simp) obtain ⟨_,_,terr⟩:=BA lt 0 (by rw [←w];exact Tfin) obtain ⟨_,_,aerr⟩:=BA la 0 (by rw [←q];exact Abfin) have tg:=B6 lt 0 (by rw [←w];exact Tfin) (by simp [a];omega) have ag:=B6 la 0 (by rw [←q];exact Abfin) (by simp [b];omega) have s: ∀k,k(A8 _ (u k D)).2 set Sx:=((Qz n).map (fun j=>FH x[r*n+j]!)).sum with z set SA:=((Qz n).map (fun j=> |FH x[r*n+j]!|)).sum with f have e1:(lt.map vr).sum=Sx:=by rw [a,EO,Ze,z];congr 1 apply Zn;intro j g;exact s j (List.mem_range.mp g) have e2:(lt.map (fun y=> |vr y|)).sum=SA:=by rw [a,EO,Ze,f];congr 1 apply Zn;intro j g;simp only [Xa];rw [s j (List.mem_range.mp g)] have e3:(la.map vr).sum=SA:=by rw [b,EO,Ze,f];congr 1 apply Zn;intro j g;simp only [Xa];rw [(Bo _).2,s j (List.mem_range.mp g)] have e4:(la.map (fun y=> |vr y|)).sum=SA:=by rw [b,EO,Ze,f];congr 1 apply Zn;intro j g;simp only [Xa] rw [(Bo _).2,abs_abs,s j (List.mem_range.mp g)] have llt:lt.length=n:=by simp [a] have lla:la.length=n:=by simp [b] rw [e1,Cs.2,zero_add] at terr rw [e2,Cs.2,abs_zero,zero_add,llt] at tg rw [e3,Cs.2,zero_add] at aerr rw [e4,Cs.2,abs_zero,zero_add,lla] at ag have e51:(2:ℝ)^(-51:ℤ)=1/2^51:=by simp have e52:(2:ℝ)^(-52:ℤ)=1/2^52:=by simp rw [e51] at tg ag set t:ℝ:=(2:ℝ)^(-1074:ℤ) with A have h:0≤t:=by positivity have i:t≤1/2^240:=by have e:(1:ℝ)/2^240=2^(-240:ℤ):=by simp rw [A,e];exact zpow_le_zpow_right₀ (by norm_num) (by norm_num) have o:(1:ℝ)≤n:=by exact_mod_cast l have c:(n:ℝ)≤2^20:=by exact_mod_cast m.le have d:0≤SA:=Ej _ (fun j=>abs_nonneg _) _ have p: |Sx| ≤SA:=Ei _ _ obtain ⟨_,rpos,rerr⟩:=EI n l m rw [e51] at rerr have em:=Bs _ _ Tfin rfin AF rw [e52] at em have E:=EZ n SA Sx (vr (GH x (r*n) n 0 0)) (vr (GI x (r*n) n 0 0)) (vr (GF n)) (vr (GH x (r*n) n 0 0*GF n)) t o c d h i p (by rw [w];linarith) (by rw [q];linarith) rpos rerr em have eA1:=Bs _ _ Abfin c48fin A1fin have eM:=AR _ _ A1fin c2fin Mfin rw [Dw.2,e52] at eA1 rw [EW.2,e52] at eM have e48:(2:ℝ)^(-48:ℤ)=1/2^48:=by simp have e200:(2:ℝ)^(-200:ℤ)=1/2^200:=by simp rw [e48] at eA1;rw [e200] at eM have B: -(1/2^210)≤vr (GI x (r*n) n 0 0):=by rw [q] have:=(abs_le.mp aerr).1 have G:3*(n:ℝ)*t≤3*2^20*(1/2^240):= mul_le_mul (mul_le_mul_of_nonneg_left c (by norm_num)) i h (by positivity) have H:(n:ℝ)*(1/2^51)*SA≤SA:=by calc (n:ℝ)*(1/2^51)*SA≤1*SA:=mul_le_mul_of_nonneg_right (by linarith) d _=SA:=one_mul SA linarith have F:=Eh _ _ _ t h i B eA1 eM rw [Ek] refine ⟨by linarith,by linarith⟩ lemma Em (g:Nat→ℝ) (d:ℝ): ∀l:List Nat, (l.map (fun k=>(g k+d)^2)).sum=(l.map (fun k=>g k^2)).sum+2*d*(l.map g).sum+l.length*d^2:=by intro l;induction l with | nil=>simp | cons y l ih=>simp only [Zr,Zq,Y6,ih];push_cast;ring lemma En (f:Nat→ℝ) (c:ℝ): ∀l:List Nat, (l.map (fun k=>f k - c)).sum=(l.map f).sum - l.length*c:=by intro l;induction l with | nil=>simp | cons y l ih=>simp only [Zr,Zq,Y6,ih];push_cast;ring lemma Eo (f:Nat→ℝ) (m:ℝ) (n:Nat) (g:0(f k - m)^2)).sum= ((Qz n).map (fun k=>(f k - ((Qz n).map f).sum/n)^2)).sum+ n*(((Qz n).map f).sum/n - m)^2:=by set μ:=((Qz n).map f).sum/n with c have a:=Em (fun k=>f k - μ) (μ - m) (Qz n) have b:=En f μ (Qz n) simp only [X9] at a b have d:((Qz n).map f).sum - n*μ=0:=by rw [c];field_simp;ring have e:(fun k=>(f k - m)^2)=(fun k=>((fun k=>f k - μ) k+(μ - m))^2):=by funext k;ring rw [e,a,b,d];ring lemma Ep (w:Word) (h:(expOf w).toNat≠255): |FH w| <2^128:=by unfold FH have hm:=Qv w have d:idxOf w≤253:=idxOf_le w (fun b=>h (by rw [b];rfl)) have a: |(sv w:ℝ)| <2^24:=by have:(sv w).natAbs=mantOf w:=by unfold sv;split<;>simp rw [←Int.cast_abs,←Int.natCast_natAbs,this];exact_mod_cast hm rw [abs_mul,abs_of_pos (by positivity:(0:ℝ)<2^((idxOf w:ℤ) - 149))] have c:(2:ℝ)^((idxOf w:ℤ) - 149)≤2^(104:ℤ):=zpow_le_zpow_right₀ (by norm_num) (by omega) have e104:(2:ℝ)^(104:ℤ)=2^104:=by norm_num calc |(sv w:ℝ)| *2^((idxOf w:ℤ) - 149)≤ |(sv w:ℝ)| *2^(104:ℤ):= mul_le_mul_of_nonneg_left c (abs_nonneg _) _<2^24*2^(104:ℤ):=mul_lt_mul_of_pos_right a (by positivity) _=2^128:=by rw [e104];norm_num lemma Eq (g h:Nat→ℝ) (c u:ℝ): ∀l:List Nat,(∀k∈l, |g k - h k| ≤c*h k+u)→ |(l.map g).sum - (l.map h).sum| ≤c*(l.map h).sum+l.length*u:=by intro l;induction l with | nil=>intro _;simp | cons y l ih=> intro f simp only [Zr,Zq,Y6] have a:=f y (Xh ..) have b:=ih (fun k d=>f k (Xg _ d)) have e:g y+(l.map g).sum - (h y+(l.map h).sum)=(g y - h y)+((l.map g).sum - (l.map h).sum):=by ring rw [e];push_cast exact le_trans (abs_add_le _ _) (by linarith) lemma Er (g h:Nat→ℝ) (c u:ℝ): ∀l:List Nat,(∀k∈l, |g k - h k| ≤c*h k+u)→ (∀k∈l,0≤h k)→(l.map (fun k=> |g k|)).sum≤(1+c)*(l.map h).sum+l.length*u:=by intro l;induction l with | nil=>intro _ _;simp | cons y l ih=> intro e f simp only [Zr,Zq,Y6] have a:=e y (Xh ..) have a0:=f y (Xh ..) have b:=ih (fun k d=>e k (Xg _ d)) (fun k d=>f k (Xg _ d)) have i: |g y| ≤h y+ |g y - h y| :=by have:=abs_sub_abs_le_abs_sub (g y) (h y);rw [abs_of_nonneg a0] at this;linarith push_cast;linarith set_option maxHeartbeats 2000000 in lemma Es (x:Array Word) (r n:Nat) (mu:Float) (o:n<2^20) (e: ∀j,j(FH x[r*n+k]! - vr mu)^2)).sum| ≤ ((n:ℝ)+5)*(1/2^51)*((Qz n).map (fun k=>(FH x[r*n+k]! - vr mu)^2)).sum+ 3*n*(2:ℝ)^(-600:ℤ):=by set u:ℝ:=(2:ℝ)^(-600:ℤ) with p set t:ℝ:=(2:ℝ)^(-1074:ℤ) with f have q:0≤t:=by positivity have G:0≤u:=by positivity have s:t≤1:=by rw [f];exact zpow_le_one_of_nonpos₀ (by norm_num) (by norm_num) have v:t*2^250≤u:=by rw [f,p,show (2:ℝ)^250=2^(250:ℤ) by norm_num,As] exact zpow_le_zpow_right₀ (by norm_num) (by norm_num) have B:t≤u:=by linarith set lq:=(List.range' 0 (n - 0)).map (fun k=>(FL x[r*n+k]! - mu)*(FL x[r*n+k]! - mu)) with a have d:GN x (r*n) n mu 0 0=lq.foldl (· + ·) 0:=Ee x (r*n) n mu n 0 0 (by simp) obtain ⟨_,lfin,lerr⟩:=BA lq 0 (by rw [←d];exact A) have lg:=B6 lq 0 (by rw [←d];exact A) (by simp [a];omega) have llen:lq.length=n:=by simp [a] set F:Nat→ℝ:=fun k=>vr ((FL x[r*n+k]! - mu)*(FL x[r*n+k]! - mu)) with I set H:Nat→ℝ:=fun k=>(FH x[r*n+k]! - vr mu)^2 with J have e52:(2:ℝ)^(-52:ℤ)=1/2^52:=by simp have e51:(2:ℝ)^(-51:ℤ)=1/2^51:=by simp -- each centred square have b: ∀k∈Qz n, |F k - H k| ≤1/2^49*H k+u:=by intro k m have g:=List.mem_range.mp m have h:(FL x[r*n+k]! - mu)*(FL x[r*n+k]! - mu)∈lq:=by rw [a,EO];exact List.mem_map.mpr ⟨k,m,rfl⟩ have tf:=lfin _ h obtain ⟨sf,_⟩:=AO _ _ tf obtain ⟨_,_,es⟩:=Ed _ _ sf have eq:=Bs _ _ sf sf tf obtain ⟨_,xv⟩:=A8 _ (e k g) rw [xv,e52] at es rw [e52] at eq have K:=Ep _ (e k g) have w: |vr (FL x[r*n+k]! - mu)| ≤2^130:=by obtain ⟨s1,s2⟩:=abs_le.mp es have i:(2:ℝ)^(129:ℤ)=2^129:=by norm_num rw [i] at hm rcases abs_cases (vr (FL x[r*n+k]! - mu)) with ⟨C,_⟩ | ⟨C,_⟩<;>rw [C] at s1 s2⊢ <;> (obtain ⟨a1,a2⟩:=abs_lt.mp K;obtain ⟨m1,m2⟩:=abs_lt.mp hm;linarith) exact Eg _ _ _ _ t u q s v es eq w have z: ∀k∈Qz n,0≤H k:=fun k _=>sq_nonneg _ have l:=Eq F H (1/2^49) u (Qz n) b have c:=Er F H (1/2^49) u (Qz n) b z simp only [X9] at l c have e1:(lq.map vr).sum=((Qz n).map F).sum:=by rw [a,EO,Ze];rfl have e2:(lq.map (fun y=> |vr y|)).sum=((Qz n).map (fun k=> |F k|)).sum:=by rw [a,EO,Ze];rfl rw [e1,Cs.2,zero_add] at lerr rw [e2,Cs.2,abs_zero,zero_add,llen,e51] at lg rw [d] set SH:=((Qz n).map H).sum with L have D:0≤SH:=Ej _ (fun k=>sq_nonneg _) _ have M:(0:ℝ)≤n:=by positivity have E:(n:ℝ)≤2^20:=by exact_mod_cast o.le have N:(n:ℝ)*(1/2^51)*((Qz n).map (fun k=> |F k|)).sum≤ (n:ℝ)*(1/2^51)*((1+1/2^49)*SH+n*u):= mul_le_mul_of_nonneg_left c (by positivity) have m:(n:ℝ)*(1/2^51)≤1:=by linarith have O:(n:ℝ)*(1/2^51)*(n*u)≤(n:ℝ)*u:=by have:=mul_le_mul_of_nonneg_right m (by positivity:(0:ℝ)≤n*u);linarith have P:(n:ℝ)*(1/2^51)*((1+1/2^49)*SH)≤((n:ℝ)+1)*(1/2^51)*SH:=by nlinarith have Q:3*(n:ℝ)*t≤(n:ℝ)*u:=by nlinarith have:=abs_sub_le (vr (lq.foldl (· + ·) 0)) ((Qz n).map F).sum SH linarith lemma Et (q V W d2 Mv a b k t u:ℝ) (x:0(FH x[r*n+j]! - (μ:ℝ))^2)).sum/n:=by unfold rowVariance push_cast rw [EP] simp only [Rat.cast_zero,zero_add] congr 1;congr 1 apply Zn;intro j _;push_cast;rw [Dz] set_option maxHeartbeats 3000000 in lemma Ev (x:Array Word) (r n:Nat) (eps:Word) (mu M:Float) (μ:ℚ) (y:0(FH x[r*n+k]! - vr mu)^2)).sum= ((Qz n).map (fun k=>(FH x[r*n+k]! - (μ:ℝ))^2)).sum+n*((μ:ℝ) - vr mu)^2) (h:GO x (r*n) n eps mu M<0x100000000): (GO x (r*n) n eps mu M).toUInt32=sqrtRational (rowVariance n x r μ+rationalWord eps):=by unfold GO at h⊢ simp only [] at h⊢ set v:=GN x (r*n) n mu 0 0*GF n+FL eps with ap by_cases c2:v.abs(FH x[r*n+k]! - vr mu)^2)).sum with ak have B:0≤Sm:=Ej _ (fun k=>sq_nonneg _) _ obtain ⟨_,rpos,rerr⟩:=EI n y i rw [e51] at rerr have eP:=Bs _ _ Qfin rnfin Pfin have eV:=AR _ _ Pfin Fi vfin obtain ⟨_,ev⟩:=A8 eps P rw [e52] at eP eV rw [ev] at eV have f:0(FH x[r*n+j]! - (μ:ℝ))^2)).sum/n+FH eps:=by rw [W];push_cast;rw [Eu,Dz] set qR:ℝ:=((q:ℚ):ℝ) with C have w:(0:ℝ)(FH x[r*n+j]! - (μ:ℝ))^2) (fun k=>sq_nonneg _) (Qz n)) w.le;linarith have X:0(FH x[r*n+j]! - (μ:ℝ))^2) (fun k=>sq_nonneg _) (Qz n)) w.le;linarith have g:k1≤1/2^29:=by rw [d];linarith have F:0≤k1:=by rw [d];positivity have ao:u≤1/2^200:=by rw [p,show (1:ℝ)/2^200=2^(-200:ℤ) by simp];exact zpow_le_zpow_right₀ (by norm_num) (by norm_num) have G:0≤vr v:=by obtain ⟨a1,_⟩:=abs_le.mp D have:qR*k1≤qR*(1/2^29):=mul_le_mul_of_nonneg_left g a.le linarith obtain ⟨dfin,derr⟩:=EF v vfin G rw [e52] at derr have c:0FH x[r*n+j]!) (GH x (r*n) n 0 0*GF n |>vr) n a rw [Ek];exact k set_option maxHeartbeats 2000000 in lemma Ex (c s G p1 r vd p2 t:ℝ) (i:1/2^126≤vd) (b:0by rw [h] at b;exact absurd b (by decide) unfold FH sv mantOf simp only [c,Zx,ite_false,a,ite_false,Y4] have d:(2:ℝ)^(-149:ℤ)≤2^((idxOf w:ℤ) - 149):=zpow_le_zpow_right₀ (by norm_num) (by omega) have hm:(2:ℝ)^23≤((2^23+(fracOf w).toNat:ℕ):ℝ):=by push_cast;linarith [(Zg (α:=ℝ) (fracOf w).toNat)] have e:(1:ℝ)/2^126=2^23*2^(-149:ℤ):=by rw [show (2:ℝ)^23=2^(23:ℤ) by norm_num,As];simp rw [e];exact mul_le_mul hm d (by positivity) (by positivity) set_option maxHeartbeats 4000000 in lemma E2 (x g b d:Word) (mu M Mr:Float) (μ:ℚ) (C:(expOf x).toNat≠255) (z:(expOf g).toNat≠255) (D:(expOf b).toNat≠255) (a: |vr mu - (μ:ℝ)| ≤vr M) (m:Mr.isFinite=true→vr M*(1/FH d)*(1+1/2^40)≤vr Mr) (h:GR x g b d mu Mr (GD d)<0x100000000): (GR x g b d mu Mr (GD d)).toUInt32= roundRational ((rationalWord x - μ)*rationalWord g/rationalWord d+rationalWord b):=by unfold GR at h⊢ by_cases c:0key) _ h have K: |vr F| <2^(126:ℤ):=Flt have: |(q:ℝ)| ≤ |vr F| + |(q:ℝ) - vr F| :=by have:=abs_sub_abs_le_abs_sub (q:ℝ) (vr F);linarith have B:(2:ℝ)^(126:ℤ)*2=2^(127:ℤ):=by rw [show (2:ℝ)^(127:ℤ)=2^(126:ℤ)*2^(1:ℤ) by rw [As];norm_num];norm_num have L:(0:ℝ)<2^(-298:ℤ):=by positivity linarith [abs_nonneg (vr E),le_abs_self (vr E)] def GS (x:Array Word) (o index:Nat):Nat→Nat→Nat | 0,m=>m | count+1,m=>GS x o (index+1) count (min m (idxOf x[o+index]!)) def GT (x:Array Word) (o m index:Nat):Nat→Int | 0=>0 | count+1=>Ff (signOf x[o+index]!) (mantOf x[o+index]! <<<(idxOf x[o+index]! - m))+ GT x o m (index+1) count def GU (n:Nat) (x:Array Word) (r:Nat):ℚ:= let m:=GS x (r*n) 0 n 1024 (GT x (r*n) m 0 n:ℚ)*2^((m:ℤ) - 149)/n lemma E3 (x:Array Word) (o:Nat): ∀count index m0,GS x o index count m0≤ m0∧ ∀k,index≤k→k< index+count→GS x o index count m0≤ idxOf x[o+k]! :=by intro count induction count with | zero=>intro index m0;exact ⟨le_rfl,fun k a b=>by omega⟩ | succ c ih=> intro index m0 obtain ⟨a,b⟩:=ih (index+1) (min m0 (idxOf x[o+index]!)) simp only [GS] refine ⟨le_trans a (min_le_left _ _),fun k d e=> ?_⟩ by_cases f:k=index ·subst f;exact le_trans a (min_le_right _ _) ·exact b k (by omega) (by omega) lemma E4 (x:Array Word) (o m:Nat): ∀count index (acc:ℚ), (∀k,index≤k→k< index+count→m≤ idxOf x[o+k]!)→ (List.range' index count).foldl (fun t j=>t+rationalWord x[o+j]!) acc= acc+(GT x o m index count:ℚ)*2^((m:ℤ) - 149):=by intro count induction count with | zero=>intro index acc _;simp [GT] | succ c ih=> intro index acc h have hm:=h index le_rfl (by omega) rw [List.range'_succ,Zk,ih (index+1) _ (fun k b d=>h k (by omega) (by omega))] simp only [GT] unfold rationalWord rw [decodeD_toRat,DD,Zp] have a:(2:ℚ)^((idxOf x[o+index]! :ℤ) - 149)= (2:ℚ)^(idxOf x[o+index]! - m)*2^((m:ℤ) - 149):=by rw [←zpow_natCast,←zpow_add₀ two_ne_zero];congr 1;push_cast [Nat.cast_sub hm];ring rw [a] unfold sv cases signOf x[o+index]! <;>simp<;>push_cast<;>ring lemma E5:GU=rowMean:=by funext n x r unfold GU rowMean simp only [] obtain ⟨_,hm⟩:=E3 x (r*n) n 0 1024 rw [Wh,E4 x (r*n) _ n 0 0 (fun k _ a=>hm k (Nat.zero_le _) a),zero_add] lemma E6 (x:Array Word) (r n:Nat) (eps:Word) (a:0b _ (by nlinarith)) c d ?_ ?_ ?_ g ·rw [e,h];norm_num ·rw [e];norm_num ·rw [e];simp ·rfl def GW (rows n:Nat) (eps:Word) (x g:Array Word):Array Word:= if stableNormDomain rows n eps x g&&n<1048576 then let dw:=Array.ofFn (n:=rows) fun r=>GV x r.val n eps let ri:=Array.ofFn (n:=rows) fun r=>GD dw[r.val]! x.mapIdx fun q _=> let f:=GE x[q]! g[q % n]! dw[q/n]! ri[q/n]! if f<0x100000000 then f.toUInt32 else roundRational (rationalWord x[q]! *rationalWord g[q % n]! /rationalWord dw[q/n]!) else rmsnormSpec rows n eps x g lemma E9:GW=rmsnormSpec:=by funext rows n eps x g unfold GW split ·rename_i k simp only [Yh,decide_eq_true_eq] at k obtain ⟨a,m⟩:=k obtain ⟨l,d,o,b,e,f,h⟩:=ES rows n eps x g a rw [show rmsnormSpec rows n eps x g=rmsnormStable rows n eps x g by unfold rmsnormSpec rmsnormWith;rw [Qw a]] unfold rmsnormStable simp only [] apply Array.ext ·simp [d] intro i t p simp only [Array.getElem_mapIdx,Yk] obtain ⟨q,r⟩: ∃q:Fin (rows*n),q.val=i:=⟨⟨i,by simpa using p⟩,rfl⟩ subst r have c:q.val/nGP x (r.val*n) n eps let dw:=Array.ofFn (n:=rows) fun r=> if st[r.val]!.d<0x100000000 then st[r.val]!.d.toUInt32 else sqrtRational (rowVariance n x r.val (rowMean n x r.val)+rationalWord eps) let ri:=Array.ofFn (n:=rows) fun r=>GD dw[r.val]! let mr:=Array.ofFn (n:=rows) fun r=>st[r.val]!.M*ri[r.val]! *GQ x.mapIdx fun q _=> let f:=if st[q/n]!.d<0x100000000 then GR x[q]! g[q % n]! b[q % n]! dw[q/n]! st[q/n]!.mu mr[q/n]! ri[q/n]! else 0x100000000 if f<0x100000000 then f.toUInt32 else roundRational ((rationalWord x[q]! - GU n x (q/n))*rationalWord g[q % n]! / rationalWord dw[q/n]! +rationalWord b[q % n]!) else layernormSpec rows n eps x g b lemma FA:GX=layernormSpec:=by funext rows n eps x g b unfold GX simp only [E5] split ·rename_i G simp only [Yh,beq_iff_eq,decide_eq_true_eq] at G obtain ⟨⟨⟨h,t⟩,k⟩,I⟩:=G obtain ⟨r,u,J,l,v,w,y⟩:=ES rows n eps x g h have z: ∀j,jH (UInt32.toNat_inj.mp (by simpa using L)) rw [show layernormSpec rows n eps x g b=layernormStable rows n eps x g b by unfold layernormSpec layernormWith;rw [Qw (by rw [h,k];simp [t])]] unfold layernormStable simp only [] apply Array.ext ·simp [u] intro i O M simp only [Array.getElem_mapIdx,Yk] obtain ⟨q,N⟩: ∃q:Fin (rows*n),q.val=i:=⟨⟨i,by simpa using M⟩,rfl⟩ subst N have A:q.val/nl _ (by nlinarith) have m: ∀e:(GP x (q.val/n*n) n eps).d<0x100000000, (GP x (q.val/n*n) n eps).d.toUInt32= sqrtRational (rowVariance n x (q.val/n) (rowMean n x (q.val/n))+rationalWord eps):= fun e=>Ew x (q.val/n) n eps r (by omega) c w y e have B:(if (GP x (q.val/n*n) n eps).d<0x100000000 then (GP x (q.val/n*n) n eps).d.toUInt32 else sqrtRational (rowVariance n x (q.val/n) (rowMean n x (q.val/n))+rationalWord eps))= sqrtRational (rowVariance n x (q.val/n) (rowMean n x (q.val/n))+rationalWord eps):=by split ·rename_i e;exact m e ·rfl simp only [ER _ _ _ A,Fin.val_mk,B] by_cases e:(GP x (q.val/n*n) n eps).d<0x100000000 ·simp only [e,ite_true] split ·rename_i s obtain ⟨f,o⟩:=E6 x (q.val/n) n eps r (by omega) c e set dd:=sqrtRational (rowVariance n x (q.val/n) (rowMean n x (q.val/n))+rationalWord eps) rw [E2 _ _ _ _ _ _ _ _ (l _ q.isLt) (v _ (Nat.mod_lt _ r)) (z _ (Nat.mod_lt _ r)) f ?_ s] intro C unfold GR at s by_cases a:0