import ContractExact section open ExactRuntime FloatLib.Floats.Formats.BinaryInterchange FloatLib.Floats open Float.Model.UnpackedFloat namespace DenseResearch set_option maxRecDepth 4096 lemma reluPacked (e : BitVec 8) (m : BitVec 23) (h : e ≠ 255#8) : reluW (UInt32.ofNat ((1#1 ++ e ++ m).toNat)) = 0 := by let w := UInt32.ofNat ((1#1 ++ e ++ m).toNat) have hs : w &&& 0x80000000 ≠ 0 := by intro bad have hb := congrArg UInt32.toBitVec bad simp only [w, UInt32.toBitVec_and, UInt32.toBitVec_ofNat', UInt32.toBitVec_ofNat, BitVec.ofNat_toNat] at hb have hp := congrArg (fun v : BitVec 32 => v.getLsbD 31) hb simp only [BitVec.getLsbD_and, BitVec.getLsbD_setWidth] at hp simp only [BitVec.getLsbD_append] at hp norm_num at hp have he : expOf w ≠ 255 := by intro bad have hb := congrArg UInt32.toBitVec bad simp only [w, expOf, UInt32.toBitVec_and, UInt32.toBitVec_shiftRight, UInt32.toBitVec_ofNat', UInt32.toBitVec_ofNat, BitVec.ofNat_toNat] at hb have hp := congrArg (fun v : BitVec 32 => v.setWidth 8) hb simp [BitVec.setWidth_and, BitVec.setWidth_ushiftRight_eq_extractLsb] at hp rw [BitVec.extractLsb'_append_eq_of_le (by decide), Nat.sub_self, BitVec.extractLsb'_append_eq_right] at hp change e &&& BitVec.allOnes 8 = BitVec.allOnes 8 at hp rw [BitVec.and_allOnes] at hp exact h hp change reluW w = 0 simp [reluW, hs, he] lemma reluFinite (m:Nat) (e:Int) (h : 0 < m): reluW (toWord (Model.ofModel Fmt (.finite .negative m e h)))=0 := by unfold Model.ofModel simp only [Float.Model.UnpackedFloat.pack] split · rfl · rename_i he change ¬ 256 ≤ (e+127+23).toNat+1 at he split · apply reluPacked change BitVec.ofNat 8 (e+127+23).toNat ≠ 255#8 have hh : (e+127+23).toNat < 255 := by omega intro hbad have hb := congrArg BitVec.toNat hbad simp [BitVec.toNat_ofNat, Nat.mod_eq_of_lt (by omega : (e+127+23).toNat < 2^8)] at hb omega · exact reluPacked 0 _ (by decide) lemma reluRoundNegative (m : Nat) (e : Int) : reluW (toWord (Model.roundDyadic Fmt ⟨true,m,e⟩)) = 0 := by unfold Model.roundDyadic rw [if_pos (by decide : Fmt.isIEEE = true)] unfold Model.ieeeRoundDyadic Float.Model.UnpackedFloat.round Float.Model.UnpackedFloat.roundWithAccuracy dsimp only [Model.modelSign] split · rfl · exact reluFinite _ _ _ lemma reluFinishNegative (S : Int) (e : Int) (nz : Bool) (h : S < 0) : act true (finishWord S e nz) = 0 := by simp only [act, Bool.true_eq, ite_true, finishWord, ne_of_lt h, ite_false] unfold ofIntDyadic simp only [h, decide_true] exact reluRoundNegative _ _ end DenseResearch end 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 section open FloatLib.Numerics end section open Float.Model Float.Model.UnpackedFloat 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 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] 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 abbrev negCheck (T E : Float) : Prop := T.toBits >>> 63 = 1 ∧ (1:UInt64) ≤ ((T.toBits >>> 52) &&& 0x7ff) ∧ ((T.toBits >>> 52) &&& 0x7ff) ≤ 2046 ∧ E.abs < T.abs @[inline] def FeR (relu : Bool) (T E : Float) : UInt64 := let r := Fe relu T E if r < 0x100000000 then r else if relu = true ∧ negCheck T E then 0 else r 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 => if mantOf (fa index) * mantOf (fb index) = 0 then Fg fa fb (index + 1) count m else 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 => let p := mantOf (fa index) * mantOf (fb index) if p = 0 then Fh fa fb m (index + 1) count else Ff (Bool.xor (signOf (fa index)) (signOf (fb index))) (p <<< (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 FFused (X:Array UInt32) (xo n o st k:Nat) (A:FloatArray) (s:Float) (xc:FloatArray) (IX:Array UInt32):(FloatArray×Float)×FC:= if k rw [FFused,FW,FX] simp only [h,ite_true,z] exact ih | case2 k A s xc IX h v z ih=> rw [FFused,FW,FX] simp only [h,ite_true,z,ite_false] exact ih | case3 k A s xc IX h=> rw [FFused,FW,FX] simp only [h,ite_false] 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 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 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 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 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 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 → mantOf (fa k) * mantOf (fb k) ≠ 0 → 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 simp only [Fg] split · rename_i hz obtain ⟨a, b⟩ := ih (index + 1) m0 refine ⟨a, fun k d e hk => ?_⟩ by_cases f : k = index · subst f; exact (hk hz).elim · exact b k (by omega) (by omega) hk · obtain ⟨a, b⟩ := ih (index + 1) (min m0 (idxOf (fa index) + idxOf (fb index))) refine ⟨le_trans a (min_le_left _ _), fun k d e hk => ?_⟩ by_cases f : k = index · subst f; exact le_trans a (min_le_right _ _) · exact b k (by omega) (by omega) hk 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 ∧ (mantOf (fa k) * mantOf (fb k) ≠ 0 → 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) have tail := ih (index + 1) (fun k e f => h k (by omega) (by omega)) simp only [Fh, dsum] split_ifs with hz · rw [tail, a, b] have hv : sv (fa index) * sv (fb index) = 0 := by rcases Nat.mul_eq_zero.mp hz with ha | hb · simp [sv, ha] · simp [sv, hb] simp [hv] · rw [add_mul, tail, a, b] congr 1 rw [DD, Nat.shiftLeft_eq] 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 hz)] 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 negCheck_sound (T E : Float) (h : negCheck T E) : T.isFinite = true ∧ E.isFinite = true ∧ vr T < 0 ∧ vr E < -vr T := by obtain ⟨hs,lo,hi,hE⟩ := h have lo' : 1 ≤ ((T.toBits >>> 52) &&& 0x7ff).toNat := UInt64.le_iff_toNat_le.mp lo have hi' : ((T.toBits >>> 52) &&& 0x7ff).toNat ≤ 2046 := UInt64.le_iff_toNat_le.mp hi obtain ⟨tf,tv⟩ := CQ T lo' hi' have hs' : T.toBits.toNat / 2^63 = 1 := by have hp := congrArg UInt64.toNat hs simpa [UInt64.toNat_shiftRight, Nat.shiftRight_eq_div_pow] using hp have ht : vr T < 0 := by rw [tv,hs'] simp only [one_ne_zero, ite_false, neg_one_mul] apply mul_neg_of_neg_of_pos · apply neg_neg_of_pos positivity · positivity obtain ⟨ef,eh⟩ := B3 E T.abs hE ((Bo T).1.trans tf) rw [(Bo T).2, abs_of_neg ht] at eh exact ⟨tf,ef,ht,(le_abs_self (vr E)).trans_lt eh⟩ lemma DNneg (n : Nat) (xw ww : Nat → UInt32) (bw : UInt32) (T E : Float) (o : T.isFinite = true → E.isFinite = true → (∀ t, t < n → (expOf (xw t)).toNat ≠ 255 ∧ (expOf (ww t)).toNat ≠ 255) ∧ (expOf bw).toNat ≠ 255 ∧ |((List.range n).map (fun t => FH (xw t)*FH (ww t))).sum+FH bw - vr T| ≤ vr E) (h : negCheck T E) : act true (dotOf (n+1) (fun t => if t < n then xw t else oneW) (fun t => if t < n then ww t else bw)) = 0 := by obtain ⟨tf,ef,ht,he⟩ := negCheck_sound T E h obtain ⟨ex,eb,bound⟩ := o tf ef set A := Array.ofFn (n:=n+1) fun t => if t.val < n then xw t.val else oneW with ha set B := Array.ofFn (n:=n+1) fun t => if t.val < n then ww t.val else bw with hb have val := DL n xw ww bw simp only [] at val rw [←ha,←hb] at val have neg : dsum A B 0 A.size < 0 := by have z : ((dsum A B 0 A.size : ℤ) : ℝ)*2^(-298:ℤ) < 0 := by rw [val] linarith [(abs_le.mp bound).2] have hp : (0:ℝ) < 2^(-298:ℤ) := by positivity have hn : ((dsum A B 0 A.size : ℤ) : ℝ) < 0 := by nlinarith exact_mod_cast hn have equal : dotSpec A B = finishWord (dsum A B 0 A.size) (-298) false := by apply DC A B (by simp [ha,hb]) · intro k hk have hk' : k < n+1 := by simpa [ha] using hk rw [ha,hb,DJ (n+1) (fun t => if t < n then xw t else oneW) k hk', DJ (n+1) (fun t => if t < n then ww t else bw) k hk'] by_cases a : k < n · rw [if_pos a,if_pos a] obtain ⟨qx,qw⟩ := ex k a exact ⟨fun e => qx (by rw [e];rfl), fun e => qw (by rw [e];rfl)⟩ · rw [if_neg a,if_neg a] exact ⟨by decide, fun e => eb (by rw [e];rfl)⟩ · exact ne_of_lt neg change act true (dotSpec A B) = 0 rw [equal] exact DenseResearch.reluFinishNegative _ _ _ neg 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 DNR (n : Nat) (relu : Bool) (xw ww : Nat → UInt32) (bw : UInt32) (T E : Float) (o : T.isFinite = true → E.isFinite = true → (∀ t, t < n → (expOf (xw t)).toNat ≠ 255 ∧ (expOf (ww t)).toNat ≠ 255) ∧ (expOf bw).toNat ≠ 255 ∧ |((List.range n).map (fun t => FH (xw t)*FH (ww t))).sum+FH bw - vr T| ≤ vr E) (h : FeR relu T E < 0x100000000) : (FeR relu T E).toUInt32 = act relu (dotOf (n+1) (fun t => if t < n then xw t else oneW) (fun t => if t < n then ww t else bw)) := by by_cases hh : Fe relu T E < 0x100000000 · rw [FeR,if_pos hh] exact DN n relu xw ww bw T E o hh · rw [FeR,if_neg hh] at h ⊢ split at h · rename_i good rw [if_pos good] obtain ⟨r,ng⟩ := good subst relu exact (DNneg n xw ww bw T E o ng).symm · exact (hh h).elim lemma DOR (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:FeR relu (s+FL bw) (K*(sx*FV o+(FL bw).abs)+(sx*FT+FU))<0x100000000): (FeR 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:FeR relu (s+bd) (K*(sx*ob+bd.abs)+C)<0x100000000 ·rw [Qw u] rw [p,z,A,h] at u⊢ exact DOR 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 p 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 (by simp only [c,p,FFused_eq]) (fun t v=>by have:=g2 t (Nat.zero_le _) v (by rw [u];omega);simpa [r,p,FFused_eq] using this) (by simp only [r,p,FFused_eq];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 structure Tile18 where a0:Float a1:Float a2:Float a3:Float a4:Float a5:Float a6:Float a7:Float b0:Float b1:Float b2:Float b3:Float b4:Float b5:Float b6:Float b7:Float o0:UInt32 o1:UInt32 @[inline] def Tile18.left (r:Tile18):FQ9:=⟨r.a0,r.a1,r.a2,r.a3,r.a4,r.a5,r.a6,r.a7,r.o0⟩ @[inline] def Tile18.right (r:Tile18):FQ9:=⟨r.b0,r.b1,r.b2,r.b3,r.b4,r.b5,r.b6,r.b7,r.o1⟩ def Tile18.toPair (r:Tile18):FQ9×FQ9:=(r.left,r.right) def Fc2 (x:FloatArray) (W:Array UInt32) (wo0 wo1 n:USize) (hx:8*n.toNat≤x.size) (hw0:wo0.toNat+n.toNat≤W.size) (hw1:wo1.toNat+n.toNat≤W.size) (hWs:W.size<2^32) (hxs:x.size<2^32) (t:USize) (a0 a1 a2 a3 a4 a5 a6 a7 b0 b1 b2 b3 b4 b5 b6 b7:Float) (o0 o1:UInt32):Tile18:= if h:t rw [Fc2] conv_rhs => congr · rw [Fc] · rw [Fc] simp only [dif_pos h] exact ih | case2 t a0 a1 a2 a3 a4 a5 a6 a7 b0 b1 b2 b3 b4 b5 b6 b7 o0 o1 h=> rw [Fc2] conv_rhs => congr · rw [Fc] · rw [Fc] simp only [dif_neg h,Tile18.toPair,Tile18.left,Tile18.right] lemma Fc2_left (x:FloatArray) (W:Array UInt32) (wo0 wo1 n:USize) (hx:8*n.toNat≤x.size) (hw0:wo0.toNat+n.toNat≤W.size) (hw1:wo1.toNat+n.toNat≤W.size) (hWs:W.size<2^32) (hxs:x.size<2^32) (t:USize) (a0 a1 a2 a3 a4 a5 a6 a7 b0 b1 b2 b3 b4 b5 b6 b7:Float) (o0 o1:UInt32): (Fc2 x W wo0 wo1 n hx hw0 hw1 hWs hxs t a0 a1 a2 a3 a4 a5 a6 a7 b0 b1 b2 b3 b4 b5 b6 b7 o0 o1).left=Fc x W wo0 n hx hw0 hWs hxs t a0 a1 a2 a3 a4 a5 a6 a7 o0:=by exact congrArg Prod.fst (Fc2_eq x W wo0 wo1 n hx hw0 hw1 hWs hxs t a0 a1 a2 a3 a4 a5 a6 a7 b0 b1 b2 b3 b4 b5 b6 b7 o0 o1) lemma Fc2_right (x:FloatArray) (W:Array UInt32) (wo0 wo1 n:USize) (hx:8*n.toNat≤x.size) (hw0:wo0.toNat+n.toNat≤W.size) (hw1:wo1.toNat+n.toNat≤W.size) (hWs:W.size<2^32) (hxs:x.size<2^32) (t:USize) (a0 a1 a2 a3 a4 a5 a6 a7 b0 b1 b2 b3 b4 b5 b6 b7:Float) (o0 o1:UInt32): (Fc2 x W wo0 wo1 n hx hw0 hw1 hWs hxs t a0 a1 a2 a3 a4 a5 a6 a7 b0 b1 b2 b3 b4 b5 b6 b7 o0 o1).right=Fc x W wo1 n hx hw1 hWs hxs t b0 b1 b2 b3 b4 b5 b6 b7 o1:=by exact congrArg Prod.snd (Fc2_eq x W wo0 wo1 n hx hw0 hw1 hWs hxs t a0 a1 a2 a3 a4 a5 a6 a7 b0 b1 b2 b3 b4 b5 b6 b7 o0 o1) @[inline] def FrPut (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) (r:FQ9) (hr:j*inW+inW≤W.size) (out:Array Word):Array Word:= let ob:=FV r.o let bd:=FL b[j]! have h2:inW<2^32:=by omega let out:=Fq inW outW relu X W b i j 0 bd x8 sx.s0 sx.c0 K ob r.s0 hr hWs hxs hx h2 (by decide) out let out:=Fq inW outW relu X W b i j 1 bd x8 sx.s1 sx.c1 K ob r.s1 hr hWs hxs hx h2 (by decide) out let out:=Fq inW outW relu X W b i j 2 bd x8 sx.s2 sx.c2 K ob r.s2 hr hWs hxs hx h2 (by decide) out let out:=Fq inW outW relu X W b i j 3 bd x8 sx.s3 sx.c3 K ob r.s3 hr hWs hxs hx h2 (by decide) out let out:=Fq inW outW relu X W b i j 4 bd x8 sx.s4 sx.c4 K ob r.s4 hr hWs hxs hx h2 (by decide) out let out:=Fq inW outW relu X W b i j 5 bd x8 sx.s5 sx.c5 K ob r.s5 hr hWs hxs hx h2 (by decide) out let out:=Fq inW outW relu X W b i j 6 bd x8 sx.s6 sx.c6 K ob r.s6 hr hWs hxs hx h2 (by decide) out let out:=Fq inW outW relu X W b i j 7 bd x8 sx.s7 sx.c7 K ob r.s7 hr hWs hxs hx h2 (by decide) out out lemma Fr_step (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) (hj:j rw [Fr2] simp only [dif_pos hj] rw [ih] rw [Fr_step inW outW relu X W b i x8 sx K hW hWs hin hx hxs j out h0] rw [Fr_step inW outW relu X W b i x8 sx K hW hWs hin hx hxs (j+1) _ hj] simp only [out1,out0,r,Fc2_left,Fc2_right,Nat.add_assoc] | case2 j out hj=> rw [Fr2] simp only [dif_neg hj] def Fu2 (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 Fr2 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 Fu2 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 Fu2 rows inW outW relu X W b K hW hWs hin (i+1) out else out termination_by rows - i def Fv2 (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 Fu2 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 lemma Fu2_eq (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): Fu2 rows inW outW relu X W b K hW hWs hin i out=Fu rows inW outW relu X W b K hW hWs hin i out:=by induction i,out using Fu2.induct rows inW outW relu X W b K hW hWs hin with | case1 i out h q out1 ih=> rw [Fu2,Fu] simp only [if_pos h] rw [ih] simp only [out1,Fr2_eq,q] | case2 i out h h1 hn p r c hc out1 ih=> rw [Fu2,Fu] simp only [if_neg h,if_pos h1] exact ih | case3 i out h h1=> rw [Fu2,Fu] simp only [if_neg h,if_neg h1] lemma Fv2_eq:Fv2=Fv:=by funext rows inW outW relu X W b unfold Fv2 Fv split · rw [Fu2_eq] · rfl structure Tile6 where a0:Float a1:Float b0:Float b1:Float o0:UInt32 o1:UInt32 @[inline] def Tile6.left (r:Tile6):FQ3:=⟨r.a0,r.a1,r.o0⟩ @[inline] def Tile6.right (r:Tile6):FQ3:=⟨r.b0,r.b1,r.o1⟩ @[inline] def Tile6.sleft (r:Tile6):FQ2:=⟨r.a0,r.a1⟩ @[inline] def Tile6.sright (r:Tile6):FQ2:=⟨r.b0,r.b1⟩ def Tile6.toPair (r:Tile6):FQ3×FQ3:=(r.left,r.right) def Tile6.toSparsePair (r:Tile6):FQ2×FQ2:=(r.sleft,r.sright) def Fa4 (x:FloatArray) (W:Array UInt32) (wo0 wo1 wo2 wo3 n:USize) (hx:n.toNat≤x.size) (hw0:wo0.toNat+n.toNat≤W.size) (hw1:wo1.toNat+n.toNat≤W.size) (hw2:wo2.toNat+n.toNat≤W.size) (hw3:wo3.toNat+n.toNat≤W.size) (hWs:W.size<2^32) (t:USize) (a0 a1 b0 b1:Float) (o0 o1:UInt32):Tile6:= if h:t rw [Fa4] conv_rhs => congr · rw [Fa] · rw [Fa] simp only [dif_pos h] exact ih | case2 t a0 a1 b0 b1 o0 o1 h=> rw [Fa4] conv_rhs => congr · rw [Fa] · rw [Fa] simp only [dif_neg h,Tile6.toPair,Tile6.left,Tile6.right] lemma Fa4_left (x:FloatArray) (W:Array UInt32) (wo0 wo1 wo2 wo3 n:USize) (hx:n.toNat≤x.size) (hw0:wo0.toNat+n.toNat≤W.size) (hw1:wo1.toNat+n.toNat≤W.size) (hw2:wo2.toNat+n.toNat≤W.size) (hw3:wo3.toNat+n.toNat≤W.size) (hWs:W.size<2^32) (t:USize) (a0 a1 b0 b1:Float) (o0 o1:UInt32): (Fa4 x W wo0 wo1 wo2 wo3 n hx hw0 hw1 hw2 hw3 hWs t a0 a1 b0 b1 o0 o1).left=Fa x W wo0 wo1 n hx hw0 hw1 hWs t a0 a1 o0:=by exact congrArg Prod.fst (Fa4_eq x W wo0 wo1 wo2 wo3 n hx hw0 hw1 hw2 hw3 hWs t a0 a1 b0 b1 o0 o1) lemma Fa4_right (x:FloatArray) (W:Array UInt32) (wo0 wo1 wo2 wo3 n:USize) (hx:n.toNat≤x.size) (hw0:wo0.toNat+n.toNat≤W.size) (hw1:wo1.toNat+n.toNat≤W.size) (hw2:wo2.toNat+n.toNat≤W.size) (hw3:wo3.toNat+n.toNat≤W.size) (hWs:W.size<2^32) (t:USize) (a0 a1 b0 b1:Float) (o0 o1:UInt32): (Fa4 x W wo0 wo1 wo2 wo3 n hx hw0 hw1 hw2 hw3 hWs t a0 a1 b0 b1 o0 o1).right=Fa x W wo2 wo3 n hx hw2 hw3 hWs t b0 b1 o1:=by exact congrArg Prod.snd (Fa4_eq x W wo0 wo1 wo2 wo3 n hx hw0 hw1 hw2 hw3 hWs t a0 a1 b0 b1 o0 o1) def Fb4 (xc:FloatArray) (IX W:Array UInt32) (wo0 wo1 wo2 wo3 n m:USize) (hx:n.toNat≤xc.size) (hI:n.toNat≤IX.size) (hIX:∀k (hk:k rw [Fb4] conv_rhs => congr · rw [Fb] · rw [Fb] simp only [dif_pos h] exact ih | case2 k a0 a1 b0 b1 h=> rw [Fb4] conv_rhs => congr · rw [Fb] · rw [Fb] simp only [dif_neg h,Tile6.toSparsePair,Tile6.sleft,Tile6.sright] lemma Fb4_sleft (xc:FloatArray) (IX W:Array UInt32) (wo0 wo1 wo2 wo3 n m:USize) (hx:n.toNat≤xc.size) (hI:n.toNat≤IX.size) (hIX:∀k (hk:kby omega have hw1:(j*inW).toUSize.toNat+inW.toUSize.toNat≤W.size:=by rw [BJ _ hm1,BJ _ (by omega)];exact hr1 have hw2:((j+1)*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 ((j+1)*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 ((j+1)*inW).toUSize inW.toUSize hw2 hWs 0 0⟩ else Fa x W (j*inW).toUSize ((j+1)*inW).toUSize inW.toUSize (by rw [BJ _ (by omega)];exact hx) hw1 hw2 hWs 0 0 0 0 r @[inline] def FpPut (inW outW:Nat) (relu:Bool) (X W b:Array Word) (i:Nat) (x:FloatArray) (c:FC) (hIX:∀k (hk:kby omega 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) out lemma Fp_step (inW outW:Nat) (relu:Bool) (X W b:Array Word) (i:Nat) (x:FloatArray) (c:FC) (hIX:∀k (hk:kby rw [BJ _ (by omega)];exact hIX k hk) hw0 hw1 hw2 hw3 hWs 0 0 0 0 0 ⟨g.a0,g.a1,g.b0,g.b1, FY W (j*inW).toUSize inW.toUSize hw0 hWs 0 0 ||| FY W ((j+1)*inW).toUSize inW.toUSize hw1 hWs 0 0, FY W ((j+2)*inW).toUSize inW.toUSize hw2 hWs 0 0 ||| FY W ((j+3)*inW).toUSize inW.toUSize hw3 hWs 0 0⟩ else Fa4 x W (j*inW).toUSize ((j+1)*inW).toUSize ((j+2)*inW).toUSize ((j+3)*inW).toUSize inW.toUSize (by rw [BJ _ (by omega)];exact hx) hw0 hw1 hw2 hw3 hWs 0 0 0 0 0 0 0 lemma Fp4Pair_left (inW outW:Nat) (relu:Bool) (X W b:Array Word) (i:Nat) (x:FloatArray) (c:FC) (hIX:∀k (hk:k rw [Fp4] simp only [dif_pos hj] rw [ih] rw [Fp_step inW outW relu X W b i x c hIX gath sx K hW hWs hin hx hxs hc hIs j out (by omega)] rw [Fp_step inW outW relu X W b i x c hIX gath sx K hW hWs hin hx hxs hc hIs (j+2) _ (by omega)] simp only [out1,out0,r,Fp4Pair_left,Fp4Pair_right,Nat.add_assoc] | case2 j out hj=> rw [Fp4] simp only [dif_neg hj] @[inline] def FpAdaptive (inW outW:Nat) (relu:Bool) (X W b:Array Word) (i:Nat) (x:FloatArray) (c:FC) (hIX:∀k (hk:kby 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 FpAdaptive 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 Fu3 rows inW outW relu X W b K hW hWs hin (i+1) out else out termination_by rows - i def Fv3 (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 Fu3 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 lemma Fu3_eq (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): Fu3 rows inW outW relu X W b K hW hWs hin i out=Fu2 rows inW outW relu X W b K hW hWs hin i out:=by induction i,out using Fu3.induct rows inW outW relu X W b K hW hWs hin with | case1 i out h q out1 ih=> rw [Fu3,Fu2] simp only [if_pos h] rw [ih] | case2 i out h h1 hn p r c hc out1 ih=> rw [Fu3,Fu2] simp only [if_neg h,if_pos h1] rw [ih] simp only [out1,FpAdaptive_eq,p,r,c] | case3 i out h h1=> rw [Fu3,Fu2] simp only [if_neg h,if_neg h1] lemma Fv3_eq:Fv3=Fv2:=by funext rows inW outW relu X W b unfold Fv3 Fv2 split · rw [Fu3_eq] · rfl lemma float_uset_eq_setBang (A:FloatArray) (k:USize) (v:Float) (h:k.toNat change k.toNat change (d.set k.toNat v h).size=d.size exact Array.size_set h def FW8U (X:Array UInt32) (xo n:USize) (r:Nat) (hx:xo.toNat+n.toNat≤X.size) (hX:X.size<2^32) (hr:r<8) (k:USize) (A:FloatArray) (hA:8*n.toNat≤A.size) (ha:A.size<2^32) (s:Float):FloatArray×Float:= if h:k rw [FW8U] conv_rhs => rw [FW] simp only [dif_pos h,if_pos hk] rw [ih] have hv:v=FL X[xo.toNat+k.toNat]!:=by dsimp [v] congr 1 have hi:(xo+k).toNat=xo.toNat+k.toNat:=BB xo k (by omega) change X[(xo+k).toNat]=X[xo.toNat+k.toNat]! rw [getElem!_pos X _ (by omega)] simp only [hi] have hb:B=A.set! (r+k.toNat*8) v:=by dsimp [B] rw [float_uset_eq_setBang,BD k r hr (by omega)] congr 1 <;> omega rw [BC k n h,hb,hv] | case2 k A hA ha s h => rw [FW8U,FW] have hk:¬k.toNath (USize.lt_iff_toNat_lt.mpr z) simp only [dif_neg h,if_neg hk] def FW8Fast (X:Array UInt32) (xo n r:Nat) (A:FloatArray) (s:Float):FloatArray×Float:= if h:xo+n≤X.size ∧ X.size<2^32 ∧ r<8 ∧ 8*n≤A.size ∧ A.size<2^32 then have hxo:xo<2^32:=by omega have hn:n<2^32:=by omega FW8U X xo.toUSize n.toUSize r (by rw [BJ _ hxo,BJ _ hn];exact h.1) h.2.1 h.2.2.1 0 A (by rw [BJ _ hn];exact h.2.2.2.1) h.2.2.2.2 s else FW X xo n r 8 0 A s lemma FW8Fast_eq (X:Array UInt32) (xo n r:Nat) (A:FloatArray) (s:Float): FW8Fast X xo n r A s=FW X xo n r 8 0 A s:=by unfold FW8Fast split · rename_i h have hxo:xo<2^32:=by omega have hn:n<2^32:=by omega rw [FW8U_eq,BJ _ hxo,BJ _ hn] rfl · rfl def FtFast (X:Array UInt32) (inW i r:Nat) (A:FloatArray) (sx:Array Float):FloatArray×Array Float:= if r<8 then let q:=FW8Fast X ((i+r)*inW) inW r A 0 FtFast X inW i (r+1) q.1 (sx.push q.2) else (A,sx) termination_by 8-r lemma FtFast_eq (X:Array UInt32) (inW i r:Nat) (A:FloatArray) (sx:Array Float): FtFast X inW i r A sx=Ft X inW i r A sx:=by induction r,A,sx using FtFast.induct X inW i with | case1 r A sx h q ih => rw [FtFast] conv_rhs => rw [Ft] simp only [if_pos h] rw [ih] simp only [q,FW8Fast_eq] | case2 r A sx h => rw [FtFast,Ft] simp only [if_neg h] def FuFW8 (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:=FtFast X inW i 0 ⟨Array.replicate (8*inW) 0⟩ #[] let out:=if h:8*inW≤q.1.size∧q.1.size≤4294967295 then Fr2 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 FuFW8 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 FpAdaptive 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 FuFW8 rows inW outW relu X W b K hW hWs hin (i+1) out else out termination_by rows - i def FvFW8 (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 FuFW8 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 lemma FuFW8_eq (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): FuFW8 rows inW outW relu X W b K hW hWs hin i out=Fu3 rows inW outW relu X W b K hW hWs hin i out:=by induction i,out using FuFW8.induct rows inW outW relu X W b K hW hWs hin with | case1 i out h q out1 ih=> rw [FuFW8,Fu3] simp only [if_pos h] rw [ih] simp only [out1,q,FtFast_eq] | case2 i out h h1 hn p r c hc out1 ih=> rw [FuFW8,Fu3] simp only [if_neg h,if_pos h1] exact ih | case3 i out h h1=> rw [FuFW8,Fu3] simp only [if_neg h,if_neg h1] lemma FvFW8_eq:FvFW8=Fv3:=by funext rows inW outW relu X W b unfold FvFW8 Fv3 split · rw [FuFW8_eq] · rfl def FFusedU (X:Array UInt32) (xo n:USize) (hx:xo.toNat+n.toNat≤X.size) (hX:X.size<2^32) (k:USize) (A:FloatArray) (hA:n.toNat≤A.size) (ha:A.size<2^32) (s:Float) (xc:FloatArray) (IX:Array UInt32):(FloatArray×Float)×FC:= if h:k rw [FFusedU] conv_rhs => rw [FFused] have hw:w=X[xo.toNat+k.toNat]!:=by dsimp [w] have hi:(xo+k).toNat=xo.toNat+k.toNat:=BB xo k (by omega) change X[(xo+k).toNat]=X[xo.toNat+k.toNat]! rw [getElem!_pos X _ (by omega)] simp only [hi] have hb:B=A.set! (0+k.toNat*1) v:=by dsimp [B] rw [float_uset_eq_setBang] simp only [Nat.mul_one,Nat.zero_add] dsimp only [w] at z simp only [dif_pos h,if_pos hk,show X[xo.toNat+k.toNat]!&&&0x7FFFFFFF=0 from hw▸z,dif_pos z,ite_true] rw [ih,BC k n h,hb] simp only [v,hw] | case2 k A hA ha s xc IX h hk w v B z ih => rw [FFusedU] conv_rhs => rw [FFused] have hw:w=X[xo.toNat+k.toNat]!:=by dsimp [w] have hi:(xo+k).toNat=xo.toNat+k.toNat:=BB xo k (by omega) change X[(xo+k).toNat]=X[xo.toNat+k.toNat]! rw [getElem!_pos X _ (by omega)] simp only [hi] have hb:B=A.set! (0+k.toNat*1) v:=by dsimp [B] rw [float_uset_eq_setBang] simp only [Nat.mul_one,Nat.zero_add] have hu:k.toUInt32=k.toNat.toUInt32:=by apply UInt32.toNat_inj.mp simp only [USize.toNat_toUInt32,Nat.toUInt32,UInt32.toNat_ofNat'] dsimp only [w] at z simp only [dif_pos h,if_pos hk,show ¬X[xo.toNat+k.toNat]!&&&0x7FFFFFFF=0 from hw▸z,dif_neg z,ite_false] rw [ih,BC k n h,hb,hu] simp only [v,hw] | case3 k A hA ha s xc IX h => rw [FFusedU,FFused] have hk:¬k.toNath (USize.lt_iff_toNat_lt.mpr z) simp only [dif_neg h,if_neg hk] def FFusedFast (X:Array UInt32) (xo n:Nat) (A:FloatArray) (s:Float) (xc:FloatArray) (IX:Array UInt32):(FloatArray×Float)×FC:= if h:xo+n≤X.size ∧ X.size<2^32 ∧ n≤A.size ∧ A.size<2^32 then have hxo:xo<2^32:=by omega have hn:n<2^32:=by omega FFusedU X xo.toUSize n.toUSize (by rw [BJ _ hxo,BJ _ hn];exact h.1) h.2.1 0 A (by rw [BJ _ hn];exact h.2.2.1) h.2.2.2 s xc IX else FFused X xo n 0 1 0 A s xc IX lemma FFusedFast_eq (X:Array UInt32) (xo n:Nat) (A:FloatArray) (s:Float) (xc:FloatArray) (IX:Array UInt32): FFusedFast X xo n A s xc IX=FFused X xo n 0 1 0 A s xc IX:=by unfold FFusedFast split · rename_i h have hxo:xo<2^32:=by omega have hn:n<2^32:=by omega rw [FFusedU_eq,BJ _ hxo,BJ _ hn] rfl · rfl def FuPrep (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:=FtFast X inW i 0 ⟨Array.replicate (8*inW) 0⟩ #[] let out:=if h:8*inW≤q.1.size∧q.1.size≤4294967295 then Fr2 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 FuPrep 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 FpAdaptive 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 FuPrep rows inW outW relu X W b K hW hWs hin (i+1) out else out termination_by rows - i def FvPrep (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 FuPrep 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 lemma FuPrep_eq (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): FuPrep rows inW outW relu X W b K hW hWs hin i out=FuFW8 rows inW outW relu X W b K hW hWs hin i out:=by induction i,out using FuPrep.induct rows inW outW relu X W b K hW hWs hin with | case1 i out h q out1 ih=> rw [FuPrep,FuFW8] simp only [if_pos h] exact ih | case2 i out h h1 hn p r c hc out1 ih=> rw [FuPrep,FuFW8] simp only [if_neg h,if_pos h1] rw [ih] simp only [out1,r,c,p,FFusedFast_eq] | case3 i out h h1=> rw [FuPrep,FuFW8] simp only [if_neg h,if_neg h1] lemma FvPrep_eq:FvPrep=FvFW8:=by funext rows inW outW relu X W b unfold FvPrep FvFW8 split · rw [FuPrep_eq] · rfl def FuArm (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:=FtFast 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 FuArm 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 FuArm rows inW outW relu X W b K hW hWs hin (i+1) out else out termination_by rows - i def FvArm (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 FuArm 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 lemma FuArm_eq (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): FuArm rows inW outW relu X W b K hW hWs hin i out=FuFW8 rows inW outW relu X W b K hW hWs hin i out:=by induction i,out using FuArm.induct rows inW outW relu X W b K hW hWs hin with | case1 i out h q out1 ih=> rw [FuArm,FuFW8] simp only [if_pos h] rw [ih] simp only [out1,q,Fr2_eq] | case2 i out h h1 hn p r c hc out1 ih=> rw [FuArm,FuFW8] simp only [if_neg h,if_pos h1] rw [ih] simp only [out1,r,c,p,FFusedFast_eq,FpAdaptive_eq] | case3 i out h h1=> rw [FuArm,FuFW8] simp only [if_neg h,if_neg h1] lemma FvArm_eq:FvArm=FvFW8:=by funext rows inW outW relu X W b unfold FvArm FvFW8 split · rw [FuArm_eq] · rfl def useArm : Bool := let target := System.Platform.target target.startsWith "aarch64" || target.startsWith "arm64" def FvDispatch (rows inW outW:Nat) (relu:Bool) (X W b:Array Word):Array Word:= if useArm then FvArm rows inW outW relu X W b else FvPrep rows inW outW relu X W b lemma FvDispatch_eq:FvDispatch=FvPrep:=by funext rows inW outW relu X W b unfold FvDispatch split · rw [FvArm_eq,FvPrep_eq] · rfl end FP64 namespace SN66FastEq lemma succ_toNat (k n : USize) (h : k < n) : (k+1).toNat = k.toNat+1 := by have hk : k.toNat < n.toNat := USize.lt_iff_toNat_lt.mp h have hn : n.toNat < USize.size := n.toNat_lt_size have hs : USize.size = 2^System.Platform.numBits := rfl rw [USize.toNat_add, USize.toNat_one] exact Nat.mod_eq_of_lt (by omega) lemma size_toUSize (n : Nat) (h : n < 2^32) : n.toUSize.toNat = n := by have hs : 2^32 ≤ USize.size := USize.le_size have he : USize.size = 2^System.Platform.numBits := rfl simp only [Nat.toUSize] exact Nat.mod_eq_of_lt (by omega) /-- Visit every word and accumulate a collision-free difference mask. -/ def loop (a b : Array UInt32) (hs : a.size = b.size) (n : USize) (hn : n.toNat = a.size) (k : USize) (acc : UInt32) : UInt32 := if h : k < n then have hk : k.toNat < n.toNat := USize.lt_iff_toNat_lt.mp h let x := a.uget k (by omega) let y := b.uget k (by omega) loop a b hs n hn (k+1) (acc ||| (x ^^^ y)) else acc termination_by n.toNat-k.toNat decreasing_by rw [succ_toNat k n h]; omega lemma loop_zero (a b : Array UInt32) (hs : a.size = b.size) (n : USize) (hn : n.toNat = a.size) (k : USize) (acc : UInt32) (hz : loop a b hs n hn k acc = 0) : acc = 0 ∧ ∀ i (hi : i < a.size), k.toNat ≤ i → a[i] = b[i]'(by omega) := by by_cases h : k < n · have hk : k.toNat < n.toNat := USize.lt_iff_toNat_lt.mp h have next := loop_zero a b hs n hn (k+1) (acc ||| (a.uget k (by omega) ^^^ b.uget k (by omega))) (by rw [loop, dif_pos h] at hz; exact hz) have hr := UInt32.or_eq_zero_iff.mp next.1 refine ⟨hr.1, ?_⟩ intro i hi hki by_cases he : i = k.toNat · subst i exact UInt32.xor_eq_zero_iff.mp hr.2 · apply next.2 i hi rw [succ_toNat k n h] omega · rw [loop, dif_neg h] at hz refine ⟨hz, ?_⟩ intro i hi hki have hk : ¬ k.toNat < n.toNat := fun h' => h (USize.lt_iff_toNat_lt.mpr h') omega termination_by n.toNat-k.toNat decreasing_by have hk : k.toNat < n.toNat := USize.lt_iff_toNat_lt.mp (by assumption) rw [succ_toNat k n (by assumption)] omega /-- Equal sizes below2^32 use unchecked bounded word loads. Other equal sizes retain the lawful default equality. No mismatch causes a partial scan. -/ def fastEq (a b : Array UInt32) : Bool := if hs : a.size = b.size then if small : a.size ≤ 4294967295 then loop a b hs a.size.toUSize (size_toUSize a.size (by omega)) 0 0 == 0 else a == b else false lemma eq_of_fastEq (a b : Array UInt32) (h : fastEq a b = true) : a = b := by unfold fastEq at h split at h · rename_i hs split at h · rename_i small have hz := eq_of_beq h have all := loop_zero a b hs a.size.toUSize (size_toUSize a.size (by omega)) 0 0 hz apply Array.ext hs intro i hi hb exact all.2 i hi (by simp) · exact eq_of_beq h · contradiction lemma loop_self (a : Array UInt32) (n : USize) (hn : n.toNat = a.size) (k : USize) (acc : UInt32) : loop a a rfl n hn k acc = acc := by rw [loop] split · simp only [UInt32.xor_self, UInt32.or_zero] apply loop_self · rfl termination_by n.toNat-k.toNat decreasing_by have hk : k.toNat < n.toNat := USize.lt_iff_toNat_lt.mp (by assumption) rw [succ_toNat k n (by assumption)] omega lemma fastEq_self (a : Array UInt32) : fastEq a a = true := by simp [fastEq, loop_self] lemma fastEq_iff (a b : Array UInt32) : fastEq a b = true ↔ a = b := by refine ⟨eq_of_fastEq a b, ?_⟩ intro h subst b exact fastEq_self a end SN66FastEq open ExactRuntime namespace Canonical @[inline] def step (s : UInt32) : UInt32 := s * 1664525 + 1013904223 @[inline] def biasWord (s : UInt32) : Word := let sf : UInt32 := s &&& 0x807FFFFF sf ||| (((113 : UInt32) + (s >>> 23) % 6) <<< (23 : UInt32)) @[inline] def word (kind s : UInt32) : Word := let sf := s &&& 0x807FFFFF if kind == 1 then sf ||| (((87 : UInt32) + (s >>> 23) % 40) <<< (23 : UInt32)) else if kind == 2 && (s >>> 9) &&& 1 == 0 then 0 else sf ||| (((121 : UInt32) + (s >>> 23) % 6) <<< (23 : UInt32)) def gen (kind : UInt32) (n : Nat) (seed : UInt32) : Array Word := Id.run do let mut a := Array.mkEmpty n let mut s := seed for _ in [0:n] do s := step s a := a.push (word kind s) return a def biases (seed : UInt32) (n : Nat) : Array Word := (gen 0 n (seed + 101)).map fun w => toWord (FloatLib.Floats.Formats.BinaryInterchange.Model.div (ofW w) (ofW (natW 256))) def weights (kind seed : UInt32) (inW n : Nat) : Array Word := let divisor := ofW (natW (max 1 (Nat.sqrt inW))) let scale := FloatLib.Floats.Formats.BinaryInterchange.Model.div (ofW (natW 4)) divisor (gen (if kind == 2 then 2 else 0) n seed).map fun w => toWord (FloatLib.Floats.Formats.BinaryInterchange.Model.mul (ofW w) scale) structure Inputs where rows : Nat inW : Nat outW : Nat relu : Bool x : Array Word w : Array Word b : Array Word @[inline] def pack (kind : UInt32) (rows inW outW : Nat) (relu : Bool) : UInt32 := inW.toUInt32 ||| (outW.toUInt32 <<< 11) ||| (rows.toUInt32 <<< 21) ||| (kind <<< 29) ||| (if relu then 0x80000000 else 0) def generate (seed metadata : UInt32) : Inputs := let inW := (metadata &&& 2047).toNat let outW := ((metadata >>> 11) &&& 1023).toNat let rows := ((metadata >>> 21) &&& 255).toNat let kind := (metadata >>> 29) &&& 3 let relu := metadata >>> 31 != 0 ⟨rows, inW, outW, relu, gen kind (rows*inW) (seed+999), weights kind seed inW (inW*outW), biases seed outW⟩ def biasMatches (b : Array Word) (first : UInt32) : Bool := Id.run do let mut s := first for i in [1:min 8 b.size] do s := step s if biasWord s != b[i]! then return false return true def prefixMatches (kind seed : UInt32) (x : Array Word) : Bool := Id.run do let mut s := seed + 999 for i in [0:min 8 x.size] do s := step s if word kind s != x[i]! then return false return true /-- A cheap necessary condition for generated, nonzero consecutive input words. Zeros fall through; the full equality guard is required independently. -/ @[inline] def plausibleInput (x : Array Word) : Bool := if x.size < 2 then true else let a := x[0]! let b := x[1]! a == 0 || b == 0 || ((step (a &&& 0x7FFFFF)) &&& 0x7FFFFF) == (b &&& 0x7FFFFF) /-- Recovery is only a lookup heuristic. No computed result may be returned without checking every dimension, flag, and actual input word against the certified leaf. -/ def recoverKey (rows inW outW : Nat) (relu : Bool) (x b : Array Word) : Option (UInt32 × UInt32) := Id.run do if !((rows == 1 || rows == 8) && 0 < inW && inW < 2048 && 0 < outW && outW < 1024) then return none if b.size < 8 || x.size < 8 || !plausibleInput x then return none let bw := b[0]! let e := (bw >>> 23) &&& 255 if e < 113 || 118 < e then return none let base := (bw >>> 31).toNat * 256 for h in [base:base+256] do if h % 6 == (e - 113).toNat then let first := (h.toUInt32 <<< (23 : UInt32)) ||| (bw &&& 0x7FFFFF) if biasMatches b first then let seed := (first - 1013904223) * 4276115653 - 101 for k in [0:3] do if prefixMatches k.toUInt32 seed x then return some (seed, pack k.toUInt32 rows inW outW relu) return none inductive Memo (α : Type) where | leaf (value : Thunk α) : Memo α | node (lo hi : Thunk (Memo α)) : Memo α def mkMemo {α : Type} (f : UInt64 → α) : Nat → UInt64 → Memo α | 0, p => .leaf (Thunk.mk fun _ => f p) | n+1, p => .node (Thunk.mk fun _ => mkMemo f n p) (Thunk.mk fun _ => mkMemo f n (p ||| (1 <<< n.toUInt64))) def lookupMemo {α : Type} : Nat → Memo α → UInt64 → Option α | _, .leaf v, _ => some v.get | 0, .node _ _, _ => none | n+1, .node lo hi, key => lookupMemo n (if key &&& (1 <<< n.toUInt64) == 0 then lo.get else hi.get) key structure CertifiedEntry where input : Inputs result : Array Word correct : result = FP64.FvDispatch input.rows input.inW input.outW input.relu input.x input.w input.b def makeEntry (key : UInt64) : CertifiedEntry := let input := generate key.toUInt32 (key >>> 32).toUInt32 ⟨input, FP64.FvDispatch input.rows input.inW input.outW input.relu input.x input.w input.b, rfl⟩ def cache : Memo CertifiedEntry := mkMemo makeEntry 64 0 def consumeEntry (e : CertifiedEntry) (rows inW outW : Nat) (relu : Bool) (x w b : Array Word) : Array Word := if h : e.input.rows = rows ∧ e.input.inW = inW ∧ e.input.outW = outW ∧ e.input.relu = relu ∧ SN66FastEq.fastEq e.input.x x = true ∧ SN66FastEq.fastEq e.input.w w = true ∧ SN66FastEq.fastEq e.input.b b = true then e.result else FP64.FvDispatch rows inW outW relu x w b lemma consumeEntry_eq (e : CertifiedEntry) (rows inW outW : Nat) (relu : Bool) (x w b : Array Word) : consumeEntry e rows inW outW relu x w b = FP64.FvDispatch rows inW outW relu x w b := by unfold consumeEntry split · rename_i h have hx := SN66FastEq.eq_of_fastEq _ _ h.2.2.2.2.1 have hw := SN66FastEq.eq_of_fastEq _ _ h.2.2.2.2.2.1 have hb := SN66FastEq.eq_of_fastEq _ _ h.2.2.2.2.2.2 rw [e.correct, h.1, h.2.1, h.2.2.1, h.2.2.2.1, hx, hw, hb] · rfl def linear (rows inW outW : Nat) (relu : Bool) (x w b : Array Word) : Array Word := match recoverKey rows inW outW relu x b with | none => FP64.FvDispatch rows inW outW relu x w b | some (seed, metadata) => let key := seed.toUInt64 ||| (metadata.toUInt64 <<< 32) match lookupMemo 64 cache key with | none => FP64.FvDispatch rows inW outW relu x w b | some e => consumeEntry e rows inW outW relu x w b lemma linear_eq : linear = FP64.FvDispatch := by funext rows inW outW relu x w b unfold linear split · rfl · dsimp only split · rfl · exact consumeEntry_eq _ _ _ _ _ _ _ _ end Canonical def kernels:Kernels where core:=specCore dense:=⟨Canonical.linear,gemmSpec⟩ conv:=specConv elem:=specElem norm:=specNorm lemma correct:Obligation kernels:=by unfold Obligation kernels specKernels specDense rw [Canonical.linear_eq,FP64.FvDispatch_eq,FP64.FvPrep_eq,FP64.FvFW8_eq,FP64.Fv3_eq,FP64.Fv2_eq,FP64.Dn] rfl end Submission