import ContractExact namespace SmallDot open FloatLib.Floats.Formats.BinaryInterchange FloatLib.Floats ExactRuntime @[inline] def FI (s:Bool) (p:Nat):Int:=if s then -(p:Int) else (p:Int) lemma AA (s:Bool) (p:Nat):FI s p=(if s then -1 else 1)*(p:Int):=by cases s<;>simp [FI] @[specialize] def FJ (fa fb:Nat→Word) (index:Nat):Nat→Nat→Nat | 0,m=>m | count+1,m=>FJ fa fb (index+1) count (min m (idxOf (fa index)+idxOf (fb index))) @[specialize] def FK (fa fb:Nat→Word) (m index:Nat):Nat→Int | 0=>0 | count+1=>FI (Bool.xor (signOf (fa index)) (signOf (fb index))) ((mantOf (fa index)*mantOf (fb index))<<<(idxOf (fa index)+idxOf (fb index) - m))+ FK fa fb m (index+1) count @[specialize] def FL (fa fb:Nat→Word) (index:Nat):Nat→Bool | 0=>true | count+1=>(expOf (fa index) !=255&&expOf (fb index) !=255)&&FL fa fb (index+1) count @[specialize] def FM (fa fb:Nat→Word) (index:Nat):Nat→Bool | 0=>true | count+1=>(decide (mantOf (fa index)*mantOf (fb index)=0)&& Bool.xor (signOf (fa index)) (signOf (fb index)))&&FM fa fb (index+1) count lemma AB (fa fb:Nat→Word) (A B:Array UInt32):∀count index, (∀k,index≤k→k< index+count→ A[k]! =fa k∧B[k]! =fb k)→ FM fa fb index count=dallNZ A B index count:=by intro count;induction count with | zero=>intro index _;rfl | succ c ih=> intro index h obtain ⟨a,b⟩:=h index le_rfl (by omega) simp only[FM,dallNZ,a,b,ih (index+1) (fun k d e=>h k (by omega) (by omega))] @[inline] def FN:DotFn:=fun n fa fb=> if FL fa fb 0 n then let m:=FJ fa fb 0 n 1024 let S:=FK fa fb m 0 n if S≠0 then finishWord S ((m:Int) - 298) false else toWord (Model.zero Fmt (decide (n≠0)&&FM fa fb 0 n)) else dotOf n fa fb lemma AC (A B:Array UInt32) (p:A.size=B.size) (b: ∀k,kintro index m0;exact ⟨le_rfl,fun k a b=>by omega⟩ | succ c ih=> intro index m0 obtain ⟨a,b⟩:=ih (index+1) (min m0 (idxOf (fa index)+idxOf (fb index))) simp only [FJ] refine ⟨le_trans a (min_le_left _ _),fun k d e=> ?_⟩ by_cases f:k=index ·subst f;exact le_trans a (min_le_right _ _) ·exact b k (by omega) (by omega) lemma AF (fa fb:Nat→Word) (m:Nat) (A B:Array UInt32): ∀count index, (∀k,index≤k→k< index+count→ A[k]! =fa k∧B[k]! =fb k∧m≤ idxOf (fa k)+idxOf (fb k))→ FK fa fb m index count*2^m=dsum A B index count:=by intro count induction count with | zero=>intro index _;simp [FK,dsum] | succ c ih=> intro index h obtain ⟨a,b,d⟩:=h index le_rfl (by omega) simp only [FK,dsum] rw [add_mul,ih (index+1) (fun k f g=>h k (by omega) (by omega)),a,b] congr 1 rw [AA,Nat.shiftLeft_eq] have e:(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 d] rw [e] unfold sv cases signOf (fa index)<;>cases signOf (fb index)<;>simp<;>push_cast<;>ring lemma AG (fa fb:Nat→Word): ∀count index,FL 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 [FL,Bool.and_eq_true,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 AH:FN=dotOf:=by funext n fa fb unfold FN split ·rename_i l simp only[] 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,m k (Nat.zero_le _) o⟩) split ·rename_i g have j:dsum A B 0 A.size≠0:=by rw [b,←h];exact mul_ne_zero g (pow_ne_zero _ two_ne_zero) show _=dotSpec A B rw [AC 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)) j false,b,←h, ←finishWord_scale] congr 1 ·rename_i g have p:dsum A B 0 A.size=0:=by rw[b,←h];simp only[not_ne_iff] at g;rw[g];simp show _=dotSpec A B rw[AD 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)) p,b] congr 2 rw[AB fa fb A B n 0 (fun k _ c=>a k (by omega))] ·rfl end SmallDot namespace Submission local notation"א"=>by omega local notation"ב"=>by norm_num local notation"ג"=>by simp local notation"ד"=>by linarith local notation"А"=>USize.lt_iff_toNat_lt local notation"Б"=>mul_le_mul_of_nonneg_right local notation"В"=>Nat.and_two_pow_sub_one_eq_mod local notation"Г"=>Nat.mod_eq_of_lt local notation"Д"=>ite_eq_right local notation"Е"=>getElem!_pos local notation"Ж"=>UInt32.le_iff_toNat_le local notation"З"=>Nat.mul_le_mul_right local notation"И"=>UInt32.toNat_inj local notation"Й"=>mul_le_mul_of_nonneg_left local notation"К"=>Nat.zero_add local notation"Л"=>ite_eq_left local notation"М"=>zpow_add₀ local notation"Н"=>Nat.pos_of_ne_zero local notation"О"=>UInt32.toNat_and local notation"П"=>abs_nonneg local notation"Р"=>dite_eq_left local notation"С"=>two_ne_zero local notation"Т"=>UInt32.toNat_toUSize local notation"У"=>abs_of_nonneg local notation"Ф"=>zpow_le_zpow_right₀ local notation"Х"=>dite_eq_right local notation"Ц"=>zpow_natCast local notation"Ч"=>abs_add_le local notation"Ш"=>mul_lt_mul_of_pos_right local notation"Щ"=>USize.toNat_one local notation"Ъ"=>Nat.mod_lt local notation"Ы"=>UInt64.toNat_add local notation"Ь"=>mul_nonneg local notation"Э"=>Nat.cast_nonneg local notation"Ю"=>Nat.shiftRight_eq_div_pow local notation"Я"=>Nat.add_zero local notation"а"=>FloatLib.Numerics.Dyadic.toRat_eq_zero_iff local notation"б"=>getElem!_neg local notation"в"=>lt_of_le_of_lt local notation"г"=>mul_le_mul local notation"д"=>Nat.pow_le_pow_right local notation"е"=>UInt32.toNat_ofNat' local notation"ж"=>FloatLib.Numerics.Dyadic.cast_toRat local notation"з"=>Nat.add_assoc local notation"и"=>Nat.lt_or_eq_of_le local notation"й"=>Nat.le_mul_of_pos_right local notation"к"=>Nat.pos_of_mul_pos_left local notation"л"=>UInt32.toNat_shiftRight local notation"м"=>UInt64.toNat_shiftRight local notation"н"=>List.mem_range local notation"о"=>Nat.mul_comm local notation"п"=>UInt32.lt_iff_toNat_lt local notation"р"=>UInt64.lt_iff_toNat_lt local notation"с"=>Nat.div_eq_of_lt local notation"т"=>Nat.shiftLeft_eq local notation"у"=>Bool.and_eq_true_iff local notation"ф"=>Nat.add_mul local notation"х"=>Nat.div_lt_of_lt_mul local notation"ц"=>Nat.one_mul local notation"ч"=>Nat.pow_add local notation"ш"=>Nat.lt_succ_iff local notation"щ"=>Nat.two_pow_add_eq_or_of_lt local notation"ъ"=>Array.ext local notation"ы"=>Finset.sum_congr local notation"ь"=>Nat.exists_eq_add_of_le local notation"э"=>UInt64.toNat_and local notation"ю"=>zpow_pos local notation"я"=>lt_of_mul_lt_mul_right local notation"ذ"=>Nat.div_div_eq_div_mul local notation"ر"=>Nat.succ_mul local notation"ز"=>Nat.succ_pos local notation"س"=>UInt32.toNat_sub_of_le local notation"ش"=>List.mem_filter local notation"ص"=>Nat.mod_add_div local notation"ض"=>Array.getElem_push_eq local notation"ط"=>Array.getElem_push_lt local notation"ظ"=>le_trans local notation"ع"=>Rat.cast_zero open ExactRuntime FloatLib.Floats.Formats.BinaryInterchange FloatLib.Floats structure F1 where (s t:Float) structure R1 where (ix:Array UInt32) (buf:FloatArray) (c:USize) (hi:UInt32) structure D_Sc where (lo hi:UInt32) structure D_C where (dw relu f4:Bool) (s:ConvShape) (X W b:Array UInt32) (k C ho wo wp:Nat) (step:USize) (hi:UInt32) (xd:FloatArray) (nf:Float) (tab:Array UInt32) structure D_P where (g:D_C) (wd:FloatArray) (off:Array UInt32) (e l1 l4:USize) (e0 bv ze:Float) (he:e.toNat<=off.size) (hw:e.toNat<=wd.size) (hs:g.xd.size<2^32) (h1:∀b:USize,b∀j (h:j∀j (h:jUInt32) (k:Nat) (a:kf i.val)[k]! =f k:=by rw[Е _ k (by simpa using a),Array.getElem_ofFn] @[inline] def FO:DotFn:=SmallDot.FN lemma AJ:FO=dotOf:=SmallDot.AH lemma AK (w:Word):toWord (ofW w)=w:=by apply И.mp;simp only[toWord,ofW,Model.toNatBits,ofUInt32_bits,UInt32.toNat_ofNat'];exact Г w.toBitVec.isLt lemma AL (z:Model Fmt):ofW (toWord z)=z:=by have h:z.toNatBits<2^32:=Model.toNatBits_lt_two_pow z;simp only[ofW,toWord,Model.ofUInt32,UInt32.toNat_ofNat',Nat.mod_eq_of_lt h];exact Model.ofNatBits_toNatBits z @[inline] def FP (w:Word):Int:= if signOf w then -((mantOf w<<< idxOf w:Nat):Int) else ((mantOf w<<< idxOf w:Nat):Int) lemma AM (w:Word):FP w=sv w*2^idxOf w:=by unfold FP sv;split<;>simp[Nat.shiftLeft_eq] lemma AN (w:Word):(decodeD w).toReal=(FP w:ℝ)*2^(-149:Int):=by rw[<-ж,decodeD_toRat,AM];push_cast;rw[zpow_sub₀ С,Ц];ring @[inline] def FQ (a b:Word):Word:= if expOf a=255∨expOf b=255 then toWord (Model.maximum (ofW a) (ofW b)) else match compare (FP a) (FP b) with | .lt=>b | .gt=>a | .eq=>toWord (if Model.isZero (ofW a)&&Model.isZero (ofW b) then Model.zero Fmt (Model.signBit (ofW a)&&Model.signBit (ofW b)) else ofW a) lemma AO (a b:Word):Model.cmpDyadic (decodeD a) (decodeD b)=compare (FP a) (FP b):=by have c:(0:ℝ)<2^(-149:Int):=ю two_pos _;cases h:compare (FP a) (FP b);. rw[Model.cmpDyadic_lt_iff,AN,AN];exact Ш (by exact_mod_cast compare_lt_iff_lt.mp h) c . rw[Model.cmpDyadic_eq_iff,AN,AN,compare_eq_iff_eq.mp h] . rw[Model.cmpDyadic_gt_iff,AN,AN];exact Ш (by exact_mod_cast compare_gt_iff_gt.mp h) c lemma AP (a b:Word):ofW (FQ a b)=Model.maximum (ofW a) (ofW b):=by unfold FQ;split;. exact AL _ . rename_i f;have g:=toDyadic_ofUInt32 a (λh=>f (Or.inl h));have i:=toDyadic_ofUInt32 b (λh=>f (Or.inr h));have d:=Model.isNaN_eq_false_of_toDyadic?_some g;have e:=Model.isNaN_eq_false_of_toDyadic?_some i;have j:Model.compare (ofW a) (ofW b)=some _:=Model.compare_eq_some_cmpDyadic_of_toDyadic? _ _ g i;rw[AO] at j;have c:Model.chooseNaN2 (ofW a) (ofW b)=none:=(Model.chooseNaN2_eq_none_iff _ _).2 ⟨d,e⟩;unfold Model.maximum;rw[Model.withNaNSelection_of_none _ _ c];dsimp only;rw[Model.compareNonNaN_eq_of_compare_eq_some _ _ _ _ j];cases compare (FP a) (FP b)<;>simp only[AL] def FR (c h w k:Nat) (inp:Array Word):Array Word:= Array.ofFn (n:=c*(h/k*(w/k))) λq=> let ch:=q.val/(h/k*(w/k)) let y:=q.val/(w/k)%(h/k) let x:=q.val%(w/k) (List.range (k*k)).foldl (λacc t=>FQ acc (poolAt h w k inp ch y x t)) (poolAt h w k inp ch y x 0) lemma AQ (p:Nat->Word) (l:List Nat) (acc:Word): l.foldl (λm t=>Model.maximum m (ofW (p t))) (ofW acc)=ofW (l.foldl (λa t=>FQ a (p t)) acc):=by induction l generalizing acc with | nil=>rfl | cons t l ih=>simp only[List.foldl_cons,<-AP,ih] lemma AR:FR=maxpoolSpec:=by funext c h w k inp;simp only[FR,maxpoolSpec,AQ,AK] lemma AS (t n:USize) (h:ta.push (FW i)) (FloatArray.emptyWithCapacity 512) lemma AW:pw.data=(List.range 512).toArray.map FW:=by have key:∀(l:List Nat) (a:FloatArray),(l.foldl (λa i=>a.push (FW i)) a).data=a.data++(l.toArray.map FW):=by intro l;induction l with | nil=>intro a;simp | cons x l ih=>intro a;simp only[List.foldl_cons,ih];simp[FloatArray.push] simp only[pw,key];simp[FloatArray.emptyWithCapacity] lemma AX:pw.size=512:=by simp[FloatArray.size,AW] lemma AY (w:UInt32):(w>>>(23:UInt32)).toUSize.toNat>>(23:UInt32)).toUSize (AY w) @[inline] def FX (w:UInt32):Bool:= let v:=w&&&0x7FFFFFFF v==0 || v-(0x00800000:UInt32)<=(0x7EFFFFFF:UInt32) def FY (A:Array UInt32) (n i:USize) (hn:n.toNat<=A.size) (lo hi:UInt32):UInt32:= if h:i>>(29:UInt64) let y:UInt64:=((s-e).toBits+(0x0FFFFFFF:UInt64))>>>(29:UInt64) let ex:UInt64:=(x>>>(23:UInt64))&&&(0x7FF:UInt64) if x==y&&ex-(897:UInt64)<(254:UInt64) then (((x>>>(34:UInt64))<<<(31:UInt64)) ||| ((x&&&(0x3FFFFFFFF:UInt64))-((896:UInt64)<<<(23:UInt64)))).toUInt32 else 0xFFFFFFFF @[inline] def mx (a w:UInt32):UInt32:= let m:=w&&&0x7FFFFFFF if m<=a then a else m def Fb (X:Array UInt32) (o n t:USize) (ix:Array UInt32) (buf:FloatArray) (c:USize) (hi:UInt32):R1:= if h:tUInt32) (bw:UInt32):ℝ:= (Finset.range n).sum (λt=>wv (xw t)*wv (ww t))+wv bw def Fd (n:Nat):Float:=(n.toUInt64+8).toFloat*Float.ofBits 0x3CC0000000000000 lemma Aa:FloatFormat.binary64.isIEEE=true:=by decide lemma Ab (a:Model FloatFormat.binary64):Model.isFinite a=(Model.toModel a).isFinite:=by have c:=Model.toDyadic?_ieee_eq_model _ Aa a;cases f:Model.toModel a with | notANumber=> rw[f] at c;cases h:Model.isFinite a with | false=>rfl | true=>obtain ⟨d,b⟩:=Model.exists_toDyadic?_of_isFinite h;rw[c] at b;cases b | infinity s=> rw[f] at c;cases h:Model.isFinite a with | false=>rfl | true=>obtain ⟨d,b⟩:=Model.exists_toDyadic?_of_isFinite h;rw[c] at b;cases b | zero s=>rw[f] at c;exact Model.isFinite_eq_true_of_toDyadic?_some c | finite s m e h=>rw[f] at c;exact Model.isFinite_eq_true_of_toDyadic?_some c abbrev Fe (x:Float):Model FloatFormat.binary64:=Model.ofFloatModel x.toModel lemma Ac (x:Float):R x=Model.toReal (Fe x):=rfl lemma Ad (x:Float):Model.isFinite (Fe x)=x.isFinite:=by rw[Ab,Model.toModel_ofFloatModel];rfl lemma Ae (e:ℤ):Formats.Flocq.bpow FloatLib.Numerics.binaryRadix e=(2:ℝ)^e:=by simp[Formats.Flocq.bpow,FloatLib.Numerics.binaryRadix,FloatLib.Numerics.Radix.toReal] lemma Af:(2:ℝ)^(1000:ℤ)<=Model.toReal (Model.posMaxFinite FloatFormat.binary64):=by rw[Model.toReal_posMaxFinite] have a:Model.pow2 FloatFormat.binary64.fracWidth+FloatFormat.binary64.maxFiniteFracField =2^53-1:=by decide+kernel have b:FloatFormat.binary64.maxNormalExponent-Int.ofNat FloatFormat.binary64.fracWidth =971:=by decide+kernel rw[a,b];have c:Model.bpow 971=(2:ℝ)^(971:ℤ):=by simp only[Model.bpow,Ae] rw[c,show (1000:ℤ)=29+971 from rfl,М ב];apply Б _ (by positivity);norm_num lemma Ag (x y:Float) (c:x.isFinite=true) (d:y.isFinite=true) (e: |R x| + |R y| ≤2^(1000:ℤ)): (x+y).isFinite=true∧R (x+y)=Model.roundAt FloatFormat.binary64 (R x+R y):=by have f:Fe (x+y)=Model.add (Fe x) (Fe y):=toModel_ofFloat_add_of_isFinite x y c d have a:Model.isFinite (Fe x)=true:=by rw[Ad,c] have b:Model.isFinite (Fe y)=true:=by rw[Ad,d] constructor . rw[<-Ad,f];exact Model.isFinite_add_of_abs_add_le_posMaxFinite _ _ Aa a b (e.trans Af) . rw[Ac,f];exact Model.toReal_add_eq_roundAt_of_abs_add_le_posMaxFinite _ _ Aa a b (e.trans Af) lemma Ah (x y:Float) (c:x.isFinite=true) (d:y.isFinite=true) (e: |R x| + |R y| ≤2^(1000:ℤ)): (x-y).isFinite=true∧R (x-y)=Model.roundAt FloatFormat.binary64 (R x-R y):=by have f:Fe (x-y)=Model.sub (Fe x) (Fe y):=toModel_ofFloat_sub_of_isFinite x y c d have a:Model.isFinite (Fe x)=true:=by rw[Ad,c] have b:Model.isFinite (Fe y)=true:=by rw[Ad,d] constructor . rw[<-Ad,f];exact Model.isFinite_sub_of_abs_add_le_posMaxFinite _ _ Aa a b (e.trans Af) . rw[Ac,f];exact Model.toReal_sub_eq_roundAt_of_abs_add_le_posMaxFinite _ _ Aa a b (e.trans Af) open Float.Model.UnpackedFloat in lemma Ai (b:BitVec 64) (s m e h) (a:Float.Model.UnpackedFloat.unpack Float.Model.Format.binary64 b=.finite s m e h):(2^52<=m∧-1074<=e)∨e=-1074:=by unfold Float.Model.UnpackedFloat.unpack at a;simp only at a;have f:(Float.Model.Format.binary64.exponentBias:ℤ)=1023:=by decide rw[f] at a;split_ifs at a with j k c l . injection a with _ _ d;right;have:(unpackExponent (spec:=Float.Model.Format.binary64) b).toNat=0:=by simp[c] rw[this] at d;omega . injection a with _ g d;left;have:(unpackExponent (spec:=Float.Model.Format.binary64) b).toNat≠0:=by intro i;exact c (BitVec.eq_of_toNat_eq (by simpa using i)) constructor;. rw[<-g,BitVec.toNat_append];refine ظ ?_ Nat.left_le_or;simp[Nat.shiftLeft_eq] . omega open Float.Model.UnpackedFloat in lemma Aj (spec:Float.Model.Format) (s:Sign) (m:ℕ) (e:ℤ) (h:e<=spec.targetExponent (Float.Model.totalExponent m e)):Float.Model.UnpackedFloat.round spec s m e=roundWithAccuracy spec s m e .exact:=by unfold Float.Model.UnpackedFloat.round decreaseExponent;have a:(e-spec.targetExponent (Float.Model.totalExponent m e)).toNat=0:=א;simp[a] open Float.Model.UnpackedFloat in lemma Ak (s₁ s₂ m₁ m₂ e₁ e₂ b c) (b₁ b₂:BitVec 64) (d:unpack Float.Model.Format.binary64 b₁=.finite s₁ m₁ e₁ b) (e:unpack Float.Model.Format.binary64 b₂=.finite s₂ m₂ e₂ c): e₁+e₂<=Float.Model.Format.binary64.targetExponent (Float.Model.totalExponent (m₁*m₂) (e₁+e₂)):=by have c₁:=Ai _ _ _ _ _ d have c₂:=Ai _ _ _ _ _ e have f:m₁*m₂≠0:=Nat.mul_ne_zero b.ne' c.ne' have a:2^52<=m₁*m₂->52<=(m₁*m₂).log2:=λh=>(Nat.le_log2 f).2 h simp only[Float.Model.Format.targetExponent,Float.Model.totalExponent,Float.Model.Format.mantissaBits,Float.Model.Format.minExponent] rcases c₁ with ⟨c₁,_⟩ | c₁ . have:=a (ظ c₁ (й _ c));apply le_max_of_le_left;norm_num;omega . rcases c₂ with ⟨c₂,_⟩ | c₂;. have:=a (ظ c₂ (Nat.le_mul_of_pos_left _ b));apply le_max_of_le_left;norm_num;omega . apply le_max_of_le_right;norm_num;omega open Float.Model.UnpackedFloat in lemma Al (x y:Float) (f:x.isFinite=true) (g:y.isFinite=true):Fe (x*y)=Model.mul (Fe x) (Fe y):=by have h:Model.toModel (Fe x)=x.toModel.unpack:=Model.toModel_ofFloatModel _;have i:Model.toModel (Fe y)=y.toModel.unpack:=Model.toModel_ofFloatModel _;change Model.ofFloatModel (Float.Model.mul x.toModel y.toModel)=_;rw[Float.Model.mul,Model.ofFloatModel_pack,Model.Proof.mul_eq_spec,Model.Spec.mul,Model.toDyadic?_ieee_eq_model _ Aa (Fe x),Model.toDyadic?_ieee_eq_model _ Aa (Fe y),h,i];change x.toModel.unpack.isFinite=true at f;change y.toModel.unpack.isFinite=true at g;cases a:x.toModel.unpack<;>cases b:y.toModel.unpack<;>simp only[a,b,Float.Model.UnpackedFloat.isFinite,Bool.false_eq_true] at f g case zero.zero s₁ s₂=> cases s₁<;>cases s₂<;>simp[Model.unpackedToDyadic?,Float.Model.UnpackedFloat.mul] all_goals first | (rw[Model.negZero_eq_ofModel_zero];rfl) | (rw[Model.posZero_eq_ofModel_zero];rfl) case zero.finite s₁ s₂ m₂ e₂ c=> cases s₁<;>cases s₂<;>simp[Model.unpackedToDyadic?,Float.Model.UnpackedFloat.mul] all_goals first | (rw[Model.negZero_eq_ofModel_zero];rfl) | (rw[Model.posZero_eq_ofModel_zero];rfl) case finite.zero s₁ m₁ e₁ d s₂=> cases s₁<;>cases s₂<;>simp[Model.unpackedToDyadic?,Float.Model.UnpackedFloat.mul] all_goals first | (rw[Model.negZero_eq_ofModel_zero];rfl) | (rw[Model.posZero_eq_ofModel_zero];rfl) case finite.finite s₁ m₁ e₁ d s₂ m₂ e₂ c=> simp only[Model.unpackedToDyadic?,Float.Model.UnpackedFloat.mul];have e:=Ak s₁ s₂ m₁ m₂ e₁ e₂ d c _ _ a b;have j:(m₁==0 || m₂==0)=false:=by simp[d.ne',c.ne'] rw[<-Aj _ _ _ _ e,j];have k:Model.modelSign (Model.modelSignBit s₁^^Model.modelSignBit s₂)=s₁*s₂:=by cases s₁<;>cases s₂<;>rfl simp only[Bool.false_eq_true,ite_false,Model.roundDyadic,Aa,ite_true,Model.ieeeRoundDyadic,k];rfl lemma Am (x y:Float) (c:x.isFinite=true) (d:y.isFinite=true) (e: |R x| * |R y| ≤2^(1000:ℤ)): (x*y).isFinite=true∧R (x*y)=Model.roundAt FloatFormat.binary64 (R x*R y):=by have f:Fe (x*y)=Model.mul (Fe x) (Fe y):=Al x y c d have a:Model.isFinite (Fe x)=true:=by rw[Ad,c] have b:Model.isFinite (Fe y)=true:=by rw[Ad,d] constructor . rw[<-Ad,f];exact Model.isFinite_mul_of_abs_mul_le_posMaxFinite _ _ Aa a b (e.trans Af) . rw[Ac,f];exact Model.toReal_mul_eq_roundAt_of_abs_mul_le_posMaxFinite _ _ Aa a b (e.trans Af) noncomputable def Ff:ℝ:=2^(-1021:ℤ) noncomputable def Fg:ℝ:=2^(300:ℤ) lemma An:0rw[<-a];exact Model.toModel_canonicalizeModel _ | negative=> have d:(Model.toModel (Fe f)).isFinite=true:=by rw[a];rfl have b:=Model.toModel_neg_of_isFinite Aa (Fe f) d;rw[a] at b;have g:Float.Model.UnpackedFloat.neg (.finite .negative m e h)=.finite .positive m e h:=rfl;rw[g] at b;rw[<-b];exact Model.toModel_canonicalizeModel _ lemma A0 (f:Float) (c:f.isFinite=true):f.abs.isFinite=true∧R f.abs= |R f|:=by have b:Fe f.abs=Model.ofModel FloatFormat.binary64 f.toModel.unpack.abs:=Model.ofFloatModel_pack _;change f.toModel.unpack.isFinite=true at c;cases a:f.toModel.unpack with | notANumber=>simp[a,Float.Model.UnpackedFloat.isFinite] at c | infinity s=>simp[a,Float.Model.UnpackedFloat.isFinite] at c | zero s=> rw[a] at b;constructor;. rw[<-Ad,b];exact Model.isFinite_ofModel_zero _ Aa _ . rw[Ac f.abs,b,Ay f,a];simp[Float.Model.UnpackedFloat.abs,Model.toReal_ofModel_zero _ Aa] | finite s m e h=> rw[a] at b;have d:=Az f s m e h a;change Model.toModel (Model.ofModel FloatFormat.binary64 (.finite .positive m e h))=_ at d;constructor;. rw[<-Ad,b,Ab];change (Model.toModel (Model.ofModel FloatFormat.binary64 (.finite .positive m e h))).isFinite=_;rw[d];rfl . rw[Ac f.abs,b,Ay f,a];change Model.toReal (Model.ofModel FloatFormat.binary64 (.finite .positive m e h))=_;rw[Model.toReal_eq_unpackedToReal_toModel Aa,d];simp only[Model.unpackedToReal_finite,Ae];have g:(0:ℝ)<=(m:ℝ)*2^e:=by positivity cases s<;>simp[Model.modelSignBit,abs_of_nonneg g] lemma A1 (f:Float) (k:ℕ) (d:k<2^53) (g:f.toModel=Float.Model.pack (Float.Model.UnpackedFloat.ofNat Float.Model.Format.binary64 k)):f.isFinite=true∧R f=k:=by have b:Fe f=Model.roundDyadic FloatFormat.binary64 (FloatLib.Numerics.Dyadic.ofScaledInt k 0):=by change Model.ofFloatModel f.toModel=_;rw[g,Model.ofFloatModel_pack];exact Model.ofModel_ofInt_eq_roundDyadic _ Aa (k:ℤ) have e:(FloatLib.Numerics.Dyadic.ofScaledInt k 0).toReal=k:=by rw[<-ж,FloatLib.Numerics.Dyadic.ofScaledInt_toRat];simp have c:(k:ℝ)<=2^(1000:ℤ):=by have h:(k:ℝ)<=2^53:=by exact_mod_cast d.le have i:(2:ℝ)^53<=2^256*2^42:=ב calc (k:ℝ)<=2^53:=h _<=2^256*2^42:=i _<=Fg:=Aq _<=Fg*2:=by linarith [Ap] _<=_:=Ar have a:Model.isFinite (Fe f)=true:=by rw[b];apply Model.isFinite_roundDyadic_of_isIEEE_of_abs_toReal_le_posMaxFinite _ Aa;rw[e,У (Э _)];exact c.trans Af refine ⟨by rw[<-Ad];exact a,?_⟩;rw[Ac,b,Model.toReal_roundDyadic_eq_roundAt _ Aa _ (b▸a),e];have:=Ax k 0 (by simpa using d) ב;simpa using this lemma A2 (m:UInt32) (h:m.toNat<2^53):m.toFloat.isFinite=true∧R m.toFloat=m.toNat:=A1 _ _ h rfl lemma A3 (m:UInt64) (h:m.toNat<2^53):m.toFloat.isFinite=true∧R m.toFloat=m.toNat:=A1 _ _ h rfl lemma A4:(0:Float).toModel.unpack=.zero .positive:=by rfl lemma A5:(0:Float).isFinite=true∧R 0=0:=by refine ⟨?_,?_⟩;. change (0:Float).toModel.unpack.isFinite=true;rw[A4];rfl . rw[Ay,A4];simp def Fh (i:ℕ):UInt64:= let e:=(i%256).toUInt64 let s:UInt64:=if i≥256 then 0x8000000000000000 else 0 if e==0 then s else s ||| ((e+873)<<<(52:UInt64)) lemma A6 (i:ℕ):FW i=Float.ofBits (Fh i):=by unfold FW Fh;dsimp only;split<;>rfl def Fi (i:ℕ):Bool:= match Float.Model.UnpackedFloat.unpack Float.Model.Format.binary64 (Fh i).toBitVec with | .finite s m e _=>(Model.modelSignBit s==decide (256<=i))&&m==2^52&& e==((i%256:ℕ):ℤ)-202&&(i%256 !=0) | .zero _=>i%256==0 | _=>false lemma A7:∀i,i<512->Fi i=true:=by decide+kernel lemma A8 (i:ℕ) (d:i<512): (FW i).isFinite=true∧R (FW i)=if i%256=0 then 0 else (if 256<=i then -1 else 1)*2^(((i%256:ℕ):ℤ)-150):=by have a:=A7 i d rw[A6] have c:(Float.ofBits (Fh i)).toModel.unpack=Float.Model.UnpackedFloat.unpack Float.Model.Format.binary64 (Fh i).toBitVec:=Model.unpack_pack_unpack _ _ unfold Fi at a rw[Ay,c] change (Float.ofBits (Fh i)).toModel.unpack.isFinite=true∧_ rw[c] cases b:Float.Model.UnpackedFloat.unpack Float.Model.Format.binary64 (Fh i).toBitVec with | notANumber=>rw[b] at a;simp at a | infinity s=>rw[b] at a;simp at a | zero s=> rw[b] at a simp only[beq_iff_eq] at a refine ⟨rfl,?_⟩ simp[a] | finite s m e h=> rw[b] at a simp only[Bool.and_eq_true,beq_iff_eq,bne_iff_ne] at a obtain ⟨⟨⟨f,g⟩,j⟩,k⟩:=a refine ⟨rfl,?_⟩ have e:((2^52:ℕ):ℝ)*2^(((i%256:ℕ):ℤ)-202)=2^(((i%256:ℕ):ℤ)-150):=by rw[Nat.cast_pow,Nat.cast_ofNat,<-Ц,<-М ב] congr 1 push_cast ring rw[Model.unpackedToReal_finite,Ae,j,f,g,mul_assoc,e] simp only[decide_eq_true_eq,k,↓reduceIte] lemma A9 (i:USize) (h:i.toNat>>(23:UInt32)).toNat=w.toNat/2^23:=by rw[л,Ю];rfl lemma BD (w:UInt32):(expOf w).toNat=w.toNat/2^23%2^8:=by unfold expOf;rw[О,BC];exact В _ 8 lemma BE (w:UInt32):signOf w=decide (2^31<=w.toNat):=by have b:=w.toNat_lt;unfold signOf;have h:((w&&&0x80000000).toNat)=(w.toNat/2^31%2)*2^31:=by rw[О];show w.toNat&&&2^31=_;rw[Nat.and_two_pow,Nat.testBit_eq_decide_div_mod_eq];have a:w.toNat/2^31%2=0∨w.toNat/2^31%2=1:=א;rcases a with a | a<;>rw[a]<;>rfl rw[Bool.eq_iff_iff];simp only[bne_iff_ne,ne_eq,decide_eq_true_eq];rw[<-И,h];simp only[UInt32.toNat_zero];omega lemma BF (w:UInt32):((w&&&0x7FFFFF) ||| 0x800000).toNat=2^23+w.toNat%2^23:=by rw[UInt32.toNat_or,BB,Nat.or_comm];have h:w.toNat%2^23<2^23:=Ъ _ (by positivity);have:=щ h 1;simpa using this.symm lemma BG (w:UInt32) (h:FX w=true):w.toNat%2^31=0∨(2^23<=w.toNat%2^31∧w.toNat%2^31<0x7F800000):=by have a:=BA w;have b:=(w&&&0x7FFFFFFF).toNat_lt;unfold FX at h;simp only[Bool.or_eq_true,beq_iff_eq,decide_eq_true_eq] at h;rcases h with h | h;. left;rw[<-a,h];rfl . right;rw[Ж,UInt32.toNat_sub] at h;rw[<-a];generalize (w&&&0x7FFFFFFF).toNat=v at*;simp at h;omega noncomputable def Fj (v:ℕ):ℝ:= if v=0 then 0 else ((2^23+v%2^23:ℕ):ℝ)*2^(((v/2^23:ℕ):ℤ)-150) lemma BH (v:ℕ):0<=Fj v:=by unfold Fj;split_ifs<;>positivity lemma BI (w:UInt32) (e:FX w=true):wv w=(if 2^31<=w.toNat then -1 else 1)*Fj (w.toNat%2^31):=by have i:=w.toNat_lt;have f:=BG w e;have a:=BD w;have c:(fracOf w).toNat=w.toNat%2^23:=BB w;have b:expOf w≠255:=by intro h;rw[h] at a;change 255=_ at a;omega have g:wv w=(decodeD w).toReal:=by unfold wv ofW;rw[Model.toReal_eq,toDyadic_ofUInt32 w b] rw[g];unfold decodeD Fj;by_cases d:w.toNat%2^31=0 . have e0:expOf w=0:=by apply И.mp;rw[a];show _=0;omega have f0:fracOf w=0:=by apply И.mp;rw[c];show _=0;omega simp only[e0,f0,d,↓reduceIte];simp[FloatLib.Numerics.Dyadic.toReal,FloatLib.Numerics.Dyadic.signedSignificand] . have e0:expOf w≠0:=by intro h;rw[h] at a;change 0=_ at a;omega simp only[e0,d,↓reduceIte];have f1:w.toNat%2^31%2^23=(fracOf w).toNat:=by rw[c];omega have f2:w.toNat%2^31/2^23=(expOf w).toNat:=by rw[a];omega rw[f1,f2];simp only[FloatLib.Numerics.Dyadic.toReal,FloatLib.Numerics.Dyadic.signedSignificand,BE];simp;split_ifs<;>ring lemma BJ (v:ℕ) (h:v<0x7F800000):Fj v<=2^128:=by unfold Fj;split_ifs with d;. positivity . have b:((2^23+v%2^23:ℕ):ℝ)<=2^24:=by have:2^23+v%2^23<=2^24:=א;exact_mod_cast this have a:(2:ℝ)^(((v/2^23:ℕ):ℤ)-150)<=2^(104:ℤ):=Ф ב א;have c:(2:ℝ)^(104:ℤ)=2^104:=ב;rw[c] at a calc _<=(2:ℝ)^24*2^104:=г b a (by positivity) (by positivity) _=2^128:=ב lemma BK (a b:ℕ) (d:a<=b) (e:a=0∨2^23<=a):Fj a<=Fj b:=by rcases e with rfl | e;. simpa [Fj] using BH b unfold Fj;simp only[show¬a=0 by omega,show¬b=0 by omega,↓reduceIte];have c:a/2^23<=b/2^23:=Nat.div_le_div_right d;rcases c.eq_or_lt with f | j;. rw[f];apply Б _ (by positivity);have:2^23+a%2^23<=2^23+b%2^23:=א;exact_mod_cast this . have g:((2^23+a%2^23:ℕ):ℝ)<=2^23*2:=by have:2^23+a%2^23<=2^23*2:=א;exact_mod_cast this have h:(2:ℝ)^(((a/2^23:ℕ):ℤ)-150)*2<=2^(((b/2^23:ℕ):ℤ)-150):=by rw[<-zpow_add_one₀ ב];exact Ф ב א have i:(2:ℝ)^23<=((2^23+b%2^23:ℕ):ℝ):=by have:2^23<=2^23+b%2^23:=א;exact_mod_cast this calc _<=((2:ℝ)^23*2)*2^(((a/2^23:ℕ):ℤ)-150):= Б g (by positivity) _=2^23*(2^(((a/2^23:ℕ):ℤ)-150)*2):=by ring _<=_:=г i h (by positivity) (by positivity) lemma BL (w:UInt32) (j:FX w=true):(dv w).isFinite=true∧R (dv w)=wv w:=by have r:=w.toNat_lt;have b:=BG w j;have c:=BF w;have d:=A2 ((w&&&0x7FFFFF) ||| 0x800000) (by rw[c];omega);have m:(w>>>(23:UInt32)).toUSize.toNat=w.toNat/2^23:=by rw[Т,BC] have e:=A8 (w.toNat/2^23) א;unfold dv;rw[A9,m];have f: |R ((w&&&0x7FFFFF) ||| 0x800000).toFloat| ≤2^24:=by rw[d.2,c,У (Э _)];have:2^23+w.toNat%2^23<=2^24:=א;exact_mod_cast this have g: |R (FW (w.toNat/2^23))| ≤2^106:=by rw[e.2];split_ifs;. simp all_goals simp only[abs_mul,abs_neg,abs_one,one_mul];rw[abs_of_pos (by positivity)];have:(2:ℝ)^(((w.toNat/2^23%256:ℕ):ℤ)-150)<=2^(106:ℤ):=Ф ב א;simpa using this have n: |R ((w&&&0x7FFFFF) ||| 0x800000).toFloat| * |R (FW (w.toNat/2^23))| ≤2^(1000:ℤ):=by have h:=Aq;have e1:(2:ℝ)^24<=2^256*2^42:=ב;have e2:(2:ℝ)^106<=2^256*2^42:=ב;exact (г (f.trans (e1.trans h)) (g.trans (e2.trans h)) (П _) Ap.le).trans As obtain ⟨o,p⟩:=Am _ _ d.1 e.1 n;refine ⟨o,?_⟩;rw[p,d.2,e.2,BI w j,c];rcases b with q | ⟨h,s⟩;. have e0:w.toNat/2^23%256=0:=א;rw[q];simp only[e0,↓reduceIte,mul_zero,Model.roundAt_zero];simp[Fj] . have e0:¬w.toNat/2^23%256=0:=א;have e1:w.toNat%2^31/2^23=w.toNat/2^23%256:=א;have e2:w.toNat%2^31%2^23=w.toNat%2^23:=א;have e3:(256<=w.toNat/2^23)↔2^31<=w.toNat:=א;unfold Fj;rw[e1,e2];simp only[e0,e3,show¬w.toNat%2^31=0 by omega,↓reduceIte];have i:-1074<=((w.toNat/2^23%256:ℕ):ℤ)-150:=א;have a:2^23+w.toNat%2^23<2^53:=א;generalize ((w.toNat/2^23%256:ℕ):ℤ)-150=k at i⊢;generalize 2^23+w.toNat%2^23=M at a⊢;by_cases l:2^31<=w.toNat;. have:=Ax (-(M:ℤ)) k (by simpa using a) i;simp only[l,↓reduceIte];push_cast at this;rw[show (M:ℝ)*(-1*2^k)=-(M:ℝ)*2^k by ring,show -1*((M:ℝ)*2^k)=-(M:ℝ)*2^k by ring];exact this . have:=Ax (M:ℤ) k (by simpa using a) i;simp only[l,↓reduceIte,one_mul];push_cast at this;exact this def Fk (l:List Float):Float:=l.foldl (.+·) 0 noncomputable def Fl (l:List Float):ℝ:=(l.map λq=>|R q|).sum noncomputable def Fm (l:List Float):ℝ:=(l.map R).sum lemma BM (l:List Float):0<=Fl l:=by induction l with | nil=>simp[Fl] | cons q l ih=>simp only[Fl,List.map_cons,List.sum_cons] at ih⊢;positivity lemma BN (l:List Float) (q:Float):Fl (l++[q])=Fl l+ |R q|:=by simp[Fl] lemma BO (l:List Float) (q:Float):Fm (l++[q])=Fm l+R q:=by simp[Fm] lemma BP (l:List Float) (q:Float):Fk (l++[q])=Fk l+q:=by simp[Fk] lemma BQ (l:List Float): |Fm l| ≤Fl l:=by induction l with | nil=>simp[Fl,Fm] | cons q l ih=>simp only[Fl,Fm,List.map_cons,List.sum_cons] at ih⊢;exact (Ч _ _).trans ד lemma BR (l:List Float) (o:∀q∈l,q.isFinite=true) (c:l.length<=2^21) (p:Fl l<=Fg/4): (Fk l).isFinite=true∧ |R (Fk l)-Fm l| ≤2*l.length*(1/2^53*(Fl l+Ff)):=by induction l using List.reverseRecOn with | nil=> simp only[Fk,List.foldl_nil,List.length_nil] refine ⟨A5.1,?_⟩ simp[A5.2,Fm] | append_singleton l q ih=> rw[BN] at p have I:=BM l have f:=П (R q) obtain ⟨v,s⟩:=ih (λx w=>o x (by simp[w])) (by simp at c;omega) ד have t:(l.length:ℝ)+1<=2^21:=by simp at c exact_mod_cast c have y:(0:ℝ)<=l.length:=Э _ have u:=BQ l have i:=An have d:=Ao have J:=Ap have g:=Aq rw[BP,BN,BO,List.length_append,List.length_singleton] have z:(8:ℝ)<=Fg:=by have:(8:ℝ)<=2^256*2^42:=ב linarith only [i,d,g] have A:Ff<=1:=by have:(1/2^200*(1/2^200):ℝ)<=1:=ב linarith only [i,d] push_cast set r:=R (Fk l) set a:=R q set P:=Fl l set S:=Fm l set k:ℝ:=(l.length:ℝ) set W:=(1/2^53:ℝ)*(P+ |a| +Ff) with b have B:(1/2^53:ℝ)*(P+Ff)<=W:=by rw[b] apply Й _ ב linarith only [f] have j:0<=W:=by rw[b];positivity have C: |r-S| ≤2*k*W:=s.trans (Й B (by positivity)) have h:2*k*(1/2^53)<=1:=by norm_num at t⊢ linarith only [i,d,t] have m:(1/2^53:ℝ)* |r-S| ≤W:= calc (1/2^53:ℝ)* |r-S| ≤1/2^53*(2*k*W):= Й C ב _=(2*k*(1/2^53))*W:=by ring _<=1*W:=Б h j _=W:=one_mul _ have D: |r-S| ≤P+1:= calc |r-S| ≤2*k*(1/2^53*(P+Ff)):=s _=(2*k*(1/2^53))*(P+Ff):=by ring _<=1*(P+Ff):=Б h (by positivity) _<=P+1:=ד have E: |r| ≤Fg:=by have e:r=(r-S)+S:=by ring have:=Ч (r-S) S rw[<-e] at this linarith only [i,d,g,f,p,u,b,m,this] have F: |a| ≤Fg:=ד obtain ⟨n,K⟩:=Au (Fk l) q v (o q ג) E F refine ⟨n,?_⟩ have t1: |R (Fk l+q)-(S+a)| ≤ |R (Fk l+q)-(r+a)| + |r-S|:=by have e:R (Fk l+q)-(S+a)=(R (Fk l+q)-(r+a))+(r-S):=by ring rw[e] exact Ч _ _ have t2: |r+a| ≤ |r-S| +P+ |a|:=by have e:r+a=(r-S)+S+a:=by ring rw[e] have G:=Ч ((r-S)+S) a have H:=Ч (r-S) S linarith only [u,G,H] have t3:(1/2^53:ℝ)*(|r+a| +Ff)<=1/2^53* |r-S| +W:=by rw[b,<-mul_add] apply Й _ ב linarith only [t2] calc |R (Fk l+q)-(S+a)| ≤W+W+2*k*W:=ד _=2*(k+1)*W:=by ring lemma BS (n:ℕ) (l:n<2^20):(Fd n).isFinite=true∧R (Fd n)=((n:ℝ)+8)/2^51:=by have a:(n.toUInt64+8).toNat=n+8:=by have g:(8:UInt64).toNat=8:=rfl;simp[UInt64.toNat_add,g];omega have b:=A3 (n.toUInt64+8) (by rw[a];omega);have c:(Float.ofBits 0x3CC0000000000000).toModel.unpack=.finite .positive (2^52) (-103) (by decide):=by rfl have h:(Float.ofBits 0x3CC0000000000000).isFinite=true:=by change (Float.ofBits 0x3CC0000000000000).toModel.unpack.isFinite=true;rw[c];rfl have d:R (Float.ofBits 0x3CC0000000000000)=1/2^51:=by rw[Ay,c,Model.unpackedToReal_finite,Ae];simp;norm_num have i:(n:ℝ)+8<=2^21:=by have:n+8<=2^21:=א;exact_mod_cast this obtain ⟨j,k⟩:=Am _ _ b.1 h (by rw[b.2,d,a];have m:(1:ℝ)<=2^256*2^42:=ב;have f:=Aq;have o:(2:ℝ)^21<=2^256*2^42:=ב;refine ظ (г ?_ ?_ (П _) Ap.le) As;. rw[Nat.cast_add,У (by positivity)];push_cast;linarith only [i,f] . rw[У (by positivity)];have:(1:ℝ)/2^51<=1:=ב linarith only [f]) unfold Fd;refine ⟨j,?_⟩;rw[k,b.2,d,a];have:=Ax ((n:ℤ)+8) (-51) א ב;push_cast at this⊢;have e:(2:ℝ)^(-51:ℤ)=1/2^51:=ב;rw[e] at this;rw[this];ring lemma BT (c Y S T E z:ℝ) (u:8<=c) (b:c<=2^20+8) (i:z<=1/2^200*(1/2^200)) (j:0<=Y) (v: |S| ≤2*Y) (w: |T-Y| ≤Y/2^30+1/2^250) (k: |E-c/2^51*T| ≤1/2^53*(|c/2^51*T| +z)) (f:1/2^127≤ |S+E| +1/2^53*(|S+E| +z)):4*(c-7)*(1/2^53*Y)+1/2^53*(|S| + |E| +z)(first | linarith only [j,l] | linarith only [j,m] | linarith) have o:c/2^51<=1/2^30:=by have:(2:ℝ)^20+8<=2^21:=ב calc c/2^51<=2^21/2^51:=by gcongr;linarith only [b] _=1/2^30:=ב set G:=c/2^51*T with a have y: |G| ≤(2*Y+1/2^250)/2^30:=by rw[a,abs_mul,abs_of_pos (by positivity)] calc _<=(1/2^30:ℝ)*(2*Y+1/2^250):= г o n (П _) (by positivity) _=_:=by ring have g: |E| ≤ |E-G| + |G|:=by have e:E=(E-G)+G:=by ring have:=Ч (E-G) G;rwa [<-e] at this have p:=Ч S E;have A:=П G;have B:=П E;have C:1/2^129<=Y:=ד;have D:Y-Y/2^30-1/2^250<=T:=ד;have F:0<=Y-Y/2^30-1/2^250:=ד;have H:0<=T:=ד;have q:0<=G:=by rw[a];positivity rw[У q] at k g y;have r:=(abs_le.mp k).1;have h:c*(Y-Y/2^30-1/2^250)/2^51<=G:=by rw[a,show c/2^51*T=c*T/2^51 by ring];gcongr have s:c*Y<=2^21*Y:=by have:c<=2^21:=by have:(2:ℝ)^20+8<=2^21:=ב;linarith only [b] exact Б this j have t:c*(Y-Y/2^30-1/2^250)=c*Y-c*Y/2^30-c*(1/2^250):=by ring rw[t] at h have I:c*(1/2^250)<=2^21*(1/2^250):=by have:c<=2^21:=by have:(2:ℝ)^20+8<=2^21:=ב;linarith only [b] exact Б this (by positivity) have d:4*(c-7)*(1/2^53*Y)=c*Y/2^51-28*Y/2^53:=by ring rw[d];linarith only [b,i,v,f,k,g,p,r,h,s] lemma BU (n:ℕ) (C:n<2^20) (s t:Float) (D:s.isFinite=true) (G:t.isFinite=true) (X Y:ℝ) (d:0<=Y) (q:Y<=Fg/8) (H: |R s-X| ≤4*((n:ℝ)+1)*(1/2^53*Y)) (E: |R t-Y| ≤Y/2^30+1/2^250) (I: |R s| ≤2*Y) (c:(2:ℝ)^(-127:ℤ)≤ |R (s+Fd n*t)|):R (s-Fd n*t)(first | linarith only [p,key,z,B] | linarith only [o,key,y,A] | linarith) lemma BV (g h:ℕ->Float) (l:List ℕ) (a b:Float): l.foldl (λ(acc:F1) t=>F1.mk (acc.s+g t) (acc.t+h t)) ⟨a,b⟩=⟨(l.map g).foldl (.+·) a,(l.map h).foldl (.+·) b⟩:=by induction l generalizing a b with | nil=>rfl | cons x l ih=>simp only[List.foldl_cons,List.map_cons,ih] lemma BW (l:List Float) (c:∀q∈l,q.isFinite=true):Fl (l.map Float.abs)=Fl l∧Fm (l.map Float.abs)=Fl l:=by induction l with | nil=>simp[Fl,Fm] | cons q l ih=>obtain ⟨a,b⟩:=ih (λx d=>c x (by simp[d]));have e:=(A0 q (c q ג)).2;simp only[Fl,Fm,List.map_cons,List.sum_cons,List.map_map] at a b⊢;simp only[Function.comp_def,e,abs_abs];simp only[Function.comp_def] at a b;rw[a,b];simp lemma BX (ts:List ℕ) (q:ℕ->Float) (p:ℕ->ℝ) (i:∀t∈ts,|R (q t)-p t| ≤1/2^53*(|p t| +Ff)): |Fm (ts.map q)-(ts.map p).sum| ≤1/2^53*((ts.map λt=>|p t|).sum+ts.length*Ff)∧ Fl (ts.map q)<=(ts.map λt=>|p t|).sum+1/2^53*((ts.map λt=>|p t|).sum+ts.length*Ff)∧ (ts.map λt=>|p t|).sum<=2*Fl (ts.map q)+ts.length*Ff:=by induction ts with | nil=>simp[Fl,Fm] | cons x ts ih=> obtain ⟨a,b,c⟩:=ih (λt j=>i t (by simp[j])) have d:=i x ג simp only[Fl,Fm,List.map_cons,List.sum_cons,List.map_map,List.length_cons] at a b c⊢ simp only[Function.comp_def] at a b c⊢ have k:=An obtain ⟨l,m⟩:=abs_le.mp d obtain ⟨n,o⟩:=abs_le.mp a have f: |p x| ≤ |R (q x)| +1/2^53*(|p x| +Ff):=by have e:p x=R (q x)-(R (q x)-p x):=by ring have:=abs_sub (R (q x)) (R (q x)-p x) rw[<-e] at this linarith only [d,this] have g: |R (q x)| ≤ |p x| +1/2^53*(|p x| +Ff):=by have e:R (q x)=p x+(R (q x)-p x):=by ring have:=Ч (p x) (R (q x)-p x) rw[<-e] at this linarith only [d,this] have h:=П (p x) refine ⟨abs_le.mpr ⟨?_,?_⟩,?_,?_⟩<;>push_cast<;>(first | linarith only [l,n] | linarith only [m,o] | linarith only [b,g] | linarith only [c,k,f,h] | linarith) lemma BY (ts:List ℕ) (f:ℕ->ℝ) (M:ℝ) (h:∀t∈ts,f t<=M):(ts.map f).sum<=ts.length*M:=by induction ts with | nil=>simp | cons x ts ih=>have a:=ih (λt b=>h t (by simp[b]));have c:=h x ג;simp only[List.map_cons,List.sum_cons,List.length_cons];push_cast;linarith only [a,c] lemma BZ (w:UInt32) (a:FX w=true): |wv w| =Fj (w.toNat%2^31):=by rw[BI w a,abs_mul,У (BH _)];split_ifs<;>simp lemma Ba (w:UInt32) (a:FX w=true): |wv w| ≤2^128:=by rw[BZ w a];apply BJ;rcases BG w a with h | h<;>omega lemma Bb (w:UInt32) (a:FX w=true) (h:w&&&0x7FFFFFFF=0):wv w=0:=by rw[BI w a,<-BA w,h];simp[Fj] lemma Bc:(2:ℝ)^128<=Fg:=by have h:(2:ℝ)^128<=2^256*2^42:=ב;linarith [Aq] lemma Bd (a b:UInt32) (d:FX a=true) (e:FX b=true): (dv a*dv b).isFinite=true∧ |R (dv a*dv b)-wv a*wv b| ≤1/2^53*(|wv a*wv b| +Ff)∧ |wv a*wv b| ≤2^256:=by obtain ⟨fa,ra⟩:=BL a d obtain ⟨fb,rb⟩:=BL b e have la:=Ba a d have lb:=Ba b e have c: |wv a*wv b| ≤2^256:=by rw[abs_mul] calc |wv a| * |wv b| ≤2^128*2^128:=г la lb (П _) (by positivity) _=2^256:=ב obtain ⟨g,f⟩:=Aw _ _ fa fb (by rw[ra];exact la.trans Bc) (by rw[rb];exact lb.trans Bc) rw[ra,rb] at f exact ⟨g,f,c⟩ lemma Be (n:ℕ) (xw ww:ℕ->UInt32) (bw:UInt32) (l:List ℕ) (d:l.Nodup) (b:∀t∈l,tt∉l->wv (xw t)*wv (ww t)=0):Fc n xw ww bw=(l.map λt=>wv (xw t)*wv (ww t)).sum+wv bw:=by unfold Fc;congr 1;rw[<-List.sum_toFinset _ d];symm;apply Finset.sum_subset;. intro t a;simp only[List.mem_toFinset] at a;simpa using b t a . intro t a c;exact e t (by simpa using a) (by simpa using c) lemma Bf (n:ℕ) (xw ww:ℕ->UInt32) (bw:UInt32) (c:∀t,tFX (xw t)=true) (d:∀t,tFX (ww t)=true) (l:List ℕ) (e:l.Nodup) (a:∀t∈l,tt∉l->xw t&&&0x7FFFFFFF=0∨ww t&&&0x7FFFFFFF=0):Fc n xw ww bw=(l.map λt=>wv (xw t)*wv (ww t)).sum+wv bw:= Be n xw ww bw l e a λt b g=>by rcases f t b g with h | h . simp[Bb (xw t) (c t b) h] . simp[Bb (ww t) (d t b) h] lemma Bg (n:ℕ) (l:List ℕ) (c:l.Nodup) (a:∀t∈l,tFloat) (p:ℕ->ℝ) (b:Float) (bv:ℝ) (W:∀t∈ts,(g t).isFinite=true∧|R (g t)-p t| ≤1/2^53*(|p t| +Ff)∧ |p t| ≤2^256) (X:b.isFinite=true) (Z:R b=bv) (D: |bv| ≤2^128) (E:(2:ℝ)^(-127:ℤ)≤ |R (Fk (ts.map g++[b])+Fd n*Fk ((ts.map g++[b]).map Float.abs))|): R (Fk (ts.map g++[b])-Fd n*Fk ((ts.map g++[b]).map Float.abs))<(ts.map p).sum+bv∧ (ts.map p).sum+bv(W t F).2.1) have c:=BY ts (λt=>|p t|) _ (λt F=>(W t F).2.2) have r:=BN (ts.map g) b have s:=BO (ts.map g) b have al:=BM (ts.map g) have d:=BM (ts.map g++[b]) rw[Z] at r s have V:(ts.length:ℝ)<=n:=by exact_mod_cast C have G:(0:ℝ)<=ts.length:=Э _ have l:(n:ℝ)+1<=2^20:=by exact_mod_cast hn have j:=An have a:=Ao have ad:Ff<=1:=by have:(1/2^200*(1/2^200):ℝ)<=1:=ב linarith only [j,a] have ap:0<=(ts.map λt=>|p t|).sum:=List.sum_nonneg (by simp only[List.mem_map];rintro _ ⟨t,_,rfl⟩;exact П _) set A:=(ts.map λt=>|p t|).sum set k:ℝ:=(ts.length:ℝ) have H:k*Ff<=2^20:=by calc k*Ff<=k*1:=mul_le_mul_of_nonneg_left ad G _<=2^20:=by dsimp [k];linarith only [V,l] have aq:A<=2^20*2^256:=by refine c.trans (Б ?_ (by positivity)) linarith only [l,j,a,V] have u:=Aq have am:(2:ℝ)^20*2^256*3+2^128+2^20+2<=2^256*2^42/8:=by norm_num have an:Fl (ts.map g++[b])+Ff<=Fg/8:=by have hU:(1/2^53:ℝ)*(A+k*Ff)<=A+k*Ff:=by have:0<=A+k*Ff:=by positivity linarith only [o,ab] linarith only [D,r,l,j,a,V,o,c,H,u] have ar:(1:ℝ)<=Fg/8:=by have:(1:ℝ)<=2^256*2^42/8:=ב linarith only [j,a,u] have f:(ts.map g++[b]).length<=2^21:=by simp;omega obtain ⟨ae,v⟩:=BR _ m f ד obtain ⟨i,w⟩:=BW _ m obtain ⟨af,y⟩:=BR ((ts.map g++[b]).map Float.abs) (by intro q U obtain ⟨x,hx,rfl⟩:=List.mem_map.mp U exact (A0 x (m x hx)).1) (by simpa using f) (by rw[i];linarith only [D,r,l,j,a,V,o,c,H,u]) rw[i,w] at y have ag:(((ts.map g++[b]).length:ℕ):ℝ)=k+1:=by simp[k] have ah:(((ts.map g++[b]).map Float.abs).length:ℝ)=k+1:=by simp[k] rw[ag] at v rw[ah] at y generalize I:Fl (ts.map g++[b])=sa at* set Y:=sa+Ff with z have J:0<=Y:=by positivity have K:0<=(1/2^53:ℝ)*Y:=by positivity have B:2*(k+1)*(1/2^53*Y)<=Y/2^30:=by have h:k+1<=2^20:=ד have:=Б h K norm_num at this⊢ linarith only [j,d,this] have ai: |Fm (ts.map g++[b])| ≤ sa:=by rw[<-I];exact BQ _ obtain ⟨L,M⟩:=abs_le.mp v obtain ⟨N,O⟩:=abs_le.mp y refine BU n hn _ _ ae af _ Y J ד ?_ ?_ ?_ E . have au:sa+k*Ff<=(k+1)*Y:=by rw[z];linarith [Ь G d] have P:(1/2^53:ℝ)*(A+k*Ff)<=2*(k+1)*(1/2^53*Y):=by have h1:A+k*Ff<=2*(sa+k*Ff):=by linarith [П bv] have h2:A+k*Ff<=2*((k+1)*Y):=ד calc (1/2^53:ℝ)*(A+k*Ff)<=1/2^53*(2*((k+1)*Y)):= Й h2 ב _=_:=by ring have Q:4*(k+1)*(1/2^53*Y)<=4*((n:ℝ)+1)*(1/2^53*Y):=Б ד K;obtain ⟨S,T⟩:=abs_le.mp aa;apply abs_le.mpr;constructor<;>(first | linarith only [s,L,P,Q,S] | linarith only [s,M,P,Q,T] | linarith) . apply abs_le.mpr;constructor . have:(0:ℝ)<=1/2^250:=ב;have:Ff<=1/2^250:=by have:(1/2^200*(1/2^200):ℝ)<=1/2^250:=ב;linarith only [j,a] linarith only [j,a,B,N] . linarith only [j,a,B,O] . have e:R (Fk (ts.map g++[b]))=(R (Fk (ts.map g++[b]))-Fm (ts.map g++[b]))+Fm (ts.map g++[b]):=by ring have h1:=Ч (R (Fk (ts.map g++[b]))-Fm (ts.map g++[b])) (Fm (ts.map g++[b]));rw[<-e] at h1;have h2:Y/2^30<=Y:=by apply div_le_self J;norm_num linarith only [j,d,v,B,ai,h1] lemma Bi (n:Nat) (x:n<2^20) (xw ww:Nat->UInt32) (bw:UInt32) (m:∀t,tFX (xw t)=true) (o:∀t,tFX (ww t)=true) (u:FX bw=true) (l:List Nat) (v:l.Nodup) (a:∀t∈l,tt∉l->xw t&&&0x7FFFFFFF=0∨ww t&&&0x7FFFFFFF=0) (s e:Float) (z:let r:=l.foldl (λ(acc:F1) t=>let q:=dv (xw t)*dv (ww t) F1.mk (acc.s+q) (acc.t+q.abs)) ⟨0,0⟩;s=r.s+dv bw∧e=Fd n*(r.t+(dv bw).abs)) (b:(2:ℝ)^(-127:ℤ)≤ |R (s+e)|): R (s-e)Float:=λt=>dv (xw t)*dv (ww t) with C set p:ℕ->ℝ:=λt=>wv (xw t)*wv (ww t) with D have c:l.foldl (λ(acc:F1) t=>let q:=dv (xw t)*dv (ww t) F1.mk (acc.s+q) (acc.t+q.abs)) ⟨0,0⟩= ⟨(l.map g).foldl (.+·) 0,(l.map λt=>(g t).abs).foldl (.+·) 0⟩:= BV g (λt=>(g t).abs) l 0 0 obtain ⟨d,f⟩:=z rw[c] at d f have h:=Bg n l v a have i:∀t∈l,(g t).isFinite=true∧|R (g t)-p t| ≤1/2^53*(|p t| +Ff)∧ |p t| ≤2^256:=λt w=>Bd _ _ (m t (a t w)) (o t (a t w)) obtain ⟨j,k⟩:=BL bw u have A:s=Fk (l.map g++[dv bw]):=by rw[d,BP];rfl have B:e=Fd n*Fk ((l.map g++[dv bw]).map Float.abs):=by rw[f] congr 1 rw[List.map_append,List.map_map,List.map_singleton,BP] rfl rw[A,B] at b⊢ rw[Bf n xw ww bw m o l v a y] exact Bh n x l h g p (dv bw) (wv bw) i j k (Ba bw u) b lemma Bj (n:Nat) (c:n<2^20) (xw ww:Nat->UInt32) (bw:UInt32) (d:∀t,tFX (xw t)=true) (f:∀t,tFX (ww t)=true) (g:FX bw=true) (l:List Nat) (h:l.Nodup) (b:∀t∈l,tt∉l->xw t&&&0x7FFFFFFF=0) (s e:Float) (j:let r:=l.foldl (λ(acc:F1) t=>let q:=dv (xw t)*dv (ww t) F1.mk (acc.s+q) (acc.t+q.abs)) ⟨0,0⟩;s=r.s+dv bw∧e=Fd n*(r.t+(dv bw).abs)) (a:(2:ℝ)^(-127:ℤ)≤ |R (s+e)|): R (s-e)Or.inl (i t k m)) s e j a lemma Bk (H J Rj Rg Rt b z k:ℝ) (a:0<=H) (q:H<=2^128) (o:0<=J) (j:0<=b) (c:0<=z) (d:z<=1/2^200*(1/2^200)) (r:k<=2^20) (s: |Rj-J| ≤2*k*(1/2^53*(J+z))) (t: |Rg-H*Rj| ≤1/2^53*(|H*Rj| +z)) (u: |Rt-(Rg+b)| ≤1/2^53*(|Rg+b| +z)): |Rt-(H*J+b+z)| ≤(H*J+b+z)/2^30+1/2^250:=by have e1: |Rj-J| ≤(J+z)/2^32:=by refine s.trans ?_ have h:0<=(1/2^53:ℝ)*(J+z):=Ь ב (add_nonneg o c) have:=Б r h norm_num at this⊢ linarith only [this] have e2: |H*Rj-H*J| ≤(H*J+H*z)/2^32:=by rw[<-mul_sub,abs_mul,У a] calc H* |Rj-J| ≤H*((J+z)/2^32):=Й e1 a _=_:=by ring have e3:H*z<=1/2^250:=by calc H*z<=2^128*(1/2^200*(1/2^200)):= г q d c ב _<=1/2^250:=ב have e:0<=H*J:=Ь a o have v:0<=H*z:=Ь a c generalize H*J=W at* generalize H*z=Z at* generalize H*Rj=G at* obtain ⟨e2a,e2b⟩:=abs_le.mp e2 obtain ⟨f,g⟩:=abs_le.mp t obtain ⟨l,m⟩:=abs_le.mp u have i: |G| ≤W+(W+Z)/2^32:=by apply abs_le.mpr constructor<;>(first | linarith only [e,e2a] | linarith only [e2b] | linarith) have n: |Rg| ≤2*W+1/2^200:=by apply abs_le.mpr constructor<;>(first | linarith only [d,e,e3,e2a,f,i] | linarith only [d,e,e3,e2b,g,i] | linarith) have p: |Rg+b| ≤2*W+b+1/2^200:=by have:=Ч Rg b rw[У j] at this linarith only [n,this] apply abs_le.mpr constructor<;>(first | linarith only [j,d,e,e3,e2a,f,l,i,p] | linarith only [j,c,e,e3,e2b,g,m,i,p] | linarith) lemma Bl (ts:List ℕ) (f g:ℕ->ℝ) (H:ℝ) (h:∀t∈ts,f t<=H*g t):(ts.map f).sum<=H*(ts.map g).sum:=by induction ts with | nil=>simp | cons x ts ih=>have a:=ih (λt b=>h t (by simp[b]));have c:=h x ג;simp only[List.map_cons,List.sum_cons,mul_add];linarith only [a,c] lemma Bm (n:ℕ) (hn:n<2^20) (ts:List ℕ) (E:ts.length<=n) (g:ℕ->Float) (p:ℕ->ℝ) (b f a:Float) (bv H J K:ℝ) (hg:∀t∈ts,(g t).isFinite=true∧|R (g t)-p t| ≤1/2^53*(|p t| +Ff)) (s:(ts.map λt=>|p t|).sum<=H*J) (F:b.isFinite=true) (G:R b=bv) (ae: |bv| ≤2^128) (hf:f.isFinite=true) (hH:R f=H) (l:0<=H) (u:H<=2^128) (af:a.isFinite=true) (m:0<=J) (I:J<=2^149) (hK:K<=2^20) (L: |R a-J| ≤2*K*(1/2^53*(J+Ff))) (M:(2:ℝ)^(-127:ℤ)≤ |R (Fk (ts.map g++[b])+Fd n*(f*a+b.abs))|): R (Fk (ts.map g++[b])-Fd n*(f*a+b.abs))<(ts.map p).sum+bv∧(ts.map p).sum+bv(hg t ht).2) have v:=BN (ts.map g) b have w:=BO (ts.map g) b have a4:=BM (ts.map g++[b]) rw[G] at v w have hk:(ts.length:ℝ)<=n:=by exact_mod_cast E have ak:(0:ℝ)<=ts.length:=Э _ have a9:(n:ℝ)+1<=2^20:=by exact_mod_cast hn have d:=An have c:=Ao have ba:Ff<=1:=by have:(1/2^200*(1/2^200):ℝ)<=1:=ב linarith only [d,c] have o:0<=(ts.map λt=>|p t|).sum:=List.sum_nonneg (by simp only[List.mem_map];rintro _ ⟨t,_,rfl⟩;exact П _) set A:=(ts.map λt=>|p t|).sum set k:ℝ:=(ts.length:ℝ) have r:=Aq have bb:(1:ℝ)<=Fg/8:=by have:(1:ℝ)<=2^256*2^42/8:=ב linarith only [d,c,r] have al:k<=2^20:=ד have am:2*K*(1/2^53)<=1:=by norm_num at hK⊢ linarith only [d,c,hK] have O: |R a-J| ≤J+1:= calc |R a-J| ≤2*K*(1/2^53*(J+Ff)):=L _=(2*K*(1/2^53))*(J+Ff):=by ring _<=1*(J+Ff):=Б am ד _<=J+1:=ד have P: |R a| ≤2^151:=by have e:R a=(R a-J)+J:=by ring have j:=Ч (R a-J) J rw[<-e,У m] at j have:(2:ℝ)*2^149+1<=2^151:=ב linarith only [I,d,c,O,j] have Q:(2:ℝ)^151<=Fg:=by have:(2:ℝ)^151<=2^256*2^42:=ב linarith only [d,c,r] obtain ⟨an,x⟩:=Aw f a hf af (by rw[hH,У l];linarith [Bc]) (P.trans Q) rw[hH] at x have ao: |H*R a| ≤2^128*2^151:=by rw[abs_mul,У l] exact г u P (П _) ב have ap: |R (f*a)| ≤Fg:=by have e:R (f*a)=(R (f*a)-H*R a)+H*R a:=by ring have j:=Ч (R (f*a)-H*R a) (H*R a) rw[<-e] at j have:(2:ℝ)^128*2^151*2+1<=2^256*2^42:=ב have h2:(1/2^53:ℝ)*(|H*R a| +Ff)≤ |H*R a| +1:=by have:=П (H*R a) linarith only [d,c,this] linarith only [d,c,r,x,ao,j] obtain ⟨aq,y⟩:=A0 b F rw[G] at y obtain ⟨ar,S⟩:=Au (f*a) b.abs an aq ap (by rw[y,abs_abs];linarith [Bc]) rw[y] at S have key2:=Bk H J (R a) (R (f*a)) (R (f*a+b.abs)) |bv| Ff K l u m (П _) d.le c hK L x S have as:H*J<=2^128*2^149:=г u I m ב have a6:0<=H*J:=Ь l m have i:=П bv have T:k*Ff<=2^20*Ff:=Б al d.le have au:H*J+ |bv| +Ff<=Fg/8:=by have:(2:ℝ)^128*2^149+2^128+1<=2^256*2^42/8:=ב linarith only [ae,d,c,r,as] have U:Fl (ts.map g++[b])+Ff<=3/2*(H*J+ |bv| +Ff):=by linarith only [v,d,s,o,N,i,T] have z:(ts.map g++[b]).length<=2^21:=by simp;omega obtain ⟨av,B⟩:=BR _ ah z ד have aw:(((ts.map g++[b]).length:ℕ):ℝ)=k+1:=by simp[k] rw[aw] at B have ax:=BQ (ts.map g++[b]) set Y:=H*J+ |bv| +Ff with ay have V:0<=Y:=ד have W:0<=(1/2^53:ℝ)*Y:=Ь ב V have C:2*(k+1)*(1/2^53*(Fl (ts.map g++[b])+Ff))≤3*(k+1)*(1/2^53*Y):= calc 2*(k+1)*(1/2^53*(Fl (ts.map g++[b])+Ff)) <=2*(k+1)*(1/2^53*(3/2*Y)):=by apply Й _ ד exact Й U ב _=_:=by ring have D:A+k*Ff<=(k+1)*Y:=by have j:A+Ff<=Y:=ד have h2:=Й j (ד:0<=k+1) have h3:=Ь ak o linarith only [d,h2,h3] have bd:(1/2^53:ℝ)*(A+k*Ff)<=(k+1)*(1/2^53*Y):= calc (1/2^53:ℝ)*(A+k*Ff)<=1/2^53*((k+1)*Y):= Й D ב _=_:=by ring have X:4*(k+1)*(1/2^53*Y)<=4*((n:ℝ)+1)*(1/2^53*Y):=Б ד W have az:3*(k+1)*(1/2^53*Y)<=Y/2:=by have h:k+1<=2^20:=ד have:=Б h W norm_num at this⊢ linarith only [d,s,o,i,this] obtain ⟨Z,aa⟩:=abs_le.mp B obtain ⟨ab,ad⟩:=abs_le.mp aj refine BU n hn _ _ av ar _ Y V au ?_ key2 ?_ M . apply abs_le.mpr;constructor<;>(first | linarith only [w,C,D,X,Z,ab] | linarith only [w,C,D,X,aa,ad] | linarith) . have e:R (Fk (ts.map g++[b]))=(R (Fk (ts.map g++[b]))-Fm (ts.map g++[b]))+Fm (ts.map g++[b]):=by ring have j:=Ч (R (Fk (ts.map g++[b]))-Fm (ts.map g++[b])) (Fm (ts.map g++[b]));rw[<-e] at j;linarith only [v,d,s,o,N,i,T,B,ax,C,az,j] lemma Bn (n:ℕ) (M:n<2^20) (ts:List ℕ) (k:ts.length<=n) (g v:ℕ->Float) (p a:ℕ->ℝ) (b f:Float) (bv H:ℝ) (r:∀t∈ts,(g t).isFinite=true∧|R (g t)-p t| ≤1/2^53*(|p t| +Ff)∧ |p t| ≤H* |a t|) (s:∀t∈ts,(v t).isFinite=true∧R (v t)=a t∧|a t| ≤2^128) (u:b.isFinite=true) (w:R b=bv) (y: |bv| ≤2^128) (N:f.isFinite=true) (O:R f=H) (z:0<=H) (A:H<=2^128) (d:(2:ℝ)^(-127:ℤ)≤ |R (Fk (ts.map g++[b])+Fd n*(f*Fk (ts.map λt=>(v t).abs)+b.abs))|): R (Fk (ts.map g++[b])-Fd n*(f*Fk (ts.map λt=>(v t).abs)+b.abs))<(ts.map p).sum+bv∧ (ts.map p).sum+bv(v t).abs)+b.abs)):=by have e:(ts.length:ℝ)<=2^20:=by have:ts.length<=2^20:=א exact_mod_cast this have B:0<=(ts.map λt=>|a t|).sum:=List.sum_nonneg (by simp only[List.mem_map];rintro _ ⟨t,_,rfl⟩;exact П _) have l:=BY ts (λt=>|a t|) _ (λt c=>(s t c).2.2) have C:=Bl ts (λt=>|p t|) (λt=>|a t|) H (λt c=>(r t c).2.2) have D:(ts.map λt=>(v t).abs)=(ts.map v).map Float.abs:=by simp[List.map_map,Function.comp_def] have m:∀q∈ts.map v,q.isFinite=true:=by intro q E obtain ⟨t,c,rfl⟩:=List.mem_map.mp E exact (s t c).1 obtain ⟨h,o⟩:=BW (ts.map v) m have F:Fl (ts.map v)=(ts.map λt=>|a t|).sum:=by simp only[Fl,List.map_map] congr 1 apply List.map_congr_left intro t c simp[(s t c).2.1] rw[D] at d⊢ rw[F] at h o set J:=(ts.map λt=>|a t|).sum have G:J<=2^20*2^128:=l.trans (Б e ב) have I:=Aq have i:((ts.map v).map Float.abs).length<=2^21:=by simp;omega obtain ⟨K,j⟩:=BR ((ts.map v).map Float.abs) (by intro q E obtain ⟨x,P,rfl⟩:=List.mem_map.mp E exact (A0 x (m x P)).1) i (by rw[h] have:(2:ℝ)^20*2^128<=2^256*2^42/4:=ב linarith only [e,l,I]) rw[h,o] at j have L:(((ts.map v).map Float.abs).length:ℝ)=(ts.length:ℝ):=by simp rw[L] at j exact Bm n M ts k g p b f _ bv H J _ (λt c=>⟨(r t c).1,(r t c).2.1⟩) C u w y N O z A K B (G.trans ב) e j d lemma Bo (a:UInt32) (e:FX a=true) (g:a<=0x7FFFFFFF): 0<=wv a∧wv a<=2^128∧ ∀w,FX w=true->w&&&0x7FFFFFFF<=a->|wv w| ≤wv a:=by have d:a.toNat<2^31:=by have:=Ж.mp g change a.toNat<=2147483647 at this omega have b:wv a=Fj a.toNat:=by rw[BI a e,Г d] simp only[show¬2^31<=a.toNat by omega,↓reduceIte,one_mul] refine ⟨by rw[b];exact BH _,ظ (le_abs_self _) (Ba a e),?_⟩ intro w c i have f:=Ж.mp i rw[BA] at f rw[BZ _ c,b] apply BK _ _ f rcases BG _ c with h | h . exact Or.inl h . exact Or.inr h.1 lemma Bp (n:Nat) (I:n<2^20) (xw ww:Nat->UInt32) (bw b:UInt32) (i:∀t,tFX (xw t)=true) (f:∀t,tFX (ww t)=true) (F:FX bw=true) (G:FX b=true) (J:∀t,txw t&&&0x7FFFFFFF<=b) (K:b<=0x7FFFFFFF) (l:List Nat) (H:l.Nodup) (a:∀t∈l,tt∉l->xw t&&&0x7FFFFFFF=0∨ww t&&&0x7FFFFFFF=0) (s e:Float) (M:s=l.foldl (λ(acc:Float) t=>acc+dv (xw t)*dv (ww t)) 0+dv bw∧e=Fd n*(dv b*(l.foldl (λ(acc:Float) t=>acc+(dv (ww t)).abs) 0)+(dv bw).abs)) (d:(2:ℝ)^(-127:ℤ)≤ |R (s+e)|): R (s-e)Float:=λt=>dv (xw t)*dv (ww t) with j set p:ℕ->ℝ:=λt=>wv (xw t)*wv (ww t) with k set v:ℕ->Float:=λt=>dv (ww t) with m obtain ⟨o,q⟩:=M obtain ⟨r,u,w⟩:=Bo b G K obtain ⟨x,y⟩:=BL bw F obtain ⟨z,A⟩:=BL b G have B:∀t∈l,(g t).isFinite=true∧|R (g t)-p t| ≤1/2^53*(|p t| +Ff)∧ |p t| ≤wv b* |wv (ww t)|:=by intro t h have c:=a t h obtain ⟨C,D,-⟩:=Bd _ _ (i t c) (f t c) refine ⟨C,D,?_⟩ simp only[k,abs_mul] exact Б (w _ (i t c) (J t c)) (П _) have E:∀t∈l,(v t).isFinite=true∧R (v t)=wv (ww t)∧|wv (ww t)| ≤2^128:=by intro t h obtain ⟨C,D⟩:=BL _ (f t (a t h)) exact ⟨C,D,Ba _ (f t (a t h))⟩ have N:s=Fk (l.map g++[dv bw]):=by rw[o,BP] simp[Fk,List.foldl_map,j] have O:e=Fd n*(dv b*Fk (l.map λt=>(v t).abs)+(dv bw).abs):=by rw[q] simp[Fk,List.foldl_map,m] rw[N,O] at d⊢ rw[Bf n xw ww bw i f l H a L] exact Bn n I l (Bg n l H a) g v p (λt=>wv (ww t)) (dv bw) (dv b) (wv bw) (wv b) B E x y (Ba bw F) z A r u d end section open ExactRuntime FloatLib.Floats.Formats.BinaryInterchange FloatLib.Floats open FloatLib.Floats.ExecFloat.Binary section open Float.Model Float.Model.UnpackedFloat lemma Bq (m K:Nat): (ExtendedMantissa.ofMantissaAndAccuracy m .exact>>>(K+1))=⟨m/2^(K+1),(m/2^K)%2 !=0,decide (m%2^K≠0)⟩:=by show Nat.repeat ExtendedMantissa.shiftRightOne (K+1) _=_ induction K with | zero=> simp[Nat.repeat,ExtendedMantissa.shiftRightOne,ExtendedMantissa.ofMantissaAndAccuracy,Nat.mod_one] | succ K ih=> show ExtendedMantissa.shiftRightOne (Nat.repeat _ (K+1) _)=_ rw[ih] simp only[ExtendedMantissa.shiftRightOne,ExtendedMantissa.mk.injEq] refine ⟨?_,?_,?_⟩ . rw[ذ,<-Nat.pow_succ] . trivial . rw[Nat.mod_pow_succ];have h:0<2^K:=by positivity by_cases a:m%2^K=0<;>by_cases b:m/2^K%2=0<;>simp[a,b];omega lemma Br (H a b:Nat) (c:b>>(K+1)).roundedMantissa=r:=by rw[Bq,Nat.pow_succ];have j:0<2^K:=by positivity generalize 2^K=H at*;have a:=Nat.div_add_mod m (H*2);have b:m%(H*2) simp[ExtendedMantissa.roundedMantissa,ExtendedMantissa.accuracy,Accuracy.roundToNearestEven,d] . have k:H>>(K+1),T):=by unfold shiftToTargetExponent shiftToExponent simp only[a] have i:(T-e).toNat=K+1:=א rw[i,b] simp only[f,Nat.shiftLeft_zero,Int.natCast_zero,Int.sub_zero,g,Bs m K r c d] lemma Bw (r:Nat) (T:Int) (a:2^23<=r) (b:r<2^24) (e:-149<=T): shiftToTargetExponent Format.binary32 r T .exact=(ExtendedMantissa.ofMantissaAndAccuracy r .exact,T):=by have c:=Bu r 23 a b unfold shiftToTargetExponent shiftToExponent simp only[totalExponent,c,Bt] have d:max (((23:Nat):Int)+1+T-24) (-149)=T:=א simp only[d,sub_self,Int.toNat_zero,Int.natCast_zero,Int.add_zero] rfl lemma Bx (T:Int) (c:-150<=T): shiftToTargetExponent Format.binary32 (2^24) T .exact=(ExtendedMantissa.ofMantissaAndAccuracy (2^23) .exact,T+1):=by have a:(2^24:Nat).log2=24:=Bu _ 24 ב ב unfold shiftToTargetExponent shiftToExponent simp only[totalExponent,a,Bt] have b:max (((24:Nat):Int)+1+T-24) (-149)-T=1:=א rw[b] rfl lemma By (s:Sign) (P:Nat) (E:Int) (a:2^23<=P) (b:P<2^24) (d:-149<=E) (e:02*P*2^(g+2)<2*m+2^(g+2)) (c:P=2^23->33554431*2^(g+2)<4*m):UnpackedFloat.round Format.binary32 s m e=.finite s P E h:=by have e1:2^(g+2)=4*2^g:=by rw[ч];ring have e2:2^(g+1)=2*2^g:=by rw[Nat.pow_succ];ring have e3:2^(g+25)=2^25*2^g:=by rw[ч];ring have e4:2^(g+25+1)=2^26*2^g:=by rw[ч,ч];ring have e5:2^(g+24)=2^24*2^g:=by rw[ч];ring have u:0<2^g:=by positivity rw[e1] at b;by_cases i:2^(g+25)<=m . have j:m.log2=g+25:=by apply Bu m _ i;rw[e4];have:(2*P+1)*(4*2^g)<=(2^25-1)*(4*2^g):=З _ א;omega have d:Format.binary32.targetExponent (totalExponent m e)=E:=by simp only[totalExponent,j,Bt];omega rw[Bv s m e E (g+1) P d א ?_ ?_];. exact By s P E k l q h . rw[e2];by_cases f:P=2^23;. subst f;rw[e3] at i;omega . have:=a f;rw[e1] at this;linarith only [this] . rw[e2];linarith only [b] . have f:P=2^23:=by by_contra n;have o:=a n;rw[e1] at o;have v:2*(2^23+1)*(4*2^g)<=2*P*(4*2^g):=З _ א;rw[e3] at i;omega have o:=c f;subst f;rw[e1] at o;rw[e3] at i;have j:m.log2=g+24:=by apply Bu m _ (by rw[e5];omega);rw[show g+24+1=g+25 from rfl,e3];omega by_cases p:-148<=E . have d:Format.binary32.targetExponent (totalExponent m e)=E-1:=by simp only[totalExponent,j,Bt];omega rw[Bv s m e (E-1) g (2^24) d א א א];exact Bz s E p h . have r:E=-149:=א;have d:Format.binary32.targetExponent (totalExponent m e)=E:=by simp only[totalExponent,j,Bt];omega rw[Bv s m e E (g+1) (2^23) d א (by rw[e2];omega) (by rw[e2];omega)];exact By s _ E ב ב q h lemma B1 (neg:Bool) (m:Nat) (e:Int): Model.roundDyadic Fmt ⟨neg,m,e⟩=Model.ofModel Fmt (UnpackedFloat.round Format.binary32 (Model.modelSign neg) m e):=by simp[Model.roundDyadic,Model.ieeeRoundDyadic] rfl lemma B2 (s:Sign):s.toBitVec.toNat=if s=.negative then 1 else 0:=by cases s<;>rfl lemma B3 (s:Sign) (M:Nat) (E:Int) (h:0simp[Nat.shiftLeft_eq] omega lemma B4 (neg:Bool) (m:Nat) (e:Int) (P:Nat) (E:Int) (p:m≠0) (c:2^23<=P) (d:P<2^24) (q:-149<=E) (r:E+150<=254) (j:2*((m:ℝ)*2^e)<(2*P+1)*2^E) (f:P≠2^23->(2*P-1)*2^E<2*((m:ℝ)*2^e)) (h:P=2^23->33554431*2^E<4*((m:ℝ)*2^e)): toWord (Model.roundDyadic Fmt ⟨neg,m,e⟩)=UInt32.ofNat ((if neg then 2^31 else 0)+(E+150).toNat*2^23+P%2^23):=by have s:02*P*2^(g+2)<2*(m*2^k)+2^(g+2):=by intro b have i:=f b rw[n,a] at i have:(2:ℝ)*P*((2^(g+2):Nat):ℝ)<2*((m*2^k:Nat):ℝ)+((2^(g+2):Nat):ℝ):=я ד l.le exact_mod_cast this have i:P=2^23->33554431*2^(g+2)<4*(m*2^k):=by intro b have i:=h b rw[n,a] at i have:(33554431:ℝ)*((2^(g+2):Nat):ℝ)<4*((m*2^k:Nat):ℝ):=я ד l.le exact_mod_cast this rw[B1,<-ExactRuntime.round_scale _ _ m e k p,B0 _ (m*2^k) (e-k) P E g s c d q o t u i] simp only[toWord,Model.toNatBits,Model.ofModel,Model.ofModelBits] congr 1 show (UnpackedFloat.pack Format.binary32 _).toNat=_ rw[B3 _ _ _ _ c d א א] cases neg<;>simp[Model.modelSign] end abbrev Fn:=ExecFloat.Binary.format (exponentBits:=11) (fractionBits:=52) lemma B5 (f:Float):Model.expField (toModel (ofFloat f))=f.toBits.toNat/2^52%2^11:=by show ((f.toBits.toBitVec>>>52)&&&BitVec.ofNat 64 2047).toNat=_;rw[BitVec.toNat_and,BitVec.toNat_ushiftRight,BitVec.toNat_ofNat,Ю];exact В _ 11 lemma B6 (f:Float):Model.fracField (toModel (ofFloat f))=f.toBits.toNat%2^52:=by show (f.toBits.toBitVec&&&BitVec.ofNat 64 (2^52-1)).toNat=_;rw[BitVec.toNat_and,BitVec.toNat_ofNat];exact В _ 52 lemma B7 (f:Float):Model.signBit (toModel (ofFloat f))=decide (2^63<=f.toBits.toNat):=by rw[Model.signBit_eq_msb];show f.toBits.toBitVec.msb=_;rw[BitVec.msb_eq_decide];rfl lemma B8 (f:Float) (s:Bool) (E F:Nat) (m:1<=E) (n:E<2047) (g:F<2^52) (h:f.toBits.toNat=(if s then 2^63 else 0)+E*2^52+F):Model.toDyadic? (toModel (ofFloat f))=some ⟨s,2^52+F,(E:Int)-1075⟩:=by have i:=B5 f;have j:=B6 f;have k:=B7 f;have b:f.toBits.toNat/2^52%2^11=E:=by split at h<;>omega have c:f.toBits.toNat%2^52=F:=by split at h<;>omega have d:decide (2^63<=f.toBits.toNat)=s:=by cases s;. simp only[Bool.false_eq_true,ite_false] at h;simp;omega . simp only[ite_true] at h;simp;omega rw[b] at i;rw[c] at j;rw[d] at k;have l:=Model.ofFields_signBit_expField_fracField (toModel (ofFloat f));rw[i,j,k] at l;rw[<-l];have a:Model.isFinite (Model.ofFields Fn s E F)=true:=by rw[Model.isFinite_ofFields Fn _ _ _ (by show E<2^11;omega) g];show (E !=2047)=true;simp;omega rw[Model.toDyadic?_ofFields_of_isFinite Fn _ _ _ (by show E<2^11;omega) g a];have e:E≠0:=א;simp only[e,ite_false,show Fn.exponentBias=1023 from rfl,show Fn.fracWidth=52 from rfl];simp only[show Model.pow2 52=2^52 from rfl];congr 2;simp only[Int.ofNat_eq_natCast];push_cast;ring lemma B9 (f:Float) (d:FloatLib.Numerics.Dyadic) (h:Model.toDyadic? (toModel (ofFloat f))=some d):f.isFinite=true:=by rw[Model.toDyadic?_ieee_eq_model _ (by decide)] at h;show (Model.toModel (toModel (ofFloat f))).isFinite=true;revert h;generalize Model.toModel (toModel (ofFloat f))=u;cases u<;>simp[Model.unpackedToDyadic?,Float.Model.UnpackedFloat.isFinite] lemma CA (f:Float) (s:Bool) (E F:Nat) (a:1<=E) (c:E<2047) (d:F<2^52) (h:f.toBits.toNat=(if s then 2^63 else 0)+E*2^52+F): f.isFinite=true∧R f=(if s then -1 else 1)*((2^52+F:Nat):ℝ)*2^((E:Int)-1075):=by have b:=B8 f s E F a c d h refine ⟨B9 f _ b,?_⟩ rw[R,Model.toReal_eq,b] cases s<;>simp[FloatLib.Numerics.Dyadic.toReal,FloatLib.Numerics.Dyadic.signedSignificand] def Fo (A:Nat) (S:Bool) (ex fr:Nat):Prop:= ∃M,A=(if S then 2^63 else 0)+M∧(ex*2^23+fr)*2^29>>(29:UInt64)).toNat=(A.toNat+268435455)%2^64/2^29:=by rw[м,Ы];norm_num [Nat.shiftRight_eq_div_pow] lemma CD (x:UInt64):((x>>>(23:UInt64))&&&(0x7FF:UInt64)).toNat=x.toNat/2^23%2^11:=by rw[э,м];have:=В (x.toNat>>>23) 11;norm_num [Nat.shiftRight_eq_div_pow] at this⊢;exact this lemma CE (v:UInt64) (h:v-(897:UInt64)<(254:UInt64)):897<=v.toNat∧v.toNat<1151:=by rw[р,UInt64.toNat_sub] at h;have a:=v.toNat_lt;norm_num at h a;omega lemma CF (x:UInt64) (f:x.toNat<2^35) (g:897<=x.toNat/2^23%2^11) (a:x.toNat/2^23%2^11<1151): (((x>>>(34:UInt64))<<<(31:UInt64)) ||| ((x&&&(0x3FFFFFFFF:UInt64))-((896:UInt64)<<<(23:UInt64)))).toUInt32= UInt32.ofNat ((if decide (2^34<=x.toNat) then 2^31 else 0)+(x.toNat/2^23%2^11-896)*2^23+x.toNat%2^23):=by have b:((x>>>(34:UInt64))<<<(31:UInt64)).toNat=(x.toNat/2^34)*2^31:=by rw[UInt64.toNat_shiftLeft,м] norm_num [Nat.shiftRight_eq_div_pow,Nat.shiftLeft_eq] omega have c:((x&&&(0x3FFFFFFFF:UInt64))-((896:UInt64)<<<(23:UInt64))).toNat=x.toNat%2^34-896*2^23:=by have a:(x&&&(0x3FFFFFFFF:UInt64)).toNat=x.toNat%2^34:=by rw[э] exact В _ 34 have d:((896:UInt64)<<<(23:UInt64))=7516192768:=by decide rw[d,UInt64.toNat_sub_of_le] . rw[a];rfl . rw[UInt64.le_iff_toNat_le,a];norm_num;omega have e:(x.toNat/2^34)*2^31 ||| (x.toNat%2^34-896*2^23)=(x.toNat/2^34)*2^31+(x.toNat%2^34-896*2^23):=by rw[о (x.toNat/2^34)] exact (щ א _).symm apply И.mp rw[UInt64.toNat_toUInt32,UInt64.toNat_or,b,c,e,е] by_cases h:2^34<=x.toNat . simp only[h,decide_true,ite_true];omega . simp only[h,decide_false,Bool.false_eq_true,ite_false];omega lemma CG (s e:Float) (h:Fa s e≠0xFFFFFFFF): ∃(S:Bool) (ex fr:Nat),897<=ex∧ex<1151∧fr<2^23∧Fa s e=UInt32.ofNat ((if S then 2^31 else 0)+(ex-896)*2^23+fr)∧Fo (s+e).toBits.toNat S ex fr∧Fo (s-e).toBits.toNat S ex fr:=by unfold Fa at h⊢ dsimp only at h⊢ generalize (s+e).toBits=A at h⊢ generalize (s-e).toBits=B at h⊢ have b:=CC A have c:=CC B generalize (A+(0x0FFFFFFF:UInt64))>>>(29:UInt64)=x at h b⊢ generalize (B+(0x0FFFFFFF:UInt64))>>>(29:UInt64)=y at h c⊢ have d:=CD x generalize (x>>>(23:UInt64))&&&(0x7FF:UInt64)=ex at h d⊢ split at h . rename_i j;have k:=j;obtain ⟨a,j⟩:=у.mp j;have a:x=y:=by simpa using a obtain ⟨f,g⟩:=CE ex (by simpa using j);rw[d] at f g;subst a;have l:=A.toNat_lt;have m:=B.toNat_lt;have i:x.toNat<2^35:=א;simp only[k,ite_true];exact ⟨_,_,_,f,g,by omega,CF x i f g,CB A.toNat x.toNat l b f g,CB B.toNat x.toNat m c f g⟩ . exact absurd rfl h set_option maxRecDepth 8192 in lemma CH (f:Float) (S:Bool) (ex fr:Nat) (y:897<=ex) (z:ex<1151) (n:fr<2^23) (o:Fo f.toBits.toNat S ex fr): f.isFinite=true∧∃v:ℝ,R f=(if S then -v else v)∧v<=(2^53+fr*2^30+2^29)*2^((ex:Int)-1076)∧(fr≠0->(2^53+fr*2^30-2^29)*2^((ex:Int)-1076)simp;ring rcases q with rfl | ⟨rfl,rfl⟩ . have e:(2:ℝ)^((E:Int)-1075)=2*2^((E:Int)-1076):=by rw[show (E:Int)-1075=1+((E:Int)-1076) by ring,М С,zpow_one] rw[e];generalize (2:ℝ)^((E:Int)-1076)=b at a⊢;have i:(F:ℝ)<=fr*2^29+2^28:=by exact_mod_cast (by omega:F<=fr*2^29+2^28) have j:fr*2^29simp[abs_of_pos d] rwa [this] lemma CJ (w:UInt32) (h:expOf w≠255):wv w=(rationalWord w:ℝ):=by rw[wv,Model.toReal_eq,ofW,toDyadic_ofUInt32 w h];simp only[rationalWord,FloatLib.Numerics.Dyadic.cast_toRat] lemma CK (w:UInt32) (h:FX w=true):expOf w≠255:=by intro b;have c:w.toNat/2^23%2^8=255:=by have:=congrArg UInt32.toNat b;rw[expOf,О,л,show (255:UInt32).toNat=2^8-1 from rfl,В] at this;simpa [Nat.shiftRight_eq_div_pow] using this have a:(w&&&0x7FFFFFFF).toNat=w.toNat%2^31:=by rw[О,show (0x7FFFFFFF:UInt32).toNat=2^31-1 from rfl,В] simp only[FX,Bool.or_eq_true,beq_iff_eq,decide_eq_true_eq] at h;rcases h with h | h;. have:=congrArg UInt32.toNat h;rw[a] at this;have d:(0:UInt32).toNat=0:=rfl;omega . rw[Ж,UInt32.toNat_sub,a] at h;norm_num at h;omega lemma CL (a b:UInt32): ((sv a:ℚ)*sv b*(2:ℚ)^(idxOf a+idxOf b))*2^(-298:Int)=rationalWord a*rationalWord b:=by simp only[rationalWord,decodeD_toRat] rw[show (-298:Int)=-149+-149 by norm_num,М С] rw[zpow_sub₀ С,zpow_sub₀ С,Ц,Ц,pow_add] norm_num [zpow_neg,zpow_natCast] ring lemma CM (a b:Array UInt32) (start n:Nat): (dsum a b start n:ℚ)*2^(-298:Int)=∑j∈Finset.range n,rationalWord a[start+j]! *rationalWord b[start+j]!:=by induction n generalizing start with | zero=>simp[dsum] | succ n ih=> rw[dsum,Int.cast_add,Int.cast_mul,Int.cast_mul,Int.cast_pow,Int.cast_ofNat,add_mul,ih] conv_rhs=>rw[Finset.sum_range_succ'] simp only[Nat.add_zero] rw[CL] have c:(∑j∈Finset.range n,rationalWord a[start+1+j]! *rationalWord b[start+1+j]!)= ∑j∈Finset.range n,rationalWord a[start+(j+1)]! *rationalWord b[start+(j+1)]!:=by apply ы rfl intro j _ simp[Nat.add_comm,Nat.add_left_comm] rw[c] ring lemma CN (a b:Array UInt32) (o:a.size=b.size) (l:∀j,jexpOf a[j]!≠255∧expOf b[j]!≠255) (p:(dsum a b 0 a.size:ℚ)*2^(-298:Int)≠0): ∃d:FloatLib.Numerics.Dyadic,d.toRat=(dsum a b 0 a.size:ℚ)*2^(-298:Int)∧dotSpec a b=toWord (Model.roundDyadic Fmt d):=by let L:=a.map (Model.ofUInt32 (fmt:=Fmt)) let K:=b.map (Model.ofUInt32 (fmt:=Fmt)) have c:L.size=K.size:=by simp[L,K,o] have h:∀j (g:jUInt32) (g:∀j,jexpOf (fa j)≠255∧expOf (fb j)≠255) (h:(∑j∈Finset.range n,rationalWord (fa j)*rationalWord (fb j))≠0): ∃d:FloatLib.Numerics.Dyadic, d.toRat=(∑j∈Finset.range n,rationalWord (fa j)*rationalWord (fb j))∧dotOf n fa fb=toWord (Model.roundDyadic Fmt d):=by have b:(dsum (Array.ofFn (n:=n) λi=>fa i) (Array.ofFn (n:=n) λi=>fb i) 0 n:ℚ)*2^(-298:Int)=∑j∈Finset.range n,rationalWord (fa j)*rationalWord (fb j):=by rw[CM] apply ы rfl intro j c have a:=Finset.mem_range.mp c rw[К,AI n fa j a,AI n fb j a] have e:(Array.ofFn (n:=n) λi=>fa i).size=n:=by simp obtain ⟨d,f,k⟩:=CN (Array.ofFn (n:=n) λi=>fa i) (Array.ofFn (n:=n) λi=>fb i) ג (by intro j c have a:jUInt32) (bw:UInt32) (b:∀t,tFX (xw t)=true) (c:∀t,tFX (ww t)=true) (d:FX bw=true): ((∑j∈Finset.range (n+1),rationalWord (if jUInt32) (bw:UInt32) (H:∀t,tFX (xw t)=true) (I:∀t,tFX (ww t)=true) (J:FX bw=true) (s e:Float) (b:R (s-e)if tif t(2^53+fr*2^30-2^29)*2^((ex:Int)-1076)(lob1 h).trans b,lob.trans b⟩ . simp only[ite_true] at g b⊢;exact ⟨-V,by simp,by linarith only [z,b],λh=>by linarith [loa1 h],by linarith only [loa,g]⟩ have Q:0if tif tcases S<;> simp only[Bool.false_eq_true,ite_false,ite_true,Int.ofNat_eq_natCast,Int.cast_neg,Int.cast_natCast] at k a . exact ⟨by linarith only [k,a],rfl⟩ . exfalso;linarith only [i,c,p,k,a] . exfalso;linarith only [i,c,p,k,a] . exact ⟨by linarith only [k,a],rfl⟩ obtain ⟨d,rfl⟩:=d have X:m≠0:=by rintro rfl simp at d linarith only [i,c,d] have l:=B4 neg m q (2^23+fr) ((ex:Int)-1046) X א א א א (by rw[d,A];push_cast;linarith only [B]) (by intro G have r:fr≠0:=by intro N;exact G א have:=C r rw[d,A];push_cast;linarith only [this]) (by intro _ rw[d,A];linarith only [c]) have e1:((ex:Int)-1046+150).toNat=ex-896:=א have e2:(2^23+fr)%2^23=fr:=א rw[O,E,l,e1,e2] end section open ExactRuntime FloatLib.Floats.Formats.BinaryInterchange FloatLib.Floats open FloatLib.Floats.ExecFloat.Binary lemma CS (n:Nat) (f:n<2^20) (xw ww:Nat->UInt32) (bw:UInt32) (g:∀t,tFX (xw t)=true) (i:∀t,tFX (ww t)=true) (j:FX bw=true) (l:List Nat) (k:l.Nodup) (b:∀t∈l,tt∉l->xw t&&&0x7FFFFFFF=0∨ww t&&&0x7FFFFFFF=0) (s e:Float) (o:let r:=l.foldl (λ(acc:F1) t=>let q:=dv (xw t)*dv (ww t) F1.mk (acc.s+q) (acc.t+q.abs)) ⟨0,0⟩;s=r.s+dv bw∧e=Fd n*(r.t+(dv bw).abs)) (h:Fa s e≠0xFFFFFFFF): Fa s e=dotOf (n+1) (λt=>if tif tUInt32) (bw a:UInt32) (i:∀t,tFX (xw t)=true) (j:∀t,tFX (ww t)=true) (k:FX bw=true) (m:FX a=true) (o:∀t,txw t&&&0x7FFFFFFF<=a) (p:a<=0x7FFFFFFF) (l:List Nat) (q:l.Nodup) (c:∀t∈l,tt∉l->xw t&&&0x7FFFFFFF=0∨ww t&&&0x7FFFFFFF=0) (s e:Float) (u:s=l.foldl (λ(acc:Float) t=>acc+dv (xw t)*dv (ww t)) 0+dv bw∧e=Fd n*(dv a*(l.foldl (λ(acc:Float) t=>acc+(dv (ww t)).abs) 0)+(dv bw).abs)) (h:Fa s e≠0xFFFFFFFF): Fa s e=dotOf (n+1) (λt=>if tif tsimp lemma CZ (a:Array UInt32) (i:USize) (v:UInt32) (q:Nat) (d:a.size<2^32) (f:i.toNatsimp[e,eq_comm] . have c:¬q<(a.uset i v (AV a i h)).size:=by simpa using b rw[б _ q c,б a q b,Д א] def Fp (N:Nat) (sp:Nat->Word) (S:Nat->Prop) (out:Array Word):Prop:= out.size=N∧∀q,qS q->out[q]! =sp q lemma Ca {N:Nat} {sp:Nat->Word} {S:Nat->Prop} {out:Array Word} (i:N<2^32) (h:Fp N sp S out) {u:USize} {p:Nat} {v:Word} (a:u.toNat=p) (j:pq=p∨S q) (FV out u v):=by obtain ⟨c,d⟩:=h;refine ⟨by rw[CY,c],λq f g=>?_⟩;rw[CZ _ _ _ _ א א,a];by_cases e:q=p;. rw[Л e,e,b] . rw[Д e];exact d q f (g.resolve_left e) lemma Cb {N:Nat} {sp:Nat->Word} {S S':Nat->Prop} {out:Array Word} (h:Fp N sp S out) (b:∀q,qS' q->S q):Fp N sp S' out:=⟨h.1,λq a c=>h.2 q a (b q a c)⟩ lemma Cc {N:Nat} {sp:Nat->Word} {S:Nat->Prop} {out:Array Word} (h:Fp N sp S out) (b:∀q,qS q):out=Array.ofFn (n:=N) λq=>sp q.val:=by obtain ⟨c,d⟩:=h;apply ъ;. simp[c] . intro q e f;have a:qa (И.mp h);omega rw[Ж,س _ _ d] at b;rw[п] at c;have e:(0x00800000:UInt32)<=v:=by rw[Ж];omega simp only[Bool.or_eq_true,decide_eq_true_eq];right;rw[Ж,س _ _ e];omega lemma Ce (c u lo:UInt32) (h:c<=if uomega lemma Cf (c v a:UInt32) (h:(if aomega lemma Cg (w:UInt32) (h:FX w=true):FX (w&&&0x7FFFFFFF)=true:=by have e:(w&&&0x7FFFFFFF)&&&0x7FFFFFFF=w&&&0x7FFFFFFF:=by rw[UInt32.and_assoc,UInt32.and_self] unfold FX at h⊢;simpa only [e] using h lemma Ch {h:UInt32} (a:h<0x7F800000):h<=0x7FFFFFFF:=by have a1:(0x7F800000:UInt32).toNat=0x7F800000:=rfl;have a2:(0x7FFFFFFF:UInt32).toNat=0x7FFFFFFF:=rfl;rw[п] at a;rw[Ж];omega def Fq (A:Array Word) (h:Word):Prop:= FX h=true∧h<=0x7FFFFFFF∧(∀k,kFX A[k]! =true)∧ ∀k,kA[k]! &&&0x7FFFFFFF<=h lemma Ci (r v a:UInt32) (h:(if aomega lemma Cj (A:Array UInt32) (n:USize) (b:n.toNat<=A.size) (d:Nat): ∀(i:USize) (lo a:UInt32),i.toNat+d=n.toNat->FY A n i b lo a≠0xFFFFFFFF→ (0x7FFFFF:UInt32)<=lo∧a<0x7F800000∧a<=FY A n i b lo a∧FY A n i b lo a<0x7F800000∧(FX a=true->FX (FY A n i b lo a)=true)∧ ∀k,i.toNat<=k->k intro i lo a s h have e:FY A n i b lo a=if 0x007FFFFF<=lo∧a<0x7F800000 then a else 0xFFFFFFFF:=by rw[FY,Х (by rw[А];omega)] rw[e] at h⊢ by_cases c:0x007FFFFF<=lo∧a<0x7F800000 . rw[Л c];exact ⟨c.1,c.2,UInt32.le_refl _,c.2,id,λk p q=>by omega⟩ . rw[Д c] at h;exact absurd rfl h | succ d ih=> intro i lo a s h have f:iv ?_,λk B o=>?_⟩ . split;. exact Cg _ r . exact g0 . by_cases e2:k=i.toNat;. subst e2;rw[Е A i.toNat g];exact ⟨r,l⟩ . exact w k (by rw[AS i n f];omega) o lemma Ck (A:Array UInt32) (c:A.size<2^32) (h:FY A A.usize 0 (AZ A) 0xFFFFFFFF 0≠0xFFFFFFFF):Fq A (FY A A.usize 0 (AZ A) 0xFFFFFFFF 0):=by have e:=CW A c;have d:(0:USize).toNat=0:=rfl;obtain ⟨-,-,-,f,g,i⟩:=Cj A A.usize (AZ A) A.size 0 _ _ (by rw[d,e];omega) h;have b:∀k,kFX A[k]! =true∧A[k]! &&&0x7FFFFFFF<=FY A A.usize 0 (AZ A) 0xFFFFFFFF 0:=λk a=>i k א א;exact ⟨g rfl,Ch f,λk a=>(b k a).1,λk a=>(b k a).2⟩ lemma Cl (w:UInt32):w&&&0x7FFFFFFF<=0x7FFFFFFF:=by rw[Ж,О];exact Nat.and_le_right def Fr (w:Nat->Word) (t:Nat) (h:Word):Prop:= FX h=true∧(∀k,kw k&&&0x7FFFFFFF<=h)∧h<=0x7FFFFFFF lemma Cm {w:Nat->Word} {t:Nat} {h:Word} (b:FX (w t)=true) (H:Fr w t h):Fr w (t+1) (mx h (w t)):=by obtain ⟨c,a,d⟩:=H;have f:=Cg _ b;unfold mx;dsimp only;by_cases e:w t&&&0x7FFFFFFF<=h . rw[Л e];refine ⟨c,λk g=>?_,d⟩;by_cases e2:k=t;. rw[e2];exact e . exact a k א . rw[Д e];refine ⟨f,λk g=>?_,Cl _⟩;by_cases e2:k=t;. rw[e2];exact UInt32.le_refl _ . have i:=a k א;simp only[UInt32.le_iff_toNat_le] at*;omega lemma Cn {w:Nat->Word} {t:Nat} {h:Word} (a:w t&&&0x7FFFFFFF=0) (H:Fr w t h):Fr w (t+1) h:=by obtain ⟨b,c,d⟩:=H;refine ⟨b,λk e=>?_,d⟩;by_cases e2:k=t;. rw[e2,a,Ж];exact Nat.zero_le _ . exact c k א lemma Co {rows inW i t:Nat} (a:isimp[e,eq_comm] . have d:¬q<(ds.set i.toNat v b).size:=by simpa using c rw[б _ q d,б ds q c,Д א] def Fs (xw:Nat->Word) (t:Nat):List Nat:= (List.range t).filter (λp=>xw p&&&0x7FFFFFFF !=0) lemma Cu (xw:Nat->Word) (t:Nat):(Fs xw t).length<=t:=by have h:=List.length_filter_le (λp=>xw p&&&0x7FFFFFFF !=0) (List.range t);simpa [Fs] using h lemma Cv (xw:Nat->Word) (t:Nat) (h:xw t&&&0x7FFFFFFF=0):Fs xw (t+1)=Fs xw t:=by simp[Fs,List.range_succ,List.filter_append,h] lemma Cw (xw:Nat->Word) (t:Nat) (h:¬xw t&&&0x7FFFFFFF=0):Fs xw (t+1)=Fs xw t++[t]:=by simp[Fs,List.range_succ,List.filter_append,h] def Ft (xw:Nat->Word) (sz t:Nat) (ix:Array UInt32) (buf:FloatArray) (c:USize) (hh:Word):Prop:= c.toNat=(Fs xw t).length∧ix.size=sz∧buf.size=sz∧ (∀k p:Nat,(Fs xw t)[k]?=some p→ (ix[k]! :UInt32).toNat=p∧buf.data[k]! =dv (xw p))∧Fr xw t hh lemma Cx {X:Array UInt32} {o n:USize} (xw:Nat->Word) (y:n.toNat<2^32) (g:∀t:USize,tFT X (o+t)=xw t.toNat) (u:∀t,tFX (xw t)=true) (d:Nat): ∀(t:USize) (ix:Array UInt32) (buf:FloatArray) (c:USize) (b:Word),t.toNat+d=n.toNat->Ft xw n.toNat t.toNat ix buf c b→ Ft xw n.toNat n.toNat (Fb X o n t ix buf c b).ix (Fb X o n t ix buf c b).buf (Fb X o n t ix buf c b).c (Fb X o n t ix buf c b).hi:=by induction d with | zero=> intro t ix buf c b v H rw[Fb,Х (by rw[А];omega)] have e:t.toNat=n.toNat:=א rw[e] at H;exact H | succ d ih=> intro t ix buf c b v H have h:t?_,Cm (u _ א) s⟩;. rw[AT _ _ (by rw[Щ];omega),Щ,i];simp . rw[CZ _ _ _ _ א א,Ct _ _ _ _ א א];rw[List.getElem?_append,<-i] at a;by_cases e:k=c.toNat;. subst e;simp at a;subst a;simp;omega . rw[Д e,Д e];by_cases e2:kintro k a c;rw[FZ,Х (by rw[А];omega)];rfl | succ d ih=> intro k a c;have b:kWord} {p:Nat} {out:Array Word} (a:N<2^32) (h:Fp N sp (λq=>qq(by omega:q=p∨qif tif tmax m v.toNat) 0:=by have key:∀(l:List UInt32) (i:Nat),i<=l.foldl (λm v=>max m v.toNat) i∧ ∀v∈l,v.toNat<=l.foldl (λm v=>max m v.toNat) i:=by intro l;induction l with | nil=>intro i;simp | cons x l ih=>intro i;obtain ⟨c,b⟩:=ih (max i x.toNat);simp only[List.foldl_cons,List.mem_cons,forall_eq_or_imp];exact ⟨by omega,by omega,b⟩ rw[<-Array.foldl_toList];exact (key a.toList 0).2 _ ג lemma C5 {n m:Nat} (d:Nat) (off:Array UInt32) (f:n<2^32) (a:∀j (h:jmax m v.toNat) 0 if h:r.c.toNat<=t.off.size∧r.c.toNat<=r.buf.size then let c:D_P:=⟨g,r.buf,t.off,r.c,(g.xd.size-(m+0)).toUSize, (g.xd.size-(m+3)).toUSize,dv g.hi*t.a,dv (FT g.b o.toUSize),0,h.1,h.2,hs, C5 0 t.off hs (C4 t.off),C5 3 t.off hs (C4 t.off),rfl⟩ GC g hs (o+1) (q+(g.ho*g.wo).toUSize) r.ix t.off r.buf (GA c (g.xd.size-(m+7)).toUSize (C5 7 t.off hs (C4 t.off)) o 0 q out) else out else out termination_by g.C-o def GD (s:ConvShape) (X:Array Word) (hs:X.size<2^32):FloatArray:= if s.pad==0 then Fw X 0 X.usize 0 hs (by simpa only[USize.toNat_zero,Nat.zero_add] using AZ X) (FloatArray.emptyWithCapacity X.size) else Fx s X hs (dv 0) (s.cin*(s.h+2*s.pad)) 0 (FloatArray.emptyWithCapacity (s.cin*(s.h+2*s.pad)*(s.w+2*s.pad))) def GE (dw:Bool) (s:ConvShape) (relu:Bool) (X W b:Array UInt32) (k C:Nat): Array UInt32:= let hp:=s.h+2*s.pad let wp:=s.w+2*s.pad let rx:=Fu X X.usize 0 (AZ X) 0xFFFFFFFF 0 if hg:X.size<2^32∧0x007FFFFF<=rx.lo∧rx.hi<0x7F800000∧X.size=s.cin*s.h*s.w∧ W.size=C*k∧b.size=C∧0>>(23:UInt32))-((rx.lo+1)>>>(23:UInt32))>20 let R:=s.cin*hp let xd:=GD s X hg.1 if hs:xd.size<2^32 then let g:D_C:=⟨dw,relu,s.stride==1,s,X,W,b,k,C,s.ho,s.wo,wp, s.stride.toUSize,rx.hi,xd,(k.toUInt64+8).toFloat*Float.ofBits 0x3CC0000000000000, Array.ofFn (n:=k) λt=>(Fy s t.val).toUInt32⟩ GC g hs 0 0 (Array.replicate k 0) (Array.replicate k 0) (FZ k.toUSize 0 (FloatArray.emptyWithCapacity k)) (Array.replicate (C*(s.ho*s.wo)) 0) else if dw then depthwiseWith FO s relu X W b else conv2dWith FO s relu X W b else if dw then depthwiseWith FO s relu X W b else conv2dWith FO s relu X W b def GF (s:ConvShape) (relu:Bool) (X W b:Array UInt32):Array UInt32:= GE false s relu X W b (s.cin*s.kh*s.kw) s.cout def GG (s:ConvShape) (relu:Bool) (X W b:Array UInt32):Array UInt32:= GE true s relu X W b (s.kh*s.kw) s.cin def GH (s:ConvShape) (X:Array Word) (c yy xx:Nat):Word:= if yyFloat) (m:Nat) (a:FloatArray):Prop:= a.size=m∧∀q,q< m->a.data[q]! =F q lemma C6 {F:Nat->Float} {m:Nat} {a:FloatArray} {v:Float} (h:GJ F m a) (b:v=F m):GJ F (m+1) (a.push v):=by refine ⟨by rw[Cy,h.1],λq c=>?_⟩;rw[C1,h.1];by_cases e:q=m;. rw[Л e,e,b] . rw[Д e];exact h.2 q א lemma C7 {F:Nat->Float} {v:Float} {n:USize} (d:Nat): ∀(k:USize) (m:Nat) (a:FloatArray),k.toNat+d=n.toNat->GJ F m a→(∀i,m<=i->i< m+d->F i=v)->GJ F (m+d) (Fv v n k a):=by induction d with | zero=> intro k m a e H _ rw[Fv,Х (by rw[А];omega)];exact H | succ d ih=> intro k m a e H b have c:kb i א א) lemma C8 {F:Nat->Float} {X:Array UInt32} {o n:USize} (e:X.size<2^32) (f:o.toNat+n.toNat<=X.size) (d:Nat): ∀(t:USize) (m:Nat) (a:FloatArray),t.toNat+d=n.toNat->GJ F m a→(∀j,jF (m+j)=dv X[o.toNat+t.toNat+j]!)→GJ F (m+d) (Fw X o n t e f a):=by induction d with | zero=> intro t m a g H _ rw[Fw,Х (by rw[А];omega)];exact H | succ d ih=> intro t m a g H c have b:t?_) . rw[Cr,AT _ _ א,e1] . have:=c (j+1) א;rw[AS t n b,show m+1+j=m+(j+1) by omega,show o.toNat+(t.toNat+1)+j=o.toNat+t.toNat+(j+1) by omega];exact this lemma C9 {c:Nat} (a:Nat) {b:Nat} (h:b intro r a A H rw[Fx,Х א] rw[(א:R=r)];exact H | succ d ih=> intro r a A H have f:rby rw[q,e] at f;simp at f) have j:r/(s.h+2*s.pad)GI s X (r*(s.w+2*s.pad)+i)=dv (GH s X (r/(s.h+2*s.pad)) (r%(s.h+2*s.pad)) i):=λi l=>DA s X r l have g:∀i,i(r%(s.h+2*s.pad)(r/(s.h+2*s.pad)*s.h+(r%(s.h+2*s.pad)-s.pad))*s.w+s.w<=X.size:=λg1=>by rw[y];exact Cp (Co j g1) (le_refl _) have c:(r+1)*(s.w+2*s.pad)=r*(s.w+2*s.pad)+s.pad+s.w+s.pad:=by rw[ф,ц];omega rw[Fx,Р f] dsimp only split . rename_i o;obtain ⟨g1,g2,g3⟩:=o;have b:=t g2;apply ih (r+1) _ א;rw[c];generalize G:r*(s.w+2*s.pad)=m at H k g have P1:=C7 (F:=GI s X) (v:=dv 0) (n:=s.pad.toUSize) s.pad 0 m a (by rw[e0,ep,К]) H (λi b x=>by obtain ⟨u,rfl⟩:=ь b exact g u א (Or.inr (Or.inl א))) have P2:=C8 (F:=GI s X) p g3 s.w 0 _ _ (by rw[e0,ew,К]) P1 (λj I=>by rw[з m,k _ א,GH,Д א,e0,Я,CU _ א,Nat.add_sub_cancel_left]) exact C7 (F:=GI s X) (v:=dv 0) (n:=s.pad.toUSize) s.pad 0 _ _ (by rw[e0,ep,К]) P2 (λi b x=>by obtain ⟨u,rfl⟩:=ь b;rw[з m,з m] exact g _ א (Or.inr (Or.inr (Or.inr א)))) . rename_i o;apply ih (r+1) _ א;have C:r%(s.h+2*s.pad)by obtain ⟨u,rfl⟩:=ь b exact g u א א) lemma DC (s:ConvShape) (X:Array Word) (c:s.pad=0) (q:Nat) (b:qby rw[Nat.zero_mul] at f;omega⟩ def GK (g:D_C) (o:Nat):Nat:=if g.dw then o*g.k else 0 def GM (g:D_C) (o y x t:Nat):Word:=windowAt g.s g.X y x (GK g o+t) def GN (g:D_C) (o y x:Nat):Word:= act g.relu (dotOf (g.k+1) (λt=>if tif tg.s.stride=1 p0:0(Fy g.s t.val).toUInt32 lemma DG {A:Array Word} {h:Word}:FX (0:Word)=true∧(0:Word)&&&0x7FFFFFFF<=h:=by refine ⟨rfl,?_⟩;rw[Ж];exact Nat.le_trans (Nat.le_of_eq rfl) (Nat.zero_le _) lemma DH {A:Array Word} (H:∀k:Nat,kFX A[k]! =true) (q:Nat):FX A[q]! =true:=by by_cases h:qby rw[e] at d;simp at d) have f:0Float) (L:List Nat):∀(i:USize) (a t:Float),i.toNat+L.length=e.toNat→ (∀j p:Nat,L[j]?=some p->xd.data[b.toNat+(off[i.toNat+j]! :UInt32).toNat]! =xf p∧wd.data[i.toNat+j]! =wf p)→ F0 xd wd off b e i o r u k a t=L.foldl (λ(acc:F1) p=>let q:=xf p*wf p F1.mk (acc.s+q) (acc.t+q.abs)) ⟨a,t⟩:=by induction L with | nil=> intro i a t d _ rw[F0,Х (by rw[А];simp at d;omega)] rfl | cons p L ih=> intro i a t d H simp only[List.length_cons] at d have f:iacc+xf 0 p*wf p) a0, L.foldl (λacc p=>acc+xf 1 p*wf p) a1, L.foldl (λacc p=>acc+xf 2 p*wf p) a2, L.foldl (λacc p=>acc+xf 3 p*wf p) a3⟩:=by induction L with | nil=> intro i a0 a1 a2 a3 c _ rw[Fz,Х (by rw[А];simp at c;omega)] rfl | cons p L ih=> intro i a0 a1 a2 a3 c H simp only[List.length_cons] at c have f:i?_ have:=H (j+1) q (by simpa using u) rw[AS i e f,show i.toNat+1+j=i.toNat+(j+1) by omega] exact this lemma DP {xd wd:FloatArray} {off:Array UInt32} {b e:USize} (n:e.toNat<=off.size) (o:e.toNat<=wd.size) (r:xd.size<2^32) (l:∀j (h:jacc+xf 0 p*wf p) a0, L.foldl (λacc p=>acc+xf 1 p*wf p) a1, L.foldl (λacc p=>acc+xf 2 p*wf p) a2, L.foldl (λacc p=>acc+xf 3 p*wf p) a3, L.foldl (λacc p=>acc+xf 4 p*wf p) a4, L.foldl (λacc p=>acc+xf 5 p*wf p) a5, L.foldl (λacc p=>acc+xf 6 p*wf p) a6, L.foldl (λacc p=>acc+xf 7 p*wf p) a7⟩:=by induction L with | nil=> intro i a0 a1 a2 a3 a4 a5 a6 a7 c _ rw[F8,Х (by rw[А];simp at c;omega)] rfl | cons p L ih=> intro i a0 a1 a2 a3 a4 a5 a6 a7 c H simp only[List.length_cons] at c have f:i?_ have:=H (j+1) q (by simpa using u) rw[AS i e f,show i.toNat+1+j=i.toNat+(j+1) by omega] exact this structure D_PO (c:D_P) (o:Nat) (L:List Nat):Prop where ok:D_Ok c.g hC:ot∉L->c.g.W[o*c.g.k+t]! &&&0x7FFFFFFF=0 rd:∀j p:Nat,L[j]?=some p→ (c.off[j]! :UInt32).toNat=Fy c.g.s (GK c.g o+p)∧ c.wd.data[j]! =dv c.g.W[o*c.g.k+p]! e0:c.e0=dv c.g.hi*L.foldl (λacc t=>acc+(dv c.g.W[o*c.g.k+t]!).abs) 0 bv:c.bv=dv c.g.b[o]! lemma DQ {c:D_P} {o:Nat} {L:List Nat} (h:D_PO c o L) {j p:Nat} (a:L[j]?=some p):pdv (GM c.g o y x p)) (λp=>dv c.g.W[o*c.g.k+p]!) L 0 0 0 (by rw[show (0:USize).toNat=0 from rfl,К];exact h.len.symm) (λj p d=>by have f:=h.rd j p d;rw[show (0:USize).toNat=0 from rfl,К,f.1,m] exact ⟨(DL h.ok h.hC i l (DQ h d)).2,f.2⟩) dsimp only;rw[c.hz,e,h.bv,h.ok.nf] by_cases a:Fa ((L.foldl (λ(acc:F1) p=>let q:=dv (GM c.g o y x p)*dv c.g.W[o*c.g.k+p]! F1.mk (acc.s+q) (acc.t+q.abs)) ⟨0,0⟩).s+dv c.g.b[o]!) (Fd c.g.k*((L.foldl (λ(acc:F1) p=> let q:=dv (GM c.g o y x p)*dv c.g.W[o*c.g.k+p]! F1.mk (acc.s+q) (acc.t+q.abs)) ⟨0,0⟩).t+(dv c.g.b[o]!).abs))=0xFFFFFFFF . rw[Л (by simpa using a)];exact DF _ _ _ _ . rw[Д (by simpa using a)];unfold GN;congr 1;exact CS c.g.k h.ok.nk (GM c.g o y x) (λt=>c.g.W[o*c.g.k+t]!) c.g.b[o]! (λt _=>(DI h.ok.Hx _ _ _).1) (λt _=>h.ok.HW _) (h.ok.Hb _) L h.nd h.lt (λt r u=>Or.inr (h.hz t r u)) _ _ ⟨rfl,rfl⟩ a . exact DF _ _ _ _ lemma DS {c:D_P} {o:Nat} {L:List Nat} (h:D_PO c o L) {y x:Nat} {b:USize} (e:yacc+dv (GM c.g o y x t)*dv c.g.W[o*c.g.k+t]!) 0):F4 c o y x b a=GN c.g o y x:=by unfold F4;dsimp only;rw[h.bv,h.ok.nf,h.e0];by_cases d:Fa (a+dv c.g.b[o]!) (Fd c.g.k*(dv c.g.hi*L.foldl (λacc t=>acc+(dv c.g.W[o*c.g.k+t]!).abs) 0+(dv c.g.b[o]!).abs))=0xFFFFFFFF;. rw[Л (by simpa using d)];exact DR h e f i . rw[Д (by simpa using d)];unfold GN;congr 1;exact CT c.g.k h.ok.nk (GM c.g o y x) (λt=>c.g.W[o*c.g.k+t]!) c.g.b[o]! c.g.hi (λt _=>(DI h.ok.Hx _ _ _).1) (λt _=>h.ok.HW _) (h.ok.Hb _) h.ok.Hx.1 (λt _=>(DI h.ok.Hx _ _ _).2) h.ok.Hx.2.1 L h.nd h.lt (λt l m=>Or.inr (h.hz t l m)) _ _ ⟨by rw[j],rfl⟩ d lemma DT {xd wd:FloatArray} {off:Array UInt32} {b e:USize} (o:e.toNat<=off.size) (r:e.toNat<=wd.size) (s:xd.size<2^32) (k:∀j (h:jFloat) (L:List Nat):∀(i:USize) (a:Float),i.toNat+L.length=e.toNat→ (∀j p:Nat,L[j]?=some p->xd.data[b.toNat+(off[i.toNat+j]! :UInt32).toNat]! =xf p∧wd.data[i.toNat+j]! =wf p)→ F5 xd wd off b e i o r s k a=L.foldl (λacc p=>acc+xf p*wf p) a:=by induction L with | nil=> intro i a d _ rw[F5,Х (by rw[А];simp at d;omega)] rfl | cons p L ih=> intro i a d H simp only[List.length_cons] at d have f:idv (GM c.g o y x p)) (fun p=>dv c.g.W[o*c.g.k+p]!) L 0 c.ze (by rw[show (0:USize).toNat=0 from rfl,К];exact h.len.symm) (fun j p i=>by have l:=h.rd j p i rw[show (0:USize).toNat=0 from rfl,К,l.1,f] exact ⟨(DL h.ok h.hC a d (DQ h i)).2,l.2⟩) rw[e,c.hz] exact DS h a d f rfl ·exact DF _ _ _ _ def GP (g:D_C) (q:Nat):Word:= GN g (q/(g.ho*g.wo)) (q/g.wo%g.ho) (q%g.wo) lemma DV (g:D_C) {o y x:Nat} (a:yb.toNat=GO c.g y x)->q.toNat=Q+x->rr.size=4→Fp (c.g.C*(c.g.ho*c.g.wo)) (GP c.g) (λp=>pp intro x b q rr out G A i u H have sN:=h.ok.sN have l:∀x',x'GN c.g o y x'=GP c.g (Q+x'):=by intro x' w;rw[E];exact DV c.g m w have l2:(2:USize).toNat=2:=uk 2 ב have l3:(3:USize).toNat=3:=uk 3 ב have l4:(4:USize).toNat=4:=uk 4 ב by_cases v:x+4<=c.g.wo∧c.g.f4=true∧bDW h.ok h.hC m B;have b0:=bB 3 א;rw[t] at b0;have a1:(b+1).toNat=GO c.g y (x+1):=by rw[t,AT _ _ (by rw[Щ];omega),f,Щ] have a2:(b+2).toNat=GO c.g y (x+2):=by rw[t,AT _ _ (by rw[l2];omega),f,l2] have a3:(b+3).toNat=GO c.g y (x+3):=by rw[t,AT _ _ (by rw[l3];omega),f,l3] have R:=DO c.he c.hw c.hs (c.h4 b v.2.2) (λk p=>dv (GM c.g o y (x+k) p)) (λp=>dv c.g.W[o*c.g.k+p]!) L 0 0 0 0 0 (by rw[show (0:USize).toNat=0 from rfl,К];exact h.len.symm) (λj p D=>by have r:=h.rd j p D;rw[show (0:USize).toNat=0 from rfl,К,r.1];refine ⟨r.2,λk B=>?_⟩;rw[show b.toNat+Fy c.g.s (GK c.g o+p)+k=GO c.g y (x+k)+Fy c.g.s (GK c.g o+p) by rw[t,f];omega] exact (DL h.ok h.hC m א (DQ h D)).2) have o0:F4 c o y x b (L.foldl (λacc p=>acc+dv (GM c.g o y (x+0) p)*dv c.g.W[o*c.g.k+p]!) 0)=GN c.g o y x:=DS h m א f rfl have o1:=DS h m (א:x+1acc+dv (GM c.g o y (x+1) p)*dv c.g.W[o*c.g.k+p]!) 0)) rfl have o2:=DS h m (א:x+2acc+dv (GM c.g o y (x+2) p)*dv c.g.W[o*c.g.k+p]!) 0)) rfl have o3:=DS h m (א:x+3acc+dv (GM c.g o y (x+3) p)*dv c.g.W[o*c.g.k+p]!) 0)) rfl rw[F7,Р v];dsimp only;rw[c.hz,R];dsimp only;rw[o0,o1,o2,o3];refine ih (d-4) א (x+4) _ _ _ _ א ?_ ?_ u ?_;. intro z;have n:=DW h.ok h.hC m z;rw[t] at n⊢;rw[AT _ _ (by rw[l4];omega),f,l4] . rw[AT _ _ (by rw[l4,i];omega),i,l4];omega . have q1:(q+1).toNat=Q+x+1:=by rw[AT _ _ (by rw[Щ,i];omega),i,Щ] have q2:(q+2).toNat=Q+x+1+1:=by rw[AT _ _ (by rw[l2,i];omega),i,l2] have q3:(q+3).toNat=Q+x+1+1+1:=by rw[AT _ _ (by rw[l3,i];omega),i,l3] have s1:GN c.g o y (x+1)=GP c.g (Q+x+1):=by rw[з];exact l _ א have s2:GN c.g o y (x+2)=GP c.g (Q+x+1+1):=by rw[show Q+x+1+1=Q+(x+2) by omega];exact l _ א have s3:GN c.g o y (x+3)=GP c.g (Q+x+1+1+1):=by rw[show Q+x+1+1+1=Q+(x+3) by omega];exact l _ א rw[show Q+(x+4)=Q+x+1+1+1+1 by omega];exact C0 sN (C0 sN (C0 sN (C0 sN H i א (l _ א)) q1 א s1) q2 א s2) q3 א s3 . by_cases r:xpp intro x b q rr out D z f n H have sN:=h.ok.sN have i:∀x',x'dv (GM c.g o y (x+k) p)) (λp=>dv c.g.W[o*c.g.k+p]!) L 0 0 0 0 0 0 0 0 0 (by rw[show (0:USize).toNat=0 from rfl,К];exact h.len.symm) (λj p r=>by have A:=h.rd j p r rw[show (0:USize).toNat=0 from rfl,К,A.1] refine ⟨A.2,λk F=>?_⟩ rw[show b.toNat+Fy c.g.s (GK c.g o+p)+k= GO c.g y (x+k)+Fy c.g.s (GK c.g o+p) by rw[l,a];omega] exact (DL h.ok h.hC e (by omega) (DQ h r)).2) have eq0:F4 c o y x b (L.foldl (λacc p=>acc+dv (GM c.g o y x p)*dv c.g.W[o*c.g.k+p]!) 0)= GN c.g o y x:=by apply DS h e (by omega) (by simpa using a) rfl have l1:(1:USize).toNat=1:=uk 1 ב have eq1:F4 c o y (x+1) (b+1) (L.foldl (λacc p=>acc+dv (GM c.g o y (x+1) p)*dv c.g.W[o*c.g.k+p]!) 0)= GN c.g o y (x+1):=by apply DS h e (by omega) (by rw[l,AT _ _ (by rw[l1];have:=DW h.ok h.hC e (show x+1acc+dv (GM c.g o y (x+2) p)*dv c.g.W[o*c.g.k+p]!) 0)= GN c.g o y (x+2):=by apply DS h e (by omega) (by rw[l,AT _ _ (by rw[l2];have:=DW h.ok h.hC e (show x+2acc+dv (GM c.g o y (x+3) p)*dv c.g.W[o*c.g.k+p]!) 0)= GN c.g o y (x+3):=by apply DS h e (by omega) (by rw[l,AT _ _ (by rw[l3];have:=DW h.ok h.hC e (show x+3acc+dv (GM c.g o y (x+4) p)*dv c.g.W[o*c.g.k+p]!) 0)= GN c.g o y (x+4):=by apply DS h e (by omega) (by rw[l,AT _ _ (by rw[l4];have:=DW h.ok h.hC e (show x+4acc+dv (GM c.g o y (x+5) p)*dv c.g.W[o*c.g.k+p]!) 0)= GN c.g o y (x+5):=by apply DS h e (by omega) (by rw[l,AT _ _ (by rw[l5];have:=DW h.ok h.hC e (show x+5acc+dv (GM c.g o y (x+6) p)*dv c.g.W[o*c.g.k+p]!) 0)= GN c.g o y (x+6):=by apply DS h e (by omega) (by rw[l,AT _ _ (by rw[l6];have:=DW h.ok h.hC e (show x+6acc+dv (GM c.g o y (x+7) p)*dv c.g.W[o*c.g.k+p]!) 0)= GN c.g o y (x+7):=by apply DS h e (by omega) (by rw[l,AT _ _ (by rw[l7];have:=DW h.ok h.hC e (show x+7ppppppppp<(o*c.g.ho+y)*c.g.wo) out→ Fp (c.g.C*(c.g.ho*c.g.wo)) (GP c.g) (λp=>p<(o*c.g.ho+c.g.ho)*c.g.wo) (GA c l8 n o y q out):=by induction d with | zero=> intro y q out t _ H rw[GA,Д א] rw[(א:y=c.g.ho)] at H;exact H | succ d ih=> intro y q out t i H have k:yby rw[e] at r;simp at r) exact к m have:=h.ok.kw omega have e1:GO c.g y 0=y*c.g.s.stride*c.g.wp:=by unfold GO;simp rw[e1] at bB have A:y*c.g.s.stride<=y*c.g.s.stride*c.g.wp:=й _ l have eS:(y.toUSize*c.g.step).toNat=y*c.g.s.stride:=by rw[CV _ _ (by rw[eY,h.ok.st];omega),eY,h.ok.st] have eP:c.g.wp.toUSize.toNat=c.g.wp:=CU _ h.ok.wp2 have ebase:(y.toUSize*c.g.step*c.g.wp.toUSize).toNat=GO c.g y 0:=by rw[CV _ _ (by rw[eS,eP];exact bB),eS,eP,e1] rw[GA,Л k] refine ih (y+1) _ _ א ?_ ?_ . rw[AT _ _ (by rw[eW,i];omega),i,eW,f] . rw[f];refine DY h k rfl א l8 n c.g.wo 0 _ _ _ _ (К _) (λ_=>ebase) (by rw[Я];exact i) ?_ (by rw[Я];exact H);rw[Cz 4 4 0 _ (by rw[show (0:USize).toNat=0 from rfl,К];exact (uk 4 ב).symm)];rfl lemma Da {g:D_C} {c:D_P} {o:Nat} {L:List Nat} (d:c.g=g) (h:D_PO c o L) (e:(o*g.ho+g.ho)*g.wo<=g.C*(g.ho*g.wo)) {l8:USize} {a:∀b:USize,bp<(o*g.ho+0)*g.wo) out): Fp (g.C*(g.ho*g.wo)) (GP g) (λp=>p<(o*g.ho+g.ho)*g.wo) (GA c l8 a o 0 q out):=by subst d exact DZ h e l8 a c.g.ho 0 q out (К _) f H lemma Db (s:ConvShape) (o:Nat) {p:Nat} (c:pFloat) (n:∀p∈L,p(ix[j]! :UInt32).toNat=p∧buf.data[j]! =wf p) (d:Nat): ∀(i:USize) (off:Array UInt32) (a:Float),i.toNat+d=e.toNat→Fp N (GQ g o L) (λq=>q< i.toNat) off→ Fp N (GQ g o L) (λq=>qacc+(wf t).abs) a:=by induction d with | zero=> intro i off a w H rw[GB,Х (by rw[А];omega)] rw[(א:i.toNat=e.toNat)] at H⊢ exact ⟨H,by rw[List.drop_eq_nil_of_le א];rfl⟩ | succ d ih=> intro i off a w H have f:iq.toNat=o*(g.ho*g.wo)->ix.size=g.k->off.size=g.k->buf.size=g.k→Fp (g.C*(g.ho*g.wo)) (GP g) (λp=>pp intro o q ix off buf out w _ _ _ _ H rw[GC,Д א] rw[(א:o=g.C)] at H;exact H | succ d ih=> intro o q ix off buf out w h z A B H have i:og.W[o*g.k+p]!) (by rw[ek];exact e) (λt f=>by have G:=А.mp f rw[ek] at G rw[CX _ _ sW2,AT _ _ (by rw[eo];omega),eo]) (λt _=>ok.HW _) g.k 0 ix buf 0 0 (by rw[show (0:USize).toNat=0 from rfl,ek,К]) ⟨by simp[Fs],by rw[ek];exact z,by rw[ek];exact B,λk p t=>by simp[Fs] at t,rfl,λk t=>absurd t (Nat.not_lt_zero _),(by decide)⟩ rw[ek] at D obtain ⟨d1,d2,d3,d4,-⟩:=D rw[GC,Л i] dsimp only have c:=Cu (λp=>g.W[o*g.k+p]!) g.k have T:=De ok o (N:=g.k) (L:=Fs (λp=>g.W[o*g.k+p]!) g.k) (λp=>dv g.W[o*g.k+p]!) (λt f=>н.mp (ش.mp f).1) e א א d1 א א d4 (Fs (λp=>g.W[o*g.k+p]!) g.k).length 0 off 0 (by rw[show (0:USize).toNat=0 from rfl,К];exact d1.symm) ⟨A,λq _ h=>absurd h (Nat.not_lt_zero _)⟩ obtain ⟨⟨T1,T3⟩,T2⟩:=T rw[Р (by rw[T1,d3,d1];exact ⟨c,c⟩)] refine ih (o+1) _ _ _ _ _ א ?_ d2 T1 d3 ?_ . rw[AT _ _ (by rw[eH,h];omega),h,eH,r] . have E:(o+1)*(g.ho*g.wo)=(o*g.ho+g.ho)*g.wo:=by ring rw[E] refine Da (L:=Fs (λp=>g.W[o*g.k+p]!) g.k) rfl ⟨ok,i,d1,(List.nodup_range).filter _,λt f=>н.mp (ش.mp f).1,λt f I=>?_,λj p m=>?_,?_,?_⟩ (by rw[<-E];exact F) (by rw[Я,h];ring) (by rw[show (o*g.ho+0)*g.wo=o*(g.ho*g.wo) by ring];exact H) . by_contra J;exact I (ش.mpr ⟨н.mpr f,by simpa using J⟩) . have K:j<(Fs (λp=>g.W[o*g.k+p]!) g.k).length:=(List.getElem?_eq_some_iff.mp m).1;have u:pdv g.hi*a) T2 . show dv (FT g.b o.toUSize)=_;rw[CX _ _ ok.sb,eOo] lemma Dg (A:Array UInt32) (n:USize) (b:n.toNat<=A.size) (d:Nat): ∀(i:USize) (lo a:UInt32),i.toNat+d=n.toNat->FY A n i b lo a= if 0x007FFFFF<=(Fu A n i b lo a).lo∧(Fu A n i b lo a).hi<0x7F800000 then (Fu A n i b lo a).hi else 0xFFFFFFFF:=by induction d with | zero=> intro i lo a c have h:¬i intro i lo a c have h:i?_⟩) (λq h=>h)).trans ?_ . rw[Cz g.k.toUSize g.k 0 _ (by rw[e,show (0:USize).toNat=0 from rfl,К])];exact К _ . rw[Nat.zero_mul] at h;exact absurd h (Nat.not_lt_zero _) . obtain ⟨dw,relu,f4,s,X,W,b,k,C,c,wo,wp,step,l,xd,nf,tab⟩:=g;have d:k=if dw then s.kh*s.kw else s.cin*s.kh*s.kw:=ok.hk;have f:C=if dw then s.cin else s.cout:=ok.hC;have i:c=s.ho:=ok.ho;have j:wo=s.wo:=ok.wo;subst d f i j;cases dw;. refine congrArg (Array.ofFn (n:=s.cout*(s.ho*s.wo))) (funext λq=>?_);simp[GP,GN,GM,GK] . refine congrArg (Array.ofFn (n:=s.cin*(s.ho*s.wo))) (funext λq=>?_);simp[GP,GN,GM,GK] lemma Di (dw:Bool) (s:ConvShape) (relu:Bool) (X W b:Array UInt32) {k C:Nat} (c:k=if dw then s.kh*s.kw else s.cin*s.kh*s.kw) (d:C=if dw then s.cin else s.cout): GE dw s relu X W b k C=if dw then depthwiseSpec s relu X W b else conv2dSpec s relu X W b:=by have a:(if dw then depthwiseWith FO s relu X W b else conv2dWith FO s relu X W b)=if dw then depthwiseSpec s relu X W b else conv2dSpec s relu X W b:=by rw[AJ];rfl unfold GE dsimp only rw[<-a] generalize (if dw then depthwiseWith FO s relu X W b else conv2dWith FO s relu X W b)=R at a⊢ split . rename_i f;split . rename_i g;obtain ⟨g1,g2,g3,g4,g5,g6,g7,g8,g9,g10,g11,g12,g13,g14,g15,g16,g17,g18,g19,g20⟩:=f;have e:=Dg X X.usize (AZ X) (X.usize.toNat) 0 0xFFFFFFFF 0 (by rw[show (0:USize).toNat=0 from rfl,К]);rw[Л ⟨g2,g3⟩] at e;have Hx:=Ck X g1 (by rw[e];intro h;rw[h] at g3;exact absurd g3 (by decide));rw[e] at Hx;refine (Dh ?_ _).trans a.symm exact ⟨c,d,rfl,rfl,rfl,CU _ g8,rfl,λh=>beq_iff_eq.mp h,g7,g9,g10,g11,g12, DE s X g1 g4 g13 g14, g,Hx,DH (Ck W g15 g19).2.2.1,DH (Ck b g16 g20).2.2.1, g5,g15,g16,g17,g14,rfl⟩ . rfl . rfl lemma Dj:GF=conv2dSpec:=by funext s relu X W b;exact Di false s relu X W b rfl rfl lemma Dk:GG=depthwiseSpec:=by funext s relu X W b;exact Di true s relu X W b rfl rfl end section open ExactRuntime FloatLib.Floats.Formats.BinaryInterchange FloatLib.Floats open FloatLib.Floats.ExecFloat.Binary open Float.Model Float.Model.UnpackedFloat lemma Dl (s:Sign) (m:Nat) (e T:Int) (K r:Nat) (a:Format.binary32.targetExponent (totalExponent m e)=T) (b:T=e+(K+1:Nat)) (c:(ExtendedMantissa.ofMantissaAndAccuracy m .exact>>>(K+1)).roundedMantissa=r): UnpackedFloat.round Format.binary32 s m e=let p:=shiftToTargetExponent Format.binary32 r T .exact if h:p.1.mantissa=0 then .zero s else .finite s p.1.mantissa p.2 (Н h):=by unfold UnpackedFloat.round decreaseExponent roundWithAccuracy simp only[a] have d:(e-T).toNat=0:=א have f:shiftToTargetExponent Format.binary32 m e .exact=(ExtendedMantissa.ofMantissaAndAccuracy m .exact>>>(K+1),T):=by unfold shiftToTargetExponent shiftToExponent simp only[a] have g:(T-e).toNat=K+1:=א rw[g,b] simp only[d,Nat.shiftLeft_zero,Int.natCast_zero,Int.sub_zero,f,c] def GR (N:Nat):Nat:= N/2^39+if 2^38>>(38+1)).roundedMantissa=GR N:=by rw[Bq];have d:=Nat.div_add_mod N (2^39);have l:N%2^39<2^39:=Ъ _ ב;unfold GR;simp[ExtendedMantissa.roundedMantissa,ExtendedMantissa.accuracy,Accuracy.roundToNearestEven];generalize a:(N/274877906944%2==1)=b;generalize e:(!decide (N%274877906944=0))=c;cases b<;>cases c<;>simp at a e⊢<;>(try split_ifs)<;>omega lemma Dn (neg:Bool) (N:Nat) (e':Int) (b:2^62<=N) (c:N<2^63) (j:-148<=e'+39) (k:e'+39+150<=253): toWord (Model.ofModel Fmt (UnpackedFloat.round Format.binary32 (Model.modelSign neg) N e'))=UInt32.ofNat ((if neg then 2^31 else 0)+(e'+39+149).toNat*2^23+GR N):=by have a:2^23<=GR N:=by unfold GR;have:2^23<=N/2^39:=א split<;>omega have d:GR N<=2^24:=by unfold GR;have:N/2^39<2^24:=א split<;>omega have f:N.log2=62:=Bu N 62 b c have g:Format.binary32.targetExponent (totalExponent N e')=e'+39:=by simp only[totalExponent,f,Bt];omega rw[Dl _ N e' _ 38 _ g (by push_cast;ring) (Dm N)] by_cases h:GR N=2^24 . rw[h,show e'+39=e'+40-1 by ring,Bz _ (e'+40) א (by norm_num:0<2^23)];simp only[toWord,Model.toNatBits,Model.ofModel,Model.ofModelBits];congr 1;show (UnpackedFloat.pack Format.binary32 _).toNat=_;rw[B3 _ _ _ _ ב ב א א];have e:(e'+40+150).toNat=(e'+40-1+149).toNat+2:=א;rw[e];cases neg<;>simp[Model.modelSign]<;>omega . have i:0simp[Model.modelSign]<;>omega @[inline] def GS (neg:Bool) (mag e0 L:UInt64):UInt32:= let n:=mag<<<(62-L) let q:=n>>>39 let rm:=n&&&0x7FFFFFFFFF let w:=((e0+L-24)<<<23)+q+ (if rm>0x4000000000 || (rm==0x4000000000&&q&&&1==1) then 1 else 0) (if neg then w ||| 0x80000000 else w).toUInt32 lemma Do (neg:Bool) (mag e0:UInt64) (d:mag.toNat≠0) (l:mag.toNat<2^63) (m:24>>39).toNat=N/2^39:=by rw[м,a1];simp[Nat.shiftRight_eq_div_pow] have a3:(n&&&0x7FFFFFFFFF).toNat=N%2^39:=by rw[э,a1];exact В N 39 generalize n>>>39=q at a2;generalize n&&&0x7FFFFFFFFF=rm at a3;have a4:(q&&&1).toNat=q.toNat%2:=by rw[э];exact В _ 1 have a5:(e0+mag.log2-24).toNat=e0.toNat+L-24:=by rw[UInt64.toNat_sub_of_le _ _ (UInt64.le_iff_toNat_le.2 (by rw[Ы,eL,Г א];show 24<=_;omega)), Ы,eL,Г א] rfl have a6:((e0+mag.log2-24)<<<23).toNat=(e0.toNat+L-24)*2^23:=by rw[UInt64.toNat_shiftLeft,a5,т];show _*2^23%_=_;rw[Г א] generalize (e0+mag.log2-24)<<<23=g at a6;have h:(decide (rm>0x4000000000) || (rm==0x4000000000&&q&&&1==1))=decide (2^38omega omega apply И.mp;rw[е];cases neg;. simp only[Bool.false_eq_true,ite_false,UInt64.toNat_toUInt32,Nat.zero_add,k] . simp only[ite_true,UInt64.toNat_toUInt32,UInt64.toNat_or];have r:w.toNat ||| (2147483648:UInt64).toNat=2^31+w.toNat:=by have:=щ i 1;simp only[Nat.mul_one] at this;rw[this,Nat.or_comm];rfl rw[r];congr 1;omega lemma Dp (w:UInt32) (h:(w&&&0x7FFFFFFF)=0):rationalWord w=0:=by have a:=BA w;rw[h] at a;have d:=w.toNat_lt have b:w=0∨w=0x80000000:=by have:w.toNat=0∨w.toNat=2147483648:=by simp at a;omega rcases this with e | e;. exact Or.inl (И.mp (by simpa using e)) . exact Or.inr (И.mp (by simpa using e)) have c:expOf w=0∧fracOf w=0:=by rcases b with rfl | rfl<;>decide simp[rationalWord,decodeD,c,FloatLib.Numerics.Dyadic.toRat_eq_zero_iff] @[inline] def GT (w:UInt32):UInt64:= if w&&&0x7FFFFFFF==0 then 255 else (expOf w).toUInt64 @[inline] def GU (w:UInt32):UInt64:= if w&&&0x7FFFFFFF==0 then 0 else (fracOf w+0x800000).toUInt64 @[inline] def GV (e0:UInt64) (w:UInt32):UInt64:=GU w<<<(GT w-e0) @[inline] def GW (e0:UInt64) (w:UInt32):Bool:= FX w&&(w&&&0x7FFFFFFF==0 || (e0<=GT w&> w-e0<=37)) @[inline] def GX (e0:UInt64) (w:UInt32) (p:UInt64):UInt64:= if signOf w then p else p+GV e0 w @[inline] def GY (e0:UInt64) (w:UInt32) (n:UInt64):UInt64:= if signOf w then n+GV e0 w else n lemma Dq (e0:UInt64) (w:UInt32) (h:GW e0 w=true): (GV e0 w).toNat<2^61∧rationalWord w= (if signOf w then -((GV e0 w).toNat:ℚ) else ((GV e0 w).toNat:ℚ))*2^((e0.toNat:Int)-150):=by unfold GW at h simp only[Bool.and_eq_true,Bool.or_eq_true,beq_iff_eq,decide_eq_true_eq] at h obtain ⟨f,i⟩:=h by_cases c:w&&&0x7FFFFFFF=0 . have j:GV e0 w=0:=by unfold GV GU;simp[c] rw[j,Dp w c];simp . obtain ⟨d,k⟩:=i.resolve_left c;have g:=BG w f;have a0:(w&&&0x7FFFFFFF).toNat≠0:=λe=>c (И.mp (by simpa using e));rw[BA] at a0;have l:=BD w;have m:(fracOf w).toNat=w.toNat%2^23:=BB w;have n:=w.toNat_lt;have x1:1<=(expOf w).toNat:=א;have x2:(expOf w).toNat<=254:=א;have f1:(fracOf w).toNat<2^23:=א;have ee:(GT w).toNat=(expOf w).toNat:=by unfold GT;simp[c] have em:(GU w).toNat=2^23+(fracOf w).toNat:=by unfold GU;simp only[c,beq_iff_eq,if_false,UInt32.toNat_toUInt64];rw[UInt32.toNat_add,Г (by show _+8388608<_;omega)];show _+8388608=_;omega have l1:=UInt64.le_iff_toNat_le.1 d;have l2:=UInt64.le_iff_toNat_le.1 k;rw[UInt64.toNat_sub_of_le _ _ d,ee] at l2;rw[ee] at l1;have l3:(expOf w).toNat-e0.toNat<=37:=l2 have es:(GV e0 w).toNat=(2^23+(fracOf w).toNat)*2^((expOf w).toNat-e0.toNat):=by unfold GV;have sh:(GT w-e0).toNat%64=(expOf w).toNat-e0.toNat:=by rw[UInt64.toNat_sub_of_le _ _ d,ee];exact Г א rw[UInt64.toNat_shiftLeft,em,sh,т];apply Г;have:2^((expOf w).toNat-e0.toNat)<=2^37:=д ב l3;have:(2^23+(fracOf w).toNat)*2^((expOf w).toNat-e0.toNat)<=2^24*2^37:=Nat.mul_le_mul א this;omega refine ⟨?_,?_⟩;. have a:2^((expOf w).toNat-e0.toNat)<=2^37:=д ב l3;have b:(2^23+(fracOf w).toNat)*2^((expOf w).toNat-e0.toNat)<=(2^24-1)*2^37:=Nat.mul_le_mul א a;rw[es];omega . have nz:expOf w≠0:=λe=>by rw[e] at x1;simp at x1 have ew:(2:ℚ)^(((expOf w).toNat:Int)-150)=2^((expOf w).toNat-e0.toNat)*2^((e0.toNat:Int)-150):=by rw[<-Ц,<-М С];congr 1;omega rw[es];simp only[rationalWord,decodeD,nz,ite_false,FloatLib.Numerics.Dyadic.toRat,FloatLib.Numerics.Dyadic.signedSignificand,ew];cases signOf w<;>simp<;>ring lemma Dr (e0:UInt64) (w:UInt32) (p n:UInt64) (V:ℚ) (B C:Nat) (d:C=2^61-1) (f:B+C<2^63) (a:GW e0 w=true) (g:p.toNat<=B) (h:n.toNat<=B) (b:V=((p.toNat:ℚ)-n.toNat)*2^((e0.toNat:Int)-150)): (GX e0 w p).toNat<=B+C∧(GY e0 w n).toNat<=B+C∧ V+rationalWord w=(((GX e0 w p).toNat:ℚ)-(GY e0 w n).toNat)*2^((e0.toNat:Int)-150):=by obtain ⟨i,c⟩:=Dq e0 w a have j:(GV e0 w).toNat<=C:=א unfold GX GY rw[c,b] cases signOf w . simp only[Bool.false_eq_true,ite_false];have e:(p+GV e0 w).toNat=p.toNat+(GV e0 w).toNat:=by rw[Ы];exact Г א rw[e];refine ⟨by omega,by omega,?_⟩;push_cast;ring . simp only[ite_true];have e:(n+GV e0 w).toNat=n.toNat+(GV e0 w).toNat:=by rw[Ы];exact Г א rw[e];refine ⟨by omega,by omega,?_⟩;push_cast;ring @[inline] def GZ (p n e0:UInt64) (f:Unit->UInt32):UInt32:= if p==n then f () else let mag:=if pUInt32) (t:p.toNat<2^63) (u:n.toNat<2^63) (v:e0.toNat<=255) (R:UInt32) (l:f ()=R) (b:p≠n->∃d:FloatLib.Numerics.Dyadic, d.toRat=((p.toNat:ℚ)-n.toNat)*2^((e0.toNat:Int)-150)∧R=toWord (Model.roundDyadic Fmt d)):GZ p n e0 f=R:=by unfold GZ split . exact l . rename_i g;have a:p≠n:=λe=>g (by simp[e]);have i:p.toNat≠n.toNat:=λe=>a (UInt64.toNat_inj.mp e);obtain ⟨d,o,b⟩:=b a;dsimp only;obtain ⟨mag,j⟩:∃m,m=if pb1 (UInt64.le_iff_toNat_le.2 h);have b4:¬(277:UInt64).toNat<=(e0+mag.log2).toNat:=λh=>b2 (UInt64.le_iff_toNat_le.2 h);rw[eA] at b3 b4;have t1:(24:UInt64).toNat=24:=rfl;have t2:(277:UInt64).toNat=277:=rfl;rw[Do _ _ _ m0 m1 א א,b];congr 1 have s0:d.significand≠0:=by intro s;have:d.toRat=0:=(а d).2 s;rw[o] at this;have q:(p.toNat:ℚ)-n.toNat≠0:=by rw[sub_ne_zero];exact_mod_cast i exact (mul_ne_zero q (zpow_ne_zero _ С)) this refine roundDyadic_congr Fmt (by decide) _ _ m0 s0 ?_;rw[o,<-m2];simp only[FloatLib.Numerics.Dyadic.toRat,FloatLib.Numerics.Dyadic.signedSignificand];cases decide (psimp lemma Dt (w:UInt32):(GT w).toNat<=255:=by unfold GT;split;. decide . have:=BD w;simp only[UInt32.toNat_toUInt64];omega @[inline] def Ga (x y:UInt64):UInt64:=if xArray UInt32->Array UInt32} (f:USize->UInt32->UInt32) {e:USize} (c:∀i x,L i x=if ie.toNat<=x.size->x.size<2^32→ (L i x).size=x.size∧∀q,(L i x)[q]! =if i.toNat<=q∧q intro i x j _ _ rw[c,if_neg (by rw[А];omega)] exact ⟨rfl,λq=>(Д א).symm⟩ | succ d ih=> intro i x j n g have a:i?_⟩ rw[m,CZ _ _ _ _ g א,AS i e a,CX _ _ g] by_cases h:q=i.toNat . subst h;rw[if_neg א,if_pos rfl,if_pos ⟨Nat.le_refl _,by omega⟩,USize.ofNat_toNat] . rw[if_neg h];by_cases b:i.toNat+1<=q∧qX[b.toNat+(t/k*w+t%k)]!) (λ_=>oneW) section open ExactRuntime FloatLib.Floats.Formats.BinaryInterchange FloatLib.Floats open FloatLib.Floats.ExecFloat.Binary open Float.Model Float.Model.UnpackedFloat def Gf (X:Array UInt32) (b:USize) (k w:Nat):UInt32:= if k=2 then let i:=b.toNat let a0:=X[i]! let a1:=X[i+1]! let a2:=X[i+w]! let a3:=X[i+(w+1)]! let e0:=Ga (Ga (GT a0) (GT a1)) (Ga (GT a2) (GT a3)) if GW e0 a0&&GW e0 a1&&GW e0 a2&&GW e0 a3 then GZ (GX e0 a3 (GX e0 a2 (GX e0 a1 (GX e0 a0 0)))) (GY e0 a3 (GY e0 a2 (GY e0 a1 (GY e0 a0 0)))) e0 λ_=>Ge X b k w else Ge X b k w else Ge X b k w lemma Dz (X:Array UInt32) (b:USize) (k w:Nat):Gf X b k w=Ge X b k w:=by unfold Gf;split . rename_i hk;subst hk;dsimp only;split . rename_i hc;simp only[Bool.and_eq_true] at hc;obtain ⟨⟨⟨h0,h1⟩,h2⟩,h3⟩:=hc;generalize hi:b.toNat=i at*;obtain ⟨p1,n1,v⟩:=Dv _ _ _ h0 h1;obtain ⟨p2,n2,v2⟩:=Dw _ _ _ _ _ _ p1 n1 v h2 h3;refine Ds _ _ _ _ p2 n2 ((Du _ _).trans ((Du _ _).trans (Dt _))) _ rfl λhne=>?_;have q0:b.toNat+(0/2*w+0%2)=i:=by simp[hi] have q1:b.toNat+(1/2*w+1%2)=i+1:=by simp[hi] have q2:b.toNat+(2/2*w+2%2)=i+w:=by simp[hi] have q3:b.toNat+(3/2*w+3%2)=i+(w+1):=by simp[hi] have hsum:(∑j∈Finset.range (2*2),rationalWord X[b.toNat+(j/2*w+j%2)]! * rationalWord oneW)=rationalWord X[i]! +rationalWord X[i+1]! +rationalWord X[i+w]! +rationalWord X[i+(w+1)]!:=by rw[show 2*2=4 from rfl] simp only[Finset.sum_range_succ,Finset.sum_range_zero,CP,mul_one,zero_add,q0,q1,q2,q3] have o:expOf oneW≠255:=by decide have hf:∀j,j<2*2->expOf X[b.toNat+(j/2*w+j%2)]!≠255∧expOf oneW≠255:=by intro j hj;rcases (by omega:j=0∨j=1∨j=2∨j=3) with rfl | rfl | rfl | rfl;. rw[q0];exact ⟨Dx _ _ h0,o⟩ . rw[q1];exact ⟨Dx _ _ h1,o⟩ . rw[q2];exact ⟨Dx _ _ h2,o⟩ . rw[q3];exact ⟨Dx _ _ h3,o⟩ obtain ⟨d,h4,h5⟩:=CO (2*2) (λj=>X[b.toNat+(j/2*w+j%2)]!) (λ_=>oneW) hf (by rw[hsum,v2] exact mul_ne_zero (sub_ne_zero.2 λe=>hne (UInt64.toNat_inj.mp (Nat.cast_injective e))) (zpow_ne_zero _ С)) refine ⟨d,?_,?_⟩;. rw[h4,hsum];exact v2 . unfold Ge;rw[AJ];exact h5 . rfl . rfl end @[noinline] def Gg (n:Nat) (s:UInt32):UInt32:= toWord (Model.div (ofW s) (ofW (natW n))) @[inline] def Gh (n:Nat) (j s:UInt32):UInt32:= if jUInt32) (sx:USize) (W x:Nat) (b q:USize) (out:Array UInt32):Array UInt32:= if xUInt32) (sy sx:USize) (W H y:Nat) (b q:USize) (out:Array UInt32):Array UInt32:= if yUInt32) (sc sy sx:USize) (W H c ch:Nat) (b q:USize) (out:Array UInt32):Array UInt32:= if ch(t.val/k*w+t.val%k).toUInt32 @[noinline] def Go (c h w k n:Nat) (X off:Array UInt32) (j z:UInt32) (u nf zb zr:Float): Array UInt32:= Gm (λb=>Gj X off k w n j z u nf zb b n.toUSize 0 zr zr 0) (h*w).toUSize (k*w).toUSize k.toUSize (w/k) (h/k) c 0 0 0 (Array.replicate (c*(h/k*(w/k))) 0) def Gp (c h w k:Nat) (X:Array UInt32):Array UInt32:= if c*h*w<=X.size∧X.size<2^32∧k*k<2^20∧ FY X X.usize 0 (AZ X) 0xFFFFFFFF 0≠0xFFFFFFFF then let n:=k*k let off:=Gn k w let j:UInt32:=if n=4 then 2 else if n=64 then 6 else 255 let z:=Gg n (FO n (λ_=>0) (λ_=>oneW)) Go c h w k n X off j z (dv oneW) (Fd n) (dv 0) 0 else avgpoolSpec c h w k X lemma D0 (s e:Float) (V:ℝ) (a:R (s-e)UInt32) (bw:UInt32) (hx:∀t,tFX (xw t)=true) (hw:∀t,tFX (ww t)=true) (hb:FX bw=true) (s e:Float) (d:FloatLib.Numerics.Dyadic) (hd:(d.toRat:ℝ)=Fc n xw ww bw) (hlo:R (s-e)hV (by rw[<-hc,(а c).mpr h0,ع]) obtain ⟨d',hd',hw'⟩:=CO (n+1) (λt=>if tif tby by_cases hj:jhV (by rw[<-hsum,h0,ع])) rw[CR n hn xw ww bw hx hw hb s e hlo hhi h,hw',roundDyadic_congr Fmt (by decide) d' d (e0 d' (by rw[hd',hsum])) (e0 d hd) (Rat.cast_injective (α:=ℝ) (by rw[hd',hsum,hd]))] def Gq (x y z:UInt32):FloatLib.Numerics.Dyadic:= Model.addDyadic ⟨Bool.xor (decodeD x).negative (decodeD y).negative, (decodeD x).significand*(decodeD y).significand, (decodeD x).exponent+(decodeD y).exponent⟩ (decodeD z) lemma D2 (x y z:UInt32) (a:expOf x≠255) (b:expOf y≠255) (c:expOf z≠255):Model.fma (ofW x) (ofW y) (ofW z)=Model.roundDyadic Fmt (Gq x y z):=by rw[Model.Proof.fma_eq_spec];have e:=toDyadic_ofUInt32 x a;have f:=toDyadic_ofUInt32 y b;have g:=toDyadic_ofUInt32 z c have o:Model.chooseNaN3 (Model.ofUInt32 x:Model Fmt) (Model.ofUInt32 y) (Model.ofUInt32 z)=none:=(Model.chooseNaN3_eq_none_iff _ _ _).2 ⟨Model.isNaN_eq_false_of_toDyadic?_some e,Model.isNaN_eq_false_of_toDyadic?_some f,Model.isNaN_eq_false_of_toDyadic?_some g⟩ simp only[Model.Spec.fma,ofW,o,Model.isInf_eq_false_of_toDyadic?_some e,Model.isInf_eq_false_of_toDyadic?_some f,Model.isInf_eq_false_of_toDyadic?_some g,Bool.or_false,Bool.false_eq_true,ite_false,e,f,g];rfl @[noinline] def Gr (relu:Bool) (x y z:UInt32):UInt32:= if h:expOf x≠255∧expOf y≠255∧expOf z≠255 then act relu (toWord (Model.roundDyadic Fmt (Gq x y z))) else Gc relu x y z lemma D3 (relu:Bool) (x y z:UInt32):Gr relu x y z=Gc relu x y z:=by unfold Gr split ·rename_i h rw[←D2 x y z h.1 h.2.1 h.2.2] rfl ·rfl lemma D4 (x y z:UInt32) (a:expOf x≠255) (b:expOf y≠255) (c:expOf z≠255):((Gq x y z).toRat:ℝ)=wv x*wv y+wv z:=by have j:=FloatLib.Numerics.Dyadic.mul_toRat (decodeD x) (decodeD y);simp only[FloatLib.Numerics.Dyadic.mul,FloatLib.Numerics.Dyadic.mulFields] at j;rw[Gq,Model.addDyadic,FloatLib.Numerics.Dyadic.add_toRat,j,CJ x a,CJ y b,CJ z c];simp only[rationalWord,Rat.cast_add,Rat.cast_mul] lemma D5 (relu:Bool) (r:UInt32) (a:expOf r≠255):Gd relu r=act relu r:=by cases relu;. rfl . show (if signOf r then 0 else r)=if signOf r&& !(expOf r=255&&fracOf r !=0) then 0 else r;simp only[a,decide_false,Bool.false_and,Bool.not_false,Bool.and_true] lemma D6 (w:UInt32):toWord (ofW w)=w:=by apply И.mp;simp only[toWord,ofW,Model.toNatBits,ofUInt32_bits,UInt32.toNat_ofNat'];exact Г w.toBitVec.isLt lemma D7 (w:UInt32) (h:expOf w≠255):Model.toReal (ofW w)=(sv w:ℝ)*2^((idxOf w:ℤ)-149):=by rw[show Model.toReal (ofW w)=wv w from rfl,CJ w h,rationalWord,decodeD_toRat];push_cast;rfl lemma D9 (s j:UInt32) (b:j.toNat<=6) (a:j.toNat<(expOf s).toNat): (expOf (s-(j<<<(23:UInt32)))).toNat=(expOf s).toNat-j.toNat∧fracOf (s-(j<<<(23:UInt32)))=fracOf s∧signOf (s-(j<<<(23:UInt32)))=signOf s:=by rw[BD] at a have c:=s.toNat_lt have e:(j<<<(23:UInt32)).toNat=j.toNat*2^23:=by rw[UInt32.toNat_shiftLeft,т] exact Г (by simp;omega) have f:j<<<(23:UInt32)<=s:=by rw[Ж,e];omega have d:(s-(j<<<(23:UInt32))).toNat=s.toNat-j.toNat*2^23:=by rw[س _ _ f,e] refine ⟨?_,?_,?_⟩ . rw[BD,BD,d];omega . apply И.mp;rw[fracOf,fracOf,BB,BB,d];omega . rw[BE,BE,d];simp;omega lemma EA (s y j:UInt32) (f:j.toNat<=6) (a:expOf s≠255) (b:j.toNat<(expOf s).toNat) (d:expOf y≠255) (g:signOf y=false) (e:mantOf y=2^23) (k:idxOf y=126+j.toNat):toWord (Model.div (ofW s) (ofW y))=s-(j<<<(23:UInt32)):=by have A:sv y=2^23:=by unfold sv;rw[g,e];rfl have B:Model.isZero (ofW y)=false:=by rw[ofW,Model.isZero_eq_beq_zero_of_toDyadic?_some (toDyadic_ofUInt32 y d),decodeD_sig_zero,e];decide obtain ⟨C,D,E⟩:=D9 s j f b;generalize s-(j<<<(23:UInt32))=r at C D E⊢;have N:=expOf_toNat_lt s;have O:(expOf s).toNat≠255:=λF=>a (И.mp (by simpa using F));have l:expOf r≠255:=by intro h;have n:=congrArg UInt32.toNat h;simp at n;omega have q:expOf r≠0:=by intro h;have n:=congrArg UInt32.toNat h;simp at n;omega have t:expOf s≠0:=by intro h;rw[h] at b;simp at b have G:sv r=sv s:=by unfold sv mantOf;rw[E,D,if_neg q,if_neg t] have H:(idxOf r:ℤ)=(idxOf s:ℤ)-j.toNat:=by unfold idxOf;rw[if_neg q,if_neg t,C];omega have o:Model.isFinite (ofW s)=true:=by simp[ofW,isFinite_ofUInt32,a] have u:Model.isFinite (ofW y)=true:=by simp[ofW,isFinite_ofUInt32,d] have v:Model.isFinite (ofW r)=true:=by simp[ofW,isFinite_ofUInt32,l] have x:Model.toReal (ofW y)=2^j.toNat:=by rw[D7 _ d,A,k];push_cast;rw[show ((126:ℤ)+j.toNat-149)=(j.toNat:ℤ)+(-23) by ring,М С,Ц];field_simp;norm_num have I:Model.toReal (ofW r)=Model.toReal (ofW s)/2^j.toNat:=by rw[D7 _ l,D7 _ a,G,H,show ((idxOf s:ℤ)-j.toNat-149)=((idxOf s:ℤ)-149)+-(j.toNat:ℤ) by ring,М С,zpow_neg,Ц];field_simp have J: |Model.toReal (ofW s)/Model.toReal (ofW y)| ≤Model.toReal (Model.posMaxFinite Fmt):=by rw[x,abs_div,abs_of_pos (by positivity:(0:ℝ)<2^j.toNat)];exact (div_le_self (П _) (one_le_pow₀ ב)).trans (Model.abs_toReal_le_posMaxFinite_of_isIEEE_of_isFinite _ (by decide) o) have z:Model.isFinite (Model.div (ofW s) (ofW y))=true:=Model.isFinite_div_of_abs_div_le_posMaxFinite _ _ (by decide) o u B J;have p:=Model.toReal_div_eq_roundAt _ _ (by decide) o u B z;rw[x,<-I,Model.roundAt_toReal_eq _ v] at p have K:Model.toReal (Model.div (ofW s) (ofW y))≠0:=by rw[p,D7 _ l];apply mul_ne_zero _ (zpow_ne_zero _ С);have:sv r≠0:=by unfold sv mantOf;split<;>omega exact_mod_cast this rw[Model.eq_of_toReal_eq_of_nonzero z v p K,D6] lemma EB (n:Nat) (j s:UInt32) (c:j=255∨(j=2∧n=4)∨(j=6∧n=64)):Gh n j s=Gg n s:=by unfold Gh;split . rename_i h;obtain ⟨a,b⟩:=h;have d:=expOf_toNat_lt s;rw[п] at a;rcases c with rfl | ⟨rfl,rfl⟩ | ⟨rfl,rfl⟩;. exfalso;simp at a;omega . exact (EA s _ 2 (by decide) b a (by decide) (by decide) (by decide) (by decide)).symm . exact (EA s _ 6 (by decide) b a (by decide) (by decide) (by decide) (by decide)).symm . rfl def Gs (xw:Nat->UInt32) (l:List Nat) (c:F1):F1:= l.foldl (λ(acc:F1) t=>let q:=dv (xw t)*dv oneW F1.mk (acc.s+q) (acc.t+q.abs)) c lemma EC (X off:Array UInt32) (k w n:Nat) (j z:UInt32) (nf zb:Float) (b m:USize) (xw:Nat->UInt32) (f:∀t:USize,t< m->FT X (b+(FT off t).toUSize)=xw t.toNat) (d:Nat):∀(t:USize) (s a:Float) (o:UInt32),t.toNat+d=m.toNat→ Gj X off k w n j z (dv oneW) nf zb b m t s a o=Gi X b k w n j z nf zb (Gs xw (List.range' t.toNat d) ⟨s,a⟩).s (Gs xw (List.range' t.toNat d) ⟨s,a⟩).t ((List.range' t.toNat d).foldl (λc i=>c ||| xw i) o):=by induction d with | zero=> intro t s a o h rw[Gj,Х (by rw[А];omega)] rfl | succ d ih=> intro t s a o h have e:t< m:=by rw[А];omega rw[Gj,Р e] dsimp only rw[f t e,ih (t+1) _ _ _ (by rw[AS t m e];omega),AS t m e,List.range'_succ] rfl lemma ED (xw:Nat->UInt32) (l:List Nat):∀o:UInt32,l.foldl (λc i=>c ||| xw i) o=0->o=0∧∀i∈l,xw i=0:=by induction l with | nil=>exact λo h=>⟨h,by simp⟩ | cons i l ih=>intro o h;obtain ⟨a,b⟩:=ih _ h;obtain ⟨d,e⟩:=UInt32.or_eq_zero_iff.mp a;exact ⟨d,List.forall_mem_cons.mpr ⟨e,b⟩⟩ lemma EE (n:Nat) (g:n<2^20) (xw:Nat->UInt32) (f:∀t,tFX (xw t)=true) (r:Fa ((Gs xw (List.range n) ⟨0,0⟩).s+dv 0) (Fd n*((Gs xw (List.range n) ⟨0,0⟩).t+(dv 0).abs))≠0xFFFFFFFF): Fa ((Gs xw (List.range n) ⟨0,0⟩).s+dv 0) (Fd n*((Gs xw (List.range n) ⟨0,0⟩).t+(dv 0).abs))=dotOf n xw (λ_=>oneW):=by obtain ⟨-,-,b⟩:=CI _ _ r obtain ⟨c,e⟩:=Bj n g xw (λ_=>oneW) 0 f (λ_ _=>by decide) (by decide) (List.range n) List.nodup_range ג (λt i k=>absurd (н.mpr i) k) _ _ ⟨rfl,rfl⟩ b have a:((∑j∈Finset.range n,rationalWord (xw j)*rationalWord oneW:ℚ):ℝ)=Fc n xw (λ_=>oneW) 0:=by rw[Fc,Bb 0 (by decide) (by decide),add_zero,Rat.cast_sum] refine ы rfl λt l=>?_ rw[Rat.cast_mul,CJ _ (CK _ (f t (Finset.mem_range.mp l))),CJ oneW (by decide)] obtain ⟨d,m,o⟩:=CO n xw (λ_=>oneW) (λj p=>⟨CK _ (f j p),by decide⟩) λh=>D0 _ _ _ c e r (by rw[<-a,h,ع]) rw[o] exact D1 n g xw (λ_=>oneW) 0 f (λ_ _=>by decide) (by decide) _ _ d (by rw[m,a]) c e r lemma EF (X:Array UInt32) (b:USize) (k w n:Nat) (a:n<2^20) (j:UInt32) (d:j=255∨(j=2∧n=4)∨(j=6∧n=64)) (xw:Nat->UInt32) (f:∀t,tFX (xw t)=true) (g:Ge X b k w=dotOf n xw (λ_=>oneW)): Gi X b k w n j (Gg n (FO n (λ_=>0) (λ_=>oneW))) (Fd n) (dv 0) (Gs xw (List.range n) ⟨0,0⟩).s (Gs xw (List.range n) ⟨0,0⟩).t ((List.range n).foldl (λc i=>c ||| xw i) 0)=Gg n (dotOf n xw (λ_=>oneW)):=by unfold Gi split . rename_i l;obtain ⟨-,m⟩:=ED xw _ _ l;have e:dotOf n xw (λ_=>oneW)=dotOf n (λ_=>0) (λ_=>oneW):=by unfold dotOf;congr 2;funext i;exact m _ (н.mpr i.isLt) rw[e,AJ] . dsimp only;rw[EB _ _ _ d];congr 1;split;. rw[Dz];exact g . rename_i o;exact EE _ a xw f (λh=>o (beq_iff_eq.mpr h)) lemma EG {c h w k ch y x t:Nat} (d:chUInt32) (out:Array UInt32) (p:Nat):Prop:= out.size=N∧N<2^32∧∀i,iout[i]! =sp i lemma EH {N p:Nat} {sp:Nat->UInt32} {out:Array UInt32} (h:Gt N sp out p) (f:p?_⟩;rw[CZ _ _ _ _ א א,a];by_cases e:i=p;. rw[if_pos e,e] . rw[if_neg e];exact d i א lemma EI (a s i:Nat):(a+(i+1)*s).toUSize=(a+i*s).toUSize+s.toUSize:=by rw[show a+(i+1)*s=a+i*s+s by ring];simp only[Nat.toUSize_eq,USize.ofNat_add] lemma EJ {L:Nat->USize->USize->Array UInt32->Array UInt32} {g:USize->USize->Array UInt32->Array UInt32} {sb S n N q0 b0:Nat} {sp:Nat->UInt32} (c:∀i b q o,L i b q o=if iGt N sp o (q0+i*S)→Gt N sp (g (b0+i*sb).toUSize (q0+i*S).toUSize o) (q0+(i+1)*S)) (d:Nat): ∀i o,i+d=n->Gt N sp o (q0+i*S)→Gt N sp (L i (b0+i*sb).toUSize (q0+i*S).toUSize o) (q0+n*S):=by induction d with | zero=> intro i o e a rw[c,if_neg א,<-e] exact a | succ d ih=> intro i o e a rw[c,if_pos א,<-EI,<-EI] exact ih (i+1) _ א (f i o א a) lemma EK {f:USize->UInt32} {sc sy sx W H c N:Nat} {sp:Nat->UInt32} (a:c*(H*W)=N) (d:∀ch y t,chytby rw[Gm]) (λch o a1 h=>by have j:(ch+1)*(H*W)<=N:=a▸З _ a1 have:=EJ (L:=Gl f sy.toUSize sx.toUSize W H) (sb:=sy) (S:=W) (n:=H) (N:=N) (q0:=ch*(H*W)) (b0:=ch*sc) (sp:=sp) (λ_ _ _ _=>by rw[Gl]) (λy o a2 h=>by have k:(y+1)*W<=H*W:=З _ a2 rw[ر] at j k have:=EJ (L:=Gk f sx.toUSize W) (g:=λb q o=>FV o q (f b)) (sb:=sx) (S:=1) (n:=W) (N:=N) (q0:=ch*(H*W)+y*W) (b0:=ch*sc+y*sy) (sp:=sp) (λ_ _ _ _=>by rw[Gk];rfl) (λi o a3 h=>by have e1:ch*(H*W)+y*W+(i+1)*1=ch*(H*W)+y*W+i*1+1:=א have e2:ch*(H*W)+y*W+i=ch*(H*W)+y*W+i*1:=א rw[e1,d ch y i a1 a2 a3,e2] exact EH h א _ (CU _ (by have:=h.2.1;omega))) W 0 o א (by simpa using h) simpa [Nat.succ_mul,Nat.add_assoc] using this) H 0 o א (by simpa using h) simpa [Nat.succ_mul,Nat.add_assoc] using this) c 0 o א (by simpa using e) simp only[Nat.zero_mul,Nat.zero_add,Nat.add_zero,a] at this exact this lemma EL {c H W q:Nat} (b:qUInt32) (c h w k:Nat) (g:c*h*w<2^32): Gm f (h*w).toUSize (k*w).toUSize k.toUSize (w/k) (h/k) c 0 0 0 (Array.replicate (c*(h/k*(w/k))) 0)= Array.ofFn (n:=c*(h/k*(w/k))) λq=>let ch:=q.val/(h/k*(w/k)) let y:=q.val/(w/k)%(h/k) let x:=q.val%(w/k) f ((ch*h+y*k)*w+x*k).toUSize:=by have j:c*(h/k*(w/k))<2^32:=by have a:h/k*(w/k)<=h*w:=Nat.mul_le_mul (Nat.div_le_self _ _) (Nat.div_le_self _ _) exact в ((Nat.mul_le_mul_left c a).trans (Nat.mul_assoc c h w).symm.le) g generalize m:h/k=H at* generalize o:w/k=W at* have d:=EK (f:=f) (sc:=h*w) (sy:=k*w) (sx:=k) (W:=W) (H:=H) (c:=c) (sp:=λq=>f ((q/(H*W)*h+q/W%H*k)*w+q%W*k).toUSize) rfl (λch y t a b l=>by obtain ⟨d1,d2⟩:=Br W (H*ch+y) t l obtain ⟨d3,d4⟩:=Br H ch y b have e:ch*(H*W)+y*W+t=W*(H*ch+y)+t:=by ring rw[e,d2,о H W,<-ذ,d1,d3,d4] congr 2 ring) (Array.replicate (c*(H*W)) 0) ⟨by simp,j,by simp⟩ apply ъ (by rw[d.1,Array.size_ofFn]) intro i a b rw[<-Е _ i a,d.2.2 i (by simpa using b),Array.getElem_ofFn] lemma EN {c h w k ch y x:Nat} {X:Array UInt32} (l:c*h*w<2^32) (b:X.size<2^32) (d:k*k<2^32) (e:ch(t/k*w+t%k).toUInt32) _ a,CX _ _ b] have e1:((t.toNat/k*w+t.toNat%k).toUInt32.toUSize).toNat=t.toNat/k*w+t.toNat%k:=by rw[Т,Nat.toUInt32_eq,е] exact Г א have e2:((ch*h+y*k)*w+x*k).toUSize.toNat=(ch*h+y*k)*w+x*k:=CU _ א show _=X[(ch*h+y*k+t.toNat/k)*w+x*k+t.toNat%k]! rw[AT _ _ (by rw[e1,e2];omega),e1,e2,e0] lemma EO {c h w k ch y x:Nat} {X:Array UInt32} (r:c*h*w<=X.size) (m:X.size<2^32) (n:k*k<2^20) (o:∀i,iFX X[i]! =true) (d:ch0) (λ_=>oneW))) (dv oneW) (Fd (k*k)) (dv 0) ((ch*h+y*k)*w+x*k).toUSize (k*k).toUSize 0 0 0 0= Gg (k*k) (dotOf (k*k) (poolAt h w k X ch y x) (λ_=>oneW)):=by have f:(k*k).toUSize.toNat=k*k:=CU _ א have q:0(ch*h+y*k+t/k)*w+x*k+t%kEG d b e a have e2:((ch*h+y*k)*w+x*k).toUSize.toNat=(ch*h+y*k)*w+x*k:=CU _ (by have:=l 0 q;simp at this;omega) rw[EC X _ k w (k*k) j _ _ _ _ _ (poolAt h w k X ch y x) (λt a=>EN א m א d b e t (by rw[А,f] at a;exact a)) (k*k) 0 0 0 0 (by rw[f,show (0:USize).toNat=0 from rfl,К]), show (0:USize).toNat=0 from rfl,<-List.range_eq_range'] refine EF X _ k w _ n j p _ (λt a=>o _ (by have:=l t a;omega)) ?_ unfold Ge rw[AJ] congr 1 funext t rw[e2] show _=X[(ch*h+y*k+t/k)*w+x*k+t%k]! congr 1 ring lemma EP:Gp=avgpoolSpec:=by funext c h w k X;unfold Gp;split . rename_i b;obtain ⟨d,a,e,f⟩:=b;simp only[avgpoolSpec,avgpoolWith];rw[Go,EM _ c h w k א];apply congrArg Array.ofFn;funext ⟨q,g⟩;obtain ⟨a1,a2,a3⟩:=EL g;dsimp only;refine EO d a e (Ck X a f).2.2.1 a1 a2 a3 _ ?_;split_ifs with e1 e2;. exact Or.inr (Or.inl ⟨rfl,e1⟩) . exact Or.inr (Or.inr ⟨rfl,e2⟩) . exact Or.inl rfl . rfl end section open ExactRuntime def Gu (rows inW outW:Nat) (relu:Bool) (X W b:Array UInt32):Array UInt32:= if rows=1 then GF ⟨inW,1,1,outW,1,1,1,0⟩ relu X W b else linearWith FO rows inW outW relu X W b lemma EQ (inW outW:Nat) (relu:Bool) (X W b:Array UInt32):linearSpec 1 inW outW relu X W b=conv2dSpec ⟨inW,1,1,outW,1,1,1,0⟩ relu X W b:=by simp only[linearSpec,linearWith,conv2dSpec,conv2dWith,ConvShape.ho,ConvShape.wo];apply ъ;. simp . intro q c d;have a:q>>(31:UInt32)==0 then 0x80000000+m else 0x80000000-m @[inline] def Gw (a b:Word):Word:= if a&&&0x7F800000==0x7F800000 || b&&&0x7F800000==0x7F800000 then FQ a b else let p:=Gv a let q:=Gv b if p?_;unfold Gx;by_cases a:m%2^23+1<2^23 . rw[show (m+1)/2^23=m/2^23 by omega,show (m+1)%2^23=m%2^23+1 by omega];split;. omega . exact Ш א (Nat.two_pow_pos _) . rw[show (m+1)/2^23=m/2^23+1 by omega,show (m+1)%2^23=0 by omega,show m%2^23=2^23-1 by omega];cases m/2^23 with | zero=>norm_num | succ e=>have:=Nat.two_pow_pos e;rw[Д א,Д א,Nat.add_sub_cancel,Nat.add_sub_cancel,pow_succ];omega lemma ET (w:Word):(w&&&0x7FFFFFFF).toNat=w.toNat%2^31∧(expOf w).toNat=w.toNat%2^31/2^23∧(fracOf w).toNat=w.toNat%2^31%2^23:=by have h:w.toNat<2^32:=w.toNat_lt;have a1:(0x7FFFFFFF:UInt32).toNat=2^31-1:=rfl;have a2:(0xFF:UInt32).toNat=2^8-1:=rfl;have a3:(0x7FFFFF:UInt32).toNat=2^23-1:=rfl;have a4:(23:UInt32).toNat%32=23:=rfl;unfold expOf fracOf;rw[О,О,О,л,a1,a2,a3,a4,В,В,В,Ю];omega lemma EU (w:Word):signOf w=true↔2^31<=w.toNat:=by have h:w.toNat<2^32:=w.toNat_lt;have a1:(0x80000000:UInt32).toNat=2^31:=rfl;unfold signOf;rw[bne_iff_ne,ne_eq,<-И,О,a1,Nat.and_two_pow,Nat.testBit_eq_decide_div_mod_eq];by_cases c:w.toNat/2^31%2=1;. rw[decide_eq_true c];simp only[Bool.toNat_true,UInt32.toNat_zero];omega . rw[decide_eq_false c];simp only[Bool.toNat_false,UInt32.toNat_zero];omega lemma EV (w:Word):mantOf w<<< idxOf w=Gx (w.toNat%2^31):=by obtain ⟨-,a,b⟩:=ET w;unfold mantOf idxOf Gx;rw[т];by_cases h:expOf w=0;. rw[Л h,Л h,Л (by rw[<-a,h];rfl),b,pow_zero,Nat.mul_one] . rw[Д h,Д h,Д (λe=>h (И.mp (by rw[a,e];rfl))),a,b] lemma EW (w:Word):FP w=if w.toNat<2^31 then (Gx (w.toNat%2^31):Int) else -(Gx (w.toNat%2^31):Int):=by unfold FP;rw[EV];by_cases c:w.toNat<2^31;. rw[Л c,Д (λe=>by have:=(EU w).mp e;omega)] . rw[Д c,Л ((EU w).mpr א)] lemma EX (w:Word):(Gv w).toNat=if w.toNat<2^31 then 2^31+w.toNat%2^31 else 2^31-w.toNat%2^31:=by have h:w.toNat<2^32:=w.toNat_lt;have a1:(0x80000000:UInt32).toNat=2^31:=rfl;have a2:(31:UInt32).toNat%32=31:=rfl;have e:(w>>>(31:UInt32)).toNat=w.toNat/2^31:=by rw[л,a2,Ю] have a:=(ET w).1;unfold Gv;dsimp only;by_cases c:w.toNat<2^31;. have e0:w>>>(31:UInt32)=0:=И.mp (by rw[e,UInt32.toNat_zero];omega);rw[e0,Л (show ((0:UInt32)==0)=true from rfl),Л c,UInt32.toNat_add,a,a1];omega . have e0:(w>>>(31:UInt32)==0)=false:=by rw[beq_eq_false_iff_ne];intro b;rw[b,UInt32.toNat_zero] at e;omega rw[e0,Д ג,Д c,UInt32.toNat_sub,a,a1];omega lemma EY (a b:Word) (h:Gv a0by have:=ES c;omega by_cases c1:a.toNat<2^31<;>by_cases c2:b.toNat<2^31<;>simp only[c1,c2,ite_true,ite_false] at d⊢;. have:=ES (א:a.toNat%2^31>>n)&&&m)<<decide . rw[Д (by simpa using b)];exact AK a lemma Ed (a b:Word):Gw a b=FQ a b:=by unfold Gw;by_cases g:(a&&&0x7F800000==0x7F800000 || b&&&0x7F800000==0x7F800000)=true;. rw[Л g] . rw[Д g];simp only[Bool.or_eq_true,not_or] at g;have f:=Ea a g.1;have c:=Ea b g.2;have d:¬(expOf a=255∨expOf b=255):=by simp[f,c] dsimp only;by_cases p:Gv aGy inp off b (k*k).toUSize 0 (FT inp b)) (h*w).toUSize (k*w).toUSize k.toUSize (w/k) (h/k) c 0 0 0 (Array.replicate (c*(h/k*(w/k))) 0) else FR c h w k inp lemma Ee (X off:Array UInt32) (b m:USize) (xw:Nat->UInt32) (e:∀t:USize,t< m->FT X (b+(FT off t).toUSize)=xw t.toNat) (d:Nat): ∀(t:USize) (a:UInt32),t.toNat+d=m.toNat→Gy X off b m t a=(List.range' t.toNat d).foldl (λa i=>Gw a (xw i)) a:=by induction d with | zero=> intro t a h rw[Gy,Х (by rw[А];omega)] rfl | succ d ih=> intro t a h have c:t< m:=by rw[А];omega rw[Gy,Р c,e t c,ih (t+1) _ (by rw[AS t m c];omega),AS t m c,List.range'_succ,List.foldl_cons] lemma Ef:Gz=maxpoolSpec:=by rw[<-AR];funext c h w k inp;unfold Gz;split . rename_i j;obtain ⟨a,b,d⟩:=j;rw[EM _ c h w k a];simp only[FR];apply congrArg Array.ofFn;funext ⟨q,l⟩;obtain ⟨a1,a2,a3⟩:=EL l;dsimp only;have f:(k*k).toUSize.toNat=k*k:=CU _ d have e:∀{ch y x:Nat},chyxEN a b d a1 a2 a3 t (by rw[А,f] at i;exact i)) (k*k) 0 _ (by rw[f,show (0:USize).toNat=0 from rfl,К]),show (0:USize).toNat=0 from rfl,<-List.range_eq_range'];simp only[Ed] . rfl end end Submission namespace Submission open ExactRuntime @[inline] def G0 (X:Array Word) (w:Nat) (z:Word) (u nf zb:Float) (b:USize):Word:= let a0:=FT X b let a1:=FT X (b+1) let a2:=FT X (b+w.toUSize) let a3:=FT X (b+w.toUSize+1) let d0:=dv a0*u let d1:=dv a1*u let d2:=dv a2*u let d3:=dv a3*u Gi X b 2 w 4 2 z nf zb ((((0:Float)+d0)+d1)+d2+d3) ((((0:Float)+d0.abs)+d1.abs)+d2.abs+d3.abs) (a0|||a1|||a2|||a3) lemma off (w:Nat) (t:USize) (a:t.toNat<4):FT (Gn 2 w) t=(t.toNat/2*w+t.toNat%2).toUInt32:=by rw [CX _ _ (by simp [Gn])] unfold Gn exact AI 4 (fun t=>(t/2*w+t%2).toUInt32) t.toNat a lemma Eg (w:Nat) (a:w<2^32):w.toUInt32.toUSize=w.toUSize:=by apply USize.toNat_inj.mp rw [UInt32.toNat_toUSize,Nat.toUInt32_eq,UInt32.toNat_ofNat',Nat.mod_eq_of_lt a,CU w a] lemma Eh (X:Array Word) (w:Nat) (n:w+1<2^32) (z:Word) (u nf zb:Float) (b:USize): G0 X w z u nf zb b=Gj X (Gn 2 w) 2 w 4 2 z u nf zb b 4 0 0 0 0:=by have j:=off w 0 (by simp) have k:=off w 1 (by simp) have l:=off w 2 (by simp) have m:=off w 3 (by simp) norm_num [USize.toNat_ofNat_of_lt_32] at j k l m unfold G0 have e:(0:USize)<4:=by simp [USize.lt_iff_toNat_lt] have f:(1:USize)<4:=by simp [USize.lt_iff_toNat_lt] have g:(2:USize)<4:=by simp [USize.lt_iff_toNat_lt] have h:(3:USize)<4:=by simp [USize.lt_iff_toNat_lt] have a:(1:USize)+1=2:=by apply USize.toNat_inj.mp;rw[AT 1 1 (by simp)];simp have c:(2:USize)+1=3:=by apply USize.toNat_inj.mp;rw[AT 2 1 (by simp)];simp have d:(3:USize)+1=4:=by apply USize.toNat_inj.mp;rw[AT 3 1 (by simp)];simp rw [Gj,dif_pos e,USize.zero_add] rw [Gj,dif_pos f,a] rw [Gj,dif_pos g,c] rw [Gj,dif_pos h,d] rw [Gj,dif_neg (show¬(4:USize)<4 from by simp [USize.lt_iff_toNat_lt])] have i:FT (Gn 2 w) 3=(w+1).toUInt32:=by simpa [Nat.toUInt32_eq,UInt32.ofNat_add] using m rw [j,k,l,i] have o:(0:UInt32).toUSize=(0:USize):=by apply USize.toNat_inj.mp;simp [UInt32.toNat_toUSize] have p:(1:UInt32).toUSize=(1:USize):=by apply USize.toNat_inj.mp;simp [UInt32.toNat_toUSize] rw [o,p,Eg w (by omega),Eg (w+1) n] simp [Nat.toUSize_eq,USize.ofNat_add,USize.add_assoc] def G1 (c h w k:Nat) (X:Array Word):Array Word:= if c*h*w<=X.size&&X.size<2^32&&k*k<2^20&&X.all FX then let n:=k*k let j:UInt32:=if n=4 then 2 else if n=64 then 6 else 255 let z:=Gg n (FO n (fun _=>0) (fun _=>oneW)) if k==2&&w+1<2^32 then Gm (G0 X w z (dv oneW) (Fd 4) (dv 0)) (h*w).toUSize (2*w).toUSize 2 (w/2) (h/2) c 0 0 0 (Array.replicate (c*(h/2*(w/2))) 0) else Go c h w k n X (Gn k w) j z (dv oneW) (Fd n) (dv 0) 0 else Gp c h w k X lemma Ei (c h w k:Nat) (X:Array Word) (a:c*h*w≤X.size) (b:X.size<2^32) (d:k*k<2^20) (e:∀i,i0) (fun _=>oneW))) (dv oneW) (Fd (k*k)) (dv 0) 0=avgpoolSpec c h w k X:=by unfold avgpoolSpec avgpoolWith rw [Go,EM _ c h w k (lt_of_le_of_lt a b)] apply congrArg Array.ofFn funext ⟨q,f⟩ obtain ⟨a1,a2,a3⟩:=EL f dsimp only refine EO a b d e a1 a2 a3 _ ?_ split_ifs with e1 e2 ·exact Or.inr (Or.inl ⟨rfl,e1⟩) ·exact Or.inr (Or.inr ⟨rfl,e2⟩) ·exact Or.inl rfl lemma Ej:G1=avgpoolSpec:=by funext c h w k X unfold G1 split ·rename_i d simp only [Bool.and_eq_true,decide_eq_true_eq] at d obtain ⟨⟨⟨e,f⟩,g⟩,m⟩:=d have a: ∀i,i Gg (k.val*k.val) (FO (k.val*k.val) (fun _=>0) (fun _=>oneW)) def G3 (k:Nat):Word:= if h:k<16 then G2[k]'(by simp [G2];exact h) else Gg (k*k) (FO (k*k) (fun _=>0) (fun _=>oneW)) lemma Ek (k:Nat):G3 k=Gg (k*k) (FO (k*k) (fun _=>0) (fun _=>oneW)):=by unfold G3 split ·simp only [G2,Array.getElem_ofFn] ·rfl def G4 (c h w k:Nat) (X:Array Word):Array Word:= if c*h*w<=X.size&&X.size<2^32&&k*k<2^20&&X.all FX then let n:=k*k let j:UInt32:=if n=4 then 2 else if n=64 then 6 else 255 let z:=G3 k if k==2&&w+1<2^32 then Gm (G0 X w z (dv oneW) (Fd 4) (dv 0)) (h*w).toUSize (2*w).toUSize 2 (w/2) (h/2) c 0 0 0 (Array.replicate (c*(h/2*(w/2))) 0) else Go c h w k n X (Gn k w) j z (dv oneW) (Fd n) (dv 0) 0 else Gp c h w k X @[inline] def G5 (a b:Word):Word:=if asimp_all only[UInt32.le_iff_toNat_le,UInt32.lt_iff_toNat_lt]<;>omega lemma Em (a:Word):G5 a a=a:=by simp[G5] lemma En (a b c:Word):G5 (G5 a b) c=G5 a (G5 b c):=by unfold G5 split_ifs<;>apply UInt32.toNat_inj.mp<;> simp_all only[UInt32.lt_iff_toNat_lt]<;>omega lemma Eo (a b:Word) (m:a<0x7F800000) (n:b<0x7F800000):Gw a b=G5 a b:=by have d:=UInt32.lt_iff_toNat_lt.mp m norm_num only [UInt32.reduceToNat] at d have f:=UInt32.lt_iff_toNat_lt.mp n norm_num only [UInt32.reduceToNat] at f have i:a.toNat<2^31:=by omega have j:b.toNat<2^31:=by omega have nmask (w:Word) (o:w.toNat<0x7F800000):w&&&0x7F800000≠0x7F800000:=by intro h have l:(w&&&0x7F800000).toNat≤w.toNat:=by rw[UInt32.toNat_and];exact Nat.and_le_left rw[h] at l norm_num only [UInt32.reduceToNat] at l omega have g:(a&&&0x7F800000==0x7F800000 || b&&&0x7F800000==0x7F800000)=false:=by simp[nmask a d,nmask b f] have oa:(Gv a).toNat=2^31+a.toNat:=by rw[EX,if_pos i,Nat.mod_eq_of_lt i] have ob:(Gv b).toNat=2^31+b.toNat:=by rw[EX,if_pos j,Nat.mod_eq_of_lt j] rw[Gw,g] simp only[Bool.false_eq_true,ite_false] by_cases c:asimp_all only[UInt32.le_iff_toNat_le,UInt32.lt_iff_toNat_lt]<;>omega have f:a<0x7F800000:=by simp only[UInt32.le_iff_toNat_le,UInt32.lt_iff_toNat_lt] at*;omega have i:b<0x7F800000:=by simp only[UInt32.le_iff_toNat_le,UInt32.lt_iff_toNat_lt] at*;omega have j:c<0x7F800000:=by simp only[UInt32.le_iff_toNat_le,UInt32.lt_iff_toNat_lt] at*;omega have k:d<0x7F800000:=by simp only[UInt32.le_iff_toNat_le,UInt32.lt_iff_toNat_lt] at*;omega have g:G5 a b<0x7F800000:=by simp only[UInt32.le_iff_toNat_le,UInt32.lt_iff_toNat_lt] at*;omega have e:G5 (G5 a b) c<0x7F800000:=by simp only[UInt32.le_iff_toNat_le,UInt32.lt_iff_toNat_lt] at*;omega rw[Eo a a f f,Em,Eo a b f i,Eo (G5 a b) c g j, Eo (G5 (G5 a b) c) d e k,En] @[inline] def G6 (inp:Array UInt32) (w:Nat) (b:USize):UInt32:= let v0:=FT inp b let v1:=FT inp (b+1) let v2:=FT inp (b+w.toUInt32.toUSize) let v3:=FT inp (b+(w+1).toUInt32.toUSize) Gw (Gw (Gw (Gw v0 v0) v1) v2) v3 @[inline] def G7 (inp:Array UInt32) (w:Nat) (b:USize):UInt32:= let v0:=FT inp b let v1:=FT inp (b+1) let v2:=FT inp (b+w.toUInt32.toUSize) let v3:=FT inp (b+(w+1).toUInt32.toUSize) let z:=G5 (G5 v0 v1) (G5 v2 v3) if z<0x7F800000 then z else G6 inp w b lemma Eq (inp:Array UInt32) (w:Nat) (b:USize):G7 inp w b=G6 inp w b:=by unfold G7 dsimp only split ·rename_i h exact (Ep _ _ _ _ h).symm ·rfl def G8 (c h w k:Nat) (inp:Array UInt32):Array UInt32:= if k==2&&c*h*w<2^32&&inp.size<2^32 then Gm (G7 inp w) (h*w).toUSize (2*w).toUSize 2 (w/2) (h/2) c 0 0 0 (Array.replicate (c*(h/2*(w/2))) 0) else Gz c h w k inp private theorem four_mod:4 % 2^System.Platform.numBits=4:=by have hs:2^32≤USize.size:=USize.le_size change 2^32≤2^System.Platform.numBits at hs apply Nat.mod_eq_of_lt omega private theorem small_mod (n:Nat) (h:n≤4):n % 2^System.Platform.numBits=n:=by have hs:2^32≤USize.size:=USize.le_size change 2^32≤2^System.Platform.numBits at hs apply Nat.mod_eq_of_lt omega private theorem add11:(1:USize)+1=2:=by apply USize.toNat_inj.mp norm_num [USize.toNat_add,USize.toNat_ofNat',small_mod] private theorem add21:(2:USize)+1=3:=by apply USize.toNat_inj.mp norm_num [USize.toNat_add,USize.toNat_ofNat',small_mod] lemma Er (w:Nat):FT (Gn 2 w) 0=0:=by simp [Gn,FT] lemma Es (w:Nat):FT (Gn 2 w) 1=1:=by simp [Gn,FT,USize.lt_iff_toNat_lt,four_mod] lemma Et (w:Nat):FT (Gn 2 w) 2=w.toUInt32:=by simp [Gn,FT,USize.le_iff_toNat_le,four_mod] lemma Eu (w:Nat):FT (Gn 2 w) 3=(w+1).toUInt32:=by simp [Gn,FT,USize.le_iff_toNat_le,four_mod] lemma Ev (inp:Array UInt32) (w:Nat) (b:USize): G7 inp w b= Gy inp (Gn 2 w) b (4:USize) 0 (FT inp b):=by set_option maxHeartbeats 1000000 in rw[Eq] simp [G6,Gy,Er,Es,Et,Eu, USize.lt_iff_toNat_lt,four_mod,small_mod,add11,add21] lemma Ew (c h w k:Nat) (inp:Array UInt32): G8 c h w k inp=Gz c h w k inp:=by unfold G8 split ·rename_i a simp only [Bool.and_eq_true,beq_iff_eq,decide_eq_true_eq] at a obtain ⟨⟨f,d⟩,e⟩:=a subst k unfold Gz simp only [d,e,show 2*2<2^32 by norm_num,and_self,↓reduceIte] congr 1 funext b exact Ev inp w b ·rfl lemma Ex:G4=G1:=by funext c h w k X simp only [G4,G1,Ek] lemma Ey:G4=avgpoolSpec:=Ex.trans Submission.Ej end Submission namespace RootNativeFinite open ExactRuntime FloatLib.Floats.Formats.BinaryInterchange open Float.Model.UnpackedFloat lemma Ez (w:Word) (b:expOf w≠255): unpackExponent (spec:=Float.Model.Format.binary32) w.toBitVec≠ -1#8:=by intro h have c:=congrArg BitVec.toNat h have a:w.toNat/2^23 % 2^8=255:=by simpa [unpackExponent,Nat.shiftRight_eq_div_pow] using c apply b apply UInt32.toNat_inj.mp simp only [expOf,UInt32.toNat_and,UInt32.toNat_shiftRight] change (w.toNat>>>23&&&255)=255 conv_lhs=>rw [show (255:Nat)=2^8-1 from rfl,Nat.and_two_pow_sub_one_eq_mod,Nat.shiftRight_eq_div_pow] exact a lemma E0 (w:Word) (a:expOf w≠255):(Float32.ofBits w).toBits=w:=by change UInt32.ofBitVec (pack Float.Model.Format.binary32 (unpack Float.Model.Format.binary32 w.toBitVec))=w rw [Model.pack_unpack_eq] have b:=Ez w a rw [if_neg (by intro h;exact b h.1)] lemma finite (w:Word) (a:expOf w≠255):(Float32.ofBits w).isFinite=true:=by change (unpack Float.Model.Format.binary32 (Float32.ofBits w).toBits.toBitVec).isFinite=true rw [E0 w a] simp only [unpack,Ez w a,ite_false] split ·split<;>rfl ·rfl end RootNativeFinite namespace FastResidual open FloatLib.Floats.Formats.BinaryInterchange FloatLib.Floats.ExecFloat lemma E1 (z:Float32): Model.ofFloat32Model z.toModel= (Model.ofUInt32 z.toBits:Model ExactRuntime.Fmt):=by change Model.ofModelBits (fmt:=ExactRuntime.Fmt) (z.toBits.toBitVec)= (Model.ofNatBits z.toBits.toNat:Model ExactRuntime.Fmt) unfold Model.ofModelBits Model.ofNatBits Model.ofBits FloatFormat.ofWordNat congr 1 change z.toBits.toBitVec=BitVec.ofNat 32 z.toBits.toNat exact (BitVec.ofNat_toNat 32 z.toBits.toBitVec).symm lemma E2 (w:UInt32) (a:(Float32.ofBits w).toBits=w): Model.ofFloat32Model (Float32.ofBits w).toModel= (Model.ofUInt32 w:Model ExactRuntime.Fmt):=by rw [E1,a] lemma E3 (w:UInt32): ExactRuntime.toWord (Model.ofUInt32 w:Model ExactRuntime.Fmt)=w:=by change UInt32.ofNat (w.toNat % 2^32)=w rw [Nat.mod_eq_of_lt (by simpa using w.toNat_lt_size)] exact UInt32.ofNat_toNat lemma E4 (x y:UInt32) (g:(Float32.ofBits x).isFinite=true) (i:(Float32.ofBits y).isFinite=true) (a:(Float32.ofBits x).toBits=x) (b:(Float32.ofBits y).toBits=y): (Float32.ofBits x+Float32.ofBits y).toBits= ExactRuntime.toWord (Model.add (ExactRuntime.ofW x) (ExactRuntime.ofW y)):=by let fx:=Float32.ofBits x let fy:=Float32.ofBits y have c:(Model.toModel (Model.ofFloat32Model fx.toModel)).isFinite=true:=by change fx.toModel.unpack.isFinite=true exact g have d:(Model.toModel (Model.ofFloat32Model fy.toModel)).isFinite=true:=by change fy.toModel.unpack.isFinite=true exact i have e:fx.toModel.unpack=(ExactRuntime.ofW x).toModel:=by exact congrArg (fun z:Model ExactRuntime.Fmt=>z.toModel) (E2 x a) have f:fy.toModel.unpack=(ExactRuntime.ofW y).toModel:=by exact congrArg (fun z:Model ExactRuntime.Fmt=>z.toModel) (E2 y b) have j:Model.ofFloat32Model (fx+fy).toModel= Model.add (ExactRuntime.ofW x) (ExactRuntime.ofW y):=by change Model.ofFloat32Model (Float32.Model.add fx.toModel fy.toModel)=_ rw [Float32.Model.add,Model.ofFloat32Model_pack] rw [e,f] have h:=Model.add_eq_ofModel_add_of_isFinite (fmt:=ExactRuntime.Fmt) (by decide) (Model.ofFloat32Model fx.toModel) (Model.ofFloat32Model fy.toModel) c d rw [E2 x a,E2 y b] at h exact h.symm have k:=congrArg ExactRuntime.toWord j simpa only [E1,E3] using k end FastResidual namespace NativeBitsOneFile open ExactRuntime @[inline] def G9 (relu:Bool) (x y:UInt32):UInt32:= if hx:expOf x≠255∧expOf y≠255 then act relu (Float32.ofBits x+Float32.ofBits y).toBits else Submission.Gb relu x y def HA (relu:Bool) (b:Array Word) (e i:USize) (a:Array Word):Array Word:= if h:iG9 relu w (Submission.FT b i)) (by intro i x;rw [HA];rfl) a.size 0 a (by rw [k];simp) (by rw [k]) c apply Array.ext ·rw [l.1];simp [addReluSpec] ·intro i n o have j:iby omega local notation"ב"=>by norm_num local notation"ג"=>by simp local notation"ד"=>by linarith local notation"А"=>USize.lt_iff_toNat_lt local notation"Б"=>mul_le_mul_of_nonneg_right local notation"В"=>Nat.and_two_pow_sub_one_eq_mod local notation"Г"=>Nat.mod_eq_of_lt local notation"Д"=>ite_eq_right local notation"Е"=>getElem!_pos local notation"Ж"=>UInt32.le_iff_toNat_le local notation"З"=>Nat.mul_le_mul_right local notation"И"=>UInt32.toNat_inj local notation"Й"=>mul_le_mul_of_nonneg_left local notation"К"=>Nat.zero_add local notation"Л"=>ite_eq_left local notation"М"=>zpow_add₀ local notation"Н"=>abs_nonneg local notation"О"=>Nat.pos_of_ne_zero local notation"П"=>Nat.cast_nonneg local notation"Р"=>abs_of_nonneg local notation"С"=>UInt32.toNat_and local notation"Т"=>two_ne_zero local notation"У"=>zpow_le_zpow_right₀ local notation"Ф"=>dite_eq_left local notation"Х"=>UInt32.toNat_toUSize local notation"Ц"=>abs_add_le local notation"Ч"=>dite_eq_right local notation"Ш"=>mul_nonneg local notation"Щ"=>mul_lt_mul_of_pos_right local notation"Ъ"=>UInt64.toNat_add local notation"Ы"=>Nat.mod_lt local notation"Ь"=>USize.toNat_one local notation"Э"=>zpow_natCast local notation"Ю"=>FloatLib.Numerics.Dyadic.cast_toRat local notation"Я"=>Nat.shiftRight_eq_div_pow local notation"а"=>Nat.add_zero local notation"б"=>FloatLib.Numerics.Dyadic.toRat_eq_zero_iff local notation"в"=>getElem!_neg local notation"г"=>mul_le_mul local notation"д"=>Nat.add_assoc local notation"е"=>Nat.pow_le_pow_right local notation"ж"=>Nat.lt_or_eq_of_le local notation"з"=>Nat.le_mul_of_pos_right local notation"и"=>Nat.pos_of_mul_pos_left local notation"й"=>UInt32.toNat_shiftRight local notation"к"=>UInt64.toNat_shiftRight local notation"л"=>List.mem_range local notation"м"=>Nat.mul_comm local notation"н"=>UInt32.lt_iff_toNat_lt local notation"о"=>UInt64.lt_iff_toNat_lt local notation"п"=>zpow_pos local notation"р"=>Nat.div_eq_of_lt local notation"с"=>Nat.shiftLeft_eq local notation"т"=>Bool.and_eq_true_iff local notation"у"=>Nat.add_mul local notation"ф"=>Nat.div_lt_of_lt_mul local notation"х"=>Nat.one_mul local notation"ц"=>Nat.pow_add local notation"ч"=>Nat.lt_succ_iff local notation"ш"=>UInt32.toNat_ofNat' local notation"щ"=>Nat.two_pow_add_eq_or_of_lt local notation"ъ"=>Array.ext local notation"ы"=>Finset.sum_congr local notation"ь"=>Nat.exists_eq_add_of_le local notation"э"=>UInt64.toNat_and local notation"ю"=>lt_of_mul_lt_mul_right local notation"я"=>Nat.div_div_eq_div_mul local notation"ذ"=>Nat.succ_mul local notation"ر"=>Nat.succ_pos local notation"ز"=>UInt32.toNat_sub_of_le local notation"س"=>List.mem_filter local notation"ش"=>Nat.mod_add_div local notation"ص"=>Array.getElem_push_eq local notation"ض"=>Array.getElem_push_lt local notation"ط"=>le_trans local notation"ظ"=>Rat.cast_zero open ExactRuntime FloatLib.Floats.Formats.BinaryInterchange FloatLib.Floats section open FloatLib.Numerics end @[inline] def HC (A B:UInt64):UInt32:= let x:UInt64:=(A+(0x0FFFFFFF:UInt64))>>>(29:UInt64) let y:UInt64:=(B+(0x0FFFFFFF:UInt64))>>>(29:UInt64) let ex:UInt64:=(x>>>(23:UInt64))&&&(0x7FF:UInt64) if x==y&&ex-(897:UInt64)<(254:UInt64) then (((x>>>(34:UInt64))<<<(31:UInt64)) ||| ((x&&&(0x3FFFFFFFF:UInt64))-((896:UInt64)<<<(23:UInt64)))).toUInt32 else 0xFFFFFFFF @[inline] def HD (s:Float):UInt32:= let a:=s.toBits HC (a+2) (a-2) section open ExactRuntime FloatLib.Floats.Formats.BinaryInterchange FloatLib.Floats open FloatLib.Floats.ExecFloat.Binary noncomputable def R (f:Float):ℝ:=Model.toReal (toModel (ofFloat f)) lemma Ac (x:Float):R x=Model.toReal (Submission.Fe x):=rfl lemma B5 (x y:Float) (c:x.isFinite=true) (d:y.isFinite=true) (e: |R x| + |R y| ≤2^(1000:ℤ)): (x+y).isFinite=true∧R (x+y)=Model.roundAt FloatFormat.binary64 (R x+R y):=by have f:Submission.Fe (x+y)=Model.add (Submission.Fe x) (Submission.Fe y):=toModel_ofFloat_add_of_isFinite x y c d have a:Model.isFinite (Submission.Fe x)=true:=by rw[Submission.Ad,c] have b:Model.isFinite (Submission.Fe y)=true:=by rw[Submission.Ad,d] constructor . rw[<-Submission.Ad,f];exact Model.isFinite_add_of_abs_add_le_posMaxFinite _ _ Submission.Aa a b (e.trans Submission.Af) . rw[Ac,f];exact Model.toReal_add_eq_roundAt_of_abs_add_le_posMaxFinite _ _ Submission.Aa a b (e.trans Submission.Af) open Float.Model.UnpackedFloat in open Float.Model.UnpackedFloat in open Float.Model.UnpackedFloat in open Float.Model.UnpackedFloat in lemma CO (x y:Float) (c:x.isFinite=true) (d:y.isFinite=true) (e: |R x| * |R y| ≤2^(1000:ℤ)): (x*y).isFinite=true∧R (x*y)=Model.roundAt FloatFormat.binary64 (R x*R y):=by have f:Submission.Fe (x*y)=Model.mul (Submission.Fe x) (Submission.Fe y):=Submission.Al x y c d have a:Model.isFinite (Submission.Fe x)=true:=by rw[Submission.Ad,c] have b:Model.isFinite (Submission.Fe y)=true:=by rw[Submission.Ad,d] constructor . rw[<-Submission.Ad,f];exact Model.isFinite_mul_of_abs_mul_le_posMaxFinite _ _ Submission.Aa a b (e.trans Submission.Af) . rw[Ac,f];exact Model.toReal_mul_eq_roundAt_of_abs_mul_le_posMaxFinite _ _ Submission.Aa a b (e.trans Submission.Af) noncomputable def Ff:ℝ:=2^(-1021:ℤ) noncomputable def Fg:ℝ:=2^(300:ℤ) lemma Bf:0(Model.modelSignBit s==decide (256<=i))&&m==2^52&& e==((i%256:ℕ):ℤ)-202&&(i%256 !=0) | .zero _=>i%256==0 | _=>false lemma Bs:∀i,i<512->Fi i=true:=by decide+kernel lemma BS (i:ℕ) (d:i<512): (Submission.FW i).isFinite=true∧R (Submission.FW i)=if i%256=0 then 0 else (if 256<=i then -1 else 1)*2^(((i%256:ℕ):ℤ)-150):=by have a:=Bs i d rw[Submission.A6] have c:(Float.ofBits (Submission.Fh i)).toModel.unpack=Float.Model.UnpackedFloat.unpack Float.Model.Format.binary64 (Submission.Fh i).toBitVec:=Model.unpack_pack_unpack _ _ unfold Fi at a rw[CG,c] change (Float.ofBits (Submission.Fh i)).toModel.unpack.isFinite=true∧_ rw[c] cases b:Float.Model.UnpackedFloat.unpack Float.Model.Format.binary64 (Submission.Fh i).toBitVec with | notANumber=>rw[b] at a;simp at a | infinity s=>rw[b] at a;simp at a | zero s=> rw[b] at a simp only[beq_iff_eq] at a refine ⟨rfl,?_⟩ simp[a] | finite s m e h=> rw[b] at a simp only[Bool.and_eq_true,beq_iff_eq,bne_iff_ne] at a obtain ⟨⟨⟨f,g⟩,j⟩,k⟩:=a refine ⟨rfl,?_⟩ have e:((2^52:ℕ):ℝ)*2^(((i%256:ℕ):ℤ)-202)=2^(((i%256:ℕ):ℤ)-150):=by rw[Nat.cast_pow,Nat.cast_ofNat,<-Э,<-М ב] congr 1 push_cast ring rw[Model.unpackedToReal_finite,Submission.Ae,j,f,g,mul_assoc,e] simp only[decide_eq_true_eq,k,↓reduceIte] noncomputable def Fj (v:ℕ):ℝ:= if v=0 then 0 else ((2^23+v%2^23:ℕ):ℝ)*2^(((v/2^23:ℕ):ℤ)-150) lemma CI (w:UInt32) (e:Submission.FX w=true):Submission.wv w=(if 2^31<=w.toNat then -1 else 1)*Fj (w.toNat%2^31):=by have i:=w.toNat_lt;have f:=Submission.BG w e;have a:=Submission.BD w;have c:(fracOf w).toNat=w.toNat%2^23:=Submission.BB w;have b:expOf w≠255:=by intro h;rw[h] at a;change 255=_ at a;omega have g:Submission.wv w=(decodeD w).toReal:=by unfold Submission.wv ofW;rw[Model.toReal_eq,toDyadic_ofUInt32 w b] rw[g];unfold decodeD Fj;by_cases d:w.toNat%2^31=0 . have e0:expOf w=0:=by apply И.mp;rw[a];show _=0;omega have f0:fracOf w=0:=by apply И.mp;rw[c];show _=0;omega simp only[e0,f0,d,↓reduceIte];simp[FloatLib.Numerics.Dyadic.toReal,FloatLib.Numerics.Dyadic.signedSignificand] . have e0:expOf w≠0:=by intro h;rw[h] at a;change 0=_ at a;omega simp only[e0,d,↓reduceIte];have f1:w.toNat%2^31%2^23=(fracOf w).toNat:=by rw[c];omega have f2:w.toNat%2^31/2^23=(expOf w).toNat:=by rw[a];omega rw[f1,f2];simp only[FloatLib.Numerics.Dyadic.toReal,FloatLib.Numerics.Dyadic.signedSignificand,Submission.BE];simp;split_ifs<;>ring lemma Af (w:UInt32) (j:Submission.FX w=true):(Submission.dv w).isFinite=true∧R (Submission.dv w)=Submission.wv w:=by have r:=w.toNat_lt;have b:=Submission.BG w j;have c:=Submission.BF w;have d:=Ed ((w&&&0x7FFFFF) ||| 0x800000) (by rw[c];omega);have m:(w>>>(23:UInt32)).toUSize.toNat=w.toNat/2^23:=by rw[Х,Submission.BC] have e:=BS (w.toNat/2^23) א;unfold Submission.dv;rw[Submission.A9,m];have f: |R ((w&&&0x7FFFFF) ||| 0x800000).toFloat| ≤2^24:=by rw[d.2,c,Р (П _)];have:2^23+w.toNat%2^23<=2^24:=א;exact_mod_cast this have g: |R (Submission.FW (w.toNat/2^23))| ≤2^106:=by rw[e.2];split_ifs;. simp all_goals simp only[abs_mul,abs_neg,abs_one,one_mul];rw[abs_of_pos (by positivity)];have:(2:ℝ)^(((w.toNat/2^23%256:ℕ):ℤ)-150)<=2^(106:ℤ):=У ב א;simpa using this have n: |R ((w&&&0x7FFFFF) ||| 0x800000).toFloat| * |R (Submission.FW (w.toNat/2^23))| ≤2^(1000:ℤ):=by have h:=Ay;have e1:(2:ℝ)^24<=2^256*2^42:=ב;have e2:(2:ℝ)^106<=2^256*2^42:=ב;exact (г (f.trans (e1.trans h)) (g.trans (e2.trans h)) (Н _) Bf.le).trans D7 obtain ⟨o,p⟩:=CO _ _ d.1 e.1 n;refine ⟨o,?_⟩;rw[p,d.2,e.2,CI w j,c];rcases b with q | ⟨h,s⟩;. have e0:w.toNat/2^23%256=0:=א;rw[q];simp only[e0,↓reduceIte,mul_zero,Model.roundAt_zero];simp[Fj] . have e0:¬w.toNat/2^23%256=0:=א;have e1:w.toNat%2^31/2^23=w.toNat/2^23%256:=א;have e2:w.toNat%2^31%2^23=w.toNat%2^23:=א;have e3:(256<=w.toNat/2^23)↔2^31<=w.toNat:=א;unfold Fj;rw[e1,e2];simp only[e0,e3,show¬w.toNat%2^31=0 by omega,↓reduceIte];have i:-1074<=((w.toNat/2^23%256:ℕ):ℤ)-150:=א;have a:2^23+w.toNat%2^23<2^53:=א;generalize ((w.toNat/2^23%256:ℕ):ℤ)-150=k at i⊢;generalize 2^23+w.toNat%2^23=M at a⊢;by_cases l:2^31<=w.toNat;. have:=Submission.Ax (-(M:ℤ)) k (by simpa using a) i;simp only[l,↓reduceIte];push_cast at this;rw[show (M:ℝ)*(-1*2^k)=-(M:ℝ)*2^k by ring,show -1*((M:ℝ)*2^k)=-(M:ℝ)*2^k by ring];exact this . have:=Submission.Ax (M:ℤ) k (by simpa using a) i;simp only[l,↓reduceIte,one_mul];push_cast at this;exact this lemma Ax:(2:ℝ)^128<=Fg:=by have h:(2:ℝ)^128<=2^256*2^42:=ב;linarith [Ay] lemma E8 (a b:UInt32) (d:Submission.FX a=true) (e:Submission.FX b=true): (Submission.dv a*Submission.dv b).isFinite=true∧ |R (Submission.dv a*Submission.dv b)-Submission.wv a*Submission.wv b| ≤1/2^53*(|Submission.wv a*Submission.wv b| +Ff)∧ |Submission.wv a*Submission.wv b| ≤2^256:=by obtain ⟨fa,ra⟩:=Af a d obtain ⟨fb,rb⟩:=Af b e have la:=Submission.Ba a d have lb:=Submission.Ba b e have c: |Submission.wv a*Submission.wv b| ≤2^256:=by rw[abs_mul] calc |Submission.wv a| * |Submission.wv b| ≤2^128*2^128:=г la lb (Н _) (by positivity) _=2^256:=ב obtain ⟨g,f⟩:=E7 _ _ fa fb (by rw[ra];exact la.trans Ax) (by rw[rb];exact lb.trans Ax) rw[ra,rb] at f exact ⟨g,f,c⟩ end section open ExactRuntime FloatLib.Floats.Formats.BinaryInterchange FloatLib.Floats open FloatLib.Floats.ExecFloat.Binary section open Float.Model Float.Model.UnpackedFloat end lemma CA (f:Float) (s:Bool) (E F:Nat) (a:1<=E) (c:E<2047) (d:F<2^52) (h:f.toBits.toNat=(if s then 2^63 else 0)+E*2^52+F): f.isFinite=true∧R f=(if s then -1 else 1)*((2^52+F:Nat):ℝ)*2^((E:Int)-1075):=by have b:=Submission.B8 f s E F a c d h refine ⟨Submission.B9 f _ b,?_⟩ rw[R,Model.toReal_eq,b] cases s<;>simp[FloatLib.Numerics.Dyadic.toReal,FloatLib.Numerics.Dyadic.signedSignificand] lemma BE (A B:UInt64) (h:HC A B≠0xFFFFFFFF): ∃(S:Bool) (ex fr:Nat),897<=ex∧ex<1151∧fr<2^23∧HC A B=UInt32.ofNat ((if S then 2^31 else 0)+(ex-896)*2^23+fr)∧Submission.Fo A.toNat S ex fr∧Submission.Fo B.toNat S ex fr:=by unfold HC at h⊢ dsimp only at h⊢ have b:=Submission.CC A have c:=Submission.CC B generalize (A+(0x0FFFFFFF:UInt64))>>>(29:UInt64)=x at h b⊢ generalize (B+(0x0FFFFFFF:UInt64))>>>(29:UInt64)=y at h c⊢ have d:=Submission.CD x generalize (x>>>(23:UInt64))&&&(0x7FF:UInt64)=ex at h d⊢ split at h . rename_i i;have j:=i;obtain ⟨a,i⟩:=т.mp i;have a:x=y:=by simpa using a obtain ⟨e,f⟩:=Submission.CE ex (by simpa using i);rw[d] at e f;subst a;have k:=A.toNat_lt;have l:=B.toNat_lt;have g:x.toNat<2^35:=א;simp only[j,ite_true];exact ⟨_,_,_,e,f,by omega,Submission.CF x g e f,Submission.CB A.toNat x.toNat k b e f,Submission.CB B.toNat x.toNat l c e f⟩ . exact absurd rfl h set_option maxRecDepth 8192 in end section open ExactRuntime FloatLib.Floats.Formats.BinaryInterchange FloatLib.Floats open FloatLib.Floats.ExecFloat.Binary end section open ExactRuntime FloatLib.Floats.Formats.BinaryInterchange FloatLib.Floats open FloatLib.Floats.ExecFloat.Binary end section open ExactRuntime FloatLib.Floats.Formats.BinaryInterchange FloatLib.Floats open FloatLib.Floats.ExecFloat.Binary open Float.Model Float.Model.UnpackedFloat end section open ExactRuntime FloatLib.Floats.Formats.BinaryInterchange FloatLib.Floats open FloatLib.Floats.ExecFloat.Binary open Float.Model Float.Model.UnpackedFloat end section open ExactRuntime FloatLib.Floats.Formats.BinaryInterchange FloatLib.Floats open FloatLib.Floats.ExecFloat.Binary lemma E9 (A P Q T g:Nat) (a:g=0∨g=2^63) (b:A<2^64) (e1:(A+2)%2^64=g+P) (e2:(2^64-2+A)%2^64=g+Q) (t1:2^61<=T) (t2:T<2^63-2^60) (l1:Tsimp) s.toBits.toNat_lt e1 e2 א א l1 u1 l2 u2 exact ⟨S,ex,fr,Q+2,d,e,f,g,a,b,c⟩ lemma Cf (v W z u:ℝ) (c:0linarith [b.1,b.2] set_option maxRecDepth 8192 in lemma Dm (ex fr E F:Nat) (y:897<=ex) (z:ex<1151) (o:fr<2^23) (p:F<2^52) (m:(ex*2^23+fr)*2^29+2(2^53+fr*2^30-2^29)*2^((ex:Int)-1076)(2^53+fr*2^30-2^29)*2^((ex:Int)-1076)cases S<;> simp only[Bool.false_eq_true,ite_false,ite_true,Int.ofNat_eq_natCast,Int.cast_neg,Int.cast_natCast] at b . exact ⟨by linarith only [b],rfl⟩ . exfalso;linarith only [c,e,g,b] . exfalso;linarith only [c,e,g,b] . exact ⟨by linarith only [b],rfl⟩ obtain ⟨a,rfl⟩:=a have s:m≠0:=by rintro rfl simp at a linarith only [c,e,a] have f:=Submission.B4 neg m q (2^23+fr) ((ex:Int)-1046) s א א א א (by rw[a,k];push_cast;linarith only [i]) (by intro n have h:fr≠0:=by intro w;exact n א have:=j h rw[a,k];push_cast;linarith only [this]) (by intro _ rw[a,k];linarith only [c]) have e1:((ex:Int)-1046+150).toNat=ex-896:=א have e2:(2^23+fr)%2^23=fr:=א rw[f,e1,e2] lemma Az (s:Float) (d:FloatLib.Numerics.Dyadic) (e: |R s-(d.toRat:ℝ)| ≤1/2^53*(|(d.toRat:ℝ)| +Ff)) (h:HD s≠0xFFFFFFFF):HD s=toWord (Model.roundDyadic Fmt d):=by obtain ⟨S,ex,fr,M,j,k,l,m,n,q,r⟩:=EE s h;have f:M=(M/2^52)*2^52+M%2^52:=א;have g:M%2^52<2^52:=Ы _ ב;generalize M/2^52=E at f;generalize M%2^52=F at f g;subst f;obtain ⟨-,o⟩:=CA s S E F א א g (by rw[n,д]);rw[o] at e obtain ⟨W,i,p⟩:∃W:ℝ,(d.toRat:ℝ)=(if S then -W else W)∧ |((2^52+F:Nat):ℝ)*2^((E:Int)-1075)-W| ≤1/2^53*(|W| +Ff):=by cases S . simp only[Bool.false_eq_true,ite_false,one_mul] at e⊢;exact ⟨_,rfl,e⟩ . simp only[ite_true] at e⊢;refine ⟨-(d.toRat:ℝ),by simp,?_⟩;rw[abs_neg,show ((2^52+F:Nat):ℝ)*2^((E:Int)-1075) - -(d.toRat:ℝ)=-(-1*((2^52+F:Nat):ℝ)*2^((E:Int)-1075)-(d.toRat:ℝ)) by ring,abs_neg];exact e obtain ⟨a,b,c⟩:=Dm ex fr E F j k l g א א W p;rw[m];exact (Cc d S ex fr j k l W i a b c).symm lemma CV (w:UInt32) (e:Submission.FX w=true): ∃(m k:ℤ),Submission.wv w=(m:ℝ)*2^k∧m.natAbs<2^25∧-160<=k:=by have f:=w.toNat_lt;rw[CI w e];unfold Fj;by_cases c:w.toNat%2^31=0;. exact ⟨0,0,by rw[if_pos c];simp,by norm_num,by norm_num⟩ . simp only[c,ite_false];have a:-160<=(((w.toNat%2^31/2^23:ℕ):ℤ)-150):=א;have b:2^23+w.toNat%2^31%2^23<2^25:=א;generalize ((w.toNat%2^31/2^23:ℕ):ℤ)-150=k at a⊢;generalize 2^23+w.toNat%2^31%2^23=M at b⊢;by_cases d:2^31<=w.toNat;. exact ⟨-(M:ℤ),k,by rw[if_pos d];push_cast;ring,by simpa using b,a⟩ . exact ⟨(M:ℤ),k,by rw[if_neg d];push_cast;ring,by simpa using b,a⟩ lemma Dh (a b:UInt32) (c:Submission.FX a=true) (d:Submission.FX b=true):(Submission.dv a*Submission.dv b).isFinite=true∧R (Submission.dv a*Submission.dv b)=Submission.wv a*Submission.wv b:=by obtain ⟨fa,ra⟩:=Af a c;obtain ⟨fb,rb⟩:=Af b d;have la:=(Submission.Ba a c).trans Ax;have lb:=(Submission.Ba b d).trans Ax obtain ⟨f,g⟩:=CO _ _ fa fb (by rw[ra,rb] exact (г la lb (Н _) Bf.le).trans D7) refine ⟨f,?_⟩;obtain ⟨m,k,e1,h,j⟩:=CV a c;obtain ⟨n,l,e2,i,o⟩:=CV b d;have e:Submission.wv a*Submission.wv b=((m*n:ℤ):ℝ)*2^(k+l):=by rw[e1,e2,М Т];push_cast;ring rw[g,ra,rb,e];refine Submission.Ax _ _ ?_ א;rw[Int.natAbs_mul];have:=Nat.mul_lt_mul'' h i;omega lemma FA (x y z:UInt32) (b:Submission.FX x=true) (c:Submission.FX y=true) (e:Submission.FX z=true) (d:FloatLib.Numerics.Dyadic) (g:(d.toRat:ℝ)=Submission.wv x*Submission.wv y+Submission.wv z): |R (Submission.dv x*Submission.dv y+Submission.dv z)-(d.toRat:ℝ)| ≤1/2^53*(|(d.toRat:ℝ)| +Ff):=by obtain ⟨f1,r1⟩:=Dh x y b c obtain ⟨-,-,l⟩:=E8 x y b c obtain ⟨f2,r2⟩:=Af z e have a:(2:ℝ)^256<=Fg:=by have:(2:ℝ)^256<=2^256*2^42:=ב linarith [Ay] obtain ⟨-,f⟩:=BI _ _ f1 f2 (by rw[r1];exact l.trans a) (by rw[r2];exact (Submission.Ba z e).trans Ax) rw[r1,r2] at f rw[g] exact f end section open ExactRuntime FloatLib.Floats.Formats.BinaryInterchange FloatLib.Floats open FloatLib.Floats.ExecFloat.Binary @[inline] def HE (relu g:Bool) (sw tw:UInt32) (y z:Float) (w:UInt32):UInt32:= if g&&Submission.FX w then let r:=HD (Submission.dv w*y+z) if r==0xFFFFFFFF then Submission.Gr relu w sw tw else Submission.Gd relu r else Submission.Gr relu w sw tw @[specialize] def HF (f:UInt32->UInt32) (e i:USize) (x:Array UInt32):Array UInt32:= if h:iUInt32) (e i:USize) (x:Array UInt32) (he:e.toNat<=x.size):Array UInt32:= if h:iUInt32) (e:USize): ∀d (i:USize) (x:Array UInt32) (b:e.toNat<=x.size) (a:x.sizeHG f e i x b=HF f e i x:=by intro d;induction d with | zero=> intro i x b a g have h:¬i intro i x b a g have h:iUInt32) (e i:USize) (x:Array UInt32):Array UInt32:= if he:e.toNat<=x.size∧x.sizeUInt32) (e i:USize) (x:Array UInt32): HH f e i x=HF f e i x:=by unfold HH split ·rename_i b by_cases a:iSubmission.Gr true v sw tw) ((ch+1)*hw).toUSize (ch*hw).toUSize x HI c hw s t (ch+1) x else x termination_by c-ch def HJ (c hw:Nat) (s t:Array UInt32) (ch:Nat) (x:Array UInt32):Array UInt32:= if chSubmission.Gr false v sw tw) ((ch+1)*hw).toUSize (ch*hw).toUSize x HJ c hw s t (ch+1) x else x termination_by c-ch def HK (relu:Bool) (c hw:Nat) (s t:Array UInt32) (ch:Nat) (x:Array UInt32):Array UInt32:= if relu then HI c hw s t ch x else HJ c hw s t ch x def HL (relu:Bool) (c hw:Nat) (s t:Array UInt32) (ch:Nat) (x:Array UInt32):Array UInt32:= if chSubmission.Gr relu v sw tw):=by funext v simp only[HE,Bool.false_and,Bool.false_eq_true,ite_false] lemma FE (c b:Nat) (s t:Array UInt32):∀d ch x,c-ch=d→ HI c b s t ch x=HL true c b s t ch x:=by intro d;induction d using Nat.strong_induction_on with | h d ih=> intro ch x f by_cases a:ch simp only[e,Bool.false_eq_true,ite_false,ite_true,FD] all_goals exact ih (c-(ch+1)) (by omega) (ch+1) _ rfl ·rw[HI,HL,if_neg a,if_neg a] lemma FF (c b:Nat) (s t:Array UInt32):∀d ch x,c-ch=d→ HJ c b s t ch x=HL false c b s t ch x:=by intro d;induction d using Nat.strong_induction_on with | h d ih=> intro ch x f by_cases a:ch simp only[e,Bool.false_eq_true,ite_false,ite_true,FD] all_goals exact ih (c-(ch+1)) (by omega) (ch+1) _ rfl ·rw[HJ,HL,if_neg a,if_neg a] lemma FG (relu:Bool) (c a:Nat) (s t:Array UInt32) (ch:Nat) (x:Array UInt32): HK relu c a s t ch x=HL relu c a s t ch x:=by cases relu ·simp only[HK,Bool.false_eq_true,ite_false] exact FF c a s t (c-ch) ch x rfl ·simp only[HK,ite_true] exact FE c a s t (c-ch) ch x rfl def HM (relu:Bool) (c hw:Nat) (x s t:Array UInt32):Array UInt32:= if x.size=c*hw∧x.size<2^32 then HK relu c hw s t 0 x else scaleShiftSpec relu c hw x s t section open ExactRuntime FloatLib.Floats.Formats.BinaryInterchange FloatLib.Floats open FloatLib.Floats.ExecFloat.Binary open Float.Model Float.Model.UnpackedFloat end lemma C1 (relu:Bool) (s:Float) (h:HD s≠0xFFFFFFFF):Submission.Gd relu (HD s)=act relu (HD s):=by apply Submission.D5;obtain ⟨S,ex,fr,e,f,g,c,-,-⟩:=BE _ _ h;have a:HD s=_:=c;intro d;have b:(expOf (HD s)).toNat=255:=by rw[d];rfl rw[Submission.BD,a,ш] at b;split at b<;>omega lemma Db (relu g:Bool) (sw tw w:UInt32) (j:g=true->Submission.FX sw=true∧Submission.FX tw=true):HE relu g sw tw (Submission.dv sw) (Submission.dv tw) w=Submission.Gc relu w sw tw:=by unfold HE;simp only [Submission.D3];split . rename_i k;obtain ⟨l,d⟩:=т.mp k;obtain ⟨e,f⟩:=j l;split;. rfl . rename_i m;have a:HD (Submission.dv w*Submission.dv sw+Submission.dv tw)≠0xFFFFFFFF:=λh=>m (beq_iff_eq.mpr h);have i:=Submission.CK _ d;have b:=Submission.CK _ e;have c:=Submission.CK _ f;rw[C1 _ _ a,Az _ (Submission.Gq w sw tw) (FA w sw tw d e f _ (Submission.D4 _ _ _ i b c)) a,Submission.Gc,Submission.D2 _ _ _ i b c] . rfl lemma FH (relu:Bool) (c e:Nat) (s t:Array UInt32) (d:Nat): ∀(ch:Nat) (x:Array UInt32),ch+d=c->x.size=c*e->x.size<2^32→ (HL relu c e s t ch x).size=x.size∧∀q,q intro ch x i _ _ rw[HL,if_neg א] refine ⟨rfl,λq f=>?_⟩ rw[if_neg (by rw[(א:ch=c)];omega)] | succ d ih=> intro ch x i j k rw[HL,if_pos א] dsimp only rw[FC] have o:(ch+1)*e<=c*e:=З _ א have p:(ch+1)*e=ch*e+e:=ذ _ _ have e1:((ch+1)*e).toUSize.toNat=(ch+1)*e:=Submission.CU _ א have e0:(ch*e).toUSize.toNat=ch*e:=Submission.CU _ א obtain ⟨g,l⟩:=Submission.Dy (λ_=>HE relu (Submission.FX s[ch]! &&Submission.FX t[ch]!) s[ch]! t[ch]! (Submission.dv s[ch]!) (Submission.dv t[ch]!)) (L:=HF _ ((ch+1)*e).toUSize) (λ_ _=>by rw[HF];rfl) e (ch*e).toUSize x א א k obtain ⟨m,n⟩:=ih (ch+1) _ א (g.trans j) א refine ⟨m.trans g,λq f=>?_⟩ rw[n q f,l,e0,e1,Db _ _ _ _ _ (λh=>т.mp h)] by_cases a:(ch+1)*e<=q . rw[if_pos a,if_neg א,if_pos א] . rw[if_neg a];by_cases b:ch*e<=q;. rw[if_pos ⟨b,by omega⟩,if_pos b,Nat.div_eq_of_lt_le b א] . rw[if_neg א,if_neg b] lemma DG:HM=scaleShiftSpec:=by funext relu c d x s t;unfold HM;simp only [FG];split . rename_i h;obtain ⟨a,g⟩:=h;obtain ⟨e,j⟩:=FH relu c d s t c 0 x א a g;apply ъ;. simp[scaleShiftSpec,e,a] . intro i f k;have b:i