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.7 Radix Conversion¶
So far we have only defined a few primitive methods for creating new instances of BigNat: two private constructors that take arrays of base-\(2^{31}\) digits (Listing 11.3) and the fromUnsignedLong() method, which converts a long integer to a BigNat (Listing 11.7). In this section we will discuss how to initialize big
integers using a string of decimal digits:
BigNat pi = BigNat.fromDecimal(
"3141592653589793238462643383279502884197169399");
In essence, this fromDecimal() method converts a number specified in base 10 to a BigNat stored in base \(2^{31}\). The opposite
conversion is just as important and mostly used for printing numbers or converting them to Strings:
String piString = pi.toString();
// "3141592653589793238462643383279502884197169399"
Here, toString() converts pi from base \(2^{31}\) to a base-10 representation. In general, the process of converting from one base or radix to another is known as radix conversion.
The general problem of radix conversion can be stated as follows. Given an integer \(x=(x_{n-1}x_{n-2}\dots x_1x_0)_b\) in some base \(b\), find the digits of the integer \(y=(y_{m-1}\ldots y_0)_B\) in another base \(B\) that has the same numerical value as \(x\). There are
two main methods for determining the digits of \(y\) that differ in whether the old or the new base is used to perform the computations.
The first method is based on the observation that \(y\) must be equal to the base-\(b\) expansion of \(x\):
\(\seteqnumber{0}{11.}{13}\)
\begin{equation}
\label {eq:decimal} y = x_{n-1}b^{n-1} + x_{n-2}b^{n-2} + \dots + x_{1}b + x_{0}.
\end{equation}
If we evaluate the expression on the right-hand side in the new base \(B\), we obtain the digits of \(y\) as a side product. The obvious way to perform this computation is to iterate over the expression from right to left, multiply each \(x_k\) by the corresponding power \(b^k\), and add
the resulting terms. If we compute the powers \(b^k\) incrementally, \(1, b, b^2,\dots \), we obtain the From-Radix’ algorithm for radix conversion shown in Algorithm 11.9. The expressions \((x_k)_B\) and \((b)_B\) indicate that the numbers \(x_k\) and \(b\) must be converted to base-\(B\) before they can be used in the surrounding expressions. This conversion is trivial if we are converting to
a larger radix, because in this case we have \(x_k<b<B\) and both quantities are single-digit numbers in base-\(B\).
Convert a base-\(b\) number with digits \(x=(x_{n-1}x_{n-2}\ldots x_0)_b\) to a different base \(B\). All arithmetic operations are performed in the new base \(B\).
An improved version of From-Radix’ can be obtained by rewriting Eq. (11.14) in the following nested form:
\(\seteqnumber{0}{11.}{14}\)
\begin{equation}
\label {eq:horner} y = \Bigl (\bigl ((x_{n-1}\cdot b + x_{n-2})\cdot b + x_{n-2}\bigr )\cdot b + \dots \Bigr )\cdot b + x_{0}.
\end{equation}
Rewriting polynomial expressions in this way is also known as Horner’s method or Horner’s scheme. Since this expression is evaluated from the inside out, we now have to iterate over the digits of \(x\) in the opposite direction, starting with \(x_{n-1}\) and ending with \(x_0\). The resulting algorithm From-Radix is shown in Algorithm 11.10. The main advantage of Horner’s method is that it requires only half as many multiplications. Since
multiplications tend to be significantly more expensive than additions, From-Radix is therefore almost twice as fast than From-Radix’ in practice.
Convert a base-\(b\) number with digits \(x=(x_{n-1}x_{n-2}\ldots x_0)_b\) to a different base \(B\). All arithmetic operations are performed in the new base \(B\).
-
Example 11.9. Let’s use From-Radix to convert the binary
number \(1101_2\) to decimal. If we follow the steps of the algorithm and write out the intermediate values of all variables, we obtain the following table:
\(\seteqnumber{0}{11.}{15}\)
\begin{equation*}
\begin{array}{cccc} k & x_k & y & 2y+x_k\\ 3 & 1 & 0 & 1\\ 2 & 1 & 1 & 3\\ 1 & 0 & 3 & 6\\ 0 & 1 & 6 & 13 \end {array}
\end{equation*}
The final value is \(13\), which is the decimal representation of \(1101_2\).
Listing 11.18 shows an implementation of From-Radix that takes a String of decimal digits and converts
it to a long integer. We start by initializing result and then iterate over the characters of decimal, each of which represents one decimal digit. If the character isn’t one of the decimal digits between '0' and '9' we abort with an exception. Otherwise, we subtract the ASCII code of '0' from that of digit, which gives us an integer with the current digit’s numerical value, and add it to
result.
Listing 11.18ch11β―/β―BigNat
// Create 64-bit integer from string of decimal digits.
private static long longFromDecimal(String decimal) {
if (decimal.isEmpty())
throw new NumberFormatException("No digits");
long result = 0;
for (int i = 0; i < decimal.length(); i++) {
char digit = decimal.charAt(i);
if (digit < '0' || digit > '9')
throw new NumberFormatException("Invalid decimal digit");
result = result * 10 + (digit - '0');
}
return result;
}
It’s easy to modify longFromDecimal() to convert a string of decimal digits into a big integer: All we have to do is change the type of result to BigNat and replace the arithmetic operations with calls to times() and plus(), respectively. A significantly faster implementation can be obtained by processing multiple decimal digits at once. To do this, we divide the decimal digits into blocks, convert each block into a long integer using longFromDecimal(), and then accumulate these numbers into a single BigNat. Since the largest positive long integer is larger than \(9\times 10^{18}\), we can handle
blocks of up to 18 decimal digits in this way, which reduces the number of BigNat operations that must be performed also by a factor of 18.
-
Example 11.10. For an integer that consists of the first 46 digits of \(\pi \), splitting the number into blocks of 18 digits is equivalent to
computing
\(\seteqnumber{0}{11.}{15}\)
\begin{equation*}
\begin{split} &3141592653589793238462643383279502884197169399\\ &\quad = 3141592653\cdot U^{2} + 589793238462643383\cdot U^{1} + 279502884197169399\\ \end {split}
\end{equation*}
with \(U=10^{18}\). Notice that we can again rewrite this expression in a nested form using Horner’s scheme
\(\seteqnumber{0}{11.}{15}\)
\begin{equation*}
((3141592653\cdot U + 589793238462643383)\cdot U + 279502884197169399.\\
\end{equation*}
In effect, we treat the input as a number in base \(10^{18}\).
The fromDecimal() method in Listing 11.19 uses this idea to convert a string of decimal digits to a BigNat. The function splits the input decimal into blocks of 18 digits. If the number of digits isn’t divisible by 18, the remaining start digits are used as the first block. Each block is first
converted to a long integer using the longFromDecimal() method defined above and then added to the current value result. Compared to a naive implementation of From-Radix, this reduces the number of temporary objects that must be created and the number of BigNat operations by a factor of 18.
Listing 11.19ch11β―/β―BigNat
// Create big integer from a string of decimal digits.
public static BigNat fromDecimal(String decimal) {
if (decimal.isEmpty())
throw new NumberFormatException("No digits");
final int blockSize = 18;
final BigNat unit = TEN.pow(blockSize);
final int start = decimal.length() % blockSize;
BigNat result = start == 0
? ZERO
: fromUnsignedLong(
longFromDecimal(decimal.substring(0, start)));
for (int i = start; i < decimal.length(); i += blockSize) {
long block =
longFromDecimal(decimal.substring(i, i + blockSize));
result = result.times(unit).plus(fromUnsignedLong(block));
}
return result;
}
Let’s turn to the second algorithm for radix conversion. Like From-Radix, this algorithm converts a base-\(b\) number \(x\) to a base-\(B\) number \(y\), but this time all arithmetic operations are
performed in the original base \(b\). To find this algorithm, we start with the base-\(B\) expansion of \(y\), which must be equal to the original number \(x\):
\(\seteqnumber{0}{11.}{15}\)
\begin{equation}
\label {eq:baseB} y_{m-1}B^{m-1}+\ldots +y_1B+y_0 = x.
\end{equation}
If we compute the remainder modulo \(B\) on both sides, we see that the rightmost digit of \(y\) must be
\(\seteqnumber{0}{11.}{16}\)
\begin{equation*}
y_0 = x\bmod B,
\end{equation*}
since all other terms on the left-hand side are multiples of \(B\). To find the other digits of \(y\), we divide both sides of Eq. (11.16) by \(B\) to obtain
\(\seteqnumber{0}{11.}{16}\)
\begin{equation*}
y_{m-1}B^{m-1}+\ldots +y_1 + \underbrace {\lfloor y_0/B\rfloor }_{=0} = \underbrace {\,\lfloor x / B\rfloor \,}_{x'}.
\end{equation*}
The next digit is therefore \(y_1=x'\bmod B\), and \(\lfloor x'/B\rfloor \) gives us an equation for the remaining digits of \(y\). We can stop the computation as soon as the division by \(B\) produces zero. The implementation of this algorithm is discussed in
Exercise 11.13.
Convert a base-\(b\) number \(x=(x_{n-1}x_{n-2}\ldots x_0)_b\) to a different base \(B\). All arithmetic operations are performed in the original base \(b\).
-
Example 11.11. What is the base-7 representation of 1234? The remainder \(1234\bmod 7=2\) gives us the rightmost digit of the result, and the quotient
\(\lfloor 1234/7\rfloor =176\) the number from which we derive the next digit. The remaining digits are obtained by repeatedly computing the remainder modulo 7 and dividing by 7 until the quotient is zero:
\(\seteqnumber{0}{11.}{16}\)
\begin{equation*}
\begin{array}{cc} 1234 \bmod 7 = 2 & \lfloor 1234 / 7\rfloor = 176\\ 176 \bmod 7 = 1 & \lfloor 176 / 7\rfloor = 25\\ 25 \bmod 7 = 4 & \lfloor 25 / 7\rfloor = 3\\ 3 \bmod 7 = 3 & \lfloor 3 / 7\rfloor = 0 \end {array}
\end{equation*}
The results in the left column are the base-7 digits from right to left, so we have \(1234=3412_7\).
Exercises
Exercise 11.12.Implement a method with the following signature that converts a string of digits into a long integer:
public static long fromDigits(String digits, int radix);
The two arguments are the digits themselves and their radix, which is assumed to be a number between \(2\) and \(36\). As usual, the characters '0' through '9' represent digits with a numerical value between
0 and 9. In addition, if the radix is greater than 10, digits with a numerical value between 10 and 35 are represented using the letters a through z. The method should throw an exception if an invalid digit
is encountered during conversion.
Exercise 11.13. Implement a method BigNat.toString() that
converts a big integer to a string of decimal digits.
Exercise 11.14.A spreadsheet consists of a two-dimensional array of cells, each of which contains a number, a piece of text, or a formula. Each cell has a unique name that encodes its position in the array. The first part of the name is a sequence of uppercase letters that indicates the
column of the cell: The letters A to Z refer to columns 1 to 26, AA to AZ refer to columns 27 to 52, BA to BZ to columns 53 to 78, and so on. The second part of the name is a
decimal number that indicate the row of the cell. Which column and row does the name XYZ27 refer to? Explain how to convert from cell names to row-column pairs and back. Optional: Implement a class CellName that implements these operations.
Exercise 11.15.Explain how to write a computer program that converts from radix 11 to radix 3.