/* Ċ Ġ* ĠCopyright Ġ( c ) Ġ 1 9 9 9 , Ġ 2 0 2 0 , ĠOracle Ġand / or Ġits Ġaffiliates . ĠAll Ġrights Ġreserved . Ċ Ġ* ĠDO ĠNOT ĠALTER ĠOR ĠREMOVE ĠCOPYRIGHT ĠNOT ICES ĠOR ĠTHIS ĠFILE ĠHEADER . Ċ Ġ* Ċ Ġ* ĠThis Ġcode Ġis Ġfree Ġsoftware ; Ġyou Ġcan Ġredistribute Ġit Ġand / or Ġmodify Ġit Ċ Ġ* Ġunder Ġthe Ġterms Ġof Ġthe ĠGNU ĠGeneral ĠPublic ĠLicense Ġversion Ġ 2 Ġonly , Ġas Ċ Ġ* Ġpublished Ġby Ġthe ĠFree ĠSoftware ĠFoundation . Ġ ĠOracle Ġdesign ates Ġthis Ċ Ġ* Ġparticular Ġfile Ġas Ġsubject Ġto Ġthe Ġ" Classpath " Ġexception Ġas Ġprovided Ċ Ġ* Ġby ĠOracle Ġin Ġthe ĠLICENSE Ġfile Ġthat Ġaccomp an ied Ġthis Ġcode . Ċ Ġ* Ċ Ġ* ĠThis Ġcode Ġis Ġdistributed Ġin Ġthe Ġhope Ġthat Ġit Ġwill Ġbe Ġuseful , Ġbut ĠWITHOUT Ċ Ġ* ĠANY ĠWARRANTY ; Ġwithout Ġeven Ġthe Ġimplied Ġwarranty Ġof ĠMERCHANTABILITY Ġor Ċ Ġ* ĠFITNESS ĠFOR ĠA ĠPARTICULAR ĠPURPOSE . Ġ ĠSee Ġthe ĠGNU ĠGeneral ĠPublic ĠLicense Ċ Ġ* Ġversion Ġ 2 Ġfor Ġmore Ġdetails Ġ( a Ġcopy Ġis Ġincluded Ġin Ġthe ĠLICENSE Ġfile Ġthat Ċ Ġ* Ġaccomp an ied Ġthis Ġcode ). Ċ Ġ* Ċ Ġ* ĠYou Ġshould Ġhave Ġreceived Ġa Ġcopy Ġof Ġthe ĠGNU ĠGeneral ĠPublic ĠLicense Ġversion Ċ Ġ* Ġ 2 Ġalong Ġwith Ġthis Ġwork ; Ġif Ġnot , Ġwrite Ġto Ġthe ĠFree ĠSoftware ĠFoundation , Ċ Ġ* ĠInc ., Ġ 5 1 ĠFranklin ĠSt , ĠFifth ĠFloor , ĠBoston , ĠMA Ġ 0 2 1 1 0 - 1 3 0 1 ĠUSA . Ċ Ġ* Ċ Ġ* ĠPlease Ġcontact ĠOracle , Ġ 5 0 0 ĠOracle ĠPark way , ĠRed wood ĠSh ores , ĠCA Ġ 9 4 0 6 5 ĠUSA Ċ Ġ* Ġor Ġvisit Ġwww . oracle . com Ġif Ġyou Ġneed Ġadditional Ġinformation Ġor Ġhave Ġany Ċ Ġ* Ġquestions . Ċ Ġ*/ Ċ package Ġcom . github . alex andre lo mb ard . common sk t . math Ċ Ċ import Ġcom . github . alex andre lo mb ard . common sk t . assert Ċ import Ġkotlin . math .* Ċ Ċ /** Ċ Ġ* ĠA Ġclass Ġused Ġto Ġrepresent Ġmultip rec ision Ġintegers Ġthat Ġmakes Ġefficient Ċ Ġ* Ġuse Ġof Ġallocated Ġspace Ġby Ġallowing Ġa Ġnumber Ġto Ġocc upy Ġonly Ġpart Ġof Ċ Ġ* Ġan Ġarray Ġso Ġthat Ġthe Ġarrays Ġdo Ġnot Ġhave Ġto Ġbe Ġre allocated Ġas Ġoften . Ċ Ġ* ĠWhen Ġperforming Ġan Ġoperation Ġwith Ġmany Ġiterations Ġthe Ġarray Ġused Ġto Ċ Ġ* Ġhold Ġa Ġnumber Ġis Ġonly Ġre allocated Ġwhen Ġnecessary Ġand Ġdoes Ġnot Ġhave Ġto Ċ Ġ* Ġbe Ġthe Ġsame Ġsize Ġas Ġthe Ġnumber Ġit Ġrepresents . ĠA Ġmutable Ġnumber Ġallows Ċ Ġ* Ġcalculations Ġto Ġoccur Ġon Ġthe Ġsame Ġnumber Ġwithout Ġhaving Ġto Ġcreate Ċ Ġ* Ġa Ġnew Ġnumber Ġfor Ġevery Ġstep Ġof Ġthe Ġcalculation Ġas Ġoccurs Ġwith Ċ Ġ* ĠBig Inte gers . Ċ Ġ* Ċ Ġ* Ġ@ see ĠBigInteger Ċ Ġ* Ċ Ġ* Ġ@ author Ġ ĠMichael ĠMc C los key Ċ Ġ* Ġ@ author Ġ ĠTim oth y ĠBu kt u Ċ Ġ* Ġ@ since ĠĠĠ 1 . 3 Ċ Ġ*/ Ċ @ Suppress (" NAME _ SH ADO WING ", Ġ" unused ") Ċ internal Ġopen Ġclass ĠMutable BigInteger Ġ{ ĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠHold s Ġthe Ġmagnitude Ġof Ġthis ĠMutable BigInteger Ġin Ġbig Ġendian Ġorder . ĊĠĠĠĠ Ġ* ĠThe Ġmagnitude Ġmay Ġstart Ġat Ġan Ġoffset Ġinto Ġthe Ġvalue Ġarray , Ġand Ġit Ġmay ĊĠĠĠĠ Ġ* Ġend Ġbefore Ġthe Ġlength Ġof Ġthe Ġvalue Ġarray . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġvar Ġvalue : ĠInt Array ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠThe Ġnumber Ġof Ġints Ġof Ġthe Ġvalue Ġarray Ġthat Ġare Ġcurrently Ġused ĊĠĠĠĠ Ġ* Ġto Ġhold Ġthe Ġmagnitude Ġof Ġthis ĠMutable BigInteger . ĠThe Ġmagnitude Ġstarts ĊĠĠĠĠ Ġ* Ġat Ġan Ġoffset Ġand Ġoffset Ġ+ Ġint Len Ġmay Ġbe Ġless Ġthan Ġvalue . length . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġvar Ġint Len : ĠInt ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠThe Ġoffset Ġinto Ġthe Ġvalue Ġarray Ġwhere Ġthe Ġmagnitude Ġof Ġthis ĊĠĠĠĠ Ġ* ĠMutable BigInteger Ġbegins . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġvar Ġoffset Ġ= Ġ 0 ĊĠĠĠ Ġ// ĠConstructors ĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠThe Ġdefault Ġconstructor . ĠAn Ġempty ĠMutable BigInteger Ġis Ġcreated Ġwith ĊĠĠĠĠ Ġ* Ġa Ġone Ġword Ġcapacity . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġconstructor () Ġ{ ĊĠĠĠĠĠĠĠ Ġvalue Ġ= ĠInt Array ( 1 ) ĊĠĠĠĠĠĠĠ Ġint Len Ġ= Ġ 0 ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠConstruct Ġa Ġnew ĠMutable BigInteger Ġwith Ġa Ġmagnitude Ġspecified Ġby ĊĠĠĠĠ Ġ* Ġthe Ġint Ġval . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġconstructor (` val `: ĠInt ) Ġ{ ĊĠĠĠĠĠĠĠ Ġvalue Ġ= ĠInt Array ( 1 ) ĊĠĠĠĠĠĠĠ Ġint Len Ġ= Ġ 1 ĊĠĠĠĠĠĠĠ Ġvalue [ 0 ] Ġ= Ġ` val ` ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠConstruct Ġa Ġnew ĠMutable BigInteger Ġwith Ġthe Ġspecified Ġvalue Ġarray ĊĠĠĠĠ Ġ* Ġup Ġto Ġthe Ġlength Ġof Ġthe Ġarray Ġsupplied . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġconstructor (` val `: ĠInt Array ) Ġ{ ĊĠĠĠĠĠĠĠ Ġvalue Ġ= Ġ` val ` ĊĠĠĠĠĠĠĠ Ġint Len Ġ= Ġ` val `. size ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠConstruct Ġa Ġnew ĠMutable BigInteger Ġwith Ġa Ġmagnitude Ġequal Ġto Ġthe ĊĠĠĠĠ Ġ* Ġspecified ĠBigInteger . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġconstructor ( b : ĠBigInteger ) Ġ{ ĊĠĠĠĠĠĠĠ Ġint Len Ġ= Ġb . mag . size ĊĠĠĠĠĠĠĠ Ġvalue Ġ= Ġb . mag . copyOf ( int Len ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠConstruct Ġa Ġnew ĠMutable BigInteger Ġwith Ġa Ġmagnitude Ġequal Ġto Ġthe ĊĠĠĠĠ Ġ* Ġspecified ĠMutable BigInteger . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġconstructor (` val `: ĠMutable BigInteger ) Ġ{ ĊĠĠĠĠĠĠĠ Ġint Len Ġ= Ġ` val `. int Len ĊĠĠĠĠĠĠĠ Ġvalue Ġ= Ġ` val `. value . copyOf Range (` val `. offset , Ġ` val `. offset Ġ+ Ġint Len ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠMakes Ġthis Ġnumber Ġan Ġ` n `- int Ġnumber Ġall Ġof Ġwhose Ġbits Ġare Ġones . ĊĠĠĠĠ Ġ* ĠUsed Ġby ĠB urn ikel - Z ie g ler Ġdivision . ĊĠĠĠĠ Ġ* Ġ@ param Ġn Ġnumber Ġof Ġints Ġin Ġthe Ġ` value ` Ġarray ĊĠĠĠĠ Ġ* Ġ@ return Ġa Ġnumber Ġequal Ġto Ġ` (( 1 <<( 3 2 * n ))) - 1 ` ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġprivate Ġfun Ġones ( n : ĠInt ) Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( n Ġ> Ġvalue . size ) Ġvalue Ġ= ĠInt Array ( n ) Ġ{ Ġ- 1 Ġ} ĊĠĠĠĠĠĠĠ Ġoffset Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġint Len Ġ= Ġn ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠInternal Ġhelper Ġmethod Ġto Ġreturn Ġthe Ġmagnitude Ġarray . ĠThe Ġcaller Ġis Ġnot ĊĠĠĠĠ Ġ* Ġsupposed Ġto Ġmodify Ġthe Ġreturned Ġarray . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġprivate Ġval Ġmagnitude Array : ĠInt Array ĊĠĠĠĠĠĠĠ Ġget () Ġ= Ġif Ġ( offset Ġ> Ġ 0 Ġ|| Ġvalue . size Ġ!= Ġint Len ) Ġvalue . copyOf Range ( ĊĠĠĠĠĠĠĠĠĠĠĠ Ġoffset , ĊĠĠĠĠĠĠĠĠĠĠĠ Ġoffset Ġ+ Ġint Len ĊĠĠĠĠĠĠĠ Ġ) Ġelse Ġvalue ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠConvert Ġthis ĠMutable BigInteger Ġto Ġa Ġlong Ġvalue . ĠThe Ġcaller Ġhas Ġto Ġmake ĊĠĠĠĠ Ġ* Ġsure Ġthis ĠMutable BigInteger Ġcan Ġbe Ġfit Ġinto Ġlong . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġprivate Ġfun Ġto Long (): ĠLong Ġ{ ĊĠĠĠĠĠĠĠ Ġassert ( int Len Ġ<= Ġ 2 ) Ġ{ Ġ" this ĠMutable BigInteger Ġexceeds Ġthe Ġrange Ġof Ġlong " Ġ} ĊĠĠĠĠĠĠĠ Ġif Ġ( int Len Ġ== Ġ 0 ) Ġreturn Ġ 0 ĊĠĠĠĠĠĠĠ Ġval Ġd Ġ= Ġ( value [ offset ]. to Long () Ġand ĠBigInteger . LONG _ MASK ) ĊĠĠĠĠĠĠĠ Ġreturn Ġif Ġ( int Len Ġ== Ġ 2 ) Ġd Ġshl Ġ 3 2 Ġor Ġ( value [ offset Ġ+ Ġ 1 ]. to Long () Ġand ĠBigInteger . LONG _ MASK ) Ġelse Ġd ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠConvert Ġthis ĠMutable BigInteger Ġto Ġa ĠBigInteger Ġobject . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġto BigInteger ( sign : ĠInt ): ĠBigInteger Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġif Ġ( int Len Ġ== Ġ 0 Ġ|| Ġsign Ġ== Ġ 0 ) ĠBigInteger . ZERO Ġelse ĠBigInteger ( magnitude Array , Ġsign ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠConverts Ġthis Ġnumber Ġto Ġa Ġnon negative Ġ` BigInteger `. ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġto BigInteger (): ĠBigInteger Ġ{ ĊĠĠĠĠĠĠĠ Ġnormalize () ĊĠĠĠĠĠĠĠ Ġreturn Ġto BigInteger ( if Ġ( is Zero ) Ġ 0 Ġelse Ġ 1 ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠConvert Ġthis ĠMutable BigInteger Ġto ĠBigDecimal Ġobject Ġwith Ġthe Ġspecified Ġsign ĊĠĠĠĠ Ġ* Ġand Ġscale . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġto BigDecimal ( sign : ĠInt , Ġscale : ĠInt ): ĠBigDecimal Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( int Len Ġ== Ġ 0 Ġ|| Ġsign Ġ== Ġ 0 ) Ġreturn ĠBigDecimal . zero ValueOf ( scale ) ĊĠĠĠĠĠĠĠ Ġval Ġmag Ġ= Ġmagnitude Array ĊĠĠĠĠĠĠĠ Ġval Ġlen Ġ= Ġmag . size ĊĠĠĠĠĠĠĠ Ġval Ġd Ġ= Ġmag [ 0 ] ĊĠĠĠĠĠĠĠ Ġ// ĠIf Ġthis ĠMutable BigInteger Ġcan 't Ġbe Ġfit Ġinto Ġlong , Ġwe Ġneed Ġto ĊĠĠĠĠĠĠĠ Ġ// Ġmake Ġa ĠBigInteger Ġobject Ġfor Ġthe Ġresult ant ĠBigDecimal Ġobject . ĊĠĠĠĠĠĠĠ Ġif Ġ( len Ġ> Ġ 2 Ġ|| Ġd Ġ< Ġ 0 Ġ&& Ġlen Ġ== Ġ 2 ) Ġreturn ĠBigDecimal ( ĊĠĠĠĠĠĠĠĠĠĠĠ ĠBigInteger ( mag , Ġsign ), ĊĠĠĠĠĠĠĠĠĠĠĠ ĠBigDecimal . IN FL ATED , ĊĠĠĠĠĠĠĠĠĠĠĠ Ġscale , ĊĠĠĠĠĠĠĠĠĠĠĠĠ 0 ĊĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠ Ġval Ġv Ġ= ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ( if Ġ( len Ġ== Ġ 2 ) Ġmag [ 1 ]. to Long () Ġand ĠBigInteger . LONG _ MASK Ġor Ġ( d . to Long () Ġand ĠBigInteger . LONG _ MASK ) Ġshl Ġ 3 2 Ġelse Ġd . to Long () Ġand ĠBigInteger . LONG _ MASK ). to Long () ĊĠĠĠĠĠĠĠ Ġreturn ĠBigDecimal . valueOf ( if Ġ( sign Ġ== Ġ- 1 ) Ġ- v Ġelse Ġv , Ġscale ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠThis Ġis Ġfor Ġinternal Ġuse Ġin Ġconverting Ġfrom Ġa ĠMutable BigInteger ĊĠĠĠĠ Ġ* Ġobject Ġinto Ġa Ġlong Ġvalue Ġgiven Ġa Ġspecified Ġsign . ĊĠĠĠĠ Ġ* Ġreturns ĠIN FL ATED Ġif Ġvalue Ġis Ġnot Ġfit Ġinto Ġlong ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġto Compact Value ( sign : ĠInt ): ĠLong Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( int Len Ġ== Ġ 0 Ġ|| Ġsign Ġ== Ġ 0 ) Ġreturn Ġ 0 L ĊĠĠĠĠĠĠĠ Ġval Ġmag Ġ= Ġmagnitude Array ĊĠĠĠĠĠĠĠ Ġval Ġlen Ġ= Ġmag . size ĊĠĠĠĠĠĠĠ Ġval Ġd Ġ= Ġmag [ 0 ] ĊĠĠĠĠĠĠĠ Ġ// ĠIf Ġthis ĠMutable BigInteger Ġcan Ġnot Ġbe Ġfit ted Ġinto Ġlong , Ġwe Ġneed Ġto ĊĠĠĠĠĠĠĠ Ġ// Ġmake Ġa ĠBigInteger Ġobject Ġfor Ġthe Ġresult ant ĠBigDecimal Ġobject . ĊĠĠĠĠĠĠĠ Ġif Ġ( len Ġ> Ġ 2 Ġ|| Ġd Ġ< Ġ 0 Ġ&& Ġlen Ġ== Ġ 2 ) Ġreturn ĠBigDecimal . IN FL ATED ĊĠĠĠĠĠĠĠ Ġval Ġv Ġ= ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ( if Ġ( len Ġ== Ġ 2 ) Ġmag [ 1 ]. to Long () Ġand ĠBigInteger . LONG _ MASK Ġor Ġ( d . to Long () Ġand ĠBigInteger . LONG _ MASK ) Ġshl Ġ 3 2 Ġelse Ġd . to Long () Ġand ĠBigInteger . LONG _ MASK ). to Long () ĊĠĠĠĠĠĠĠ Ġreturn Ġif Ġ( sign Ġ== Ġ- 1 ) Ġ- v Ġelse Ġv ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠClear Ġout Ġa ĠMutable BigInteger Ġfor Ġreuse . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġclear () Ġ{ ĊĠĠĠĠĠĠĠ Ġint Len Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġoffset Ġ= Ġint Len ĊĠĠĠĠĠĠĠ Ġvar Ġindex Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġval Ġn Ġ= Ġvalue . size ĊĠĠĠĠĠĠĠ Ġwhile Ġ( index Ġ< Ġn ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvalue [ index ] Ġ= Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġindex ++ ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠSet Ġa ĠMutable BigInteger Ġto Ġzero , Ġremoving Ġits Ġoffset . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġreset () Ġ{ ĊĠĠĠĠĠĠĠ Ġint Len Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġoffset Ġ= Ġint Len ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠCompare Ġthe Ġmagnitude Ġof Ġtwo ĠMutable Big Inte gers . ĠReturns Ġ- 1 , Ġ 0 Ġor Ġ 1 ĊĠĠĠĠ Ġ* Ġas Ġthis ĠMutable BigInteger Ġis Ġnumeric ally Ġless Ġthan , Ġequal Ġto , Ġor ĊĠĠĠĠ Ġ* Ġgreater Ġthan Ġ` b `. ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġcompare ( b : ĠMutable BigInteger ?): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġb len Ġ= Ġb !!. int Len ĊĠĠĠĠĠĠĠ Ġif Ġ( int Len Ġ< Ġb len ) Ġreturn Ġ- 1 ĊĠĠĠĠĠĠĠ Ġif Ġ( int Len Ġ> Ġb len ) Ġreturn Ġ 1 ĊĊĠĠĠĠĠĠĠ Ġ// ĠAdd ĠInteger . MIN _ VALUE Ġto Ġmake Ġthe Ġcomparison Ġact Ġas Ġunsigned Ġinteger ĊĠĠĠĠĠĠĠ Ġ// Ġcomparison . ĊĠĠĠĠĠĠĠ Ġval Ġb val Ġ= Ġb . value ĊĠĠĠĠĠĠĠ Ġvar Ġi Ġ= Ġoffset ĊĠĠĠĠĠĠĠ Ġvar Ġj Ġ= Ġb . offset ĊĠĠĠĠĠĠĠ Ġwhile Ġ( i Ġ< Ġint Len Ġ+ Ġoffset ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġb 1 Ġ= Ġvalue [ i ] Ġ+ Ġ- 0 x 8 0 0 0 0 0 0 0 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġb 2 Ġ= Ġb val [ j ] Ġ+ Ġ- 0 x 8 0 0 0 0 0 0 0 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( b 1 Ġ< Ġb 2 ) Ġreturn Ġ- 1 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( b 1 Ġ> Ġb 2 ) Ġreturn Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġi ++ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġj ++ ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġ 0 ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠReturns Ġa Ġvalue Ġequal Ġto Ġwhat Ġ` b . left Shift ( 3 2 * ints ); Ġreturn Ġcompare ( b ); ` ĊĠĠĠĠ Ġ* Ġwould Ġreturn , Ġbut Ġdoesn 't Ġchange Ġthe Ġvalue Ġof Ġ` b `. ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġprivate Ġfun Ġcompare Shift ed ( b : ĠMutable BigInteger , Ġints : ĠInt ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġb len Ġ= Ġb . int Len ĊĠĠĠĠĠĠĠ Ġval Ġal en Ġ= Ġint Len Ġ- Ġints ĊĠĠĠĠĠĠĠ Ġif Ġ( al en Ġ< Ġb len ) Ġreturn Ġ- 1 ĊĠĠĠĠĠĠĠ Ġif Ġ( al en Ġ> Ġb len ) Ġreturn Ġ 1 ĊĊĠĠĠĠĠĠĠ Ġ// ĠAdd ĠInteger . MIN _ VALUE Ġto Ġmake Ġthe Ġcomparison Ġact Ġas Ġunsigned Ġinteger ĊĠĠĠĠĠĠĠ Ġ// Ġcomparison . ĊĠĠĠĠĠĠĠ Ġval Ġb val Ġ= Ġb . value ĊĠĠĠĠĠĠĠ Ġvar Ġi Ġ= Ġoffset ĊĠĠĠĠĠĠĠ Ġvar Ġj Ġ= Ġb . offset ĊĠĠĠĠĠĠĠ Ġwhile Ġ( i Ġ< Ġal en Ġ+ Ġoffset ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġb 1 Ġ= Ġvalue [ i ] Ġ+ Ġ- 0 x 8 0 0 0 0 0 0 0 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġb 2 Ġ= Ġb val [ j ] Ġ+ Ġ- 0 x 8 0 0 0 0 0 0 0 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( b 1 Ġ< Ġb 2 ) Ġreturn Ġ- 1 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( b 1 Ġ> Ġb 2 ) Ġreturn Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġi ++ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġj ++ ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġ 0 ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠCompare Ġthis Ġagainst Ġhalf Ġof Ġa ĠMutable BigInteger Ġobject Ġ( Needed Ġfor ĊĠĠĠĠ Ġ* Ġremainder Ġtests ). ĊĠĠĠĠ Ġ* ĠAss umes Ġno Ġleading Ġunnecessary Ġzeros , Ġwhich Ġholds Ġfor Ġresults ĊĠĠĠĠ Ġ* Ġfrom Ġdivide (). ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġcompare Half ( b : ĠMutable BigInteger ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġb len Ġ= Ġb . int Len ĊĠĠĠĠĠĠĠ Ġval Ġlen Ġ= Ġint Len ĊĠĠĠĠĠĠĠ Ġif Ġ( len Ġ<= Ġ 0 ) Ġreturn Ġif Ġ( bl en Ġ<= Ġ 0 ) Ġ 0 Ġelse Ġ- 1 ĊĠĠĠĠĠĠĠ Ġif Ġ( len Ġ> Ġb len ) Ġreturn Ġ 1 ĊĠĠĠĠĠĠĠ Ġif Ġ( len Ġ< Ġb len Ġ- Ġ 1 ) Ġreturn Ġ- 1 ĊĠĠĠĠĠĠĠ Ġval Ġb val Ġ= Ġb . value ĊĠĠĠĠĠĠĠ Ġvar Ġb start Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġvar Ġcarry Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġ// ĠOnly Ġ 2 Ġcases Ġleft : len Ġ== Ġb len Ġor Ġlen Ġ== Ġb len Ġ- Ġ 1 ĊĠĠĠĠĠĠĠ Ġif Ġ( len Ġ!= Ġb len ) Ġ{ Ġ// Ġlen Ġ== Ġb len Ġ- Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġcarry Ġ= Ġif Ġ( b val [ b start ] Ġ== Ġ 1 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ++ b start ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ- 0 x 8 0 0 0 0 0 0 0 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġreturn Ġ- 1 ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ// Ġcompare Ġvalues Ġwith Ġright - shift ed Ġvalues Ġof Ġb , ĊĠĠĠĠĠĠĠ Ġ// Ġcarry ing Ġshifted - out Ġbits Ġacross Ġwords ĊĠĠĠĠĠĠĠ Ġval Ġ` val ` Ġ= Ġvalue ĊĠĠĠĠĠĠĠ Ġvar Ġi Ġ= Ġoffset ĊĠĠĠĠĠĠĠ Ġvar Ġj Ġ= Ġb start ĊĠĠĠĠĠĠĠ Ġwhile Ġ( i Ġ< Ġlen Ġ+ Ġoffset ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġbv Ġ= Ġb val [ j ++] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġhb Ġ= Ġ(( bv Ġ ush r Ġ 1 ) Ġ+ Ġcarry . to Long () Ġand ĠBigInteger . LONG _ MASK ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġv Ġ= Ġ(` val ` [ i ++ ]. to Long () Ġand ĠBigInteger . LONG _ MASK ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( v Ġ!= Ġhb ) Ġreturn Ġif Ġ( v Ġ< Ġhb ) Ġ- 1 Ġelse Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġcarry Ġ= Ġbv Ġand Ġ 1 Ġshl Ġ 3 1 Ġ// Ġc array Ġwill Ġbe Ġeither Ġ 0 x 8 0 0 0 0 0 0 0 Ġor Ġ 0 ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġif Ġ( carry Ġ== Ġ 0 ) Ġ 0 Ġelse Ġ- 1 ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠReturn Ġthe Ġindex Ġof Ġthe Ġlowest Ġset Ġbit Ġin Ġthis ĠMutable BigInteger . ĠIf Ġthe ĊĠĠĠĠ Ġ* Ġmagnitude Ġof Ġthis ĠMutable BigInteger Ġis Ġzero , Ġ- 1 Ġis Ġreturned . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġ@ Experimental Std lib Api ĊĠĠĠ Ġprivate Ġval Ġlowest Set Bit : ĠInt ĊĠĠĠĠĠĠĠ Ġget () Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( int Len Ġ== Ġ 0 ) Ġreturn Ġ- 1 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġj : ĠInt ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġb : ĠInt ĊĠĠĠĠĠĠĠĠĠĠĠ Ġj Ġ= Ġint Len Ġ- Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ( j Ġ> Ġ 0 Ġ&& Ġvalue [ j Ġ+ Ġoffset ] Ġ== Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġj -- ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġb Ġ= Ġvalue [ j Ġ+ Ġoffset ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġif Ġ( b Ġ== Ġ 0 ) Ġ- 1 Ġelse Ġ( int Len Ġ- Ġ 1 Ġ- Ġj Ġshl Ġ 5 ) Ġ+ Ġb . count Trailing Zero Bits () ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠReturn Ġthe Ġint Ġin Ġuse Ġin Ġthis ĠMutable BigInteger Ġat Ġthe Ġspecified ĊĠĠĠĠ Ġ* Ġindex . ĠThis Ġmethod Ġis Ġnot Ġused Ġbecause Ġit Ġis Ġnot Ġin lined Ġon Ġall ĊĠĠĠĠ Ġ* Ġplatforms . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġprivate Ġfun Ġget Int ( index : ĠInt ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġvalue [ offset Ġ+ Ġindex ] ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠReturn Ġa Ġlong Ġwhich Ġis Ġequal Ġto Ġthe Ġunsigned Ġvalue Ġof Ġthe Ġint Ġin ĊĠĠĠĠ Ġ* Ġuse Ġin Ġthis ĠMutable BigInteger Ġat Ġthe Ġspecified Ġindex . ĠThis Ġmethod Ġis ĊĠĠĠĠ Ġ* Ġnot Ġused Ġbecause Ġit Ġis Ġnot Ġin lined Ġon Ġall Ġplatforms . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġprivate Ġfun Ġget Long ( index : ĠInt ): ĠLong Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġ( value [ offset Ġ+ Ġindex ]. to Long () Ġand ĠBigInteger . LONG _ MASK ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠEnsure Ġthat Ġthe ĠMutable BigInteger Ġis Ġin Ġnormal Ġform , Ġspecifically ĊĠĠĠĠ Ġ* Ġmaking Ġsure Ġthat Ġthere Ġare Ġno Ġleading Ġzeros , Ġand Ġthat Ġif Ġthe ĊĠĠĠĠ Ġ* Ġmagnitude Ġis Ġzero , Ġthen Ġint Len Ġis Ġzero . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġnormalize () Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( int Len Ġ== Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġoffset Ġ= Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġvar Ġindex Ġ= Ġoffset ĊĠĠĠĠĠĠĠ Ġif Ġ( value [ index ] Ġ!= Ġ 0 ) Ġreturn ĊĠĠĠĠĠĠĠ Ġval Ġindex Bound Ġ= Ġindex Ġ+ Ġint Len ĊĠĠĠĠĠĠĠ Ġdo Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġindex ++ ĊĠĠĠĠĠĠĠ Ġ} Ġwhile Ġ( index Ġ< Ġindex Bound Ġ&& Ġvalue [ index ] Ġ== Ġ 0 ) ĊĠĠĠĠĠĠĠ Ġval Ġnum Z eros Ġ= Ġindex Ġ- Ġoffset ĊĠĠĠĠĠĠĠ Ġint Len Ġ-= Ġnum Z eros ĊĠĠĠĠĠĠĠ Ġoffset Ġ= Ġif Ġ( int Len Ġ== Ġ 0 ) Ġ 0 Ġelse Ġoffset Ġ+ Ġnum Z eros ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠIf Ġthis ĠMutable BigInteger Ġcannot Ġhold Ġlen Ġwords , Ġincrease Ġthe Ġsize ĊĠĠĠĠ Ġ* Ġof Ġthe Ġvalue Ġarray Ġto Ġlen Ġwords . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġprivate Ġfun Ġensure Capacity ( len : ĠInt ) Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( value . size Ġ< Ġlen ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvalue Ġ= ĠInt Array ( len ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġoffset Ġ= Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġint Len Ġ= Ġlen ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠConvert Ġthis ĠMutable BigInteger Ġinto Ġan Ġint Ġarray Ġwith Ġno Ġleading ĊĠĠĠĠ Ġ* Ġzeros , Ġof Ġa Ġlength Ġthat Ġis Ġequal Ġto Ġthis ĠMutable BigInteger 's Ġint Len . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġto IntArray (): ĠInt Array Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġresult Ġ= ĠInt Array ( int Len ) ĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil Ġint Len ) Ġresult [ i ] Ġ= Ġvalue [ offset Ġ+ Ġi ] ĊĠĠĠĠĠĠĠ Ġreturn Ġresult ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠSets Ġthe Ġint Ġat Ġindex + offset Ġin Ġthis ĠMutable BigInteger Ġto Ġval . ĊĠĠĠĠ Ġ* ĠThis Ġdoes Ġnot Ġget Ġin lined Ġon Ġall Ġplatforms Ġso Ġit Ġis Ġnot Ġused ĊĠĠĠĠ Ġ* Ġas Ġoften Ġas Ġoriginally Ġintended . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġset Int ( index : ĠInt , Ġ` val `: ĠInt ) Ġ{ ĊĠĠĠĠĠĠĠ Ġvalue [ offset Ġ+ Ġindex ] Ġ= Ġ` val ` ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠSets Ġthis ĠMutable BigInteger 's Ġvalue Ġarray Ġto Ġthe Ġspecified Ġarray . ĊĠĠĠĠ Ġ* ĠThe Ġint Len Ġis Ġset Ġto Ġthe Ġspecified Ġlength . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun ĠsetValue (` val `: ĠInt Array , Ġlength : ĠInt ) Ġ{ ĊĠĠĠĠĠĠĠ Ġvalue Ġ= Ġ` val ` ĊĠĠĠĠĠĠĠ Ġint Len Ġ= Ġlength ĊĠĠĠĠĠĠĠ Ġoffset Ġ= Ġ 0 ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠSets Ġthis ĠMutable BigInteger 's Ġvalue Ġarray Ġto Ġa Ġcopy Ġof Ġthe Ġspecified ĊĠĠĠĠ Ġ* Ġarray . ĠThe Ġint Len Ġis Ġset Ġto Ġthe Ġlength Ġof Ġthe Ġnew Ġarray . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġcopy Value ( src : ĠMutable BigInteger ) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġlen Ġ= Ġsrc . int Len ĊĠĠĠĠĠĠĠ Ġif Ġ( value . size Ġ< Ġlen ) Ġvalue Ġ= ĠInt Array ( len ) ĊĠĠĠĠĠĠĠ Ġsrc . value . copy Into ( value , Ġ 0 , Ġsrc . offset , Ġsrc . offset Ġ+ Ġlen ) ĊĠĠĠĠĠĠĠ Ġint Len Ġ= Ġlen ĊĠĠĠĠĠĠĠ Ġoffset Ġ= Ġ 0 ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠSets Ġthis ĠMutable BigInteger 's Ġvalue Ġarray Ġto Ġa Ġcopy Ġof Ġthe Ġspecified ĊĠĠĠĠ Ġ* Ġarray . ĠThe Ġint Len Ġis Ġset Ġto Ġthe Ġlength Ġof Ġthe Ġspecified Ġarray . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġcopy Value (` val `: ĠInt Array ) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġlen Ġ= Ġ` val `. size ĊĠĠĠĠĠĠĠ Ġif Ġ( value . size Ġ< Ġlen ) Ġvalue Ġ= ĠInt Array ( len ) ĊĠĠĠĠĠĠĠ Ġ` val `. copy Into ( value , Ġ 0 , Ġ 0 , Ġlen ) ĊĠĠĠĠĠĠĠ Ġint Len Ġ= Ġlen ĊĠĠĠĠĠĠĠ Ġoffset Ġ= Ġ 0 ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠReturns Ġtrue Ġiff Ġthis ĠMutable BigInteger Ġhas Ġa Ġvalue Ġof Ġone . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġval Ġis One : ĠBoolean ĊĠĠĠĠĠĠĠ Ġget () Ġ= Ġint Len Ġ== Ġ 1 Ġ&& Ġvalue [ offset ] Ġ== Ġ 1 ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠReturns Ġtrue Ġiff Ġthis ĠMutable BigInteger Ġhas Ġa Ġvalue Ġof Ġzero . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġval Ġis Zero : ĠBoolean ĊĠĠĠĠĠĠĠ Ġget () Ġ= Ġint Len Ġ== Ġ 0 ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠReturns Ġtrue Ġiff Ġthis ĠMutable BigInteger Ġis Ġeven . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġval Ġis Even : ĠBoolean ĊĠĠĠĠĠĠĠ Ġget () Ġ= Ġint Len Ġ== Ġ 0 Ġ|| Ġvalue [ offset Ġ+ Ġint Len Ġ- Ġ 1 ] Ġand Ġ 1 Ġ== Ġ 0 ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠReturns Ġtrue Ġiff Ġthis ĠMutable BigInteger Ġis Ġodd . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġval Ġis Odd : ĠBoolean ĊĠĠĠĠĠĠĠ Ġget () Ġ= Ġif Ġ( is Zero ) Ġfalse Ġelse Ġvalue [ offset Ġ+ Ġint Len Ġ- Ġ 1 ] Ġand Ġ 1 Ġ== Ġ 1 ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠReturns Ġtrue Ġiff Ġthis ĠMutable BigInteger Ġis Ġin Ġnormal Ġform . ĠA ĊĠĠĠĠ Ġ* ĠMutable BigInteger Ġis Ġin Ġnormal Ġform Ġif Ġit Ġhas Ġno Ġleading Ġzeros ĊĠĠĠĠ Ġ* Ġafter Ġthe Ġoffset , Ġand Ġint Len Ġ+ Ġoffset Ġ<= Ġvalue . length . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġval Ġis Normal : ĠBoolean ĊĠĠĠĠĠĠĠ Ġget () Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( int Len Ġ+ Ġoffset Ġ> Ġvalue . size ) Ġreturn Ġfalse ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġif Ġ( int Len Ġ== Ġ 0 ) Ġtrue Ġelse Ġvalue [ offset ] Ġ!= Ġ 0 ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠReturns Ġa ĠString Ġrepresentation Ġof Ġthis ĠMutable BigInteger Ġin Ġradix Ġ 1 0 . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġ@ Experimental Std lib Api ĊĠĠĠ Ġoverride Ġfun ĠtoString (): ĠString Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġb : ĠBigInteger Ġ= Ġto BigInteger ( 1 ) ĊĠĠĠĠĠĠĠ Ġreturn Ġb . toString () ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠLike Ġ[. right Shift ] Ġbut Ġ` n ` Ġcan Ġbe Ġgreater Ġthan Ġthe Ġlength Ġof Ġthe Ġnumber . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġ@ Experimental Std lib Api ĊĠĠĠ Ġfun Ġsafe Right Shift ( n : ĠInt ) Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( n Ġ/ Ġ 3 2 Ġ>= Ġint Len ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreset () ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġright Shift ( n ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠRight Ġshift Ġthis ĠMutable BigInteger Ġn Ġbits . ĠThe ĠMutable BigInteger Ġis Ġleft ĊĠĠĠĠ Ġ* Ġin Ġnormal Ġform . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġ@ Experimental Std lib Api ĊĠĠĠ Ġfun Ġright Shift ( n : ĠInt ) Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( int Len Ġ== Ġ 0 ) Ġreturn ĊĠĠĠĠĠĠĠ Ġval Ġn Ints Ġ= Ġn Ġ ush r Ġ 5 ĊĠĠĠĠĠĠĠ Ġval Ġn Bits Ġ= Ġn Ġand Ġ 0 x 1 F ĊĠĠĠĠĠĠĠ Ġint Len Ġ-= Ġn Ints ĊĠĠĠĠĠĠĠ Ġif Ġ( n Bits Ġ== Ġ 0 ) Ġreturn ĊĠĠĠĠĠĠĠ Ġval Ġbits In High Word : ĠInt Ġ= ĠBigInteger . bit Length For Int ( value [ offset ]) ĊĠĠĠĠĠĠĠ Ġif Ġ( n Bits Ġ>= Ġbits In High Word ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġprimitive Left Shift ( 3 2 Ġ- Ġn Bits ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġint Len -- ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġprimitive Right Shift ( n Bits ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠLike Ġ[. left Shift ] Ġbut Ġ` n ` Ġcan Ġbe Ġzero . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġ@ Experimental Std lib Api ĊĠĠĠ Ġfun Ġsafe Left Shift ( n : ĠInt ) Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( n Ġ> Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġleft Shift ( n ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠLeft Ġshift Ġthis ĠMutable BigInteger Ġn Ġbits . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġ@ Experimental Std lib Api ĊĠĠĠ Ġfun Ġleft Shift ( n : ĠInt ) Ġ{ ĊĠĠĠĠĠĠĠ Ġ/* ĊĠĠĠĠĠĠĠĠ Ġ* ĠIf Ġthere Ġis Ġenough Ġstorage Ġspace Ġin Ġthis ĠMutable BigInteger Ġalready ĊĠĠĠĠĠĠĠĠ Ġ* Ġthe Ġavailable Ġspace Ġwill Ġbe Ġused . ĠSpace Ġto Ġthe Ġright Ġof Ġthe Ġused ĊĠĠĠĠĠĠĠĠ Ġ* Ġints Ġin Ġthe Ġvalue Ġarray Ġis Ġfaster Ġto Ġutilize , Ġso Ġthe Ġextra Ġspace ĊĠĠĠĠĠĠĠĠ Ġ* Ġwill Ġbe Ġtaken Ġfrom Ġthe Ġright Ġif Ġpossible . ĊĠĠĠĠĠĠĠĠ Ġ*/ ĊĠĠĠĠĠĠĠ Ġif Ġ( int Len Ġ== Ġ 0 ) Ġreturn ĊĠĠĠĠĠĠĠ Ġval Ġn Ints Ġ= Ġn Ġ ush r Ġ 5 ĊĠĠĠĠĠĠĠ Ġval Ġn Bits Ġ= Ġn Ġand Ġ 0 x 1 F ĊĠĠĠĠĠĠĠ Ġval Ġbits In High Word : ĠInt Ġ= ĠBigInteger . bit Length For Int ( value [ offset ]) ĊĊĠĠĠĠĠĠĠ Ġ// ĠIf Ġshift Ġcan Ġbe Ġdone Ġwithout Ġmoving Ġwords , Ġdo Ġso ĊĠĠĠĠĠĠĠ Ġif Ġ( n Ġ<= Ġ 3 2 Ġ- Ġbits In High Word ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġprimitive Left Shift ( n Bits ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġvar Ġnew Len Ġ= Ġint Len Ġ+ Ġn Ints Ġ+ Ġ 1 ĊĠĠĠĠĠĠĠ Ġif Ġ( n Bits Ġ<= Ġ 3 2 Ġ- Ġbits In High Word ) Ġnew Len -- ĊĠĠĠĠĠĠĠ Ġif Ġ( value . size Ġ< Ġnew Len ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠThe Ġarray Ġmust Ġgrow ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġresult Ġ= ĠInt Array ( new Len ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil Ġint Len ) Ġresult [ i ] Ġ= Ġvalue [ offset Ġ+ Ġi ] ĊĠĠĠĠĠĠĠĠĠĠĠ ĠsetValue ( result , Ġnew Len ) ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġif Ġ( value . size Ġ- Ġoffset Ġ>= Ġnew Len ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠUse Ġspace Ġon Ġright ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil Ġnew Len Ġ- Ġint Len ) Ġvalue [ offset Ġ+ Ġint Len Ġ+ Ġi ] Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠMust Ġuse Ġspace Ġon Ġleft ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil Ġint Len ) Ġvalue [ i ] Ġ= Ġvalue [ offset Ġ+ Ġi ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġint Len Ġuntil Ġnew Len ) Ġvalue [ i ] Ġ= Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġoffset Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġint Len Ġ= Ġnew Len ĊĠĠĠĠĠĠĠ Ġif Ġ( n Bits Ġ== Ġ 0 ) Ġreturn ĊĠĠĠĠĠĠĠ Ġif Ġ( n Bits Ġ<= Ġ 3 2 Ġ- Ġbits In High Word ) Ġprimitive Left Shift ( n Bits ) Ġelse Ġprimitive Right Shift ( 3 2 Ġ- Ġn Bits ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠA Ġprimitive Ġused Ġfor Ġdivision . ĠThis Ġmethod Ġadds Ġin Ġone Ġmultiple Ġof Ġthe ĊĠĠĠĠ Ġ* Ġdivisor Ġa Ġback Ġto Ġthe Ġdiv id end Ġresult Ġat Ġa Ġspecified Ġoffset . ĠIt Ġis Ġused ĊĠĠĠĠ Ġ* Ġwhen Ġq hat Ġwas Ġestimated Ġtoo Ġlarge , Ġand Ġmust Ġbe Ġadjusted . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġprivate Ġfun Ġdiv add ( a : ĠInt Array , Ġresult : ĠInt Array , Ġoffset : ĠInt ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġvar Ġcarry : ĠLong Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġfor Ġ( j Ġin Ġa . indices . reversed ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġsum Ġ= Ġ( a [ j ]. to Long () Ġand ĠBigInteger . LONG _ MASK ) Ġ+ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ( result [ j Ġ+ Ġoffset ]. to Long () Ġand ĠBigInteger . LONG _ MASK ) Ġ+ Ġcarry ĊĠĠĠĠĠĠĠĠĠĠĠ Ġresult [ j Ġ+ Ġoffset ] Ġ= Ġsum . toInt () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġcarry Ġ= Ġsum Ġ ush r Ġ 3 2 ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġcarry . toInt () ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠThis Ġmethod Ġis Ġused Ġfor Ġdivision . ĠIt Ġmultip lies Ġan Ġn Ġword Ġinput Ġa Ġby Ġone ĊĠĠĠĠ Ġ* Ġword Ġinput Ġx , Ġand Ġsubtract s Ġthe Ġn Ġword Ġproduct Ġfrom Ġq . ĠThis Ġis Ġneeded ĊĠĠĠĠ Ġ* Ġwhen Ġsubtract ing Ġq hat * div isor Ġfrom Ġdiv id end . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġprivate Ġfun Ġmul sub ( q : ĠInt Array , Ġa : ĠInt Array , Ġx : ĠInt , Ġlen : ĠInt , Ġoffset : ĠInt ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġvar Ġoffset Ġ= Ġoffset ĊĠĠĠĠĠĠĠ Ġval Ġx Long Ġ= Ġ( x . to Long () Ġand ĠBigInteger . LONG _ MASK ) ĊĠĠĠĠĠĠĠ Ġvar Ġcarry : ĠLong Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġoffset Ġ+= Ġlen ĊĠĠĠĠĠĠĠ Ġfor Ġ( j Ġin Ġlen Ġ- Ġ 1 Ġdown To Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġproduct Ġ= Ġ( a [ j ]. to Long () Ġand ĠBigInteger . LONG _ MASK ) Ġ* Ġx Long Ġ+ Ġcarry ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġdifference Ġ= Ġq [ offset ] Ġ- Ġproduct ĊĠĠĠĠĠĠĠĠĠĠĠ Ġq [ offset -- ] Ġ= Ġdifference . toInt () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġcarry Ġ= Ġ(( product Ġ ush r Ġ 3 2 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ+ Ġif Ġ( difference Ġand ĠBigInteger . LONG _ MASK Ġ> ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ( product . toInt (). inv (). to Long () Ġand ĠBigInteger . LONG _ MASK )) Ġ 1 Ġelse Ġ 0 ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġcarry . toInt () ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠThe Ġmethod Ġis Ġthe Ġsame Ġas Ġmul sun , Ġexcept Ġthe Ġfact Ġthat Ġq Ġarray Ġis Ġnot ĊĠĠĠĠ Ġ* Ġupdated , Ġthe Ġonly Ġresult Ġof Ġthe Ġmethod Ġis Ġborrow Ġflag . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġprivate Ġfun Ġmul sub Borrow ( q : ĠInt Array , Ġa : ĠInt Array , Ġx : ĠInt , Ġlen : ĠInt , Ġoffset : ĠInt ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġvar Ġoffset Ġ= Ġoffset ĊĠĠĠĠĠĠĠ Ġval Ġx Long Ġ= Ġ( x . to Long () Ġand ĠBigInteger . LONG _ MASK ) ĊĠĠĠĠĠĠĠ Ġvar Ġcarry : ĠLong Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġoffset Ġ+= Ġlen ĊĠĠĠĠĠĠĠ Ġfor Ġ( j Ġin Ġlen Ġ- Ġ 1 Ġdown To Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġproduct Ġ= Ġ( a [ j ]. to Long () Ġand ĠBigInteger . LONG _ MASK ) Ġ* Ġx Long Ġ+ Ġcarry ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġdifference Ġ= Ġq [ offset -- ] Ġ- Ġproduct ĊĠĠĠĠĠĠĠĠĠĠĠ Ġcarry Ġ= Ġ(( product Ġ ush r Ġ 3 2 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ+ Ġif Ġ( difference Ġand ĠBigInteger . LONG _ MASK Ġ> ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ( product . toInt (). inv (). to Long () Ġand ĠBigInteger . LONG _ MASK )) Ġ 1 Ġelse Ġ 0 ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġcarry . toInt () ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠRight Ġshift Ġthis ĠMutable BigInteger Ġn Ġbits , Ġwhere Ġn Ġis ĊĠĠĠĠ Ġ* Ġless Ġthan Ġ 3 2 . ĊĠĠĠĠ Ġ* ĠAss umes Ġthat Ġint Len Ġ> Ġ 0 , Ġn Ġ> Ġ 0 Ġfor Ġspeed ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġprivate Ġfun Ġprimitive Right Shift ( n : ĠInt ) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġ` val ` Ġ= Ġvalue ĊĠĠĠĠĠĠĠ Ġval Ġn 2 Ġ= Ġ 3 2 Ġ- Ġn ĊĠĠĠĠĠĠĠ Ġvar Ġi Ġ= Ġoffset Ġ+ Ġint Len Ġ- Ġ 1 ĊĠĠĠĠĠĠĠ Ġvar Ġc Ġ= Ġ` val ` [ i ] ĊĠĠĠĠĠĠĠ Ġwhile Ġ( i Ġ> Ġoffset ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġb Ġ= Ġc ĊĠĠĠĠĠĠĠĠĠĠĠ Ġc Ġ= Ġ` val ` [ i Ġ- Ġ 1 ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ` val ` [ i ] Ġ= Ġc Ġshl Ġn 2 Ġor Ġ( b Ġ ush r Ġn ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġi -- ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ` val ` [ offset ] Ġ= Ġ` val ` [ offset ] Ġ ush r Ġn ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠLeft Ġshift Ġthis ĠMutable BigInteger Ġn Ġbits , Ġwhere Ġn Ġis ĊĠĠĠĠ Ġ* Ġless Ġthan Ġ 3 2 . ĊĠĠĠĠ Ġ* ĠAss umes Ġthat Ġint Len Ġ> Ġ 0 , Ġn Ġ> Ġ 0 Ġfor Ġspeed ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġprivate Ġfun Ġprimitive Left Shift ( n : ĠInt ) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġ` val ` Ġ= Ġvalue ĊĠĠĠĠĠĠĠ Ġval Ġn 2 Ġ= Ġ 3 2 Ġ- Ġn ĊĠĠĠĠĠĠĠ Ġvar Ġi Ġ= Ġoffset ĊĠĠĠĠĠĠĠ Ġvar Ġc Ġ= Ġ` val ` [ i ] ĊĠĠĠĠĠĠĠ Ġval Ġm Ġ= Ġi Ġ+ Ġint Len Ġ- Ġ 1 ĊĠĠĠĠĠĠĠ Ġwhile Ġ( i Ġ< Ġm ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġb Ġ= Ġc ĊĠĠĠĠĠĠĠĠĠĠĠ Ġc Ġ= Ġ` val ` [ i Ġ+ Ġ 1 ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ` val ` [ i ] Ġ= Ġb Ġshl Ġn Ġor Ġ( c Ġ ush r Ġn 2 ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġi ++ ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ` val ` [ offset Ġ+ Ġint Len Ġ- Ġ 1 ] Ġ= Ġ` val ` [ offset Ġ+ Ġint Len Ġ- Ġ 1 ] Ġshl Ġn ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠReturns Ġa Ġ` BigInteger ` Ġequal Ġto Ġthe Ġ` n ` ĊĠĠĠĠ Ġ* Ġlow Ġints Ġof Ġthis Ġnumber . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġprivate Ġfun Ġget Lower ( n : ĠInt ): ĠBigInteger Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġif Ġ( is Zero ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ ĠBigInteger . ZERO ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġif Ġ( int Len Ġ< Ġn ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġto BigInteger ( 1 ) ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġstrip Ġzeros ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġlen Ġ= Ġn ĊĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ( len Ġ> Ġ 0 Ġ&& Ġvalue [ offset Ġ+ Ġint Len Ġ- Ġlen ] Ġ== Ġ 0 ) Ġlen -- ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġsign Ġ= Ġif Ġ( len Ġ> Ġ 0 ) Ġ 1 Ġelse Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠ ĠBigInteger ( value . copyOf Range ( offset Ġ+ Ġint Len Ġ- Ġlen , Ġoffset Ġ+ Ġint Len ), Ġsign ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠDis cards Ġall Ġints Ġwhose Ġindex Ġis Ġgreater Ġthan Ġ` n `. ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġprivate Ġfun Ġkeep Lower ( n : ĠInt ) Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( int Len Ġ>= Ġn ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġoffset Ġ+= Ġint Len Ġ- Ġn ĊĠĠĠĠĠĠĠĠĠĠĠ Ġint Len Ġ= Ġn ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠAdds Ġthe Ġcontents Ġof Ġtwo ĠMutable BigInteger Ġobjects . The Ġresult ĊĠĠĠĠ Ġ* Ġis Ġplaced Ġwithin Ġthis ĠMutable BigInteger . ĊĠĠĠĠ Ġ* ĠThe Ġcontents Ġof Ġthe Ġadd end Ġare Ġnot Ġchanged . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġadd ( add end : ĠMutable BigInteger ?) Ġ{ ĊĠĠĠĠĠĠĠ Ġvar Ġx Ġ= Ġint Len ĊĠĠĠĠĠĠĠ Ġvar Ġy Ġ= Ġadd end !!. int Len ĊĠĠĠĠĠĠĠ Ġvar Ġresult Len Ġ= Ġif Ġ( int Len Ġ> Ġadd end . int Len ) Ġint Len Ġelse Ġadd end . int Len ĊĠĠĠĠĠĠĠ Ġvar Ġresult Ġ= Ġif Ġ( value . size Ġ< Ġresult Len ) ĠInt Array ( result Len ) Ġelse Ġvalue ĊĠĠĠĠĠĠĠ Ġvar Ġr start Ġ= Ġresult . size Ġ- Ġ 1 ĊĠĠĠĠĠĠĠ Ġvar Ġsum : ĠLong ĊĠĠĠĠĠĠĠ Ġvar Ġcarry : ĠLong Ġ= Ġ 0 ĊĊĠĠĠĠĠĠĠ Ġ// ĠAdd Ġcommon Ġparts Ġof Ġboth Ġnumbers ĊĠĠĠĠĠĠĠ Ġwhile Ġ( x Ġ> Ġ 0 Ġ&& Ġy Ġ> Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġx -- ĊĠĠĠĠĠĠĠĠĠĠĠ Ġy -- ĊĠĠĠĠĠĠĠĠĠĠĠ Ġsum Ġ= Ġ( value [ x Ġ+ Ġoffset ]. to Long () Ġand ĠBigInteger . LONG _ MASK ) Ġ+ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ( add end . value [ y Ġ+ Ġadd end . offset ]. to Long () Ġand ĠBigInteger . LONG _ MASK ) Ġ+ Ġcarry ĊĠĠĠĠĠĠĠĠĠĠĠ Ġresult [ r start -- ] Ġ= Ġsum . toInt () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġcarry Ġ= Ġsum Ġ ush r Ġ 3 2 ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġ// ĠAdd Ġremainder Ġof Ġthe Ġlonger Ġnumber ĊĠĠĠĠĠĠĠ Ġwhile Ġ( x Ġ> Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġx -- ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( carry Ġ== Ġ 0 L Ġ&& Ġresult Ġ=== Ġvalue Ġ&& Ġr start Ġ== Ġx Ġ+ Ġoffset ) Ġreturn ĊĠĠĠĠĠĠĠĠĠĠĠ Ġsum Ġ= Ġ( value [ x Ġ+ Ġoffset ]. to Long () Ġand ĠBigInteger . LONG _ MASK ) Ġ+ Ġcarry ĊĠĠĠĠĠĠĠĠĠĠĠ Ġresult [ r start -- ] Ġ= Ġsum . toInt () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġcarry Ġ= Ġsum Ġ ush r Ġ 3 2 ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġwhile Ġ( y Ġ> Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġy -- ĊĠĠĠĠĠĠĠĠĠĠĠ Ġsum Ġ= Ġ( add end . value [ y Ġ+ Ġadd end . offset ]. to Long () Ġand ĠBigInteger . LONG _ MASK ) Ġ+ Ġcarry ĊĠĠĠĠĠĠĠĠĠĠĠ Ġresult [ r start -- ] Ġ= Ġsum . toInt () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġcarry Ġ= Ġsum Ġ ush r Ġ 3 2 ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġif Ġ( carry Ġ> Ġ 0 ) Ġ{ Ġ// ĠResult Ġmust Ġgrow Ġin Ġlength ĊĠĠĠĠĠĠĠĠĠĠĠ Ġresult Len ++ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( result . size Ġ< Ġresult Len ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġtemp Ġ= ĠInt Array ( result Len ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠResult Ġone Ġword Ġlonger Ġfrom Ġcarry - out ; Ġcopy Ġlow - order ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġbits Ġinto Ġnew Ġresult . ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġresult . copy Into ( temp , Ġ 1 , Ġ 0 , Ġresult . size ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġtemp [ 0 ] Ġ= Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġresult Ġ= Ġtemp ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġresult [ r start -- ] Ġ= Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġvalue Ġ= Ġresult ĊĠĠĠĠĠĠĠ Ġint Len Ġ= Ġresult Len ĊĠĠĠĠĠĠĠ Ġoffset Ġ= Ġresult . size Ġ- Ġresult Len ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠAdds Ġthe Ġvalue Ġof Ġ` add end ` Ġshifted Ġ` n ` Ġints Ġto Ġthe Ġleft . ĊĠĠĠĠ Ġ* ĠHas Ġthe Ġsame Ġeffect Ġas Ġ` add end . left Shift ( 3 2 * ints ); Ġadd ( add end ); ` ĊĠĠĠĠ Ġ* Ġbut Ġdoesn 't Ġchange Ġthe Ġvalue Ġof Ġ` add end `. ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġadd Shift ed ( add end : ĠMutable BigInteger , Ġn : ĠInt ) Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( add end . is Zero ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġvar Ġx Ġ= Ġint Len ĊĠĠĠĠĠĠĠ Ġvar Ġy Ġ= Ġadd end . int Len Ġ+ Ġn ĊĠĠĠĠĠĠĠ Ġvar Ġresult Len Ġ= Ġif Ġ( int Len Ġ> Ġy ) Ġint Len Ġelse Ġy ĊĠĠĠĠĠĠĠ Ġvar Ġresult Ġ= Ġif Ġ( value . size Ġ< Ġresult Len ) ĠInt Array ( result Len ) Ġelse Ġvalue ĊĠĠĠĠĠĠĠ Ġvar Ġr start Ġ= Ġresult . size Ġ- Ġ 1 ĊĠĠĠĠĠĠĠ Ġvar Ġsum : ĠLong ĊĠĠĠĠĠĠĠ Ġvar Ġcarry : ĠLong Ġ= Ġ 0 ĊĊĠĠĠĠĠĠĠ Ġ// ĠAdd Ġcommon Ġparts Ġof Ġboth Ġnumbers ĊĠĠĠĠĠĠĠ Ġwhile Ġ( x Ġ> Ġ 0 Ġ&& Ġy Ġ> Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġx -- ĊĠĠĠĠĠĠĠĠĠĠĠ Ġy -- ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġb val Ġ= Ġif Ġ( y Ġ+ Ġadd end . offset Ġ< Ġadd end . value . size ) Ġadd end . value [ y Ġ+ Ġadd end . offset ] Ġelse Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġsum Ġ= Ġ( value [ x Ġ+ Ġoffset ]. to Long () Ġand ĠBigInteger . LONG _ MASK ) Ġ+ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ( b val . to Long () Ġand ĠBigInteger . LONG _ MASK ) Ġ+ Ġcarry ĊĠĠĠĠĠĠĠĠĠĠĠ Ġresult [ r start -- ] Ġ= Ġsum . toInt () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġcarry Ġ= Ġsum Ġ ush r Ġ 3 2 ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġ// ĠAdd Ġremainder Ġof Ġthe Ġlonger Ġnumber ĊĠĠĠĠĠĠĠ Ġwhile Ġ( x Ġ> Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġx -- ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( carry Ġ== Ġ 0 L Ġ&& Ġresult Ġ=== Ġvalue Ġ&& Ġr start Ġ== Ġx Ġ+ Ġoffset ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġsum Ġ= Ġ( value [ x Ġ+ Ġoffset ]. to Long () Ġand ĠBigInteger . LONG _ MASK ) Ġ+ Ġcarry ĊĠĠĠĠĠĠĠĠĠĠĠ Ġresult [ r start -- ] Ġ= Ġsum . toInt () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġcarry Ġ= Ġsum Ġ ush r Ġ 3 2 ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġwhile Ġ( y Ġ> Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġy -- ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġb val Ġ= Ġif Ġ( y Ġ+ Ġadd end . offset Ġ< Ġadd end . value . size ) Ġadd end . value [ y Ġ+ Ġadd end . offset ] Ġelse Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġsum Ġ= Ġ( b val . to Long () Ġand ĠBigInteger . LONG _ MASK ) Ġ+ Ġcarry ĊĠĠĠĠĠĠĠĠĠĠĠ Ġresult [ r start -- ] Ġ= Ġsum . toInt () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġcarry Ġ= Ġsum Ġ ush r Ġ 3 2 ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġif Ġ( carry Ġ> Ġ 0 ) Ġ{ Ġ// ĠResult Ġmust Ġgrow Ġin Ġlength ĊĠĠĠĠĠĠĠĠĠĠĠ Ġresult Len ++ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( result . size Ġ< Ġresult Len ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġtemp Ġ= ĠInt Array ( result Len ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠResult Ġone Ġword Ġlonger Ġfrom Ġcarry - out ; Ġcopy Ġlow - order ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġbits Ġinto Ġnew Ġresult . ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġresult . copy Into ( temp , Ġ 1 , Ġ 0 , Ġresult . size ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġtemp [ 0 ] Ġ= Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġresult Ġ= Ġtemp ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġresult [ r start -- ] Ġ= Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġvalue Ġ= Ġresult ĊĠĠĠĠĠĠĠ Ġint Len Ġ= Ġresult Len ĊĠĠĠĠĠĠĠ Ġoffset Ġ= Ġresult . size Ġ- Ġresult Len ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠLike Ġ[. add Shift ed ] Ġbut Ġ` this . int Len ` Ġmust ĊĠĠĠĠ Ġ* Ġnot Ġbe Ġgreater Ġthan Ġ` n `. ĠIn Ġother Ġwords , Ġconcaten ates Ġ` this ` ĊĠĠĠĠ Ġ* Ġand Ġ` add end `. ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġadd Dis joint ( add end : ĠMutable BigInteger ?, Ġn : ĠInt ) Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( add end !!. is Zero ) Ġreturn ĊĠĠĠĠĠĠĠ Ġval Ġx Ġ= Ġint Len ĊĠĠĠĠĠĠĠ Ġvar Ġy Ġ= Ġadd end . int Len Ġ+ Ġn ĊĠĠĠĠĠĠĠ Ġval Ġresult Len Ġ= Ġif Ġ( int Len Ġ> Ġy ) Ġint Len Ġelse Ġy ĊĠĠĠĠĠĠĠ Ġval Ġresult : ĠInt Array ĊĠĠĠĠĠĠĠ Ġif Ġ( value . size Ġ< Ġresult Len ) Ġresult Ġ= ĠInt Array ( result Len ) Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġresult Ġ= Ġvalue ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvalue . fill ( 0 , Ġoffset Ġ+ Ġint Len , Ġvalue . size ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġvar Ġr start Ġ= Ġresult . size Ġ- Ġ 1 ĊĊĠĠĠĠĠĠĠ Ġ// Ġcopy Ġfrom Ġthis Ġif Ġneeded ĊĠĠĠĠĠĠĠ Ġvalue . copy Into ( result , Ġr start Ġ+ Ġ 1 Ġ- Ġx , Ġoffset , Ġoffset Ġ+ Ġx ) ĊĠĠĠĠĠĠĠ Ġy Ġ-= Ġx ĊĠĠĠĠĠĠĠ Ġr start Ġ-= Ġx ĊĠĠĠĠĠĠĠ Ġval Ġlen : ĠInt Ġ= Ġmin ( y , Ġadd end . value . size Ġ- Ġadd end . offset ) ĊĠĠĠĠĠĠĠ Ġadd end . value . copy Into ( result , Ġr start Ġ+ Ġ 1 Ġ- Ġy , Ġadd end . offset , Ġadd end . offset Ġ+ Ġlen ) ĊĊĠĠĠĠĠĠĠ Ġ// Ġzero Ġthe Ġgap ĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġr start Ġ+ Ġ 1 Ġ- Ġy Ġ+ Ġlen Ġuntil Ġr start Ġ+ Ġ 1 ) Ġresult [ i ] Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġvalue Ġ= Ġresult ĊĠĠĠĠĠĠĠ Ġint Len Ġ= Ġresult Len ĊĠĠĠĠĠĠĠ Ġoffset Ġ= Ġresult . size Ġ- Ġresult Len ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠAdds Ġthe Ġlow Ġ` n ` Ġints Ġof Ġ` add end `. ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġadd Lower ( add end : ĠMutable BigInteger , Ġn : ĠInt ) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġa Ġ= ĠMutable BigInteger ( add end ) ĊĠĠĠĠĠĠĠ Ġif Ġ( a . offset Ġ+ Ġa . int Len Ġ>= Ġn ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġa . offset Ġ= Ġa . offset Ġ+ Ġa . int Len Ġ- Ġn ĊĠĠĠĠĠĠĠĠĠĠĠ Ġa . int Len Ġ= Ġn ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġa . normalize () ĊĠĠĠĠĠĠĠ Ġadd ( a ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠSubtract s Ġthe Ġsmaller Ġof Ġthis Ġand Ġb Ġfrom Ġthe Ġlarger Ġand Ġplaces Ġthe ĊĠĠĠĠ Ġ* Ġresult Ġinto Ġthis ĠMutable BigInteger . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġsubtract ( b : ĠMutable BigInteger ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġvar Ġb Ġ= Ġb ĊĠĠĠĠĠĠĠ Ġvar Ġa : ĠMutable BigInteger Ġ= Ġthis ĊĠĠĠĠĠĠĠ Ġvar Ġresult Ġ= Ġvalue ĊĠĠĠĠĠĠĠ Ġval Ġsign Ġ= Ġa . compare ( b ) ĊĠĠĠĠĠĠĠ Ġif Ġ( sign Ġ== Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreset () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġ 0 ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġif Ġ( sign Ġ< Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġtmp Ġ= Ġa ĊĠĠĠĠĠĠĠĠĠĠĠ Ġa Ġ= Ġb ĊĠĠĠĠĠĠĠĠĠĠĠ Ġb Ġ= Ġtmp ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġval Ġresult Len Ġ= Ġa . int Len ĊĠĠĠĠĠĠĠ Ġif Ġ( result . size Ġ< Ġresult Len ) Ġresult Ġ= ĠInt Array ( result Len ) ĊĠĠĠĠĠĠĠ Ġvar Ġdiff : ĠLong Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġvar Ġx Ġ= Ġa . int Len ĊĠĠĠĠĠĠĠ Ġvar Ġy Ġ= Ġb . int Len ĊĠĠĠĠĠĠĠ Ġvar Ġr start Ġ= Ġresult . size Ġ- Ġ 1 ĊĊĠĠĠĠĠĠĠ Ġ// ĠSubtract Ġcommon Ġparts Ġof Ġboth Ġnumbers ĊĠĠĠĠĠĠĠ Ġwhile Ġ( y Ġ> Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġx -- ĊĠĠĠĠĠĠĠĠĠĠĠ Ġy -- ĊĠĠĠĠĠĠĠĠĠĠĠ Ġdiff Ġ= Ġ(( a . value [ x Ġ+ Ġa . offset ]. to Long () Ġand ĠBigInteger . LONG _ MASK ) Ġ- ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ( b . value [ y Ġ+ Ġb . offset ]. to Long () Ġand ĠBigInteger . LONG _ MASK ) Ġ- Ġ(- ( diff Ġshr Ġ 3 2 )). toInt ()) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġresult [ r start -- ] Ġ= Ġdiff . toInt () ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ// ĠSubtract Ġremainder Ġof Ġlonger Ġnumber ĊĠĠĠĠĠĠĠ Ġwhile Ġ( x Ġ> Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġx -- ĊĠĠĠĠĠĠĠĠĠĠĠ Ġdiff Ġ= Ġ(( a . value [ x Ġ+ Ġa . offset ]. to Long () Ġand ĠBigInteger . LONG _ MASK ) Ġ- Ġ(- ( diff Ġshr Ġ 3 2 )). toInt ()) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġresult [ r start -- ] Ġ= Ġdiff . toInt () ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġvalue Ġ= Ġresult ĊĠĠĠĠĠĠĠ Ġint Len Ġ= Ġresult Len ĊĠĠĠĠĠĠĠ Ġoffset Ġ= Ġvalue . size Ġ- Ġresult Len ĊĠĠĠĠĠĠĠ Ġnormalize () ĊĠĠĠĠĠĠĠ Ġreturn Ġsign ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠSubtract s Ġthe Ġsmaller Ġof Ġa Ġand Ġb Ġfrom Ġthe Ġlarger Ġand Ġplaces Ġthe Ġresult ĊĠĠĠĠ Ġ* Ġinto Ġthe Ġlarger . ĠReturns Ġ 1 Ġif Ġthe Ġanswer Ġis Ġin Ġa , Ġ- 1 Ġif Ġin Ġb , Ġ 0 Ġif Ġno ĊĠĠĠĠ Ġ* Ġoperation Ġwas Ġperformed . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġprivate Ġfun Ġdifference ( b : ĠMutable BigInteger ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġvar Ġb Ġ= Ġb ĊĠĠĠĠĠĠĠ Ġvar Ġa : ĠMutable BigInteger Ġ= Ġthis ĊĠĠĠĠĠĠĠ Ġval Ġsign Ġ= Ġa . compare ( b ) ĊĠĠĠĠĠĠĠ Ġif Ġ( sign Ġ== Ġ 0 ) Ġreturn Ġ 0 ĊĠĠĠĠĠĠĠ Ġif Ġ( sign Ġ< Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġtmp Ġ= Ġa ĊĠĠĠĠĠĠĠĠĠĠĠ Ġa Ġ= Ġb ĊĠĠĠĠĠĠĠĠĠĠĠ Ġb Ġ= Ġtmp ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġvar Ġdiff : ĠLong Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġvar Ġx Ġ= Ġa . int Len ĊĠĠĠĠĠĠĠ Ġvar Ġy Ġ= Ġb . int Len ĊĊĠĠĠĠĠĠĠ Ġ// ĠSubtract Ġcommon Ġparts Ġof Ġboth Ġnumbers ĊĠĠĠĠĠĠĠ Ġwhile Ġ( y Ġ> Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġx -- ĊĠĠĠĠĠĠĠĠĠĠĠ Ġy -- ĊĠĠĠĠĠĠĠĠĠĠĠ Ġdiff Ġ= Ġ(( a . value [ a . offset Ġ+ Ġx ]. to Long () Ġand ĠBigInteger . LONG _ MASK ) Ġ- ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ( b . value [ b . offset Ġ+ Ġy ]. to Long () Ġand ĠBigInteger . LONG _ MASK ) Ġ- Ġ(- ( diff Ġshr Ġ 3 2 )). toInt ()) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġa . value [ a . offset Ġ+ Ġx ] Ġ= Ġdiff . toInt () ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ// ĠSubtract Ġremainder Ġof Ġlonger Ġnumber ĊĠĠĠĠĠĠĠ Ġwhile Ġ( x Ġ> Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġx -- ĊĠĠĠĠĠĠĠĠĠĠĠ Ġdiff Ġ= Ġ(( a . value [ a . offset Ġ+ Ġx ]. to Long () Ġand ĠBigInteger . LONG _ MASK ) Ġ- Ġ(- ( diff Ġshr Ġ 3 2 )). toInt ()) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġa . value [ a . offset Ġ+ Ġx ] Ġ= Ġdiff . toInt () ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġa . normalize () ĊĠĠĠĠĠĠĠ Ġreturn Ġsign ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠMultiply Ġthe Ġcontents Ġof Ġtwo ĠMutable BigInteger Ġobjects . ĠThe Ġresult Ġis ĊĠĠĠĠ Ġ* Ġplaced Ġinto ĠMutable BigInteger Ġz . ĠThe Ġcontents Ġof Ġy Ġare Ġnot Ġchanged . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġmultiply ( y : ĠMutable BigInteger , Ġz : ĠMutable BigInteger ) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġx Len Ġ= Ġint Len ĊĠĠĠĠĠĠĠ Ġval Ġy Len Ġ= Ġy . int Len ĊĠĠĠĠĠĠĠ Ġval Ġnew Len Ġ= Ġx Len Ġ+ Ġy Len ĊĊĠĠĠĠĠĠĠ Ġ// ĠPut Ġz Ġinto Ġan Ġappropriate Ġstate Ġto Ġreceive Ġproduct ĊĠĠĠĠĠĠĠ Ġif Ġ( z . value . size Ġ< Ġnew Len ) Ġz . value Ġ= ĠInt Array ( new Len ) ĊĠĠĠĠĠĠĠ Ġz . offset Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġz . int Len Ġ= Ġnew Len ĊĊĠĠĠĠĠĠĠ Ġ// ĠThe Ġfirst Ġiteration Ġis Ġho isted Ġout Ġof Ġthe Ġloop Ġto Ġavoid Ġextra Ġadd ĊĠĠĠĠĠĠĠ Ġvar Ġcarry : ĠLong Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġvar Ġj Ġ= Ġy Len Ġ- Ġ 1 ĊĠĠĠĠĠĠĠ Ġvar Ġk Ġ= Ġy Len Ġ+ Ġx Len Ġ- Ġ 1 ĊĠĠĠĠĠĠĠ Ġwhile Ġ( j Ġ>= Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġproduct Ġ= Ġ( y . value [ j Ġ+ Ġy . offset ]. to Long () Ġand ĠBigInteger . LONG _ MASK ) Ġ* ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ( value [ x Len Ġ- Ġ 1 Ġ+ Ġoffset ]. to Long () Ġand ĠBigInteger . LONG _ MASK ) Ġ+ Ġcarry ĊĠĠĠĠĠĠĠĠĠĠĠ Ġz . value [ k ] Ġ= Ġproduct . toInt () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġcarry Ġ= Ġproduct Ġ ush r Ġ 3 2 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġj -- ĊĠĠĠĠĠĠĠĠĠĠĠ Ġk -- ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġz . value [ x Len Ġ- Ġ 1 ] Ġ= Ġcarry . toInt () ĊĊĠĠĠĠĠĠĠ Ġ// ĠPerform Ġthe Ġmultiplication Ġword Ġby Ġword ĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġx Len Ġ- Ġ 2 Ġdown To Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġcarry Ġ= Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġj Ġ= Ġy Len Ġ- Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġk Ġ= Ġy Len Ġ+ Ġi ĊĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ( j Ġ>= Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġproduct Ġ= Ġ( y . value [ j Ġ+ Ġy . offset ]. to Long () Ġand ĠBigInteger . LONG _ MASK ) Ġ* ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ( value [ i Ġ+ Ġoffset ]. to Long () Ġand ĠBigInteger . LONG _ MASK ) Ġ+ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ( z . value [ k ]. to Long () Ġand ĠBigInteger . LONG _ MASK ) Ġ+ Ġcarry ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġz . value [ k ] Ġ= Ġproduct . toInt () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcarry Ġ= Ġproduct Ġ ush r Ġ 3 2 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġj -- ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġk -- ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġz . value [ i ] Ġ= Ġcarry . toInt () ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġ// ĠRemove Ġleading Ġzeros Ġfrom Ġproduct ĊĠĠĠĠĠĠĠ Ġz . normalize () ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠMultiply Ġthe Ġcontents Ġof Ġthis ĠMutable BigInteger Ġby Ġthe Ġword Ġy . ĠThe ĊĠĠĠĠ Ġ* Ġresult Ġis Ġplaced Ġinto Ġz . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġfun Ġmul ( y : ĠInt , Ġz : ĠMutable BigInteger ) Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( y Ġ== Ġ 1 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġz . copy Value ( this ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġif Ġ( y Ġ== Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġz . clear () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġ// ĠPerform Ġthe Ġmultiplication Ġword Ġby Ġword ĊĠĠĠĠĠĠĠ Ġval Ġy long Ġ= Ġ( y . to Long () Ġand ĠBigInteger . LONG _ MASK ) ĊĠĠĠĠĠĠĠ Ġval Ġz val Ġ= Ġif Ġ( z . value . size Ġ< Ġint Len Ġ+ Ġ 1 ) ĠInt Array ( int Len Ġ+ Ġ 1 ) Ġelse Ġz . value ĊĠĠĠĠĠĠĠ Ġvar Ġcarry : ĠLong Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġint Len Ġ- Ġ 1 Ġdown To Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġproduct Ġ= Ġy long Ġ* Ġ( value [ i Ġ+ Ġoffset ]. to Long () Ġand ĠBigInteger . LONG _ MASK ) Ġ+ Ġcarry ĊĠĠĠĠĠĠĠĠĠĠĠ Ġz val [ i Ġ+ Ġ 1 ] Ġ= Ġproduct . toInt () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġcarry Ġ= Ġproduct Ġ ush r Ġ 3 2 ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġif Ġ( carry Ġ== Ġ 0 L ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġz . offset Ġ= Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġz . int Len Ġ= Ġint Len ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġz . offset Ġ= Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġz . int Len Ġ= Ġint Len Ġ+ Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġz val [ 0 ] Ġ= Ġcarry . toInt () ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġz . value Ġ= Ġz val ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠThis Ġmethod Ġis Ġused Ġfor Ġdivision Ġof Ġan Ġn Ġword Ġdiv id end Ġby Ġa Ġone Ġword ĊĠĠĠĠ Ġ* Ġdivisor . ĠThe Ġquot ient Ġis Ġplaced Ġinto Ġquot ient . ĠThe Ġone Ġword Ġdivisor Ġis ĊĠĠĠĠ Ġ* Ġspecified Ġby Ġdivisor . ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* Ġ@ return Ġthe Ġremainder Ġof Ġthe Ġdivision Ġis Ġreturned . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġ@ Experimental Std lib Api ĊĠĠĠ Ġfun Ġdivide One Word ( div isor : ĠInt , Ġquot ient : ĠMutable BigInteger ?): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġdivisor Long Ġ= Ġ( div isor . to Long () Ġand ĠBigInteger . LONG _ MASK ) ĊĊĠĠĠĠĠĠĠ Ġ// ĠSpecial Ġcase Ġof Ġone Ġword Ġdiv id end ĊĠĠĠĠĠĠĠ Ġif Ġ( int Len Ġ== Ġ 1 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġdiv id end Value Ġ= Ġ( value [ offset ]. to Long () Ġand ĠBigInteger . LONG _ MASK ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġq Ġ= Ġ( divid end Value Ġ/ Ġdivisor Long ). toInt () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġr Ġ= Ġ( divid end Value Ġ- Ġq Ġ* Ġdivisor Long ). toInt () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġquot ient !!. value [ 0 ] Ġ= Ġq ĊĠĠĠĠĠĠĠĠĠĠĠ Ġquot ient . int Len Ġ= Ġif Ġ( q Ġ== Ġ 0 ) Ġ 0 Ġelse Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġquot ient . offset Ġ= Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġr ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġif Ġ( quot ient !!. value . size Ġ< Ġint Len ) Ġquot ient . value Ġ= ĠInt Array ( int Len ) ĊĠĠĠĠĠĠĠ Ġquot ient . offset Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġquot ient . int Len Ġ= Ġint Len ĊĊĠĠĠĠĠĠĠ Ġ// ĠNormalize Ġthe Ġdivisor ĊĠĠĠĠĠĠĠ Ġval Ġshift : ĠInt Ġ= Ġdivisor . count Leading Zero Bits () ĊĠĠĠĠĠĠĠ Ġvar Ġrem Ġ= Ġvalue [ offset ] ĊĠĠĠĠĠĠĠ Ġvar Ġrem Long Ġ= Ġ( rem . to Long () Ġand ĠBigInteger . LONG _ MASK ) ĊĠĠĠĠĠĠĠ Ġif Ġ( rem Long Ġ< Ġdivisor Long ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġquot ient . value [ 0 ] Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġquot ient . value [ 0 ] Ġ= Ġ( rem Long Ġ/ Ġdivisor Long ). toInt () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġrem Ġ= Ġ( rem Long Ġ- Ġquot ient . value [ 0 ] Ġ* Ġdivisor Long ). toInt () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġrem Long Ġ= Ġ( rem . to Long () Ġand ĠBigInteger . LONG _ MASK ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġvar Ġx len Ġ= Ġint Len ĊĠĠĠĠĠĠĠ Ġwhile Ġ(-- x len Ġ> Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġdiv id end Estimate Ġ= Ġrem Long Ġshl Ġ 3 2 Ġor ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ( value [ offset Ġ+ Ġint Len Ġ- Ġx len ]. to Long () Ġand ĠBigInteger . LONG _ MASK ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġq : ĠInt ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( divid end Estimate Ġ>= Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġq Ġ= Ġ( divid end Estimate Ġ/ Ġdivisor Long ). toInt () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġrem Ġ= Ġ( divid end Estimate Ġ- Ġq Ġ* Ġdivisor Long ). toInt () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġtmp Ġ= Ġdiv Word ( divid end Estimate , Ġdivisor ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġq Ġ= Ġ( tmp Ġand ĠBigInteger . LONG _ MASK ). toInt () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġrem Ġ= Ġ( tmp Ġ ush r Ġ 3 2 ). toInt () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġquot ient . value [ int Len Ġ- Ġx len ] Ġ= Ġq ĊĠĠĠĠĠĠĠĠĠĠĠ Ġrem Long Ġ= Ġ( rem . to Long () Ġand ĠBigInteger . LONG _ MASK ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġquot ient . normalize () ĊĠĠĠĠĠĠĠ Ġ// ĠUn normalize ĊĠĠĠĠĠĠĠ Ġreturn Ġif Ġ( shift Ġ> Ġ 0 ) Ġrem Ġ% Ġdivisor Ġelse Ġrem ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠCalculates Ġthe Ġquot ient Ġof Ġthis Ġdiv Ġb Ġand Ġplaces Ġthe Ġquot ient Ġin Ġthe ĊĠĠĠĠ Ġ* Ġprovided ĠMutable BigInteger Ġobjects Ġand Ġthe Ġremainder Ġobject Ġis Ġreturned . ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġ@ Experimental Std lib Api ĊĠĠĠ Ġfun Ġdivide ( ĊĠĠĠĠĠĠĠ Ġb : ĠMutable BigInteger , ĊĠĠĠĠĠĠĠ Ġquot ient : ĠMutable BigInteger , ĊĠĠĠĠĠĠĠ Ġneed Remain der : ĠBoolean Ġ= Ġtrue ĊĠĠĠ Ġ): ĠMutable BigInteger ? Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġif Ġ( b . int Len Ġ< ĠBigInteger . B URN IK EL _ Z IE GL ER _ THRESHOLD Ġ|| ĊĠĠĠĠĠĠĠĠĠĠĠ Ġint Len Ġ- Ġb . int Len Ġ< ĠBigInteger . B URN IK EL _ Z IE GL ER _ OFFSET ĊĠĠĠĠĠĠĠ Ġ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġdivide Kn uth ( b , Ġquot ient , Ġneed Remain der ) ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġdivide And Remain der Burn ikel Z ie g ler ( b , Ġquot ient ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠCalculates Ġthe Ġquot ient Ġof Ġthis Ġdiv Ġb Ġand Ġplaces Ġthe Ġquot ient Ġin Ġthe ĊĠĠĠĠ Ġ* Ġprovided ĠMutable BigInteger Ġobjects Ġand Ġthe Ġremainder Ġobject Ġis Ġreturned . ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĠUses ĠAlgorithm ĠD Ġin ĠKn uth Ġsection Ġ 4 . 3 . 1 . ĊĠĠĠĠ Ġ* ĠMany Ġoptimizations Ġto Ġthat Ġalgorithm Ġhave Ġbeen Ġadapted Ġfrom Ġthe ĠCol in ĊĠĠĠĠ Ġ* ĠPl umb ĠC Ġlibrary . ĊĠĠĠĠ Ġ* ĠIt Ġspecial Ġcases Ġone Ġword Ġdiv is ors Ġfor Ġspeed . ĠThe Ġcontent Ġof Ġb Ġis Ġnot ĊĠĠĠĠ Ġ* Ġchanged . ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* Ġ@ see Ġ. divide Kn uth ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġ@ Experimental Std lib Api ĊĠĠĠ Ġfun Ġdivide Kn uth ( ĊĠĠĠĠĠĠĠ Ġb : ĠMutable BigInteger , ĊĠĠĠĠĠĠĠ Ġquot ient : ĠMutable BigInteger , ĊĠĠĠĠĠĠĠ Ġneed Remain der : ĠBoolean Ġ= Ġtrue ĊĠĠĠ Ġ): ĠMutable BigInteger ? Ġ{ ĊĠĠĠĠĠĠĠ Ġvar Ġb Ġ= Ġb ĊĠĠĠĠĠĠĠ Ġif Ġ( b . int Len Ġ== Ġ 0 ) Ġthrow ĠArithmetic Exception (" BigInteger Ġdivide Ġby Ġzero ") ĊĊĠĠĠĠĠĠĠ Ġ// ĠDiv id end Ġis Ġzero ĊĠĠĠĠĠĠĠ Ġif Ġ( int Len Ġ== Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġquot ient . offset Ġ= Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġquot ient . int Len Ġ= Ġquot ient . offset ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġif Ġ( need Remain der ) ĠMutable BigInteger () Ġelse Ġnull ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġval Ġcmp Ġ= Ġcompare ( b ) ĊĠĠĠĠĠĠĠ Ġ// ĠDiv id end Ġless Ġthan Ġdivisor ĊĠĠĠĠĠĠĠ Ġif Ġ( cmp Ġ< Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġquot ient . offset Ġ= Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġquot ient . int Len Ġ= Ġquot ient . offset ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġif Ġ( need Remain der ) ĠMutable BigInteger ( this ) Ġelse Ġnull ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ// ĠDiv id end Ġequal Ġto Ġdivisor ĊĠĠĠĠĠĠĠ Ġif Ġ( cmp Ġ== Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġquot ient . int Len Ġ= Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġquot ient . value [ 0 ] Ġ= Ġquot ient . int Len ĊĠĠĠĠĠĠĠĠĠĠĠ Ġquot ient . offset Ġ= Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġif Ġ( need Remain der ) ĠMutable BigInteger () Ġelse Ġnull ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġquot ient . clear () ĊĠĠĠĠĠĠĠ Ġ// ĠSpecial Ġcase Ġone Ġword Ġdivisor ĊĠĠĠĠĠĠĠ Ġif Ġ( b . int Len Ġ== Ġ 1 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġr Ġ= Ġdivide One Word ( b . value [ b . offset ], Ġquot ient ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġif Ġ( need Remain der ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( r Ġ== Ġ 0 ) ĠMutable BigInteger () Ġelse ĠMutable BigInteger ( r ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnull ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġ// ĠCancel Ġcommon Ġpowers Ġof Ġtwo Ġif Ġwe 're Ġabove Ġthe ĠK N UTH _ PO W 2 _* Ġthresholds ĊĠĠĠĠĠĠĠ Ġif Ġ( int Len Ġ>= ĠK N UTH _ PO W 2 _ THRESH _ LEN ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġtrailing Zero Bits : ĠInt Ġ= Ġmin ( lowest Set Bit , Ġb . lowest Set Bit ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( trailing Zero Bits Ġ>= ĠK N UTH _ PO W 2 _ THRESH _ Z ER OS Ġ* Ġ 3 2 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġa Ġ= ĠMutable BigInteger ( this ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġb Ġ= ĠMutable BigInteger ( b ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġa . right Shift ( trailing Zero Bits ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġb . right Shift ( trailing Zero Bits ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġr : ĠMutable BigInteger ? Ġ= Ġa . divide Kn uth ( b , Ġquot ient ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġr !!. left Shift ( trailing Zero Bits ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġr ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġdivide Magnitude ( b , Ġquot ient , Ġneed Remain der ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠComputes Ġ` this / b ` Ġand Ġ` this % b ` Ġusing Ġthe ĊĠĠĠĠ Ġ* Ġ[ ĠB urn ikel - Z ie g ler Ġalgorithm ]( http :// cr . yp . to / bib / 1 9 9 8 / burn ikel . ps ). ĊĠĠĠĠ Ġ* ĠThis Ġmethod Ġimplements Ġalgorithm Ġ 3 Ġfrom Ġpg . Ġ 9 Ġof Ġthe ĠB urn ikel - Z ie g ler Ġpaper . ĊĠĠĠĠ Ġ* ĠThe Ġparameter Ġbeta Ġwas Ġchosen Ġto Ġb Ġ 2 < sup > 3 2 </ sup > Ġso Ġalmost Ġall Ġsh ifts Ġare ĊĠĠĠĠ Ġ* Ġmultip les Ġof Ġ 3 2 Ġbits .< br ></ br > ĊĠĠĠĠ Ġ* Ġ` this ` Ġand Ġ` b ` Ġmust Ġbe Ġnon negative . ĊĠĠĠĠ Ġ* Ġ@ param Ġb Ġthe Ġdivisor ĊĠĠĠĠ Ġ* Ġ@ param Ġquot ient Ġoutput Ġparameter Ġfor Ġ` this / b ` ĊĠĠĠĠ Ġ* Ġ@ return Ġthe Ġremainder ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġ@ Experimental Std lib Api ĊĠĠĠ Ġfun Ġdivide And Remain der Burn ikel Z ie g ler ( ĊĠĠĠĠĠĠĠ Ġb : ĠMutable BigInteger , ĊĠĠĠĠĠĠĠ Ġquot ient : ĠMutable BigInteger ĊĠĠĠ Ġ): ĠMutable BigInteger Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġr Ġ= Ġint Len ĊĠĠĠĠĠĠĠ Ġval Ġs Ġ= Ġb . int Len ĊĊĠĠĠĠĠĠĠ Ġ// ĠClear Ġthe Ġquot ient ĊĠĠĠĠĠĠĠ Ġquot ient . int Len Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġquot ient . offset Ġ= Ġquot ient . int Len ĊĠĠĠĠĠĠĠ Ġreturn Ġif Ġ( r Ġ< Ġs ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġthis ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠUn like ĠKn uth Ġdivision , Ġwe Ġdon 't Ġcheck Ġfor Ġcommon Ġpowers Ġof Ġtwo Ġhere Ġbecause ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠB Z Ġalready Ġruns Ġfaster Ġif Ġboth Ġnumbers Ġcontain Ġpowers Ġof Ġtwo Ġand Ġcancell ing Ġthem Ġhas Ġno ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġadditional Ġbenefit . ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġstep Ġ 1 : Ġlet Ġm Ġ= Ġmin { 2 ^ k Ġ| Ġ( 2 ^ k )* B URN IK EL _ Z IE GL ER _ THRESHOLD Ġ> Ġs } ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġm Ġ= ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ 1 Ġshl Ġ 3 2 Ġ- Ġ( s Ġ/ ĠBigInteger . B URN IK EL _ Z IE GL ER _ THRESHOLD ). count Leading Zero Bits () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġj Ġ= Ġ( s Ġ+ Ġm Ġ- Ġ 1 ) Ġ/ Ġm Ġ// Ġstep Ġ 2 a : Ġj Ġ= Ġceil ( s / m ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġn Ġ= Ġj Ġ* Ġm Ġ// Ġstep Ġ 2 b : Ġblock Ġlength Ġin Ġ 3 2 - bit Ġunits ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġn 3 2 Ġ= Ġ 3 2 L Ġ* Ġn Ġ// Ġblock Ġlength Ġin Ġbits ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġsigma Ġ= ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġmax ( 0 , Ġn 3 2 Ġ- Ġb . bit Length ()). toInt () Ġ// Ġstep Ġ 3 : Ġsigma Ġ= Ġmax { T Ġ| Ġ( 2 ^ T )* B Ġ< Ġbeta ^ n } ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġb Shift ed Ġ= ĠMutable BigInteger ( b ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġb Shift ed . safe Left Shift ( sigma ) Ġ// Ġstep Ġ 4 a : Ġshift Ġb Ġso Ġits Ġlength Ġis Ġa Ġmultiple Ġof Ġn ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġa Shift ed Ġ= ĠMutable BigInteger ( this ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġa Shift ed . safe Left Shift ( sigma ) Ġ// Ġstep Ġ 4 b : Ġshift Ġa Ġby Ġthe Ġsame Ġamount ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġstep Ġ 5 : Ġt Ġis Ġthe Ġnumber Ġof Ġblocks Ġneeded Ġto Ġac commod ate Ġa Ġplus Ġone Ġadditional Ġbit ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġt : ĠInt Ġ= Ġ(( a Shift ed . bit Length () Ġ+ Ġn 3 2 ) Ġ/ Ġn 3 2 ). toInt () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( t Ġ< Ġ 2 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġt Ġ= Ġ 2 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġstep Ġ 6 : Ġconcept ually Ġsplit Ġa Ġinto Ġblocks Ġa [ t - 1 ], Ġ..., Ġa [ 0 ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġa 1 : ĠMutable BigInteger Ġ= Ġa Shift ed . getBlock ( t Ġ- Ġ 1 , Ġt , Ġn ) Ġ// Ġthe Ġmost Ġsignificant Ġblock Ġof Ġa ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġstep Ġ 7 : Ġz [ t - 2 ] Ġ= Ġ[ a [ t - 1 ], Ġa [ t - 2 ]] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġz : ĠMutable BigInteger Ġ= Ġa Shift ed . getBlock ( t Ġ- Ġ 2 , Ġt , Ġn ) Ġ// Ġthe Ġsecond Ġto Ġmost Ġsignificant Ġblock ĊĠĠĠĠĠĠĠĠĠĠĠ Ġz . add Dis joint ( a 1 , Ġn ) Ġ// Ġz [ t - 2 ] ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġdo Ġschool book Ġdivision Ġon Ġblocks , Ġdiv iding Ġ 2 - block Ġnumbers Ġby Ġ 1 - block Ġnumbers ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġq i Ġ= ĠMutable BigInteger () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġri : ĠMutable BigInteger ? ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġt Ġ- Ġ 2 Ġdown To Ġ 1 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġstep Ġ 8 a : Ġcompute Ġ( qi , ri ) Ġsuch Ġthat Ġz = b * qi + ri ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġri Ġ= Ġz . divide 2 n 1 n ( b Shift ed , Ġq i ) ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġstep Ġ 8 b : Ġz Ġ= Ġ[ ri , Ġa [ i - 1 ]] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġz Ġ= Ġa Shift ed . getBlock ( i Ġ- Ġ 1 , Ġt , Ġn ) Ġ// Ġa [ i - 1 ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġz . add Dis joint ( ri , Ġn ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġquot ient . add Shift ed ( qi , Ġi Ġ* Ġn ) Ġ// Ġupdate Ġq Ġ( part Ġof Ġstep Ġ 9 ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġfinal Ġiteration Ġof Ġstep Ġ 8 : Ġdo Ġthe Ġloop Ġone Ġmore Ġtime Ġfor Ġi = 0 Ġbut Ġleave Ġz Ġunchanged ĊĠĠĠĠĠĠĠĠĠĠĠ Ġri Ġ= Ġz . divide 2 n 1 n ( b Shift ed , Ġq i ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġquot ient . add ( qi ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġri . right Shift ( sigma ) Ġ// Ġstep Ġ 9 : Ġa Ġand Ġb Ġwere Ġshifted , Ġso Ġshift Ġback ĊĠĠĠĠĠĠĠĠĠĠĠ Ġri ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠThis Ġmethod Ġimplements Ġalgorithm Ġ 1 Ġfrom Ġpg . Ġ 4 Ġof Ġthe ĠB urn ikel - Z ie g ler Ġpaper . ĊĠĠĠĠ Ġ* ĠIt Ġdiv ides Ġa Ġ 2 n - digit Ġnumber Ġby Ġa Ġn - digit Ġnumber .< br ></ br > ĊĠĠĠĠ Ġ* ĠThe Ġparameter Ġbeta Ġis Ġ 2 < sup > 3 2 </ sup > Ġso Ġall Ġsh ifts Ġare Ġmultip les Ġof Ġ 3 2 Ġbits . ĊĠĠĠĠ Ġ* Ġ< br ></ br > ĊĠĠĠĠ Ġ* Ġ` this ` Ġmust Ġbe Ġa Ġnon negative Ġnumber Ġsuch Ġthat Ġ` this . bit Length () Ġ<= Ġ 2 * b . bit Length ()` ĊĠĠĠĠ Ġ* Ġ@ param Ġb Ġa Ġpositive Ġnumber Ġsuch Ġthat Ġ` b . bit Length ()` Ġis Ġeven ĊĠĠĠĠ Ġ* Ġ@ param Ġquot ient Ġoutput Ġparameter Ġfor Ġ` this / b ` ĊĠĠĠĠ Ġ* Ġ@ return Ġ` this % b ` ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġ@ Experimental Std lib Api ĊĠĠĠ Ġprivate Ġfun Ġdivide 2 n 1 n ( ĊĠĠĠĠĠĠĠ Ġb : ĠMutable BigInteger , ĊĠĠĠĠĠĠĠ Ġquot ient : ĠMutable BigInteger ĊĠĠĠ Ġ): ĠMutable BigInteger Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġn Ġ= Ġb . int Len ĊĊĠĠĠĠĠĠĠ Ġ// Ġstep Ġ 1 : Ġbase Ġcase ĊĠĠĠĠĠĠĠ Ġif Ġ( n Ġ% Ġ 2 Ġ!= Ġ 0 Ġ|| Ġn Ġ< ĠBigInteger . B URN IK EL _ Z IE GL ER _ THRESHOLD ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġdivide Kn uth ( b , Ġquot ient ) !! ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġ// Ġstep Ġ 2 : Ġview Ġthis Ġas Ġ[ a 1 , a 2 , a 3 , a 4 ] Ġwhere Ġeach Ġai Ġis Ġn / 2 Ġints Ġor Ġless ĊĠĠĠĠĠĠĠ Ġval Ġa Upper Ġ= ĠMutable BigInteger ( this ) ĊĠĠĠĠĠĠĠ Ġa Upper . safe Right Shift ( 3 2 Ġ* Ġ( n Ġ/ Ġ 2 )) Ġ// Ġa Upper Ġ= Ġ[ a 1 , a 2 , a 3 ] ĊĠĠĠĠĠĠĠ Ġkeep Lower ( n Ġ/ Ġ 2 ) Ġ// Ġthis Ġ= Ġa 4 ĊĊĠĠĠĠĠĠĠ Ġ// Ġstep Ġ 3 : Ġq 1 = a Upper / b , Ġr 1 = a Upper % b ĊĠĠĠĠĠĠĠ Ġval Ġq 1 Ġ= ĠMutable BigInteger () ĊĠĠĠĠĠĠĠ Ġval Ġr 1 : ĠMutable BigInteger Ġ= Ġa Upper . divide 3 n 2 n ( b , Ġq 1 ) ĊĊĠĠĠĠĠĠĠ Ġ// Ġstep Ġ 4 : Ġquot ient =[ r 1 , this ]/ b , Ġr 2 =[ r 1 , this ] % b ĊĠĠĠĠĠĠĠ Ġadd Dis joint ( r 1 , Ġn Ġ/ Ġ 2 ) Ġ// Ġthis Ġ= Ġ[ r 1 , this ] ĊĠĠĠĠĠĠĠ Ġval Ġr 2 Ġ= Ġdivide 3 n 2 n ( b , Ġquot ient ) ĊĊĠĠĠĠĠĠĠ Ġ// Ġstep Ġ 5 : Ġlet Ġquot ient =[ q 1 , quot ient ] Ġand Ġreturn Ġr 2 ĊĠĠĠĠĠĠĠ Ġquot ient . add Dis joint ( q 1 , Ġn Ġ/ Ġ 2 ) ĊĠĠĠĠĠĠĠ Ġreturn Ġr 2 ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠThis Ġmethod Ġimplements Ġalgorithm Ġ 2 Ġfrom Ġpg . Ġ 5 Ġof Ġthe ĠB urn ikel - Z ie g ler Ġpaper . ĊĠĠĠĠ Ġ* ĠIt Ġdiv ides Ġa Ġ 3 n - digit Ġnumber Ġby Ġa Ġ 2 n - digit Ġnumber .< br ></ br > ĊĠĠĠĠ Ġ* ĠThe Ġparameter Ġbeta Ġis Ġ 2 < sup > 3 2 </ sup > Ġso Ġall Ġsh ifts Ġare Ġmultip les Ġof Ġ 3 2 Ġbits .< br ></ br > ĊĠĠĠĠ Ġ* Ġ< br ></ br > ĊĠĠĠĠ Ġ* Ġ` this ` Ġmust Ġbe Ġa Ġnon negative Ġnumber Ġsuch Ġthat Ġ` 2 * this . bit Length () Ġ<= Ġ 3 * b . bit Length ()` ĊĠĠĠĠ Ġ* Ġ@ param Ġquot ient Ġoutput Ġparameter Ġfor Ġ` this / b ` ĊĠĠĠĠ Ġ* Ġ@ return Ġ` this % b ` ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġ@ Experimental Std lib Api ĊĠĠĠ Ġprivate Ġfun Ġdivide 3 n 2 n ( ĊĠĠĠĠĠĠĠ Ġb : ĠMutable BigInteger , ĊĠĠĠĠĠĠĠ Ġquot ient : ĠMutable BigInteger ĊĠĠĠ Ġ): ĠMutable BigInteger Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġn Ġ= Ġb . int Len Ġ/ Ġ 2 Ġ// Ġhalf Ġthe Ġlength Ġof Ġb Ġin Ġints ĊĊĠĠĠĠĠĠĠ Ġ// Ġstep Ġ 1 : Ġview Ġthis Ġas Ġ[ a 1 , a 2 , a 3 ] Ġwhere Ġeach Ġai Ġis Ġn Ġints Ġor Ġless ; Ġlet Ġa 1 2 =[ a 1 , a 2 ] ĊĠĠĠĠĠĠĠ Ġval Ġa 1 2 Ġ= ĠMutable BigInteger ( this ) ĊĠĠĠĠĠĠĠ Ġa 1 2 . safe Right Shift ( 3 2 Ġ* Ġn ) ĊĊĠĠĠĠĠĠĠ Ġ// Ġstep Ġ 2 : Ġview Ġb Ġas Ġ[ b 1 , b 2 ] Ġwhere Ġeach Ġbi Ġis Ġn Ġints Ġor Ġless ĊĠĠĠĠĠĠĠ Ġval Ġb 1 Ġ= ĠMutable BigInteger ( b ) ĊĠĠĠĠĠĠĠ Ġb 1 . safe Right Shift ( n Ġ* Ġ 3 2 ) ĊĠĠĠĠĠĠĠ Ġval Ġb 2 : ĠBigInteger Ġ= Ġb . get Lower ( n ) ĊĠĠĠĠĠĠĠ Ġval Ġr : ĠMutable BigInteger ĊĠĠĠĠĠĠĠ Ġval Ġd : ĠMutable BigInteger ĊĠĠĠĠĠĠĠ Ġif Ġ( compare Shift ed ( b , Ġn ) Ġ< Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġstep Ġ 3 a : Ġif Ġa 1 < b 1 , Ġlet Ġquot ient = a 1 2 / b 1 Ġand Ġr = a 1 2 % b 1 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġr Ġ= Ġa 1 2 . divide 2 n 1 n ( b 1 , Ġquot ient ) ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġstep Ġ 4 : Ġd = quot ient * b 2 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġd Ġ= ĠMutable BigInteger ( quot ient . to BigInteger (). multiply ( b 2 )) ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġstep Ġ 3 b : Ġif Ġa 1 >= b 1 , Ġlet Ġquot ient = beta ^ n - 1 Ġand Ġr = a 1 2 - b 1 * 2 ^ n + b 1 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġquot ient . ones ( n ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġa 1 2 . add ( b 1 ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġb 1 . left Shift ( 3 2 Ġ* Ġn ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġa 1 2 . subtract ( b 1 ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġr Ġ= Ġa 1 2 ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġstep Ġ 4 : Ġd = quot ient * b 2 =( b 2 Ġ<< Ġ 3 2 * n ) Ġ- Ġb 2 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġd Ġ= ĠMutable BigInteger ( b 2 ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġd . left Shift ( 3 2 Ġ* Ġn ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġd . subtract ( Mutable BigInteger ( b 2 )) ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġ// Ġstep Ġ 5 : Ġr Ġ= Ġr * beta ^ n Ġ+ Ġa 3 Ġ- Ġd Ġ( paper Ġsays Ġa 4 ) ĊĠĠĠĠĠĠĠ Ġ// ĠHowever , Ġdon 't Ġsubtract Ġd Ġuntil Ġafter Ġthe Ġwhile Ġloop Ġso Ġr Ġdoesn 't Ġbecome Ġnegative ĊĠĠĠĠĠĠĠ Ġr . left Shift ( 3 2 Ġ* Ġn ) ĊĠĠĠĠĠĠĠ Ġr . add Lower ( this , Ġn ) ĊĊĠĠĠĠĠĠĠ Ġ// Ġstep Ġ 6 : Ġadd Ġb Ġuntil Ġr >= d ĊĠĠĠĠĠĠĠ Ġwhile Ġ( r . compare ( d ) Ġ< Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġr . add ( b ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġquot ient . subtract ( ONE ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġr . subtract ( d ) ĊĠĠĠĠĠĠĠ Ġreturn Ġr ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠReturns Ġa Ġ` Mutable BigInteger ` Ġcontaining Ġ` block Length ` Ġints Ġfrom ĊĠĠĠĠ Ġ* Ġ` this ` Ġnumber , Ġstarting Ġat Ġ` index * block Length `. < br ></ br > ĊĠĠĠĠ Ġ* ĠUsed Ġby ĠB urn ikel - Z ie g ler Ġdivision . ĊĠĠĠĠ Ġ* Ġ@ param Ġindex Ġthe Ġblock Ġindex ĊĠĠĠĠ Ġ* Ġ@ param Ġnum Blocks Ġthe Ġtotal Ġnumber Ġof Ġblocks Ġin Ġ` this ` Ġnumber ĊĠĠĠĠ Ġ* Ġ@ param Ġblock Length Ġlength Ġof Ġone Ġblock Ġin Ġunits Ġof Ġ 3 2 Ġbits ĊĠĠĠĠ Ġ* Ġ@ return ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġprivate Ġfun Ġget Block ( index : ĠInt , Ġnum Blocks : ĠInt , Ġblock Length : ĠInt ): ĠMutable BigInteger Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġblock Start Ġ= Ġindex Ġ* Ġblock Length ĊĠĠĠĠĠĠĠ Ġif Ġ( block Start Ġ>= Ġint Len ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn ĠMutable BigInteger () ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġval Ġblock End : ĠInt ĊĠĠĠĠĠĠĠ Ġblock End Ġ= Ġif Ġ( index Ġ== Ġnum Blocks Ġ- Ġ 1 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġint Len ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ( index Ġ+ Ġ 1 ) Ġ* Ġblock Length ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġif Ġ( block End Ġ> Ġint Len ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn ĠMutable BigInteger () ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġval ĠnewVal : ĠInt Array Ġ= ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvalue . copyOf Range ( offset Ġ+ Ġint Len Ġ- Ġblock End , Ġoffset Ġ+ Ġint Len Ġ- Ġblock Start ) ĊĠĠĠĠĠĠĠ Ġreturn ĠMutable BigInteger ( new Val ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** Ġ@ see ĠBigInteger . bit Length ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġ@ Experimental Std lib Api ĊĠĠĠ Ġfun Ġbit Length (): ĠLong Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġif Ġ( int Len Ġ== Ġ 0 ) Ġ 0 Ġelse Ġint Len Ġ* Ġ 3 2 L Ġ- Ġ( value [ offset ]. count Leading Zero Bits ()) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠIntern ally Ġused Ġ Ġto Ġcalculate Ġthe Ġquot ient Ġof Ġthis Ġdiv Ġv Ġand Ġplaces Ġthe ĊĠĠĠĠ Ġ* Ġquot ient Ġin Ġthe Ġprovided ĠMutable BigInteger Ġobject Ġand Ġthe Ġremainder Ġis ĊĠĠĠĠ Ġ* Ġreturned . ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* Ġ@ return Ġthe Ġremainder Ġof Ġthe Ġdivision Ġwill Ġbe Ġreturned . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġ@ Experimental Std lib Api ĊĠĠĠ Ġfun Ġdivide ( v : ĠLong , Ġquot ient : ĠMutable BigInteger ): ĠLong Ġ{ ĊĠĠĠĠĠĠĠ Ġvar Ġv Ġ= Ġv ĊĠĠĠĠĠĠĠ Ġif Ġ( v Ġ== Ġ 0 L ) Ġthrow ĠArithmetic Exception (" BigInteger Ġdivide Ġby Ġzero ") ĊĊĠĠĠĠĠĠĠ Ġ// ĠDiv id end Ġis Ġzero ĊĠĠĠĠĠĠĠ Ġif Ġ( int Len Ġ== Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġquot ient . offset Ġ= Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġquot ient . int Len Ġ= Ġquot ient . offset ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġ 0 ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġif Ġ( v Ġ< Ġ 0 ) Ġv Ġ= Ġ- v ĊĠĠĠĠĠĠĠ Ġval Ġd Ġ= Ġ( v Ġ ush r Ġ 3 2 ). toInt () ĊĠĠĠĠĠĠĠ Ġquot ient . clear () ĊĠĠĠĠĠĠĠ Ġ// ĠSpecial Ġcase Ġon Ġword Ġdivisor ĊĠĠĠĠĠĠĠ Ġreturn Ġif Ġ( d Ġ== Ġ 0 ) Ġ( divide One Word ( v . toInt (), Ġquot ient ). to Long () Ġand ĠBigInteger . LONG _ MASK ) Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġdivide Long Magnitude ( v , Ġquot ient ). to Long () ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠDiv ide Ġthis ĠMutable BigInteger Ġby Ġthe Ġdivisor . ĊĠĠĠĠ Ġ* ĠThe Ġquot ient Ġwill Ġbe Ġplaced Ġinto Ġthe Ġprovided Ġquot ient Ġobject Ġ& ĊĠĠĠĠ Ġ* Ġthe Ġremainder Ġobject Ġis Ġreturned . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġ@ Experimental Std lib Api ĊĠĠĠ Ġprivate Ġfun Ġdivide Magnitude ( ĊĠĠĠĠĠĠĠ Ġdiv : ĠMutable BigInteger ?, ĊĠĠĠĠĠĠĠ Ġquot ient : ĠMutable BigInteger ?, ĊĠĠĠĠĠĠĠ Ġneed Remain der : ĠBoolean ĊĠĠĠ Ġ): ĠMutable BigInteger ? Ġ{ ĊĠĠĠĠĠĠĠ Ġ// Ġassert Ġdiv . int Len Ġ> Ġ 1 ĊĠĠĠĠĠĠĠ Ġ// ĠD 1 Ġnormalize Ġthe Ġdivisor ĊĠĠĠĠĠĠĠ Ġval Ġshift : ĠInt Ġ= Ġ( div !!. value [ div . offset ]). count Leading Zero Bits () ĊĠĠĠĠĠĠĠ Ġ// ĠCopy Ġdivisor Ġvalue Ġto Ġprotect Ġdivisor ĊĠĠĠĠĠĠĠ Ġval Ġd len Ġ= Ġdiv . int Len ĊĠĠĠĠĠĠĠ Ġval Ġdivisor : ĠInt Array ĊĠĠĠĠĠĠĠ Ġval Ġrem : ĠMutable BigInteger Ġ// ĠRem ain der Ġstarts Ġas Ġdiv id end Ġwith Ġspace Ġfor Ġa Ġleading Ġzero ĊĠĠĠĠĠĠĠ Ġif Ġ( shift Ġ> Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġdivisor Ġ= ĠInt Array ( d len ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġcopy And Shift ( div . value , Ġdiv . offset , Ġd len , Ġdivisor , Ġ 0 , Ġshift ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ(( value [ offset ]). count Leading Zero Bits () Ġ>= Ġshift ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġrem arr Ġ= ĠInt Array ( int Len Ġ+ Ġ 1 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġrem Ġ= ĠMutable BigInteger ( rem arr ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġrem . int Len Ġ= Ġint Len ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġrem . offset Ġ= Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcopy And Shift ( value , Ġoffset , Ġint Len , Ġrem arr , Ġ 1 , Ġshift ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġrem arr Ġ= ĠInt Array ( int Len Ġ+ Ġ 2 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġrem Ġ= ĠMutable BigInteger ( rem arr ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġrem . int Len Ġ= Ġint Len Ġ+ Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġrem . offset Ġ= Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġr From Ġ= Ġoffset ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġc Ġ= Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġn 2 Ġ= Ġ 3 2 Ġ- Ġshift ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġi Ġ= Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ( i Ġ< Ġint Len Ġ+ Ġ 1 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġb Ġ= Ġc ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġc Ġ= Ġvalue [ r From ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġrem arr [ i ] Ġ= Ġb Ġshl Ġshift Ġor Ġ( c Ġ ush r Ġn 2 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġi ++ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġr From ++ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġrem arr [ int Len Ġ+ Ġ 1 ] Ġ= Ġc Ġshl Ġshift ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġdivisor Ġ= Ġdiv . value . copyOf Range ( div . offset , Ġdiv . offset Ġ+ Ġdiv . int Len ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġrem Ġ= ĠMutable BigInteger ( IntArray ( int Len Ġ+ Ġ 1 )) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvalue . copy Into ( rem . value , Ġ 1 , Ġoffset , Ġoffset Ġ+ Ġint Len ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġrem . int Len Ġ= Ġint Len ĊĠĠĠĠĠĠĠĠĠĠĠ Ġrem . offset Ġ= Ġ 1 ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġval Ġn len Ġ= Ġrem . int Len ĊĊĠĠĠĠĠĠĠ Ġ// ĠSet Ġthe Ġquot ient Ġsize ĊĠĠĠĠĠĠĠ Ġval Ġlimit Ġ= Ġn len Ġ- Ġd len Ġ+ Ġ 1 ĊĠĠĠĠĠĠĠ Ġif Ġ( quot ient !!. value . size Ġ< Ġlimit ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġquot ient . value Ġ= ĠInt Array ( limit ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġquot ient . offset Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġquot ient . int Len Ġ= Ġlimit ĊĠĠĠĠĠĠĠ Ġval Ġq Ġ= Ġquot ient . value ĊĊĊĠĠĠĠĠĠĠ Ġ// ĠMust Ġinsert Ġleading Ġ 0 Ġin Ġrem Ġif Ġits Ġlength Ġdid Ġnot Ġchange ĊĠĠĠĠĠĠĠ Ġif Ġ( rem . int Len Ġ== Ġn len ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġrem . offset Ġ= Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġrem . value [ 0 ] Ġ= Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġrem . int Len ++ ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġval Ġdh Ġ= Ġdivisor [ 0 ] ĊĠĠĠĠĠĠĠ Ġval Ġdh Long Ġ= Ġ( dh . to Long () Ġand ĠBigInteger . LONG _ MASK ) ĊĠĠĠĠĠĠĠ Ġval Ġdl Ġ= Ġdivisor [ 1 ] ĊĊĠĠĠĠĠĠĠ Ġ// ĠD 2 ĠInitialize Ġj ĊĠĠĠĠĠĠĠ Ġfor Ġ( j Ġin Ġ 0 Ġuntil Ġlimit Ġ- Ġ 1 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠD 3 ĠCalculate Ġq hat ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġestimate Ġq hat ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġq hat : ĠInt ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġq rem : ĠInt ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġskip Correction Ġ= Ġfalse ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġnh Ġ= Ġrem . value [ j Ġ+ Ġrem . offset ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġnh 2 Ġ= Ġnh Ġ+ Ġ- 0 x 8 0 0 0 0 0 0 0 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġnm Ġ= Ġrem . value [ j Ġ+ Ġ 1 Ġ+ Ġrem . offset ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( nh Ġ== Ġdh ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġq hat Ġ= Ġ 0 . inv () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġq rem Ġ= Ġnh Ġ+ Ġnm ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġskip Correction Ġ= Ġq rem Ġ+ Ġ- 0 x 8 0 0 0 0 0 0 0 Ġ< Ġnh 2 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġn Chunk Ġ= Ġnh . to Long () Ġshl Ġ 3 2 Ġor Ġ( nm . to Long () Ġand ĠBigInteger . LONG _ MASK ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( n Chunk Ġ>= Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġq hat Ġ= Ġ( n Chunk Ġ/ Ġdh Long ). toInt () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġq rem Ġ= Ġ( n Chunk Ġ- Ġq hat Ġ* Ġdh Long ). toInt () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġtmp Ġ= Ġdiv Word ( n Chunk , Ġdh ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġq hat Ġ= Ġ( tmp Ġand ĠBigInteger . LONG _ MASK ). toInt () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġq rem Ġ= Ġ( tmp Ġ ush r Ġ 3 2 ). toInt () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( q hat Ġ== Ġ 0 ) Ġcontinue ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ(! skip Correction ) Ġ{ Ġ// ĠCorrect Ġq hat ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġnl Ġ= Ġ( rem . value [ j Ġ+ Ġ 2 Ġ+ Ġrem . offset ]. to Long () Ġand ĠBigInteger . LONG _ MASK ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġrs Ġ= Ġ( q rem . to Long () Ġand ĠBigInteger . LONG _ MASK Ġshl Ġ 3 2 ) Ġor Ġnl ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġest Product Ġ= ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ(( dl . to Long () Ġand ĠBigInteger . LONG _ MASK ) Ġ* Ġ( q hat . to Long () Ġand ĠBigInteger . LONG _ MASK )) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( unsigned Long Compare ( est Product , Ġrs )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġq hat -- ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġq rem Ġ= Ġ(( q rem . to Long () Ġand ĠBigInteger . LONG _ MASK ) Ġ+ Ġdh Long ). toInt () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( q rem . to Long () Ġand ĠBigInteger . LONG _ MASK Ġ>= Ġdh Long ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġest Product Ġ-= Ġdl . to Long () Ġand ĠBigInteger . LONG _ MASK ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġrs Ġ= Ġ( q rem . to Long () Ġand ĠBigInteger . LONG _ MASK Ġshl Ġ 3 2 ) Ġor Ġnl ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( unsigned Long Compare ( est Product , Ġrs )) Ġq hat -- ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠD 4 ĠMultiply Ġand Ġsubtract ĊĠĠĠĠĠĠĠĠĠĠĠ Ġrem . value [ j Ġ+ Ġrem . offset ] Ġ= Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġborrow Ġ= Ġmul sub ( rem . value , Ġdivisor , Ġq hat , Ġd len , Ġj Ġ+ Ġrem . offset ) ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠD 5 ĠTest Ġremainder ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( borrow Ġ+ Ġ- 0 x 8 0 0 0 0 0 0 0 Ġ> Ġnh 2 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠD 6 ĠAdd Ġback ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġdiv add ( div isor , Ġrem . value , Ġj Ġ+ Ġ 1 Ġ+ Ġrem . offset ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġq hat -- ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠStore Ġthe Ġquot ient Ġdigit ĊĠĠĠĠĠĠĠĠĠĠĠ Ġq [ j ] Ġ= Ġq hat ĊĠĠĠĠĠĠĠ Ġ} Ġ// ĠD 7 Ġloop Ġon Ġj ĊĠĠĠĠĠĠĠ Ġ// ĠD 3 ĠCalculate Ġq hat ĊĠĠĠĠĠĠĠ Ġ// Ġestimate Ġq hat ĊĠĠĠĠĠĠĠ Ġvar Ġq hat : ĠInt ĊĠĠĠĠĠĠĠ Ġvar Ġq rem : ĠInt ĊĠĠĠĠĠĠĠ Ġvar Ġskip Correction Ġ= Ġfalse ĊĠĠĠĠĠĠĠ Ġval Ġnh Ġ= Ġrem . value [ limit Ġ- Ġ 1 Ġ+ Ġrem . offset ] ĊĠĠĠĠĠĠĠ Ġval Ġnh 2 Ġ= Ġnh Ġ+ Ġ- 0 x 8 0 0 0 0 0 0 0 ĊĠĠĠĠĠĠĠ Ġval Ġnm Ġ= Ġrem . value [ limit Ġ+ Ġrem . offset ] ĊĠĠĠĠĠĠĠ Ġif Ġ( nh Ġ== Ġdh ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġq hat Ġ= Ġ 0 . inv () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġq rem Ġ= Ġnh Ġ+ Ġnm ĊĠĠĠĠĠĠĠĠĠĠĠ Ġskip Correction Ġ= Ġq rem Ġ+ Ġ- 0 x 8 0 0 0 0 0 0 0 Ġ< Ġnh 2 ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġn Chunk Ġ= Ġnh . to Long () Ġshl Ġ 3 2 Ġor Ġ( nm . to Long () Ġand ĠBigInteger . LONG _ MASK ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( n Chunk Ġ>= Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġq hat Ġ= Ġ( n Chunk Ġ/ Ġdh Long ). toInt () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġq rem Ġ= Ġ( n Chunk Ġ- Ġq hat Ġ* Ġdh Long ). toInt () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġtmp Ġ= Ġdiv Word ( n Chunk , Ġdh ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġq hat Ġ= Ġ( tmp Ġand ĠBigInteger . LONG _ MASK ). toInt () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġq rem Ġ= Ġ( tmp Ġ ush r Ġ 3 2 ). toInt () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġif Ġ( q hat Ġ!= Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ(! skip Correction ) Ġ{ Ġ// ĠCorrect Ġq hat ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġnl Ġ= Ġ( rem . value [ limit Ġ+ Ġ 1 Ġ+ Ġrem . offset ]. to Long () Ġand ĠBigInteger . LONG _ MASK ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġrs Ġ= Ġ( q rem . to Long () Ġand ĠBigInteger . LONG _ MASK Ġshl Ġ 3 2 ) Ġor Ġnl ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġest Product Ġ= ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ(( dl . to Long () Ġand ĠBigInteger . LONG _ MASK ) Ġ* Ġ( q hat . to Long () Ġand ĠBigInteger . LONG _ MASK )) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( unsigned Long Compare ( est Product , Ġrs )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġq hat -- ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġq rem Ġ= Ġ(( q rem . to Long () Ġand ĠBigInteger . LONG _ MASK ) Ġ+ Ġdh Long ). toInt () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( q rem . to Long () Ġand ĠBigInteger . LONG _ MASK Ġ>= Ġdh Long ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġest Product Ġ-= Ġdl . to Long () Ġand ĠBigInteger . LONG _ MASK ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġrs Ġ= Ġ( q rem . to Long () Ġand ĠBigInteger . LONG _ MASK Ġshl Ġ 3 2 ) Ġor Ġnl ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( unsigned Long Compare ( est Product , Ġrs )) Ġq hat -- ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠD 4 ĠMultiply Ġand Ġsubtract ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġborrow : ĠInt ĊĠĠĠĠĠĠĠĠĠĠĠ Ġrem . value [ limit Ġ- Ġ 1 Ġ+ Ġrem . offset ] Ġ= Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġborrow Ġ= Ġif Ġ( need Remain der ) Ġmul sub ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġrem . value , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġdivisor , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġq hat , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġd len , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġlimit Ġ- Ġ 1 Ġ+ Ġrem . offset ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ) Ġelse Ġmul sub Borrow ( rem . value , Ġdivisor , Ġq hat , Ġd len , Ġlimit Ġ- Ġ 1 Ġ+ Ġrem . offset ) ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠD 5 ĠTest Ġremainder ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( borrow Ġ+ Ġ- 0 x 8 0 0 0 0 0 0 0 Ġ> Ġnh 2 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠD 6 ĠAdd Ġback ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( need Remain der ) Ġdiv add ( div isor , Ġrem . value , Ġlimit Ġ- Ġ 1 Ġ+ Ġ 1 Ġ+ Ġrem . offset ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġq hat -- ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠStore Ġthe Ġquot ient Ġdigit ĊĠĠĠĠĠĠĠĠĠĠĠ Ġq [ limit Ġ- Ġ 1 ] Ġ= Ġq hat ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġif Ġ( need Remain der ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠD 8 ĠUn normalize ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( shift Ġ> Ġ 0 ) Ġrem . right Shift ( shift ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġrem . normalize () ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġquot ient . normalize () ĊĠĠĠĠĠĠĠ Ġreturn Ġif Ġ( need Remain der ) Ġrem Ġelse Ġnull ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠDiv ide Ġthis ĠMutable BigInteger Ġby Ġthe Ġdivisor Ġrepresented Ġby Ġpositive Ġlong ĊĠĠĠĠ Ġ* Ġvalue . ĠThe Ġquot ient Ġwill Ġbe Ġplaced Ġinto Ġthe Ġprovided Ġquot ient Ġobject Ġ& ĊĠĠĠĠ Ġ* Ġthe Ġremainder Ġobject Ġis Ġreturned . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġ@ Experimental Std lib Api ĊĠĠĠ Ġprivate Ġfun Ġdivide Long Magnitude ( ĊĠĠĠĠĠĠĠ Ġl div isor : ĠLong , ĊĠĠĠĠĠĠĠ Ġquot ient : ĠMutable BigInteger ĊĠĠĠ Ġ): ĠMutable BigInteger Ġ{ ĊĠĠĠĠĠĠĠ Ġ// ĠRem ain der Ġstarts Ġas Ġdiv id end Ġwith Ġspace Ġfor Ġa Ġleading Ġzero ĊĠĠĠĠĠĠĠ Ġvar Ġl div isor Ġ= Ġl div isor ĊĠĠĠĠĠĠĠ Ġval Ġrem Ġ= ĠMutable BigInteger ( IntArray ( int Len Ġ+ Ġ 1 )) ĊĠĠĠĠĠĠĠ Ġvalue . copy Into ( rem . value , Ġ 1 , Ġoffset , Ġoffset Ġ+ Ġint Len ) ĊĠĠĠĠĠĠĠ Ġrem . int Len Ġ= Ġint Len ĊĠĠĠĠĠĠĠ Ġrem . offset Ġ= Ġ 1 ĊĠĠĠĠĠĠĠ Ġval Ġn len : ĠInt Ġ= Ġrem . int Len ĊĠĠĠĠĠĠĠ Ġval Ġlimit Ġ= Ġn len Ġ- Ġ 2 Ġ+ Ġ 1 ĊĠĠĠĠĠĠĠ Ġif Ġ( quot ient . value . size Ġ< Ġlimit ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġquot ient . value Ġ= ĠInt Array ( limit ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġquot ient . offset Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġquot ient . int Len Ġ= Ġlimit ĊĠĠĠĠĠĠĠ Ġval Ġq Ġ= Ġquot ient . value ĊĊĠĠĠĠĠĠĠ Ġ// ĠD 1 Ġnormalize Ġthe Ġdivisor ĊĠĠĠĠĠĠĠ Ġval Ġshift : ĠInt Ġ= Ġl div isor . count Leading Zero Bits () ĊĠĠĠĠĠĠĠ Ġif Ġ( shift Ġ> Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġl div isor Ġ= Ġl div isor Ġshl Ġshift ĊĠĠĠĠĠĠĠĠĠĠĠ Ġrem . left Shift ( shift ) ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġ// ĠMust Ġinsert Ġleading Ġ 0 Ġin Ġrem Ġif Ġits Ġlength Ġdid Ġnot Ġchange ĊĠĠĠĠĠĠĠ Ġif Ġ( rem . int Len Ġ== Ġn len ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġrem . offset Ġ= Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġrem . value [ 0 ] Ġ= Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġrem . int Len ++ ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġval Ġdh Ġ= Ġ( l div isor Ġ ush r Ġ 3 2 ). toInt () ĊĠĠĠĠĠĠĠ Ġval Ġdh Long Ġ= Ġ( dh . to Long () Ġand ĠBigInteger . LONG _ MASK ) ĊĠĠĠĠĠĠĠ Ġval Ġdl Ġ= Ġ( l div isor Ġand ĠBigInteger . LONG _ MASK ). toInt () ĊĊĠĠĠĠĠĠĠ Ġ// ĠD 2 ĠInitialize Ġj ĊĠĠĠĠĠĠĠ Ġfor Ġ( j Ġin Ġ 0 Ġuntil Ġlimit ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠD 3 ĠCalculate Ġq hat ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġestimate Ġq hat ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġq hat : ĠInt ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġq rem : ĠInt ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġskip Correction Ġ= Ġfalse ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġnh : ĠInt Ġ= Ġrem . value . get ( j Ġ+ Ġrem . offset ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġnh 2 Ġ= Ġnh Ġ+ Ġ- 0 x 8 0 0 0 0 0 0 0 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġnm : ĠInt Ġ= Ġrem . value . get ( j Ġ+ Ġ 1 Ġ+ Ġrem . offset ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( nh Ġ== Ġdh ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġq hat Ġ= Ġ 0 . inv () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġq rem Ġ= Ġnh Ġ+ Ġnm ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġskip Correction Ġ= Ġq rem Ġ+ Ġ- 0 x 8 0 0 0 0 0 0 0 Ġ< Ġnh 2 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġn Chunk Ġ= Ġnh . to Long () Ġshl Ġ 3 2 Ġor Ġ( nm . to Long () Ġand ĠBigInteger . LONG _ MASK ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( n Chunk Ġ>= Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġq hat Ġ= Ġ( n Chunk Ġ/ Ġdh Long ). toInt () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġq rem Ġ= Ġ( n Chunk Ġ- Ġq hat Ġ* Ġdh Long ). toInt () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġtmp Ġ= Ġdiv Word ( n Chunk , Ġdh ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġq hat Ġ= Ġ( tmp Ġand ĠBigInteger . LONG _ MASK ). toInt () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġq rem Ġ= Ġ( tmp Ġ ush r Ġ 3 2 ). toInt () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( q hat Ġ== Ġ 0 ) Ġcontinue ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ(! skip Correction ) Ġ{ Ġ// ĠCorrect Ġq hat ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġnl : ĠLong Ġ= Ġ( rem . value [ j Ġ+ Ġ 2 Ġ+ Ġrem . offset ]. to Long () Ġand ĠBigInteger . LONG _ MASK ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġrs Ġ= Ġ( q rem . to Long () Ġand ĠBigInteger . LONG _ MASK Ġshl Ġ 3 2 ) Ġor Ġnl ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġest Product Ġ= ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ(( dl . to Long () Ġand ĠBigInteger . LONG _ MASK ) Ġ* Ġ( q hat . to Long () Ġand ĠBigInteger . LONG _ MASK )) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( unsigned Long Compare ( est Product , Ġrs )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġq hat -- ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġq rem Ġ= Ġ(( q rem . to Long () Ġand ĠBigInteger . LONG _ MASK ) Ġ+ Ġdh Long ). toInt () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( q rem . to Long () Ġand ĠBigInteger . LONG _ MASK Ġ>= Ġdh Long ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġest Product Ġ-= Ġdl . to Long () Ġand ĠBigInteger . LONG _ MASK ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġrs Ġ= Ġ( q rem . to Long () Ġand ĠBigInteger . LONG _ MASK Ġshl Ġ 3 2 ) Ġor Ġnl ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( unsigned Long Compare ( est Product , Ġrs )) Ġq hat -- ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠD 4 ĠMultiply Ġand Ġsubtract ĊĠĠĠĠĠĠĠĠĠĠĠ Ġrem . value [ j Ġ+ Ġrem . offset ] Ġ= Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġborrow Ġ= Ġmul sub Long ( rem . value , Ġdh , Ġdl , Ġq hat , Ġj Ġ+ Ġrem . offset ) ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠD 5 ĠTest Ġremainder ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( borrow Ġ+ Ġ- 0 x 8 0 0 0 0 0 0 0 Ġ> Ġnh 2 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠD 6 ĠAdd Ġback ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġdiv add Long ( dh , Ġdl , Ġrem . value , Ġj Ġ+ Ġ 1 Ġ+ Ġrem . offset ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġq hat -- ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠStore Ġthe Ġquot ient Ġdigit ĊĠĠĠĠĠĠĠĠĠĠĠ Ġq [ j ] Ġ= Ġq hat ĊĠĠĠĠĠĠĠ Ġ} Ġ// ĠD 7 Ġloop Ġon Ġj ĊĊĠĠĠĠĠĠĠ Ġ// ĠD 8 ĠUn normalize ĊĠĠĠĠĠĠĠ Ġif Ġ( shift Ġ> Ġ 0 ) Ġrem . right Shift ( shift ) ĊĠĠĠĠĠĠĠ Ġquot ient . normalize () ĊĠĠĠĠĠĠĠ Ġrem . normalize () ĊĠĠĠĠĠĠĠ Ġreturn Ġrem ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠA Ġprimitive Ġused Ġfor Ġdivision Ġby Ġlong . ĊĠĠĠĠ Ġ* ĠSpecial ized Ġversion Ġof Ġthe Ġmethod Ġdiv add . ĊĠĠĠĠ Ġ* Ġdh Ġis Ġa Ġhigh Ġpart Ġof Ġthe Ġdivisor , Ġdl Ġis Ġa Ġlow Ġpart ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġprivate Ġfun Ġdiv add Long ( dh : ĠInt , Ġdl : ĠInt , Ġresult : ĠInt Array , Ġoffset : ĠInt ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġvar Ġcarry : ĠLong Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġvar Ġsum Ġ= ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ(( dl . to Long () Ġand ĠBigInteger . LONG _ MASK ) Ġ+ Ġ( result [ 1 Ġ+ Ġoffset ]. to Long () Ġand ĠBigInteger . LONG _ MASK )) ĊĠĠĠĠĠĠĠ Ġresult [ 1 Ġ+ Ġoffset ] Ġ= Ġsum . toInt () ĊĠĠĠĠĠĠĠ Ġsum Ġ= Ġ( dh . to Long () Ġand ĠBigInteger . LONG _ MASK ) Ġ+ Ġ( result [ offset ]. to Long () Ġand ĠBigInteger . LONG _ MASK ) Ġ+ Ġcarry ĊĠĠĠĠĠĠĠ Ġresult [ offset ] Ġ= Ġsum . toInt () ĊĠĠĠĠĠĠĠ Ġcarry Ġ= Ġsum Ġ ush r Ġ 3 2 ĊĠĠĠĠĠĠĠ Ġreturn Ġcarry . toInt () ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠThis Ġmethod Ġis Ġused Ġfor Ġdivision Ġby Ġlong . ĊĠĠĠĠ Ġ* ĠSpecial ized Ġversion Ġof Ġthe Ġmethod Ġsul sub . ĊĠĠĠĠ Ġ* Ġdh Ġis Ġa Ġhigh Ġpart Ġof Ġthe Ġdivisor , Ġdl Ġis Ġa Ġlow Ġpart ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġprivate Ġfun Ġmul sub Long ( q : ĠInt Array , Ġdh : ĠInt , Ġdl : ĠInt , Ġx : ĠInt , Ġoffset : ĠInt ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġvar Ġoffset Ġ= Ġoffset ĊĠĠĠĠĠĠĠ Ġval Ġx Long Ġ= Ġ( x . to Long () Ġand ĠBigInteger . LONG _ MASK ) ĊĠĠĠĠĠĠĠ Ġoffset Ġ+= Ġ 2 ĊĠĠĠĠĠĠĠ Ġvar Ġproduct Ġ= Ġ( dl . to Long () Ġand ĠBigInteger . LONG _ MASK ) Ġ* Ġx Long ĊĠĠĠĠĠĠĠ Ġvar Ġdifference Ġ= Ġq [ offset ] Ġ- Ġproduct ĊĠĠĠĠĠĠĠ Ġq [ offset -- ] Ġ= Ġdifference . toInt () ĊĠĠĠĠĠĠĠ Ġvar Ġcarry : ĠLong Ġ= Ġ(( product Ġ ush r Ġ 3 2 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ+ Ġif Ġ( difference Ġand ĠBigInteger . LONG _ MASK Ġ> ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ( product . toInt (). inv (). to Long () Ġand ĠBigInteger . LONG _ MASK )) Ġ 1 Ġelse Ġ 0 ) ĊĠĠĠĠĠĠĠ Ġproduct Ġ= Ġ( dh . to Long () Ġand ĠBigInteger . LONG _ MASK ) Ġ* Ġx Long Ġ+ Ġcarry ĊĠĠĠĠĠĠĠ Ġdifference Ġ= Ġq [ offset ] Ġ- Ġproduct ĊĠĠĠĠĠĠĠ Ġq [ offset -- ] Ġ= Ġdifference . toInt () ĊĠĠĠĠĠĠĠ Ġcarry Ġ= Ġ(( product Ġ ush r Ġ 3 2 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ+ Ġif Ġ( difference Ġand ĠBigInteger . LONG _ MASK Ġ> ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ( product . toInt (). inv (). to Long () Ġand ĠBigInteger . LONG _ MASK )) 1 Ġelse Ġ 0 ) ĊĠĠĠĠĠĠĠ Ġreturn Ġcarry . toInt () ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠCompare Ġtwo Ġlong s Ġas Ġif Ġthey Ġwere Ġunsigned . ĊĠĠĠĠ Ġ* ĠReturns Ġtrue Ġiff Ġone Ġis Ġbigger Ġthan Ġtwo . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġprivate Ġfun Ġunsigned Long Compare ( one : ĠLong , Ġtwo : ĠLong ): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġone Ġ+ ĠLong . MIN _ VALUE Ġ> Ġtwo Ġ+ ĠLong . MIN _ VALUE ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠCalculate Ġthe Ġinteger Ġsquare Ġroot Ġ` floor ( sqrt ( this )) ` Ġwhere ĊĠĠĠĠ Ġ* Ġ` sqrt ( .) ` Ġden otes Ġthe Ġmathematical Ġsquare Ġroot . ĠThe Ġcontents Ġof ĊĠĠĠĠ Ġ* Ġ` this ` Ġare Ġ** not ** Ġchanged . ĠThe Ġvalue Ġof Ġ` this ` Ġis Ġassumed ĊĠĠĠĠ Ġ* Ġto Ġbe Ġnon - negative . ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* Ġ@ impl Note ĠThe Ġimplementation Ġis Ġbased Ġon Ġthe Ġmaterial Ġin ĠHen ry ĠS . ĠWar ren , ĊĠĠĠĠ Ġ* ĠJ r ., Ġ* H acker 's ĠDel ight Ġ( 2 nd Ġed . )* Ġ( Add ison ĠW es ley , Ġ 2 0 1 3 ), Ġ 2 7 9 - 2 8 2 . ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* Ġ@ throws ĠArithmetic Exception Ġif Ġthe Ġvalue Ġreturned Ġby Ġ` bit Length ()` ĊĠĠĠĠ Ġ* Ġoverflow s Ġthe Ġrange Ġof Ġ` int `. ĊĠĠĠĠ Ġ* Ġ@ return Ġthe Ġinteger Ġsquare Ġroot Ġof Ġ` this ` ĊĠĠĠĠ Ġ* Ġ@ since Ġ 9 ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġ@ Experimental Std lib Api ĊĠĠĠ Ġfun Ġsqrt (): ĠMutable BigInteger Ġ{ ĊĠĠĠĠĠĠĠ Ġ// ĠSpecial Ġcases . ĊĠĠĠĠĠĠĠ Ġif Ġ( is Zero ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn ĠMutable BigInteger ( 0 ) ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġif Ġ( value . size Ġ== Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ&& Ġvalue [ 0 ]. to Long () Ġand ĠBigInteger . LONG _ MASK Ġ< Ġ 4 ĊĠĠĠĠĠĠĠ Ġ) Ġ{ Ġ// Ġresult Ġis Ġun ity ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn ĠONE ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġif Ġ( bit Length () Ġ<= Ġ 6 3 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠInitial Ġestimate Ġis Ġthe Ġsquare Ġroot Ġof Ġthe Ġpositive Ġlong Ġvalue . ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġv : ĠLong Ġ= ĠBigInteger ( value , Ġ 1 ). to Long Exact () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġx k Ġ= Ġfloor ( sqrt ( v . toDouble ())). to Long () ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠRef ine Ġthe Ġestimate . ĊĠĠĠĠĠĠĠĠĠĠĠ Ġdo Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġx k 1 Ġ= Ġ( xk Ġ+ Ġv Ġ/ Ġx k ) Ġ/ Ġ 2 ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠTermin ate Ġwhen Ġnon - de creasing . ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( xk 1 Ġ>= Ġx k ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn ĠMutable BigInteger ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġint ArrayOf ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ( xk Ġ ush r Ġ 3 2 ). toInt (), Ġ( xk Ġand ĠBigInteger . LONG _ MASK ). toInt () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġx k Ġ= Ġx k 1 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġwhile Ġ( true ) ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠSet Ġup Ġthe Ġinitial Ġestimate Ġof Ġthe Ġiteration . ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠObtain Ġthe Ġbit Length Ġ> Ġ 6 3 . ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġbit Length Ġ= Ġbit Length (). toInt () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( bit Length . to Long () Ġ!= Ġbit Length ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġthrow ĠArithmetic Exception (" bit Length () Ġinteger Ġoverflow ") ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠDetermine Ġan Ġeven Ġval ued Ġright Ġshift Ġinto Ġpositive Ġlong Ġrange . ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġshift Ġ= Ġbit Length Ġ- Ġ 6 3 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( shift Ġ% Ġ 2 Ġ== Ġ 1 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġshift ++ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠShift Ġthe Ġvalue Ġinto Ġpositive Ġlong Ġrange . ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġx k Ġ= ĠMutable BigInteger ( this ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġx k . right Shift ( shift ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġx k . normalize () ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠUse Ġthe Ġsquare Ġroot Ġof Ġthe Ġshifted Ġvalue Ġas Ġan Ġapproximation . ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġd : ĠDouble Ġ= ĠBigInteger ( xk . value , Ġ 1 ). toDouble () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġbi : ĠBigInteger Ġ= ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠBigInteger . valueOf ( ceil ( sqrt ( d )). to Long ()) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġx k Ġ= ĠMutable BigInteger ( bi . mag ) ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠShift Ġthe Ġapproximate Ġsquare Ġroot Ġback Ġinto Ġthe Ġoriginal Ġrange . ĊĠĠĠĠĠĠĠĠĠĠĠ Ġx k . left Shift ( shift Ġ/ Ġ 2 ) ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠRef ine Ġthe Ġestimate . ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġx k 1 Ġ= ĠMutable BigInteger () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġdo Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġx k 1 Ġ= Ġ( xk Ġ+ Ġn / xk )/ 2 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġthis . divide ( xk , Ġx k 1 , Ġfalse ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġx k 1 . add ( xk ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġx k 1 . right Shift ( 1 ) ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠTermin ate Ġwhen Ġnon - de creasing . ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( xk 1 . compare ( xk ) Ġ>= Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġx k ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġx k Ġ= Ġx k 1 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġx k . copy Value ( xk 1 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġx k 1 . reset () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġwhile Ġ( true ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠCalculate ĠG CD Ġof Ġthis Ġand Ġb . ĠThis Ġand Ġb Ġare Ġchanged Ġby Ġthe Ġcomputation . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġ@ Experimental Std lib Api ĊĠĠĠ Ġfun Ġhybrid G CD ( b : ĠMutable BigInteger ): ĠMutable BigInteger Ġ{ ĊĠĠĠĠĠĠĠ Ġ// ĠUse ĠE u cl id 's Ġalgorithm Ġuntil Ġthe Ġnumbers Ġare Ġapproximately Ġthe ĊĠĠĠĠĠĠĠ Ġ// Ġsame Ġlength , Ġthen Ġuse Ġthe Ġbinary ĠG CD Ġalgorithm Ġto Ġfind Ġthe ĠG CD . ĊĠĠĠĠĠĠĠ Ġvar Ġb Ġ= Ġb ĊĠĠĠĠĠĠĠ Ġvar Ġa : ĠMutable BigInteger Ġ= Ġthis ĊĠĠĠĠĠĠĠ Ġval Ġq Ġ= ĠMutable BigInteger () ĊĠĠĠĠĠĠĠ Ġwhile Ġ( b . int Len Ġ!= Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( abs ( a . int Len Ġ- Ġb . int Len ) Ġ< Ġ 2 ) Ġreturn Ġa . binary G CD ( b ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġr Ġ= Ġa . divide ( b , Ġq ) !! ĊĠĠĠĠĠĠĠĠĠĠĠ Ġa Ġ= Ġb ĊĠĠĠĠĠĠĠĠĠĠĠ Ġb Ġ= Ġr ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġa ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠCalculate ĠG CD Ġof Ġthis Ġand Ġv . ĊĠĠĠĠ Ġ* ĠAss umes Ġthat Ġthis Ġand Ġv Ġare Ġnot Ġzero . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġ@ Experimental Std lib Api ĊĠĠĠ Ġprivate Ġfun Ġbinary G CD ( v : ĠMutable BigInteger ): ĠMutable BigInteger Ġ{ ĊĠĠĠĠĠĠĠ Ġ// ĠAlgorithm ĠB Ġfrom ĠKn uth Ġsection Ġ 4 . 5 . 2 ĊĠĠĠĠĠĠĠ Ġvar Ġv Ġ= Ġv ĊĠĠĠĠĠĠĠ Ġvar Ġu : ĠMutable BigInteger Ġ= Ġthis ĊĠĠĠĠĠĠĠ Ġval Ġr Ġ= ĠMutable BigInteger () ĊĊĠĠĠĠĠĠĠ Ġ// Ġstep ĠB 1 ĊĠĠĠĠĠĠĠ Ġval Ġs 1 Ġ= Ġu . lowest Set Bit ĊĠĠĠĠĠĠĠ Ġval Ġs 2 Ġ= Ġv . lowest Set Bit ĊĠĠĠĠĠĠĠ Ġval Ġk Ġ= Ġif Ġ( s 1 Ġ< Ġs 2 ) Ġs 1 Ġelse Ġs 2 ĊĠĠĠĠĠĠĠ Ġif Ġ( k Ġ!= Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġu . right Shift ( k ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġv . right Shift ( k ) ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġ// Ġstep ĠB 2 ĊĠĠĠĠĠĠĠ Ġval Ġu Odd Ġ= Ġk Ġ== Ġs 1 ĊĠĠĠĠĠĠĠ Ġvar Ġt Ġ= Ġif Ġ( u Odd ) Ġv Ġelse Ġu ĊĠĠĠĠĠĠĠ Ġvar Ġt sign Ġ= Ġif Ġ( u Odd ) Ġ- 1 Ġelse Ġ 1 ĊĠĠĠĠĠĠĠ Ġvar Ġlb : ĠInt ĊĠĠĠĠĠĠĠ Ġwhile Ġ( t . lowest Set Bit . also Ġ{ Ġlb Ġ= Ġit Ġ} Ġ>= Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġsteps ĠB 3 Ġand ĠB 4 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġt . right Shift ( lb ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġstep ĠB 5 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( t sign Ġ> Ġ 0 ) Ġu Ġ= Ġt Ġelse Ġv Ġ= Ġt ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠSpecial Ġcase Ġone Ġword Ġnumbers ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( u . int Len Ġ< Ġ 2 Ġ&& Ġv . int Len Ġ< Ġ 2 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġx Ġ= Ġu . value [ u . offset ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġy Ġ= Ġv . value [ v . offset ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġx Ġ= Ġbinary G cd ( x , Ġy ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġr . value [ 0 ] Ġ= Ġx ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġr . int Len Ġ= Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġr . offset Ġ= Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( k Ġ> Ġ 0 ) Ġr . left Shift ( k ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġr ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġstep ĠB 6 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( u . difference ( v ). also Ġ{ Ġt sign Ġ= Ġit Ġ} Ġ== Ġ 0 ) Ġbreak ĊĠĠĠĠĠĠĠĠĠĠĠ Ġt Ġ= Ġif Ġ( t sign Ġ>= Ġ 0 ) Ġu Ġelse Ġv ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġif Ġ( k Ġ> Ġ 0 ) Ġu . left Shift ( k ) ĊĠĠĠĠĠĠĠ Ġreturn Ġu ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠReturns Ġthe Ġmod Inverse Ġof Ġthis Ġmod Ġp . ĠThis Ġand Ġp Ġare Ġnot Ġaffected Ġby ĊĠĠĠĠ Ġ* Ġthe Ġoperation . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġ@ Experimental Std lib Api ĊĠĠĠ Ġfun Ġmutable Mod Inverse ( p : ĠMutable BigInteger ): ĠMutable BigInteger Ġ{ ĊĠĠĠĠĠĠĠ Ġ// ĠMod ulus Ġis Ġodd , Ġuse ĠSch ro e pp el 's Ġalgorithm ĊĠĠĠĠĠĠĠ Ġif Ġ( p . is Odd ) Ġreturn Ġmod Inverse ( p ) ĊĊĠĠĠĠĠĠĠ Ġ// ĠBase Ġand Ġmod ulus Ġare Ġeven , Ġthrow Ġexception ĊĠĠĠĠĠĠĠ Ġif Ġ( is Even ) Ġthrow ĠArithmetic Exception (" BigInteger Ġnot Ġinvert ible .") ĊĊĠĠĠĠĠĠĠ Ġ// ĠGet Ġeven Ġpart Ġof Ġmod ulus Ġexpressed Ġas Ġa Ġpower Ġof Ġ 2 ĊĠĠĠĠĠĠĠ Ġval Ġpowers Of 2 Ġ= Ġp . lowest Set Bit ĊĊĠĠĠĠĠĠĠ Ġ// ĠConstruct Ġodd Ġpart Ġof Ġmod ulus ĊĠĠĠĠĠĠĠ Ġval Ġodd Mod Ġ= ĠMutable BigInteger ( p ) ĊĠĠĠĠĠĠĠ Ġodd Mod . right Shift ( pow ers Of 2 ) ĊĠĠĠĠĠĠĠ Ġif Ġ( odd Mod . is One ) Ġreturn Ġmod Inverse MP 2 ( pow ers Of 2 ) ĊĊĠĠĠĠĠĠĠ Ġ// ĠCalculate Ġ 1 / a Ġmod Ġodd Mod ĊĠĠĠĠĠĠĠ Ġval Ġodd Part Ġ= Ġmod Inverse ( odd Mod ) ĊĊĠĠĠĠĠĠĠ Ġ// ĠCalculate Ġ 1 / a Ġmod Ġeven Mod ĊĠĠĠĠĠĠĠ Ġval Ġeven Part Ġ= Ġmod Inverse MP 2 ( pow ers Of 2 ) ĊĊĠĠĠĠĠĠĠ Ġ// ĠCombine Ġthe Ġresults Ġusing ĠChinese ĠRem ain der ĠThe orem ĊĠĠĠĠĠĠĠ Ġval Ġy 1 Ġ= Ġmod Inverse BP 2 ( odd Mod , Ġpowers Of 2 ) ĊĠĠĠĠĠĠĠ Ġval Ġy 2 : ĠMutable BigInteger Ġ= Ġodd Mod . mod Inverse MP 2 ( pow ers Of 2 ) ĊĠĠĠĠĠĠĠ Ġval Ġtemp 1 Ġ= ĠMutable BigInteger () ĊĠĠĠĠĠĠĠ Ġval Ġtemp 2 Ġ= ĠMutable BigInteger () ĊĠĠĠĠĠĠĠ Ġval Ġresult Ġ= ĠMutable BigInteger () ĊĠĠĠĠĠĠĠ Ġodd Part . left Shift ( pow ers Of 2 ) ĊĠĠĠĠĠĠĠ Ġodd Part . multiply ( y 1 , Ġresult ) ĊĠĠĠĠĠĠĠ Ġeven Part . multiply ( odd Mod , Ġtemp 1 ) ĊĠĠĠĠĠĠĠ Ġtemp 1 . multiply ( y 2 , Ġtemp 2 ) ĊĠĠĠĠĠĠĠ Ġresult . add ( temp 2 ) ĊĠĠĠĠĠĠĠ Ġreturn Ġresult . divide ( p , Ġtemp 1 ) !! ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/* ĊĠĠĠĠ Ġ* ĠCalculate Ġthe Ġmultip lic ative Ġinverse Ġof Ġthis Ġmod Ġ 2 ^ k . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġ@ Experimental Std lib Api ĊĠĠĠ Ġfun Ġmod Inverse MP 2 ( k : ĠInt ): ĠMutable BigInteger Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( is Even ) Ġthrow ĠArithmetic Exception (" Non - invert ible . Ġ( G CD Ġ!= Ġ 1 )") ĊĠĠĠĠĠĠĠ Ġif Ġ( k Ġ> Ġ 6 4 ) Ġreturn Ġeu cl id Mod Inverse ( k ) ĊĠĠĠĠĠĠĠ Ġvar Ġt Ġ= Ġinverse Mod 3 2 ( value [ offset Ġ+ Ġint Len Ġ- Ġ 1 ]) ĊĠĠĠĠĠĠĠ Ġif Ġ( k Ġ< Ġ 3 3 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġt Ġ= Ġif Ġ( k Ġ== Ġ 3 2 ) Ġt Ġelse Ġt Ġand Ġ( 1 Ġshl Ġk ) Ġ- Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn ĠMutable BigInteger ( t ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġvar Ġp Long Ġ= Ġ( value [ offset Ġ+ Ġint Len Ġ- Ġ 1 ]. to Long () Ġand ĠBigInteger . LONG _ MASK ) ĊĠĠĠĠĠĠĠ Ġif Ġ( int Len Ġ> Ġ 1 ) Ġp Long Ġ= Ġp Long Ġor Ġ( value [ offset Ġ+ Ġint Len Ġ- Ġ 2 ]. to Long () Ġshl Ġ 3 2 ) ĊĠĠĠĠĠĠĠ Ġvar Ġt Long Ġ= Ġ( t . to Long () Ġand ĠBigInteger . LONG _ MASK ) ĊĠĠĠĠĠĠĠ Ġt Long Ġ= Ġt Long Ġ* Ġ( 2 Ġ- Ġp Long Ġ* Ġt Long ) Ġ// Ġ 1 Ġmore ĠNew ton Ġiter Ġstep ĊĠĠĠĠĠĠĠ Ġt Long Ġ= Ġif Ġ( k Ġ== Ġ 6 4 ) Ġt Long Ġelse Ġt Long Ġand Ġ( 1 L Ġshl Ġk ) Ġ- Ġ 1 ĊĠĠĠĠĠĠĠ Ġval Ġresult Ġ= ĠMutable BigInteger ( IntArray ( 2 )) ĊĠĠĠĠĠĠĠ Ġresult . value [ 0 ] Ġ= Ġ( t Long Ġ ush r Ġ 3 2 ). toInt () ĊĠĠĠĠĠĠĠ Ġresult . value [ 1 ] Ġ= Ġt Long . toInt () ĊĠĠĠĠĠĠĠ Ġresult . int Len Ġ= Ġ 2 ĊĠĠĠĠĠĠĠ Ġresult . normalize () ĊĠĠĠĠĠĠĠ Ġreturn Ġresult ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠCalculate Ġthe Ġmultip lic ative Ġinverse Ġof Ġthis Ġmodulo Ġmod , Ġwhere Ġthe Ġmod ĊĠĠĠĠ Ġ* Ġargument Ġis Ġodd . Ġ ĠThis Ġand Ġmod Ġare Ġnot Ġchanged Ġby Ġthe Ġcalculation . ĊĠĠĠĠ Ġ* ĊĠĠĠĠ Ġ* ĠThis Ġmethod Ġimplements Ġan Ġalgorithm Ġdue Ġto ĠRichard ĠSch ro e pp el , Ġthat Ġuses ĊĠĠĠĠ Ġ* Ġthe Ġsame Ġintermediate Ġrepresentation Ġas ĠMont gom ery ĠRed uction ĊĠĠĠĠ Ġ* Ġ(" Mont gom ery ĠForm "). Ġ ĠThe Ġalgorithm Ġis Ġdescribed Ġin Ġan Ġun published ĊĠĠĠĠ Ġ* Ġman us cript Ġent itled Ġ" Fast ĠMod ular ĠRe ci pro cal s ." ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġ@ Experimental Std lib Api ĊĠĠĠ Ġprivate Ġfun Ġmod Inverse ( mod : ĠMutable BigInteger ): ĠMutable BigInteger Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġp Ġ= ĠMutable BigInteger ( mod ) ĊĠĠĠĠĠĠĠ Ġvar Ġf Ġ= ĠMutable BigInteger ( this ) ĊĠĠĠĠĠĠĠ Ġvar Ġg Ġ= ĠMutable BigInteger ( p ) ĊĠĠĠĠĠĠĠ Ġvar Ġc Ġ= ĠSigned Mutable BigInteger ( 1 ) ĊĠĠĠĠĠĠĠ Ġvar Ġd Ġ= ĠSigned Mutable BigInteger () ĊĠĠĠĠĠĠĠ Ġvar Ġtemp : ĠMutable BigInteger ? ĊĠĠĠĠĠĠĠ Ġvar Ġs Temp : ĠSigned Mutable BigInteger ? ĊĠĠĠĠĠĠĠ Ġvar Ġk Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġ// ĠRight Ġshift Ġf Ġk Ġtimes Ġuntil Ġodd , Ġleft Ġshift Ġd Ġk Ġtimes ĊĠĠĠĠĠĠĠ Ġif Ġ( f . is Even ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġtrailing Z eros Ġ= Ġf . lowest Set Bit ĊĠĠĠĠĠĠĠĠĠĠĠ Ġf . right Shift ( trailing Z eros ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġd . left Shift ( trailing Z eros ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġk Ġ= Ġtrailing Z eros ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġ// ĠThe ĠAl most ĠIn verse ĠAlgorithm ĊĠĠĠĠĠĠĠ Ġwhile Ġ(! f . is One ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠIf Ġgcd ( f , Ġg ) Ġ!= Ġ 1 , Ġnumber Ġis Ġnot Ġinvert ible Ġmodulo Ġmod ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( f . is Zero ) Ġthrow ĠArithmetic Exception (" BigInteger Ġnot Ġinvert ible .") ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠIf Ġf Ġ< Ġg Ġexchange Ġf , Ġg Ġand Ġc , Ġd ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( f . compare ( g ) Ġ< Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġtemp Ġ= Ġf ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġf Ġ= Ġg ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġg Ġ= Ġtemp ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġs Temp Ġ= Ġd ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġd Ġ= Ġc ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġc Ġ= Ġs Temp ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠIf Ġf Ġ== Ġg Ġ( mod Ġ 4 ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( f . value [ f . offset Ġ+ Ġf . int Len Ġ- Ġ 1 ] Ġxor ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġg . value [ g . offset Ġ+ Ġg . int Len Ġ- Ġ 1 ] Ġand Ġ 3 Ġ== Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġf . subtract ( g ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġc . signed Subtract ( d ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ Ġ// ĠIf Ġf Ġ!= Ġg Ġ( mod Ġ 4 ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġf . add ( g ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġc . signed Add ( d ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠRight Ġshift Ġf Ġk Ġtimes Ġuntil Ġodd , Ġleft Ġshift Ġd Ġk Ġtimes ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġtrailing Z eros Ġ= Ġf . lowest Set Bit ĊĠĠĠĠĠĠĠĠĠĠĠ Ġf . right Shift ( trailing Z eros ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġd . left Shift ( trailing Z eros ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġk Ġ+= Ġtrailing Z eros ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġif Ġ( c . compare ( p ) Ġ>= Ġ 0 ) Ġ{ Ġ// Ġc Ġhas Ġa Ġlarger Ġmagnitude Ġthan Ġp ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġremainder Ġ= Ġc . divide ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġp , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠMutable BigInteger ()) !! ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠThe Ġprevious Ġline Ġignores Ġthe Ġsign Ġso Ġwe Ġcopy Ġthe Ġdata Ġback ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġinto Ġc Ġwhich Ġwill Ġrestore Ġthe Ġsign Ġas Ġneeded Ġ( and Ġconverts ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġit Ġback Ġto Ġa ĠSigned Mutable BigInteger ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġc . copy Value ( remainder ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġif Ġ( c . sign Ġ< Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġc . signed Add ( p ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġfix up ( c , Ġp , Ġk ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ/** ĊĠĠĠĠ Ġ* ĠUses Ġthe Ġextended ĠE uclidean Ġalgorithm Ġto Ġcompute Ġthe Ġmod Inverse Ġof Ġbase ĊĠĠĠĠ Ġ* Ġmod Ġa Ġmod ulus Ġthat Ġis Ġa Ġpower Ġof Ġ 2 . ĠThe Ġmod ulus Ġis Ġ 2 ^ k . ĊĠĠĠĠ Ġ*/ ĊĠĠĠ Ġ@ Experimental Std lib Api ĊĠĠĠ Ġfun Ġeu cl id Mod Inverse ( k : ĠInt ): ĠMutable BigInteger Ġ{ ĊĠĠĠĠĠĠĠ Ġvar Ġb Ġ= ĠMutable BigInteger ( 1 ) ĊĠĠĠĠĠĠĠ Ġb . left Shift ( k ) ĊĠĠĠĠĠĠĠ Ġval Ġmod Ġ= ĠMutable BigInteger ( b ) ĊĠĠĠĠĠĠĠ Ġvar Ġa Ġ= ĠMutable BigInteger ( this ) ĊĠĠĠĠĠĠĠ Ġvar Ġq Ġ= ĠMutable BigInteger () ĊĠĠĠĠĠĠĠ Ġvar Ġr Ġ= Ġb . divide ( a , Ġq ) !! ĊĠĠĠĠĠĠĠ Ġvar Ġswap per : ĠMutable BigInteger ĊĠĠĠĠĠĠĠ Ġ// Ġswap Ġb Ġ& Ġr ĊĠĠĠĠĠĠĠ Ġb Ġ= Ġr ĊĠĠĠĠĠĠĠ Ġval Ġt 1 Ġ= ĠMutable BigInteger ( q ) ĊĠĠĠĠĠĠĠ Ġval Ġt 0 Ġ= ĠMutable BigInteger ( 1 ) ĊĠĠĠĠĠĠĠ Ġvar Ġtemp Ġ= ĠMutable BigInteger () ĊĠĠĠĠĠĠĠ Ġwhile Ġ(! b . is One ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġr Ġ= Ġa . divide ( b , Ġq ) !! ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( r . int Len Ġ== Ġ 0 ) Ġthrow ĠArithmetic Exception (" BigInteger Ġnot Ġinvert ible .") ĊĠĠĠĠĠĠĠĠĠĠĠ Ġswap per Ġ= Ġr ĊĠĠĠĠĠĠĠĠĠĠĠ Ġa Ġ= Ġswap per ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( q . int Len Ġ== Ġ 1 ) Ġt 1 . mul ( q . value [ q . offset ], Ġtemp ) Ġelse Ġq . multiply ( t 1 , Ġtemp ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġswap per Ġ= Ġq ĊĠĠĠĠĠĠĠĠĠĠĠ Ġq Ġ= Ġtemp ĊĠĠĠĠĠĠĠĠĠĠĠ Ġtemp Ġ= Ġswap per ĊĠĠĠĠĠĠĠĠĠĠĠ Ġt 0 . add ( q ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( a . is One ) Ġreturn Ġt 0 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġr Ġ= Ġb . divide ( a , Ġq ) !! ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( r . int Len Ġ== Ġ 0 ) Ġthrow ĠArithmetic Exception (" BigInteger Ġnot Ġinvert ible .") ĊĠĠĠĠĠĠĠĠĠĠĠ Ġb Ġ= Ġr ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( q . int Len Ġ== Ġ 1 ) Ġt 0 . mul ( q . value [ q . offset ], Ġtemp ) Ġelse Ġq . multiply ( t 0 , Ġtemp ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġswap per Ġ= Ġq ĊĠĠĠĠĠĠĠĠĠĠĠ Ġq Ġ= Ġtemp ĊĠĠĠĠĠĠĠĠĠĠĠ Ġtemp Ġ= Ġswap per ĊĠĠĠĠĠĠĠĠĠĠĠ Ġt 1 . add ( q ) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġmod . subtract ( t 1 ) ĊĠĠĠĠĠĠĠ Ġreturn Ġmod ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġcompanion Ġobject Ġ{ ĊĠĠĠĠĠĠĠ Ġ// ĠConstants ĊĠĠĠĠĠĠĠ Ġ/** ĊĠĠĠĠĠĠĠĠ Ġ* ĠMutable BigInteger Ġwith Ġone Ġelement Ġvalue Ġarray Ġwith Ġthe Ġvalue Ġ 1 . ĠUsed Ġby ĊĠĠĠĠĠĠĠĠ Ġ* ĠBigDecimal Ġdivide And Round Ġto Ġincrement Ġthe Ġquot ient . ĠUse Ġthis Ġconstant ĊĠĠĠĠĠĠĠĠ Ġ* Ġonly Ġwhen Ġthe Ġmethod Ġis Ġnot Ġgoing Ġto Ġmodify Ġthis Ġobject . ĊĠĠĠĠĠĠĠĠ Ġ*/ ĊĠĠĠĠĠĠĠ Ġval ĠONE : ĠMutable BigInteger Ġ= ĠMutable BigInteger ( 1 ) ĊĊĠĠĠĠĠĠĠ Ġ/** ĊĠĠĠĠĠĠĠĠ Ġ* ĠThe Ġminimum Ġ` int Len ` Ġfor Ġcancell ing Ġpowers Ġof Ġtwo Ġbefore ĊĠĠĠĠĠĠĠĠ Ġ* Ġdiv iding . ĊĠĠĠĠĠĠĠĠ Ġ* ĠIf Ġthe Ġnumber Ġof Ġints Ġis Ġless Ġthan Ġthis Ġthreshold , ĊĠĠĠĠĠĠĠĠ Ġ* Ġ` divide Kn uth ` Ġdoes Ġnot Ġeliminate Ġcommon Ġpowers Ġof Ġtwo Ġfrom ĊĠĠĠĠĠĠĠĠ Ġ* Ġthe Ġdiv id end Ġand Ġdivisor . ĊĠĠĠĠĠĠĠĠ Ġ*/ ĊĠĠĠĠĠĠĠ Ġconst Ġval ĠK N UTH _ PO W 2 _ THRESH _ LEN Ġ= Ġ 6 ĊĊĠĠĠĠĠĠĠ Ġ/** ĊĠĠĠĠĠĠĠĠ Ġ* ĠThe Ġminimum Ġnumber Ġof Ġtrailing Ġzero Ġints Ġfor Ġcancell ing Ġpowers Ġof Ġtwo ĊĠĠĠĠĠĠĠĠ Ġ* Ġbefore Ġdiv iding . ĊĠĠĠĠĠĠĠĠ Ġ* ĠIf Ġthe Ġdiv id end Ġand Ġdivisor Ġdon 't Ġshare Ġat Ġleast Ġthis Ġmany Ġzero Ġints ĊĠĠĠĠĠĠĠĠ Ġ* Ġat Ġthe Ġend , Ġ` divide Kn uth ` Ġdoes Ġnot Ġeliminate Ġcommon Ġpowers ĊĠĠĠĠĠĠĠĠ Ġ* Ġof Ġtwo Ġfrom Ġthe Ġdiv id end Ġand Ġdivisor . ĊĠĠĠĠĠĠĠĠ Ġ*/ ĊĠĠĠĠĠĠĠ Ġconst Ġval ĠK N UTH _ PO W 2 _ THRESH _ Z ER OS Ġ= Ġ 3 ĊĠĠĠĠĠĠĠ Ġprivate Ġfun Ġcopy And Shift ( ĊĠĠĠĠĠĠĠĠĠĠĠ Ġsrc : ĠInt Array , ĊĠĠĠĠĠĠĠĠĠĠĠ Ġsrc From : ĠInt , ĊĠĠĠĠĠĠĠĠĠĠĠ Ġsrc Len : ĠInt , ĊĠĠĠĠĠĠĠĠĠĠĠ Ġdst : ĠInt Array , ĊĠĠĠĠĠĠĠĠĠĠĠ Ġdst From : ĠInt , ĊĠĠĠĠĠĠĠĠĠĠĠ Ġshift : ĠInt ĊĠĠĠĠĠĠĠ Ġ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġsrc From Ġ= Ġsrc From ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġn 2 Ġ= Ġ 3 2 Ġ- Ġshift ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġc Ġ= Ġsrc [ src From ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 Ġuntil Ġsrc Len Ġ- Ġ 1 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġb Ġ= Ġc ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġc Ġ= Ġsrc [++ src From ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġdst [ dst From Ġ+ Ġi ] Ġ= Ġb Ġshl Ġshift Ġor Ġ( c Ġ ush r Ġn 2 ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġdst [ dst From Ġ+ Ġsrc Len Ġ- Ġ 1 ] Ġ= Ġc Ġshl Ġshift ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġ/** ĊĠĠĠĠĠĠĠĠ Ġ* ĠThis Ġmethod Ġdiv ides Ġa Ġlong Ġquantity Ġby Ġan Ġint Ġto Ġestimate ĊĠĠĠĠĠĠĠĠ Ġ* Ġq hat Ġfor Ġtwo Ġmulti Ġprecision Ġnumbers . ĠIt Ġis Ġused Ġwhen ĊĠĠĠĠĠĠĠĠ Ġ* Ġthe Ġsigned Ġvalue Ġof Ġn Ġis Ġless Ġthan Ġzero . ĊĠĠĠĠĠĠĠĠ Ġ* ĠReturns Ġlong Ġvalue Ġwhere Ġhigh Ġ 3 2 Ġbits Ġcontain Ġremainder Ġvalue Ġand ĊĠĠĠĠĠĠĠĠ Ġ* Ġlow Ġ 3 2 Ġbits Ġcontain Ġquot ient Ġvalue . ĊĠĠĠĠĠĠĠĠ Ġ*/ ĊĠĠĠĠĠĠĠ Ġfun Ġdiv Word ( n : ĠLong , Ġd : ĠInt ): ĠLong Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġd Long Ġ= Ġ( d . to Long () Ġand ĠBigInteger . LONG _ MASK ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġr : ĠLong ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġq : ĠLong ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( d Long Ġ== Ġ 1 L ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġq Ġ= Ġn . toInt (). to Long () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġr Ġ= Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġr Ġshl Ġ 3 2 Ġor Ġ( q Ġand ĠBigInteger . LONG _ MASK ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠAppro x imate Ġthe Ġquot ient Ġand Ġremainder ĊĠĠĠĠĠĠĠĠĠĠĠ Ġq Ġ= Ġ( n Ġ ush r Ġ 1 ) Ġ/ Ġ( d Long Ġ ush r Ġ 1 ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġr Ġ= Ġn Ġ- Ġq Ġ* Ġd Long ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠCorrect Ġthe Ġapproximation ĊĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ( r Ġ< Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġr Ġ+= Ġd Long ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġq -- ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ( r Ġ>= Ġd Long ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġr Ġ-= Ġd Long ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġq ++ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġn Ġ- Ġq * d long Ġ== Ġr Ġ&& Ġ 0 Ġ<= Ġr Ġ< d Long , Ġhence Ġwe 're Ġdone . ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġr Ġshl Ġ 3 2 Ġor Ġ( q Ġand ĠBigInteger . LONG _ MASK ) ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġ/** ĊĠĠĠĠĠĠĠĠ Ġ* ĠCalculate ĠG CD Ġof Ġa Ġand Ġb Ġinterpreted Ġas Ġunsigned Ġintegers . ĊĠĠĠĠĠĠĠĠ Ġ*/ ĊĠĠĠĠĠĠĠ Ġ@ Experimental Std lib Api ĊĠĠĠĠĠĠĠ Ġfun Ġbinary G cd ( a : ĠInt , Ġb : ĠInt ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġa Ġ= Ġa ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġb Ġ= Ġb ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( b Ġ== Ġ 0 ) Ġreturn Ġa ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( a Ġ== Ġ 0 ) Ġreturn Ġb ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠRight Ġshift Ġa Ġ& Ġb Ġtill Ġtheir Ġlast Ġbits Ġequal Ġto Ġ 1 . ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġa Z eros : ĠInt Ġ= Ġa . count Trailing Zero Bits () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġb Z eros : ĠInt Ġ= Ġb . count Trailing Zero Bits () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġa Ġ= Ġa Ġ ush r Ġa Z eros ĊĠĠĠĠĠĠĠĠĠĠĠ Ġb Ġ= Ġb Ġ ush r Ġb Z eros ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġt Ġ= Ġif Ġ( a Z eros Ġ< Ġb Z eros ) Ġa Z eros Ġelse Ġb Z eros ĊĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ( a Ġ!= Ġb ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( a Ġ+ Ġ- 0 x 8 0 0 0 0 0 0 0 Ġ> Ġb Ġ+ Ġ- 0 x 8 0 0 0 0 0 0 0 ) Ġ{ Ġ Ġ// Ġa Ġ> Ġb Ġas Ġunsigned ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġa Ġ-= Ġb ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġa Ġ= Ġa Ġ ush r Ġa . count Trailing Zero Bits () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġb Ġ-= Ġa ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġb Ġ= Ġb Ġ ush r Ġb . count Trailing Zero Bits () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġa Ġshl Ġt ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġ/** ĊĠĠĠĠĠĠĠĠ Ġ* ĠReturns Ġthe Ġmultip lic ative Ġinverse Ġof Ġval Ġmod Ġ 2 ^ 3 2 . Ġ ĠAss umes Ġval Ġis Ġodd . ĊĠĠĠĠĠĠĠĠ Ġ*/ ĊĠĠĠĠĠĠĠ Ġfun Ġinverse Mod 3 2 (` val `: ĠInt ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠNew ton 's Ġiteration ! ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġt Ġ= Ġ` val ` ĊĠĠĠĠĠĠĠĠĠĠĠ Ġt Ġ*= Ġ 2 Ġ- Ġ` val ` Ġ* Ġt ĊĠĠĠĠĠĠĠĠĠĠĠ Ġt Ġ*= Ġ 2 Ġ- Ġ` val ` Ġ* Ġt ĊĠĠĠĠĠĠĠĠĠĠĠ Ġt Ġ*= Ġ 2 Ġ- Ġ` val ` Ġ* Ġt ĊĠĠĠĠĠĠĠĠĠĠĠ Ġt Ġ*= Ġ 2 Ġ- Ġ` val ` Ġ* Ġt ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġt ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġ/** ĊĠĠĠĠĠĠĠĠ Ġ* ĠReturns Ġthe Ġmultip lic ative Ġinverse Ġof Ġval Ġmod Ġ 2 ^ 6 4 . Ġ ĠAss umes Ġval Ġis Ġodd . ĊĠĠĠĠĠĠĠĠ Ġ*/ ĊĠĠĠĠĠĠĠ Ġfun Ġinverse Mod 6 4 (` val `: ĠLong ): ĠLong Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠNew ton 's Ġiteration ! ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġt Ġ= Ġ` val ` ĊĠĠĠĠĠĠĠĠĠĠĠ Ġt Ġ*= Ġ 2 Ġ- Ġ` val ` Ġ* Ġt ĊĠĠĠĠĠĠĠĠĠĠĠ Ġt Ġ*= Ġ 2 Ġ- Ġ` val ` Ġ* Ġt ĊĠĠĠĠĠĠĠĠĠĠĠ Ġt Ġ*= Ġ 2 Ġ- Ġ` val ` Ġ* Ġt ĊĠĠĠĠĠĠĠĠĠĠĠ Ġt Ġ*= Ġ 2 Ġ- Ġ` val ` Ġ* Ġt ĊĠĠĠĠĠĠĠĠĠĠĠ Ġt Ġ*= Ġ 2 Ġ- Ġ` val ` Ġ* Ġt ĊĠĠĠĠĠĠĠĠĠĠĠ Ġassert ( t Ġ* Ġ` val ` Ġ== Ġ 1 L ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġt ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġ/** ĊĠĠĠĠĠĠĠĠ Ġ* ĠCalculate Ġthe Ġmultip lic ative Ġinverse Ġof Ġ 2 ^ k Ġmod Ġmod , Ġwhere Ġmod Ġis Ġodd . ĊĠĠĠĠĠĠĠĠ Ġ*/ ĊĠĠĠĠĠĠĠ Ġ@ Experimental Std lib Api ĊĠĠĠĠĠĠĠ Ġfun Ġmod Inverse BP 2 ( mod : ĠMutable BigInteger , Ġk : ĠInt ): ĠMutable BigInteger Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠCopy Ġthe Ġmod Ġto Ġprotect Ġoriginal ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġfix up ( ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠMutable BigInteger ( 1 ), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠMutable BigInteger ( mod ), ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġk ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ) ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġ/** ĊĠĠĠĠĠĠĠĠ Ġ* ĠThe ĠFix up ĠAlgorithm ĊĠĠĠĠĠĠĠĠ Ġ* ĠCalculates ĠX Ġsuch Ġthat ĠX Ġ= ĠC Ġ* Ġ 2 ^ (- k ) Ġ( mod ĠP ) ĊĠĠĠĠĠĠĠĠ Ġ* ĠAss umes ĠC < P Ġand ĠP Ġis Ġodd . ></ P > ĊĠĠĠĠĠĠĠĠ Ġ*/ ĊĠĠĠĠĠĠĠ Ġ@ Experimental Std lib Api ĊĠĠĠĠĠĠĠ Ġfun Ġfix up ( ĊĠĠĠĠĠĠĠĠĠĠĠ Ġc : ĠMutable BigInteger , Ġp : ĠMutable BigInteger , ĊĠĠĠĠĠĠĠĠĠĠĠ Ġk : ĠInt ĊĠĠĠĠĠĠĠ Ġ): ĠMutable BigInteger Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġc Ġ= Ġc ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġtemp Ġ= ĠMutable BigInteger () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠSet Ġr Ġto Ġthe Ġmultip lic ative Ġinverse Ġof Ġp Ġmod Ġ 2 ^ 3 2 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġr Ġ= Ġ- inverse Mod 3 2 ( p . value [ p . offset Ġ+ Ġp . int Len Ġ- Ġ 1 ]) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġi Ġ= Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġnum Words Ġ= Ġk Ġshr Ġ 5 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ( i Ġ< Ġnum Words ) Ġ{ ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠV Ġ= ĠR Ġ* Ġc Ġ( mod Ġ 2 ^ j ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġv Ġ= Ġr Ġ* Ġc . value [ c . offset Ġ+ Ġc . int Len Ġ- Ġ 1 ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġc Ġ= Ġc Ġ+ Ġ( v Ġ* Ġp ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġp . mul ( v , Ġtemp ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġc . add ( temp ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġc Ġ= Ġc Ġ/ Ġ 2 ^ j ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġc . int Len -- ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġi ++ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġnum Bits Ġ= Ġk Ġand Ġ 0 x 1 f ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( num Bits Ġ!= Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠV Ġ= ĠR Ġ* Ġc Ġ( mod Ġ 2 ^ j ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġv Ġ= Ġr Ġ* Ġc . value [ c . offset Ġ+ Ġc . int Len Ġ- Ġ 1 ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġv Ġ= Ġv Ġand Ġ( 1 Ġshl Ġnum Bits ) Ġ- Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġc Ġ= Ġc Ġ+ Ġ( v Ġ* Ġp ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġp . mul ( v , Ġtemp ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġc . add ( temp ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġc Ġ= Ġc Ġ/ Ġ 2 ^ j ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġc . right Shift ( num Bits ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠIn Ġtheory , Ġc Ġmay Ġbe Ġgreater Ġthan Ġp Ġat Ġthis Ġpoint Ġ( Very Ġrare !) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( c . compare ( p ) Ġ>= Ġ 0 ) Ġc Ġ= Ġc . divide ( p , ĠMutable BigInteger ()) !! ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġc ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} Ċ }