11 Big Integers
\(\newcommand{\footnotename}{footnote}\)
\(\def \LWRfootnote {1}\)
\(\newcommand {\footnote }[2][\LWRfootnote ]{{}^{\mathrm {#1}}}\)
\(\newcommand {\footnotemark }[1][\LWRfootnote ]{{}^{\mathrm {#1}}}\)
\(\let \LWRorighspace \hspace \)
\(\renewcommand {\hspace }{\ifstar \LWRorighspace \LWRorighspace }\)
\(\newcommand {\TextOrMath }[2]{#2}\)
\(\newcommand {\mathnormal }[1]{{#1}}\)
\(\newcommand \ensuremath [1]{#1}\)
\(\newcommand {\LWRframebox }[2][]{\fbox {#2}} \newcommand {\framebox }[1][]{\LWRframebox } \)
\(\newcommand {\setlength }[2]{}\)
\(\newcommand {\addtolength }[2]{}\)
\(\newcommand {\setcounter }[2]{}\)
\(\newcommand {\addtocounter }[2]{}\)
\(\newcommand {\arabic }[1]{}\)
\(\newcommand {\number }[1]{}\)
\(\newcommand {\noalign }[1]{\text {#1}\notag \\}\)
\(\newcommand {\cline }[1]{}\)
\(\newcommand {\directlua }[1]{\text {(directlua)}}\)
\(\newcommand {\luatexdirectlua }[1]{\text {(directlua)}}\)
\(\newcommand {\protect }{}\)
\(\def \LWRabsorbnumber #1 {}\)
\(\def \LWRabsorbquotenumber "#1 {}\)
\(\newcommand {\LWRabsorboption }[1][]{}\)
\(\newcommand {\LWRabsorbtwooptions }[1][]{\LWRabsorboption }\)
\(\def \mathchar {\ifnextchar "\LWRabsorbquotenumber \LWRabsorbnumber }\)
\(\def \mathcode #1={\mathchar }\)
\(\let \delcode \mathcode \)
\(\let \delimiter \mathchar \)
\(\def \oe {\unicode {x0153}}\)
\(\def \OE {\unicode {x0152}}\)
\(\def \ae {\unicode {x00E6}}\)
\(\def \AE {\unicode {x00C6}}\)
\(\def \aa {\unicode {x00E5}}\)
\(\def \AA {\unicode {x00C5}}\)
\(\def \o {\unicode {x00F8}}\)
\(\def \O {\unicode {x00D8}}\)
\(\def \l {\unicode {x0142}}\)
\(\def \L {\unicode {x0141}}\)
\(\def \ss {\unicode {x00DF}}\)
\(\def \SS {\unicode {x1E9E}}\)
\(\def \dag {\unicode {x2020}}\)
\(\def \ddag {\unicode {x2021}}\)
\(\def \P {\unicode {x00B6}}\)
\(\def \copyright {\unicode {x00A9}}\)
\(\def \pounds {\unicode {x00A3}}\)
\(\let \LWRref \ref \)
\(\renewcommand {\ref }{\ifstar \LWRref \LWRref }\)
\( \newcommand {\multicolumn }[3]{#3}\)
\(\require {textcomp}\)
\(\newcommand {\intertext }[1]{\text {#1}\notag \\}\)
\(\let \Hat \hat \)
\(\let \Check \check \)
\(\let \Tilde \tilde \)
\(\let \Acute \acute \)
\(\let \Grave \grave \)
\(\let \Dot \dot \)
\(\let \Ddot \ddot \)
\(\let \Breve \breve \)
\(\let \Bar \bar \)
\(\let \Vec \vec \)
\(\renewcommand {\vec }{\boldsymbol }\)
\(\newcommand {\Edge }{\ensuremath {\,\textemdash \,}}\)
\(\newcommand \Const [1]{\text {\textsf {#1}}}\)
\(\DeclareMathOperator {\lerp }{lerp}\)
\(\DeclareMathOperator {\bitlen }{bitlen}\)
\(\DeclareMathOperator {\sign }{sign}\)
\(\newcommand {\I }{\mathrm {i}}\)
\(\newcommand \AND {\mathbin {\&}}\)
\(\newcommand \OR {\mathbin {|}}\)
\(\newcommand \XOR {\mathbin {{}^{\wedge }}}\)
\(\newcommand \shl {\ll }\)
\(\newcommand \shr {\ggg }\)
\(\newcommand \asr {\gg }\)
\(\newcommand \NOT {\ensuremath {\mathord {\sim }}}\)
\(\newcommand {\isep }{\mathrel {{.}\,{.}}}\)
\(\newcommand {\Id }[1]{\mathit {#1}}\)
\(\newcommand {\const }[1]{\mathsf {#1}}\)
\(\newcommand {\algorithmname }[1]{\text {\textsc {#1}}}\)
\(\newcommand {\bits }[1]{\text {#1}}\)
\(\newcommand {\hexa }[1]{\mathtt {0x#1}}\)
\(\newcommand {\num }[1]{#1}\)
\(\newcommand {\qed }{\quad \square }\)
\(\newcommand {\idiv }[2]{\lfloor #1/#2\rfloor }\)
\(\newcommand \attribdot {\ensuremath {\mkern 1.5mu.\mkern 1.5mu}}\)
\(\newcommand \attribxr [2]{#1\attribdot \text {#2}}\)
\(\newcommand \attribir [2]{\Id {#1}\attribdot \text {#2}}\)
\(\newcommand \attribii [2]{\Id {#1}\attribdot \Id {#2}}\)
\(\newcommand \textsc [1]{#1}\)
\(\require {colortbl}\)
\(\let \LWRorigcolumncolor \columncolor \)
\(\renewcommand {\columncolor }[2][named]{\LWRorigcolumncolor [#1]{#2}\LWRabsorbtwooptions }\)
\(\let \LWRorigrowcolor \rowcolor \)
\(\renewcommand {\rowcolor }[2][named]{\LWRorigrowcolor [#1]{#2}\LWRabsorbtwooptions }\)
\(\let \LWRorigcellcolor \cellcolor \)
\(\renewcommand {\cellcolor }[2][named]{\LWRorigcellcolor [#1]{#2}\LWRabsorbtwooptions }\)
\(\newcommand {\tcbset }[1]{}\)
\(\newcommand {\tcbsetforeverylayer }[1]{}\)
\(\newcommand {\tcbox }[2][]{\boxed {\text {#2}}}\)
\(\newcommand {\tcboxfit }[2][]{\boxed {#2}}\)
\(\newcommand {\tcblower }{}\)
\(\newcommand {\tcbline }{}\)
\(\newcommand {\tcbtitle }{}\)
\(\newcommand {\tcbsubtitle [2][]{\mathrm {#2}}}\)
\(\newcommand {\tcboxmath }[2][]{\boxed {#2}}\)
\(\newcommand {\tcbhighmath }[2][]{\boxed {#2}}\)
\(\newcommand {\toprule }[1][]{\hline }\)
\(\let \midrule \toprule \)
\(\let \bottomrule \toprule \)
\(\def \LWRbooktabscmidruleparen (#1)#2{}\)
\(\newcommand {\LWRbooktabscmidrulenoparen }[1]{}\)
\(\newcommand {\cmidrule }[1][]{\ifnextchar (\LWRbooktabscmidruleparen \LWRbooktabscmidrulenoparen }\)
\(\newcommand {\morecmidrules }{}\)
\(\newcommand {\specialrule }[3]{\hline }\)
\(\newcommand {\addlinespace }[1][]{}\)
\(\newcommand {\LWRsubmultirow }[2][]{#2}\)
\(\newcommand {\LWRmultirow }[2][]{\LWRsubmultirow }\)
\(\newcommand {\multirow }[2][]{\LWRmultirow }\)
\(\newcommand {\mrowcell }{}\)
\(\newcommand {\mcolrowcell }{}\)
\(\newcommand {\STneed }[1]{}\)
\(\newcommand {\LWRldelimtwo }[1][]{\text {#1}~\LWRbigdelim }\)
\(\newcommand {\LWRldelimone }[2][]{\LWRldelimtwo }\)
\(\def \ldelim #1#2{\def \LWRbigdelim {#1}\LWRldelimone }\)
\(\newcommand {\LWRrdelimtwo }[1][]{\LWRbigdelim ~\text {#1}}\)
\(\newcommand {\LWRrdelimone }[2][]{\LWRrdelimtwo }\)
\(\def \rdelim #1#2{\def \LWRbigdelim {#1}\LWRrdelimone }\)
\(\let \symnormal \mathit \)
\(\let \symliteral \mathrm \)
\(\let \symbb \mathbb \)
\(\let \symbbit \mathbb \)
\(\let \symcal \mathcal \)
\(\let \symscr \mathscr \)
\(\let \symfrak \mathfrak \)
\(\let \symsfup \mathsf \)
\(\let \symsfit \mathit \)
\(\let \symbfsf \mathbf \)
\(\let \symbfup \mathbf \)
\(\newcommand {\symbfit }[1]{\boldsymbol {#1}}\)
\(\let \symbfcal \mathcal \)
\(\let \symbfscr \mathscr \)
\(\let \symbffrak \mathfrak \)
\(\let \symbfsfup \mathbf \)
\(\newcommand {\symbfsfit }[1]{\boldsymbol {#1}}\)
\(\let \symup \mathrm \)
\(\let \symbf \mathbf \)
\(\let \symit \mathit \)
\(\let \symsf \symsfit \)
\(\let \symtt \mathtt \)
\(\let \symbffrac \mathbffrac \)
\(\newcommand {\mathfence }[1]{\mathord {#1}}\)
\(\newcommand {\mathover }[1]{#1}\)
\(\newcommand {\mathunder }[1]{#1}\)
\(\newcommand {\mathaccent }[1]{#1}\)
\(\newcommand {\mathbotaccent }[1]{#1}\)
\(\newcommand {\mathalpha }[1]{\mathord {#1}}\)
\(\def\Alpha{\unicode{x1D6E2}}\)
\(\def\Beta{\unicode{x1D6E3}}\)
\(\def\Gamma{\unicode{x1D6E4}}\)
\(\def\Digamma{\mathit{\unicode{x03DC}}}\)
\(\def\Delta{\unicode{x1D6E5}}\)
\(\def\Epsilon{\unicode{x1D6E6}}\)
\(\def\Zeta{\unicode{x1D6E7}}\)
\(\def\Eta{\unicode{x1D6E8}}\)
\(\def\Theta{\unicode{x1D6E9}}\)
\(\def\Vartheta{\unicode{x1D6F3}}\)
\(\def\Iota{\unicode{x1D6EA}}\)
\(\def\Kappa{\unicode{x1D6EB}}\)
\(\def\Lambda{\unicode{x1D6EC}}\)
\(\def\Mu{\unicode{x1D6ED}}\)
\(\def\Nu{\unicode{x1D6EE}}\)
\(\def\Xi{\unicode{x1D6EF}}\)
\(\def\Omicron{\unicode{x1D6F0}}\)
\(\def\Pi{\unicode{x1D6F1}}\)
\(\def\Rho{\unicode{x1D6F2}}\)
\(\def\Sigma{\unicode{x1D6F4}}\)
\(\def\Tau{\unicode{x1D6F5}}\)
\(\def\Upsilon{\unicode{x1D6F6}}\)
\(\def\Phi{\unicode{x1D6F7}}\)
\(\def\Chi{\unicode{x1D6F8}}\)
\(\def\Psi{\unicode{x1D6F9}}\)
\(\def\Omega{\unicode{x1D6FA}}\)
\(\def\alpha{\unicode{x1D6FC}}\)
\(\def\beta{\unicode{x1D6FD}}\)
\(\def\varbeta{\unicode{x03D0}}\)
\(\def\gamma{\unicode{x1D6FE}}\)
\(\def\digamma{\mathit{\unicode{x03DD}}}\)
\(\def\delta{\unicode{x1D6FF}}\)
\(\def\epsilon{\unicode{x1D716}}\)
\(\def\varepsilon{\unicode{x1D700}}\)
\(\def\zeta{\unicode{x1D701}}\)
\(\def\eta{\unicode{x1D702}}\)
\(\def\theta{\unicode{x1D703}}\)
\(\def\vartheta{\unicode{x1D717}}\)
\(\def\iota{\unicode{x1D704}}\)
\(\def\kappa{\unicode{x1D705}}\)
\(\def\varkappa{\unicode{x1D718}}\)
\(\def\lambda{\unicode{x1D706}}\)
\(\def\mu{\unicode{x1D707}}\)
\(\def\nu{\unicode{x1D708}}\)
\(\def\xi{\unicode{x1D709}}\)
\(\def\omicron{\unicode{x1D70A}}\)
\(\def\pi{\unicode{x1D70B}}\)
\(\def\varpi{\unicode{x1D71B}}\)
\(\def\rho{\unicode{x1D70C}}\)
\(\def\varrho{\unicode{x1D71A}}\)
\(\def\sigma{\unicode{x1D70E}}\)
\(\def\varsigma{\unicode{x1D70D}}\)
\(\def\tau{\unicode{x1D70F}}\)
\(\def\upsilon{\unicode{x1D710}}\)
\(\def\phi{\unicode{x1D719}}\)
\(\def\varphi{\unicode{x1D711}}\)
\(\def\chi{\unicode{x1D712}}\)
\(\def\psi{\unicode{x1D713}}\)
\(\def\omega{\unicode{x1D714}}\)
\(\def\upAlpha{\unicode{x0391}}\)
\(\def\upBeta{\unicode{x0392}}\)
\(\def\upGamma{\unicode{x0393}}\)
\(\def\upDigamma{\unicode{x03DC}}\)
\(\def\upDelta{\unicode{x0394}}\)
\(\def\upEpsilon{\unicode{x0395}}\)
\(\def\upZeta{\unicode{x0396}}\)
\(\def\upEta{\unicode{x0397}}\)
\(\def\upTheta{\unicode{x0398}}\)
\(\def\upVartheta{\unicode{x03F4}}\)
\(\def\upIota{\unicode{x0399}}\)
\(\def\upKappa{\unicode{x039A}}\)
\(\def\upLambda{\unicode{x039B}}\)
\(\def\upMu{\unicode{x039C}}\)
\(\def\upNu{\unicode{x039D}}\)
\(\def\upXi{\unicode{x039E}}\)
\(\def\upOmicron{\unicode{x039F}}\)
\(\def\upPi{\unicode{x03A0}}\)
\(\def\upVarpi{\unicode{x03D6}}\)
\(\def\upRho{\unicode{x03A1}}\)
\(\def\upSigma{\unicode{x03A3}}\)
\(\def\upTau{\unicode{x03A4}}\)
\(\def\upUpsilon{\unicode{x03A5}}\)
\(\def\upPhi{\unicode{x03A6}}\)
\(\def\upChi{\unicode{x03A7}}\)
\(\def\upPsi{\unicode{x03A8}}\)
\(\def\upOmega{\unicode{x03A9}}\)
\(\def\itAlpha{\unicode{x1D6E2}}\)
\(\def\itBeta{\unicode{x1D6E3}}\)
\(\def\itGamma{\unicode{x1D6E4}}\)
\(\def\itDigamma{\mathit{\unicode{x03DC}}}\)
\(\def\itDelta{\unicode{x1D6E5}}\)
\(\def\itEpsilon{\unicode{x1D6E6}}\)
\(\def\itZeta{\unicode{x1D6E7}}\)
\(\def\itEta{\unicode{x1D6E8}}\)
\(\def\itTheta{\unicode{x1D6E9}}\)
\(\def\itVartheta{\unicode{x1D6F3}}\)
\(\def\itIota{\unicode{x1D6EA}}\)
\(\def\itKappa{\unicode{x1D6EB}}\)
\(\def\itLambda{\unicode{x1D6EC}}\)
\(\def\itMu{\unicode{x1D6ED}}\)
\(\def\itNu{\unicode{x1D6EE}}\)
\(\def\itXi{\unicode{x1D6EF}}\)
\(\def\itOmicron{\unicode{x1D6F0}}\)
\(\def\itPi{\unicode{x1D6F1}}\)
\(\def\itRho{\unicode{x1D6F2}}\)
\(\def\itSigma{\unicode{x1D6F4}}\)
\(\def\itTau{\unicode{x1D6F5}}\)
\(\def\itUpsilon{\unicode{x1D6F6}}\)
\(\def\itPhi{\unicode{x1D6F7}}\)
\(\def\itChi{\unicode{x1D6F8}}\)
\(\def\itPsi{\unicode{x1D6F9}}\)
\(\def\itOmega{\unicode{x1D6FA}}\)
\(\def\upalpha{\unicode{x03B1}}\)
\(\def\upbeta{\unicode{x03B2}}\)
\(\def\upvarbeta{\unicode{x03D0}}\)
\(\def\upgamma{\unicode{x03B3}}\)
\(\def\updigamma{\unicode{x03DD}}\)
\(\def\updelta{\unicode{x03B4}}\)
\(\def\upepsilon{\unicode{x03F5}}\)
\(\def\upvarepsilon{\unicode{x03B5}}\)
\(\def\upzeta{\unicode{x03B6}}\)
\(\def\upeta{\unicode{x03B7}}\)
\(\def\uptheta{\unicode{x03B8}}\)
\(\def\upvartheta{\unicode{x03D1}}\)
\(\def\upiota{\unicode{x03B9}}\)
\(\def\upkappa{\unicode{x03BA}}\)
\(\def\upvarkappa{\unicode{x03F0}}\)
\(\def\uplambda{\unicode{x03BB}}\)
\(\def\upmu{\unicode{x03BC}}\)
\(\def\upnu{\unicode{x03BD}}\)
\(\def\upxi{\unicode{x03BE}}\)
\(\def\upomicron{\unicode{x03BF}}\)
\(\def\uppi{\unicode{x03C0}}\)
\(\def\upvarpi{\unicode{x03D6}}\)
\(\def\uprho{\unicode{x03C1}}\)
\(\def\upvarrho{\unicode{x03F1}}\)
\(\def\upsigma{\unicode{x03C3}}\)
\(\def\upvarsigma{\unicode{x03C2}}\)
\(\def\uptau{\unicode{x03C4}}\)
\(\def\upupsilon{\unicode{x03C5}}\)
\(\def\upphi{\unicode{x03D5}}\)
\(\def\upvarphi{\unicode{x03C6}}\)
\(\def\upchi{\unicode{x03C7}}\)
\(\def\uppsi{\unicode{x03C8}}\)
\(\def\upomega{\unicode{x03C9}}\)
\(\def\italpha{\unicode{x1D6FC}}\)
\(\def\itbeta{\unicode{x1D6FD}}\)
\(\def\itvarbeta{\unicode{x03D0}}\)
\(\def\itgamma{\unicode{x1D6FE}}\)
\(\def\itdigamma{\mathit{\unicode{x03DD}}}\)
\(\def\itdelta{\unicode{x1D6FF}}\)
\(\def\itepsilon{\unicode{x1D716}}\)
\(\def\itvarepsilon{\unicode{x1D700}}\)
\(\def\itzeta{\unicode{x1D701}}\)
\(\def\iteta{\unicode{x1D702}}\)
\(\def\ittheta{\unicode{x1D703}}\)
\(\def\itvartheta{\unicode{x1D717}}\)
\(\def\itiota{\unicode{x1D704}}\)
\(\def\itkappa{\unicode{x1D705}}\)
\(\def\itvarkappa{\unicode{x1D718}}\)
\(\def\itlambda{\unicode{x1D706}}\)
\(\def\itmu{\unicode{x1D707}}\)
\(\def\itnu{\unicode{x1D708}}\)
\(\def\itxi{\unicode{x1D709}}\)
\(\def\itomicron{\unicode{x1D70A}}\)
\(\def\itpi{\unicode{x1D70B}}\)
\(\def\itvarpi{\unicode{x1D71B}}\)
\(\def\itrho{\unicode{x1D70C}}\)
\(\def\itvarrho{\unicode{x1D71A}}\)
\(\def\itsigma{\unicode{x1D70E}}\)
\(\def\itvarsigma{\unicode{x1D70D}}\)
\(\def\ittau{\unicode{x1D70F}}\)
\(\def\itupsilon{\unicode{x1D710}}\)
\(\def\itphi{\unicode{x1D719}}\)
\(\def\itvarphi{\unicode{x1D711}}\)
\(\def\itchi{\unicode{x1D712}}\)
\(\def\itpsi{\unicode{x1D713}}\)
\(\def\itomega{\unicode{x1D714}}\)
\(\let \lparen (\)
\(\let \rparen )\)
\(\newcommand {\cuberoot }[1]{\,{}^3\!\!\sqrt {#1}}\,\)
\(\newcommand {\fourthroot }[1]{\,{}^4\!\!\sqrt {#1}}\,\)
\(\newcommand {\longdivision }[1]{\mathord {\unicode {x027CC}#1}}\)
\(\newcommand {\mathcomma }{,}\)
\(\newcommand {\mathcolon }{:}\)
\(\newcommand {\mathsemicolon }{;}\)
\(\newcommand {\overbracket }[1]{\mathinner {\overline {\ulcorner {#1}\urcorner }}}\)
\(\newcommand {\underbracket }[1]{\mathinner {\underline {\llcorner {#1}\lrcorner }}}\)
\(\newcommand {\overbar }[1]{\mathord {#1\unicode {x00305}}}\)
\(\newcommand {\ovhook }[1]{\mathord {#1\unicode {x00309}}}\)
\(\newcommand {\ocirc }[1]{\mathord {#1\unicode {x0030A}}}\)
\(\newcommand {\candra }[1]{\mathord {#1\unicode {x00310}}}\)
\(\newcommand {\oturnedcomma }[1]{\mathord {#1\unicode {x00312}}}\)
\(\newcommand {\ocommatopright }[1]{\mathord {#1\unicode {x00315}}}\)
\(\newcommand {\droang }[1]{\mathord {#1\unicode {x0031A}}}\)
\(\newcommand {\leftharpoonaccent }[1]{\mathord {#1\unicode {x020D0}}}\)
\(\newcommand {\rightharpoonaccent }[1]{\mathord {#1\unicode {x020D1}}}\)
\(\newcommand {\vertoverlay }[1]{\mathord {#1\unicode {x020D2}}}\)
\(\newcommand {\leftarrowaccent }[1]{\mathord {#1\unicode {x020D0}}}\)
\(\newcommand {\annuity }[1]{\mathord {#1\unicode {x020E7}}}\)
\(\newcommand {\widebridgeabove }[1]{\mathord {#1\unicode {x020E9}}}\)
\(\newcommand {\asteraccent }[1]{\mathord {#1\unicode {x020F0}}}\)
\(\newcommand {\threeunderdot }[1]{\mathord {#1\unicode {x020E8}}}\)
\(\newcommand {\Bbbsum }{\mathop {\unicode {x2140}}\limits }\)
\(\newcommand {\oiint }{\mathop {\unicode {x222F}}\limits }\)
\(\newcommand {\oiiint }{\mathop {\unicode {x2230}}\limits }\)
\(\newcommand {\intclockwise }{\mathop {\unicode {x2231}}\limits }\)
\(\newcommand {\ointclockwise }{\mathop {\unicode {x2232}}\limits }\)
\(\newcommand {\ointctrclockwise }{\mathop {\unicode {x2233}}\limits }\)
\(\newcommand {\varointclockwise }{\mathop {\unicode {x2232}}\limits }\)
\(\newcommand {\leftouterjoin }{\mathop {\unicode {x27D5}}\limits }\)
\(\newcommand {\rightouterjoin }{\mathop {\unicode {x27D6}}\limits }\)
\(\newcommand {\fullouterjoin }{\mathop {\unicode {x27D7}}\limits }\)
\(\newcommand {\bigbot }{\mathop {\unicode {x27D8}}\limits }\)
\(\newcommand {\bigtop }{\mathop {\unicode {x27D9}}\limits }\)
\(\newcommand {\xsol }{\mathop {\unicode {x29F8}}\limits }\)
\(\newcommand {\xbsol }{\mathop {\unicode {x29F9}}\limits }\)
\(\newcommand {\bigcupdot }{\mathop {\unicode {x2A03}}\limits }\)
\(\newcommand {\bigsqcap }{\mathop {\unicode {x2A05}}\limits }\)
\(\newcommand {\conjquant }{\mathop {\unicode {x2A07}}\limits }\)
\(\newcommand {\disjquant }{\mathop {\unicode {x2A08}}\limits }\)
\(\newcommand {\bigtimes }{\mathop {\unicode {x2A09}}\limits }\)
\(\newcommand {\modtwosum }{\mathop {\unicode {x2A0A}}\limits }\)
\(\newcommand {\sumint }{\mathop {\unicode {x2A0B}}\limits }\)
\(\newcommand {\intbar }{\mathop {\unicode {x2A0D}}\limits }\)
\(\newcommand {\intBar }{\mathop {\unicode {x2A0E}}\limits }\)
\(\newcommand {\fint }{\mathop {\unicode {x2A0F}}\limits }\)
\(\newcommand {\cirfnint }{\mathop {\unicode {x2A10}}\limits }\)
\(\newcommand {\awint }{\mathop {\unicode {x2A11}}\limits }\)
\(\newcommand {\rppolint }{\mathop {\unicode {x2A12}}\limits }\)
\(\newcommand {\scpolint }{\mathop {\unicode {x2A13}}\limits }\)
\(\newcommand {\npolint }{\mathop {\unicode {x2A14}}\limits }\)
\(\newcommand {\pointint }{\mathop {\unicode {x2A15}}\limits }\)
\(\newcommand {\sqint }{\mathop {\unicode {x2A16}}\limits }\)
\(\newcommand {\intlarhk }{\mathop {\unicode {x2A17}}\limits }\)
\(\newcommand {\intx }{\mathop {\unicode {x2A18}}\limits }\)
\(\newcommand {\intcap }{\mathop {\unicode {x2A19}}\limits }\)
\(\newcommand {\intcup }{\mathop {\unicode {x2A1A}}\limits }\)
\(\newcommand {\upint }{\mathop {\unicode {x2A1B}}\limits }\)
\(\newcommand {\lowint }{\mathop {\unicode {x2A1C}}\limits }\)
\(\newcommand {\bigtriangleleft }{\mathop {\unicode {x2A1E}}\limits }\)
\(\newcommand {\zcmp }{\mathop {\unicode {x2A1F}}\limits }\)
\(\newcommand {\zpipe }{\mathop {\unicode {x2A20}}\limits }\)
\(\newcommand {\zproject }{\mathop {\unicode {x2A21}}\limits }\)
\(\newcommand {\biginterleave }{\mathop {\unicode {x2AFC}}\limits }\)
\(\newcommand {\bigtalloblong }{\mathop {\unicode {x2AFF}}\limits }\)
\(\newcommand {\arabicmaj }{\mathop {\unicode {x1EEF0}}\limits }\)
\(\newcommand {\arabichad }{\mathop {\unicode {x1EEF1}}\limits }\)
11.2 Comparison and Conversion¶
We just saw how to compare big integers for equality; but what about the remaining comparison operators \(<\), \(\le \), \(\ge \), and \(>\)? In Java, these operators are implemented using the Comparable interface, which defines a single method
compareTo():
interface Comparable<T> {
int compareTo(T value);
}
The compareTo() method implements a so-called three-way comparison, which means that combines the operators \(<\), \(=\), and \(>\) into a single operation. The return value is an integer that indicates how this is related to value:
-
• If \(\mathtt {this} < \mathtt {value}\) the return value is \(<0\).
-
• If \(\mathtt {this} = \mathtt {value}\) the return value is 0.
-
• If \(\mathtt {this} > \mathtt {value}\) the return value is \(>0\).
Similarly, the operators \(\le \) and \(\ge \) correspond to a return value that is \(\le 0\) or \(\ge 0\).
The easiest way to implement a three-way comparison of two numbers and is to compute their difference and return the sign of the result. (This follows directly from the definition above.) But for big integers we can usually determine the proper return value much more
quickly. First, if the two numbers differ in length, we immediately know that the numbers with more digits is the larger of the two. And if the two numbers have the same length, we can often find the larger one by comparing only the first few digits. For instance, 8451 is obviously larger than 849 because it
has one more digit, and we only need to examine the first two digits to establish that 8451 is smaller than 8591.
This leads us to the implementation of compareTo() shown in Listing 11.5, which first compares size and then
the digits themselves. If the two big integers differ in length, we perform a three-way comparison of their size fields using Integer.compare() and return the result. Otherwise, we use a
for loop to iterate over the digits, from most to least significant, to find the first pair that differs. These two digits are again compared using Integer.compare(). The last line in
compareTo() is only reached if both numbers have the same length and if all digits are equal. In this case the numbers are equal and we return 0.
Listing 11.5ch11 / BigNat
public int compareTo(BigNat v) {
if (size != v.size)
return Integer.compare(size, v.size);
for (int i = size - 1; i >= 0; i--) {
int ui = digit(i), vi = v.digit(i);
if (ui != vi)
return Integer.compare(ui, vi);
}
return 0;
}
The methods we have implemented so far are independent of the number system’s base and treat the digits as a plain array of integers, but most of the remaining operations on big integers need to take the radix into account. Listing 11.6 defines three constants that will simplify the task of working with base-\(2^{31}\) digits. The first is BASE, which simply holds the radix \(2^{31}\). Since this number is too large for a regular int, we define
the variable as a long integer and compute its value using a bit shift. The second constant is DIGIT_BITS, which holds the number of bits required to store each digit, in our
case 31. And the last constant DIGIT_MASK is a bit mask that selects the lowest 31 bits of a long integer. We use this bit mask mainly to
replace the remainder operation x % BASE with the faster bit operation x & DIGIT_MASK.1
Listing 11.6ch11 / BigNat
static final long BASE = 1L << 31;
static final int DIGIT_BITS = 31;
static final long DIGIT_MASK = 0x7fffffff;
To see these constants in action, recall the fundamental relationship between a number \(N\) and its digits \(d_n,\dots ,d_0\):
\(\seteqnumber{0}{11.}{2}\)
\begin{align*}
N = d_{n}\cdot \mathtt {BASE}^{n} + d_{n-1}\cdot \mathtt {BASE}^{n-1} + \cdots + d_{0}\cdot \mathtt {BASE}^0
\end{align*}
Since BASE is a power of \(2\), we can rewrite this formula using bit shifts instead of multiplications, which gives us
\(\seteqnumber{0}{11.}{2}\)
\begin{align*}
N &= (d_{n}\shl \mathtt {DIGIT\_BITS}\cdot n)\\ &\qquad + (d_{n-1}\shl \mathtt {DIGIT\_BITS}\cdot (n-1))\\ &\qquad + \cdots \\ &\qquad + (d_{0}\shl 0).
\end{align*}
What this formula tells us is that the binary representation of \(N\) can be constructed by concatenating all \(31\)-bit digits into one long string of bits. Conversely, if we know the binary representation of \(N\), we can compute the base-\(2^{31}\) digits by splitting the number into \(31\)-bit
chunks. The \(k\)th digit can be obtained by shifting \(N\)’s bits \(k\cdot \mathtt {DIGIT\_BITS}\) bits to the right and isolating the lowest 31 bits:
\(\seteqnumber{0}{11.}{2}\)
\begin{equation*}
d_k = (N\shr k\cdot \mathtt {DIGIT\_BITS}) \AND \mathtt {DIGIT\_MASK}.
\end{equation*}
A simple application of this idea is the factory method fromUnsignedLong() shown in Listing 11.7, which constructs a
BigNat from a given 64-bit integer by splitting it into three parts of 31 bits each. This method is primarily useful for constructing small integers such as the three constants ZERO, ONE, and TEN shown in the same listing. With these constants, code that needs to refer to the number 0 can simply use BigNat.ZERO
without having to construct a new instance of BigNat. Notice that it is safe to define these numbers as public constants only because BigNat is immutable and their values cannot be
changed by other parts of the program.
Listing 11.7ch11 / BigNat
// Create a new instance from the bit pattern of 'v'.
public static BigNat fromUnsignedLong(long v) {
return new BigNat(new int[]{
(int) (v & DIGIT_MASK),
(int) ((v >>> DIGIT_BITS) & DIGIT_MASK),
(int) ((v >>> 2 * DIGIT_BITS) & DIGIT_MASK)
});
}
public static final BigNat
ZERO = fromUnsignedLong(0),
ONE = fromUnsignedLong(1),
TEN = fromUnsignedLong(10);
For the opposite conversion, from big integers to integers of type long, we take three digits and reassemble them into a 64-bit integer (Listing 11.8). The toUnsignedLong() method doesn’t check whether the result fits into a long integer and simply returns the number’s lowest 64 bits; this mirrors the way type casts, say, from long to int, work in Java. We will discuss a similar method with appropriate error handling when we discuss signed big integers in Section 11.8.
Listing 11.8ch11 / BigNat
// Return the lowest 64 bits of the big integer.
public long toUnsignedLong() {
return ((long) digitOr0(2) << 2 * DIGIT_BITS)
| ((long) digitOr0(1) << DIGIT_BITS)
| (long) digitOr0(0);
}